Fast dynamic programming algorithm for the large scale VCVRP problem

ZHANG Pengle, XIAO Kaiming, FU Chunxiao, YANG Kewei

Systems Engineering - Theory & Practice ›› 2016, Vol. 36 ›› Issue (3) : 694-705.

PDF(1963 KB)
PDF(1963 KB)
Systems Engineering - Theory & Practice ›› 2016, Vol. 36 ›› Issue (3) : 694-705. DOI: 10.12011/1000-6788(2016)03-0694-12

Fast dynamic programming algorithm for the large scale VCVRP problem

  • ZHANG Pengle1, XIAO Kaiming2, FU Chunxiao1, YANG Kewei1
Author information +
History +

Abstract

Vehicle routing problem (VRP) is a kind of typical combination optimization problems. Most of the researches focus on VRP with fixed transportation capacity; however, the capacity of vehicles is varied with the cargo shape and customer requirement. Therefore, we propose a varied capacitated vehicle routing problem (VCVRP) to deal with the practical problems. In this paper, a fast dynamic programming algorithm is proposed for large-scale VCVRP. And it is based on the traditional best fit decreasing (BFD) algorithm and minimum spanning tree (MST) algorithm. A K-backtracking strategy and a principle of short-priority are introduced to the dynamic programming algorithm. In this fast algorithm, the bin packing problem and routing problem are decoupled approximately. Analysis of the upper bound of objective total distance is given theoretically. Finally, experimental results of practical logistics of passenger vehicles are discussed to illustrate the quality and efficiency of the proposed algorithm.

Key words

vehicle routing problem / VCVRP problem / dynamic programming / combinatorial optimization / fast algorithm / inspire algorithm

Cite this article

Download Citations
ZHANG Pengle , XIAO Kaiming , FU Chunxiao , YANG Kewei. Fast dynamic programming algorithm for the large scale VCVRP problem. Systems Engineering - Theory & Practice, 2016, 36(3): 694-705 https://doi.org/10.12011/1000-6788(2016)03-0694-12

References

[1] Laporte G. Fifty years of vehicle routing[J]. Transport Science, 2009, 43(4): 408-416.
[2] Potvin J Y. State-of-the art review-evolutionary algorithms for vehicle routing[J]. INFORMS Journal on Computing, 2009, 21(4): 518-548.
[3] Solomon M M. Algorithms for the vehicle routing and scheduling problem with time windows constraints[J]. Operations Research, 1987, 35(2): 254-265.
[4] Labbe M, Laporte G, Mercure H. Capacitated vehicle routing problems on trees[J]. Operations Research, 1991, 39(4): 616-622.
[5] Gendreau M, Hert Z A, Laporte G. A tabu search heuristic for the vehicle routing problem[J]. Management Science, 1994, 40(10): 1276-1289.
[6] 符卓.带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J]. 系统工程理论与实践, 2004, 24(3): 123-128. Fu Z. The capacitated open vehicle routing problem and its tabu search algorithm[J]. Systems Engineering—— Theory & Practice, 2004, 24(3): 123-128.
[7] 张军, 唐加福, 潘震东. 分散搜索算法求解带货物权重的车辆路径问题[J]. 系统工程学报, 2010, 25(1): 91-97. Zhang J, Tang J F, Pan Z D, et al. Scatter search algorithm for solving weighted vehicle routing problem[J]. Journal of Systems Engineering, 2010, 25(1): 91-97.
[8] 张燕, 周支立, 翟斌. 集货送货一体化的物流配送车辆路径问题的标号算法[J]. 运筹与管理, 2007, 16(3): 12-19. Zhang Y, Zhou Z L, Zhai B. Multi-attribute label matching algorithm for vehicle routing problems with time wndows and backhauls[J]. Operations Research & Management Science, 2007, 16(3): 12-19.
[9] 姚峰, 邢立宁, 李菊芳,等. 求解双层CARP优化问题的知识型遗传算法[J]. 系统工程理论与实践, 2014, 34(1): 237-247. Yao F, Xing L N, Li J F, et al. Knowledge-based genetic algorithm to the double layer capacitated arc routing problems[J]. Systems Engineering—— Theory & Practice, 2014, 34(1): 237-247.
[10] 张建勇, 张军. 具有模糊旅行时间的VRP的一种混合遗传算法[J]. 管理工程学报, 2006, 20(4): 13-17. Zhang J Y, Zhang J. A hybrid genetic algorithm to the vehicle routing problem with fuzzy traveling time[J]. Journal of Industrial Engineering & Engineering Management, 2006, 20(4): 13-17.
[11] 赵燕伟,彭典军,张景玲,等. 有能力约束车辆路径问题的量子进化算法[J]. 系统工程理论与实践, 2009, 29(2): 159-166. Zhao Y W, Peng D J, Zhang J L, et al. Quantum evolutionary algorithm for capacitated vehicle routing problem[J]. Systems Engineering—— Theory & Practice, 2009, 29(2): 159-166.
[12] 吴斌,钱存华,董敏,等. 具有同时集送货需求车辆路径问题的混沌量子进化算法研究[J]. 控制与决策, 2010, 25(3): 383-388. Wu B, Qian C H, Dong M, et al. Chaos quantum evolutionary algorithm for vehicle routing problem with simultaneous delivery and pickup[J]. Control & Decision, 2010, 25(3): 383-388.
[13] 饶卫振, 金淳. 求解大规模CVRP问题的快速贪婪算法[J]. 管理工程学报, 2014(2): 45-54. Rao W Z, Jin C. An efficient greedy heuristic for solving large-scale capacitated vehicle routing problem[J]. Journal of Industrial Engineering & Engineering Management, 2014(2): 45-54.
[14] 刘阿宁, 闭应洲, 王仁民, 等. CVRP 中二维装箱问题的研究 [J]. 广西师范学院学报: 自然科学版, 2012, 29(1): 72-76.
[15] Boyd S, Vandenberghe L, Faybusovich L. Convex optimization[J]. IEEE Transactions on Automatic Control, 2006, 51(11): 1859-1859.
[16] 胡运权. 运筹学教程[M].北京: 清华大学出版社, 2007.
[17] Curtis S A. The classification of greedy algorithms[J]. Science of Computer Programming, 2003, 49(1-3): 125-157.
[18] 杨跃武. 一种新的基于最小生成树的物流配送优化路线算法 [J]. 计算技术与自动化, 2008, 27(3): 7-11. Yang Y W. A new algorithm for vehicle routing problems with capacity limited based on minimum spanning tree[J]. Computing Technology and Automation, 2008, 27(3): 7-11.
[19] 农健恒,崔耀东. 同尺寸物品装箱的动态规划算法 [J]. 计算机应用与软件, 2014, 31(7): 249-251. Nong J H, Cui Y D. Dynamic programming algorithm for packing containers with items in same size[J]. Computer Applications & Software, 2014, 31(7): 249-251.

Funding

National Natural Science Foundation of China (71201168)
PDF(1963 KB)

706

Accesses

0

Citation

Detail

Sections
Recommended

/