-
摘要: 对于集货过程中客户需求随时间变化的动态车辆路径规划问题, 按时间段划分为一系列车辆已驶离中心车场的静态车辆路径问题, 引入虚拟任务点与相关约束方法, 将其进一步等价转化为普通的静态车辆路径问题, 使用适用于静态问题的算法对其进行求解。应用此车辆路径规划方法, 以改进的节约法为静态算法, 对于客户数为20的动态路径规划问题进行求解, 得到重新优化路径所用的时间为0.49s, 说明这种规划方法可行。Abstract: A real-time vehicle routing problem(VRP) with customers' dynamic requests in logistics collection was decomposed into a set of static VRPs, in which vehicles were not at depot. Static VRPs were equally converted into general static VRPs by adding virtual customers and relative restrictions, and they were solved by static problem algorithm. With the solving VRP method, a dynamic VRP with 20 customers was solved by using improved saving algorithm. The result shows that the method is feasible, it takes 0.49 s to get the reoptimized route.
-
Key words:
- traffic planning /
- vehicle routing /
- saving algorithm /
- dynamic routing
-
[1] Dantzig G B, Ramser R H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91. doi: 10.1287/mnsc.6.1.80 [2] 宋厚冰, 蔡远利. 带时间窗的车辆路径混合遗传算法[J]. 交通运输工程学报, 2003, 3(4): 112-115. http://transport.chd.edu.cn/article/id/200304009Song Hou-bing, Cai Yuan-li. Hybrid genetic algorithm of vehicle routing withti me windows[J]. Journal of Traffic and Transportation Engineering, 2003, 3(4): 112-115. (in Chinese) http://transport.chd.edu.cn/article/id/200304009 [3] Thangiah S R, Osman I H, Sun T. Hybrid genetic algorithm simulated annealing and tabu search methods for vehicle routing problem with ti me windows[R]. Slipery Rock: Slippery Rock University, 1994. [4] Osman I H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J]. Annals of Operations Research, 1993, 41(1): 421-451. [5] 张波, 叶家玮, 胡郁葱. 模拟退火算法在路径优化问题中的应用[J]. 中国公路学报, 2004, 17(1): 79-81. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200401019.htmZhang Bo, Ye Jia-wei, Hu Yu-cong. Application of optimizing the path by simulated annealing[J]. China Journal of Highway and Transport, 2004, 17(1): 79-81. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200401019.htm [6] 胡大伟, 胡勇, 朱志强. 基于空间填充曲线和动态规划解的定位路线问题[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 problem based on space filling curve and dynamic programming[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 [7] Clarke G, Wright J W. Scheduling of vehicles froma central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581. [8] 杨瑞臣, 周永付, 云庆夏. 寻找车辆最优路径的混合算法[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 algorithm for vehicle's optimal 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 [9] Psaraftis H N. Vehicle Routing: Methods and Studies[M]. Amstersam: North-Holland Press, 1988. [10] Ghiani G, Guerriero F, Laporte G, et al. Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies[J]. European Journal of Operational Research, 2003, 151(1): 1-11. [11] 李军, 郭耀煌. 物流配送车辆优化调度理论与方法[M]. 北京: 中国物资出版社, 2001. -
下载:
点击查看大图
图(2) / 表(3)
计量
- 文章访问数: 195
- HTML全文浏览量: 71
- PDF下载量: 526
- 被引次数: 0
