Saving algorithm of multi-vehicle routing problem with pickup-delivery and soft time window
-
摘要: 研究了物流配送中多车运输的集货与送货车辆路径规划问题, 以增加时间惩罚费用的方式插入软时间窗约束, 将租车费用、货车运输费用和时间惩罚费用三者之和最小作为优化目标, 建立数学模型。采用启发式节约算法求解该模型, 考虑时间惩罚费用和运输费用, 比较每一配送节点上直接送货和间接送货的节约费用关系, 求出最优配送路径。试验结果表明: 当配送次数达到50次时, 货车平均装载率仍能达到80%以上, 该节约算法能减少货车空程行驶和租车次数, 优化了全局费用。Abstract: Multi-vehicle routing problem with pickups and deliveries was studied, and soft time window constraint was considered by adding time punishment cost. The mathematical model was built, and its optimized object was the minimum of combination with vehicle rent cost, transportation cost and time punishment cost, and the model was solved by using heuristic saving algorithm. Time punishment cost and transpiration cost were calculated respectively, and the relation between direct and indirect deliveries was compared to obtain best routes. Test result indicates that when the times of pickups and deliveries reach 50, the average loading rate of freight car still achieves above 80%, so the heuristic saving algorithm can reduce the distance without loadage and rent times, and optimize total cost.
-
表 1 货车属性
Table 1. Vehicle attributes
最大载货质量/t 10 货车最多可调用数量 10n 速度/ (km·h-1) 40 每辆车的固定租车费用/元 300 最大行驶距离/km 240 每公里运输费用/ (元·km-1) 2 固定装货时间/h 0.5 时间窗上界惩罚系数/ (元·h-1) 200 固定卸货时间/h 0.5 时间窗下界惩罚系数/ (元·h-1) 300 
下载: 导出CSV
表 2 算例结果
Table 2. Test results
任务数 租车数量/veh 总费用/元 计算时间/s 货车平均利用率/% 有效运输时间比率平均值/% 10 2 1 478 13.2 93.2 87.6 20 8 4 780 67.5 91.4 82.9 30 13 7 872 163.2 88.3 85.4 40 16 10 290 266.4 85.3 88.5 50 22 13 753 475.6 81.6 84.8
下载: 导出CSV
-
[1] CLARKE G, WRIGHT J W. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research, 1964, 12 (4): 568-581. doi: 10.1287/opre.12.4.568 [2] GILLETT B E, MILLER L R. Aheuristic algorithm for the vehicle-dispatch problem[J]. Operations Research, 1974, 22 (2): 340-349. doi: 10.1287/opre.22.2.340 [3] MONTANE F A T, GALVAO R D. A tabu search algorithmfor the vehicle routing problem with si multaneous pickup and delivery service[J]. Computers & Operations Research, 2006, 33 (3): 595-619. [4] NAGY G, SALHI S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J]. European Journal of Operational Research, 2005, 162 (1): 126-141. doi: 10.1016/j.ejor.2002.11.003 [5] 李军. 有时间窗的车辆路线安排问题的启发式算法[J]. 系统工程, 1996, 14 (5): 45-50. https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT199605009.htmLI Jun. A heuristic algorithmfor vehicle routing scheduling problem with time windows[J]. Systems Engineering, 1996, 14 (5): 45-50. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT199605009.htm [6] 唐勇, 刘峰涛. 新型遗传模拟退火算法求解带VRPTW问题[J]. 计算机工程与应用, 2006, 42 (7): 7-9. doi: 10.3321/j.issn:1002-8331.2006.07.003TANG Yong, LIU Feng-tao. New genetic si mulated annealing algorithmfor vehicle routing problem with time window[J]. Computer Engineering and Applications, 2006, 42 (7): 7-9. (in Chinese) doi: 10.3321/j.issn:1002-8331.2006.07.003 [7] 霍佳震, 张磊. 有时间窗的集货送货一体化车辆路径规划启发式算法研究[J]. 物流技术, 2004, 23 (5): 64-66. doi: 10.3969/j.issn.1005-152X.2004.05.025HUO Jia-zhen, ZHANG Lei. Study on heuristic algorithm for picking-delivery problem with time window constraint[J]. Logistics Technology, 2004, 23 (5): 64-66. (in Chinese) doi: 10.3969/j.issn.1005-152X.2004.05.025 [8] 张燕, 周支立, 翟斌. 集货送货一体化的物流配送车辆路线问题的标号算法[J]. 运筹与管理, 2007, 16 (3): 12-19. doi: 10.3969/j.issn.1007-3221.2007.03.003ZHANG Yan, ZHOU Zhi-li, ZHAI Bin. Multi-attribute label matching algorithm for vehicle routing problems with time windows and backhauls[J]. Operations Research and Management Science, 2007, 16 (3): 12-19. (in Chinese) doi: 10.3969/j.issn.1007-3221.2007.03.003 [9] 屈援, 汪波, 钟石泉. 单车场集送一体化车辆路径问题及其混合算法研究[J]. 武汉理工大学学报: 交通科学与工程版, 2007, 31 (5): 811-814. doi: 10.3963/j.issn.2095-3844.2007.05.015QU Yuan, WANG Bo, ZHONG Shi-quan. Research on singledepot integrated vehicle routing problem and its hybrid algorithm[J]. Journal of Wuhan University of Technology: Transportation Science and Engineering, 2007, 31 (5): 811-814. (in Chinese) doi: 10.3963/j.issn.2095-3844.2007.05.015 [10] 赵鲁华. 城市多网点配送车辆调度模型与算法研究[J]. 物流技术, 2007, 26 (8): 91-93. doi: 10.3969/j.issn.1005-152X.2007.08.028ZHAO Lu-hua. Study on vehicle scheduling model and algorithmfor city multi-node delivery[J]. Logistics Technology, 2007, 26 (8): 91-93. (in Chinese) doi: 10.3969/j.issn.1005-152X.2007.08.028 [11] 郎茂祥, 胡思继. 用混合遗传算法求解物流配送路径优化问题的研究[J]. 中国管理科学, 2002, 10 (5): 51-56. doi: 10.3321/j.issn:1003-207X.2002.05.011LANG Mao-xiang, HU Si-ji. Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm[J]. Chinese Journal of Management Science, 2002, 10 (5): 51-56. (in Chinese) doi: 10.3321/j.issn:1003-207X.2002.05.011 -
点击查看大图
图(4) / 表(2)
计量
- 文章访问数: 446
- HTML全文浏览量: 42
- PDF下载量: 517
- 被引次数: 0
