方格路网车辆路径在线选择模型及竞争分析

Online selection model and competitive analysis of vehicle routing in grid transportation network

为分析城市方格路网遭遇突发性堵塞下的车辆路径选择问题,应用在线问题与竞争策略的方法建模,设计了2种在线路径选择竞争策略,即方向贪婪策略和多选择移动策略,计算了2种策略的竞争性能比。通过策略竞争分析得出:在发生突发性堵塞的情形下,方向贪婪策略下的费用为最优费用的3倍;利用多选择移动策略在对网络具有实际意义约束条件下的部分情形能够得到最优费用,且在最坏情形下的费用为最优费用的2倍;2种策略的竞争性能比优于以往研究给出的堵塞不可恢复问题竞争比的下界。

In order to analyze the vehicle routing problem under sudden road blockage in grid transportation network, a vehicle routing model was proposed by using the methods of online problem and competitive strategy, direction greedy strategy and multi-alternative moving strategy were designed, and the competitive ratios of two strategies were computed. Analysis result indicates that the cost of direction greedy strategy is 3 times than the optimal cost under sudden road blockage state, multi-alternative moving strategy has a good performance with practical restriction for different cases, the cost of multi-alternative moving strategy is 2 times than the optimal cost in the worst case, the competitive ratios of two strategies are not more than the infimum of the competitive ratio for unexpected blockage problem in general networks. 3 figs, 17 refs.