Online selection model and competitive analysis of vehicle routing in grid transportation network
-
摘要: 为分析城市方格路网遭遇突发性堵塞下的车辆路径选择问题, 应用在线问题与竞争策略的方法建模, 设计了2种在线路径选择竞争策略, 即方向贪婪策略和多选择移动策略, 计算了2种策略的竞争性能比。通过策略竞争分析得出: 在发生突发性堵塞的情形下, 方向贪婪策略下的费用为最优费用的3倍; 利用多选择移动策略在对网络具有实际意义约束条件下的部分情形能够得到最优费用, 且在最坏情形下的费用为最优费用的2倍; 2种策略的竞争性能比优于以往研究给出的堵塞不可恢复问题竞争比的下界。Abstract: 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.
-
[1] 贺竹磬, 孙林岩. 动态交通下车辆路径选择模型及算法[J]. 交通运输工程学报, 2007, 7 (1): 111-115. doi: 10.3321/j.issn:1671-1637.2007.01.023HE Zhu-qing, SUN Lin-yan. Model and algorithmof vehicle routing problemunder dynamic traffic[J]. Journal of Traffic and Transportation Engineering, 2007, 7 (1): 111-115. (in Chinese) doi: 10.3321/j.issn:1671-1637.2007.01.023 [2] THANGI AH S R, OSMAMI H, SUN T. Hybrid genetic algorithmsi mulated annealing and tabu search met hods for vehicle routing problem with ti me windows[R]. Slippery Rock: Slippery Rock University, 1994. [3] 张波, 叶家玮, 胡郁葱. 模拟退火算法在路径优化问题中的应用[J]. 中国公路学报, 2004, 17 (1): 79-81. doi: 10.3321/j.issn:1001-7372.2004.01.018ZHANG Bo, YE Jia-wei, HU Yu-cong. Application of opti-mizing the path by si mulated annealing[J]. China Journal of Highway and Transport, 2004, 17 (1): 79-81. (in Chinese) doi: 10.3321/j.issn:1001-7372.2004.01.018 [4] 胡大伟, 胡勇, 朱志强. 基于空间填充曲线和动态规划解的定位路线问题[J]. 长安大学学报: 自然科学版, 2006, 26 (3): 80-83. https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200603021.htmHU Da-wei, HU Yong, ZHU Zhi-qiang. Solving location routing problembased on space filling curve and dynamic pro-gramming[J]. Journal of Chang an University: Natural Science Edition, 2006, 26 (3): 80-83. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200603021.htm [5] 李兵, 郑四发, 曹剑东, 等. 求解客户需求动态变化的车辆路径规划方法[J]. 交通运输工程学报, 2007, 7 (1): 106-110. http://transport.chd.edu.cn/article/id/200701022LI Bing, ZHENG Si-fa, CAO Jian-dong, et al. Method of solving vehicle routing problem with customers dynamic requests[J]. Journal of Traffic and Transportation Engineering, 2007, 7 (1): 106-110. (in Chinese) http://transport.chd.edu.cn/article/id/200701022 [6] 杨瑞臣, 周永付, 云庆夏. 寻找车辆最优路径的混合算法[J]. 交通运输工程学报, 2005, 5 (1): 102-105. doi: 10.3321/j.issn:1671-1637.2005.01.024YANG Rui-chen, ZHOU Yong-fu, YUN Qing-xia. Hybrid algorithmfor vehicle s opti mal route[J]. Journal of Traffic and Transportation Engineering, 2005, 5 (1): 102-105. (in Chinese) doi: 10.3321/j.issn:1671-1637.2005.01.024 [7] MANASSE MS, MCGEOCH L A, SLEATOR D D. Com-petitive algorithms for server problems[J]. Journal of Algo-rithms, 1990, 11: 208-230. doi: 10.1016/0196-6774(90)90003-W [8] DAVID S B, BORODI N A. A new measure for the study of the on-line algorithm[J]. Algorithmica, 1994, 11: 73-91. doi: 10.1007/BF01294264 [9] EI YANI V R, KNAIEL R, LI NEAL N. Competitive opti mal on-line leasing[J]. Algorithmica, 1999, 25: 116-140. doi: 10.1007/PL00009279 [10] EI YANI V R, FI AT A, KARP R M, et al. Opti mal search and one-way trading online algorithm[J]. Algorithmica, 2001, 30: 101-139. doi: 10.1007/s00453-001-0003-0 [11] KESKI NOCAK P, RAVI R, TAYUR S. Scheduling and re-liable lead-ti me quotation for orders with availability intervals and lead-ti me sensitive revenues[J]. Management Science, 2001, 47 (2): 264-279. doi: 10.1287/mnsc.47.2.264.9836 [12] PAPADI MITRIOUC H, YANNAKAKIS M. Shortest paths without a map[J]. Lecture Notes in Computer Science, 1989, 372: 610-620. https://www.sciencedirect.com/science/article/pii/0304397591902632 [13] XUYin-feng, HU Mao-lin, SUBing, et al. The Canadian traveller problemand its competitive analysis[J]. Journal of Combinatorial Opti mization, 2008, 15 (3): 223-227. doi: 10.1007/s10878-008-9156-y [14] SU Bing, XU Yin-feng, ZHU Zhi-jun. Online recoverable Canadian traveler problemon a road[J]. Information, 2004, 7 (4): 477-486. https://www.researchgate.net/publication/266981539_Online_recoverable_Canadian_traveler_problem_on_a_road [15] 苏兵, 徐寅峰. 连续网络上的占线可恢复加拿大旅行者问题[J]. 系统工程, 2004, 22 (8): 10-13. https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200408003.htmSU Bing, XU Yin-feng. Online recoverable Canadian traveler problemon a continuous network[J]. Systems Engineering, 2004, 22 (8): 10-13. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200408003.htm [16] 苏兵, 徐寅峰. 堵塞恢复时间随机的在线加拿大旅行者问题[J]. 系统工程理论与实践, 2005, 25 (10): 108-113. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200510015.htmSU Bing, XU Yin-feng. Online Canadian traveler problem with stochastic blockages recovery ti me[J]. Systems Engi-neering-theory and Practice, 2005, 25 (10): 108-113. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200510015.htm [17] 苏兵, 徐寅峰. 居住和单位小区对方格网络交通便捷度的影响分析[J]. 系统工程, 2006, 24 (12): 33-39. https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200612005.htmSU Bing, XU Yin-feng. Influence analysis of square block for transportation convenience capability on grid network[J]. System Engineering, 2006, 24 (12): 33-39. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200612005.htm -
下载:
点击查看大图
图(3)
计量
- 文章访问数: 270
- HTML全文浏览量: 97
- PDF下载量: 240
- 被引次数: 0
