车辆路径问题研究进展

doi:10.12263/DZXB.20201154

摘要/Abstract

摘要：

车辆路径作为经典的组合优化问题一直是研究的热点与难点，无论是在应急管理工作还是物流配送中，对它的合理规划都至关重要.为了今后更好地开展相关工作，本文回顾了精确算法、启发式算法和机器学习算法在车辆路径优化问题中的研究进展，并基于Solomon标准数据集对六种经典算法的求解性能进行了比较分析；分别从局部最优和收敛速度间的平衡关系、个体评价函数、动态车辆路径问题以及机器学习算法在车辆路径问题中的应用等四个方面对其发展趋势进行了展望.

关键词: 车辆路径优化, 启发式算法, 精确算法, 机器学习

Abstract:

As a classical combinatorial optimization problem, vehicle routing has always been a hot and difficult research topic. It is very important to make reasonable planning for it in both emergency management and logistics distribution. In order to better carry out related work in the future, this paper reviewed the research progress of exact algorithm, heuristic algorithm, and machine learning algorithm in vehicle routing optimization problem. Then the comparisons of the performance of six classical algorithms were conducted based on Solomon standard data set. The development trend was prospected from the aspects of balance relationship between the local optimum and the convergence speed, individual evaluation function, dynamic vehicle routing problem, and the application of machine learning algorithms in the vehicle routing problem.

Key words: vehicle routing optimization, heuristic algorithm, precise algorithm, machine learning

中图分类号:

TP399

蒋华伟, 郭陶, 杨震. 车辆路径问题研究进展[J]. 电子学报, 2022, 50(2): 480-492.

JIANG Hua-wei, GUO Tao, YANG Zhen. Research Progress of Vehicle Routing Problem[J]. Acta Electronica Sinica, 2022, 50(2): 480-492.

图/表 11

参考文献 67

1	DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
2	DORLING K, HEINRICHS J, MESSIER G G, et al. Vehicle routing problems for drone delivery[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 47(1): 70-85.
3	戚远航, 蔡延光, 蔡颢, 等. 带时间窗的车辆路径问题的离散蝙蝠算法[J]. 电子学报, 2018, 46(3): 672-679.
	QI Y H, CAI Y G, CAI H, et al. Discrete bat algorithm for vehicle routing problem with time window[J]. Acta Electronica Sinica, 2018, 46(3): 672-679. （in Chinese）
4	LAU H C W, CHAN T M, TSUI W T, et al. Application of genetic algorithms to solve the multidepot vehicle routing problem[J]. IEEE Transactions on Automation Science & Engineering, 2010, 7(2): 383-392.
5	易云飞, 蔡永乐, 董文永, 等. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J]. 电子学报, 2015, 43(10): 2053-2061.
	YI Y F, CAI Y L, DONG W Y, et al. Improved ITO algorithm for multiobjective real-time vehicle routing problem with customers’ satisfaction[J]. Acta Electronica Sinica, 2015, 43(10): 2053-2061. （in Chinese）
6	KIM G, ONG Y S, CHEONG T, et al. Solving the dynamic vehicle routing problem under traffic congestion[J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(8): 2367-2380.
7	王江晴, 覃俊, 李子茂. 求解动态最优路径的混合优化算法[J]. 通信学报, 2008, 29(7): 135-140.
	WANG J Q, QIN J, LI Z M. Hybrid optimization algorithm for dynamic optimal path[J]. Journal on Communications, 2008, 29(7): 135-140. （in Chinese）
8	涂伟, 李清泉, 方志祥. 一种大规模车辆路径问题的启发式算法[J]. 武汉大学学报(信息科学版), 2013, 38(3): 307-310, 338.
	TU W, LI Q Q, FANG Z X. A heuristic algorithm for largescale vehicle routing problem[J]. Geomatics and Information Science of Wuhan University, 2013, 38(3): 307-310, 338. （in Chinese）
9	黄戈文, 蔡延光, 戚远航, 等. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报, 2019, 47(12): 2602-2610.
	HUANG G W, CAI Y G, QI Y H, et al. Adaptive genetic gray wolf optimizer algorithm for vehicle routing problem with capacity constraint[J]. Acta Electronica Sinica, 2019, 47(12): 2602-2610. （in Chinese）
10	LAWLER E L, WOOD D E. Branch-and-bound methods: A survey[J]. Operations Research, 1966, 14(4): 699-719.
11	PECIN D, CONTARDO C, DESAULNIERS G, et al. New enhancements for the exact solution of the vehicle routing problem with time windows[J]. Informs Journal on Computing, 2017, 29(3): 489-502.
12	CESELLI A, RIGHINI G, TRESOLDI E. Vehicle routing problems with different service constraints: A branch‐and-cut-and-price algorithm[J]. Networks, 2014, 64(4): 282-291.
13	SANTOS F A, MATEUS G R, CUNHA A S DA. A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem[J]. Transportation Science, 2013, 49(2): 355-368.
14	DANTZIG G B, WOLFE P. Decomposition principle for linear programs[J]. Operations Research, 1960, 8(1): 101-111.
15	CHABRIER A. Vehicle routing problem with elementary shortest path based column generation[J]. Computers & Operations Research, 2006, 33(10): 2972-2990.
16	HERNANDEZ F, FEILLET D, GIROUDEAU R, et al. Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows[J]. European Journal of Operational Research, 2016, 249(2): 551-559.
17	PECIN D, PESSOA A, POGGI M, et al. Improved branch-cut-and-price for capacitated vehicle routing[C]//Integer Programming and Combinatorial Optimization. Bonn, Germany: Springer, Cham, 2014: 393-403.
18	FUKASAWA R, LONGO H, LYSGAARD J, et al. Robust branch-and-but-and-price for the capacitated vehicle routing problem[J]. Math-ematical Programming, 2006, 106(3): 491-511.
19	BELLMAN R. Dynamic programming[J]. Science, 1966, 153(3731): 34-37.
20	SOYSAL M, CIMEN M. A simulation based restricted dynamic programming approach for the green time dependent vehicle routing problem[J]. Computers & Operations Research, 2017, 88(12): 297-305.
21	XIAO Y, KONAK A. A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem[J]. Journal of Cleaner Production, 2016, 167: 1450-1463.
22	MARINELLI M, COLOVIC A, DELL’ORCO M. A novel dynamic programming approach for two-echelon capacitated vehicle routing problem in city logistics with environmental considerations[J]. Transportation Research Procedia, 2018, 30: 147-156.
23	DORIGO M, MANIEZZO V, COLORNI A. Ant System: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 1996, 26(1): 29-41.
24	KUO R J, WIBOWO B S, ZULVIA F E. Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time[J]. Applied Mathematical Modelling, 2016, 40(23-24): 9990-10001.
25	TANG Y L, CAI Y G, YANG Q J. Improved ant colony optimization for multi-depot heterogeneous vehicle routing problem with soft time windows[J]. Journal of Southeast University(English Edition), 2015, 31(1): 94-99.
26	ZHANG H, ZHANG Q, MA L, et al. A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows[J]. Information Sciences, 2019, 490: 166-190.
27	胡蓉, 李洋, 钱斌, 等. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题[J/OL]. 自动化学报, 2020: 1-16. .
	HU R, LI Y, QIAN B, et al. Enhanced ant colony algorithm combined with clustering decomposition for complex green vehicle routing problem[J/OL]. Acta Automatica Sinica, 2020: 1-16. （in Chinese）
28	MAVROVOUNIOTIS M, YANG S. Ant algorithms with immigrants schemes for the dynamic vehicle routing problem[J]. Information Sciences, 2015, 294: 456-477.
29	NARASIMHA K, KIVELEVITCH E, SHARMA B, et al. An ant colony optimization technique for solving min-max multi-depot vehicle routing problem[J]. Swarm and Evolutionary Computation, 2013, 13: 63-73.
30	YAO B, CHEN C, SONG X, et al. Fresh seafood delivery routing problem using an improved ant colony optimization[J]. Annals of Operations Research, 2019, 273(1-2): 163-186.
31	HOLLAND J H. Adaptation in Natural and Artificial Systems[M]. USA: University of Michigan Press, 1975: 126-137.
32	SRIPRIYA J, RAMALINGAM A, RAJESWARI K. A hybrid genetic algorithm for vehicle routing problem with time windows[C]//International Conference on Innovations in Information, Embedded and Communication Systems. Coimbatore, India: IEEE, 2015: 1-4.
33	BOUCHRA B, BTISSAM D, MOHAMMAD C. A hybrid genetic algorithm for the static and dynamic vehicle routing problem with soft time windows[C]//International Conference on Logistics Operations Management. Fez, Morocco: IEEE, 2016: 1-9.
34	WANG K, LAN S, ZHAO Y. A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service[J]. Journal of the Operational Research Society, 2017, 68(11): 1409-1421.
35	MA Y, LI Z, YAN F, et al. A hybrid priority-based genetic algorithm for simultaneous pickup and delivery problems in reverse logistics with time windows and multiple decision-makers[J]. Soft Computing, 2019, 23(15): 6697-6714.
36	ERFAN T, ALI H, MEHDI S, et al. A hybrid genetic algorithm for multi-trip green capacitated arc routing problem in the scope of urban services[J]. Sustainability, 2018, 10(5): 1366.
37	WANG S, LU Z, WEI L, et al. Fitness-scaling adaptive genetic algorithm with local search for solving the multiple depot vehicle routing problem[J]. Simulation: Transactions of the Society for Modeling and Simulation International, 2016, 92(7): 601-616.
38	CATTARUZZA D, ABSI N, FEILLET D, et al. The multi-trip vehicle routing problem with time windows and release dates[J]. Transportation Science, 2015, 50(2): 676-693.
39	PIERRE D M, ZAKARIA N. Stochastic partially optimized cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows[J]. Applied Soft Computing, 2016, 52: 863-876.
40	ALIJLA B O, WONG L P, LIM C P, et al. An ensemble of intelligent water drop algorithms and its application to optimization problems[J]. Information Sciences, 2015, 325: 175-189.
41	EZUGWU A E, OLUSANYA M O, ADEWUMI A O. A hybrid method based on intelligent water drop algorithm and simulated annealing for solving multi-depot vehicle routing problem[C]//Advances in Intelligent Systems and Computing. Cham, Germany: Springer, 2017: 204-219.
42	TEYMOURIAN E, KAYVANFAR V, KOMAKI G M, et al. Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem[J]. Information Sciences, 2016, 334/335: 354-378.
43	KENNEDY J, EBERHART R. Particle swarm optimization[C]//International Conference on Neural Networks. Perth, WA, Australia: IEEE, 1995: 1942-1948.
44	MIRHASSANI S A, ABOLGHASEMI N. A particle swarm optimization algorithm for open vehicle routing problem[J]. Expert Systems with Applications, 2011, 38(9): 11547-11551.
45	ALINAGHIAN M, GHAZANFARI M, NOROUZI N, et al. A novel model for the time dependent competitive vehicle routing problem: Modified random topology particle swarm optimization[J]. Networks and Spatial Economics, 2017, 17(4): 1-27.
46	GALLEGO R A, ROMERO R. Tabu search algorithm for network synthesis[J]. IEEE Transactions on Power Systems, 2000, 15(2): 490-495.
47	李国明, 李军华. 基于混合禁忌搜索算法的随机车辆路径问题研究[J/OL]. 控制与决策, 2020: 1-10. .
	LI G M, LI J H. Research on stochastic vehicle routing problem based on hybrid tabu search algorithm[J/OL]. Control and Decision, 2020: 1-10. （in Chinese）
48	ZHANG D, CAI S, YE F, et al. A hybrid algorithm for a vehicle routing problem with realistic constraints[J]. Information Sciences, 2017, 394/395: 167-182.
49	JAIN A K, MAO J, MOHIUDDIN K M. Artificial neural networks: A tutorial[J]. Computer, 1996, 29(3): 31-44.
50	STEINHAUS M, SHIRAZI A N, SODHI M. Modified self organizing neural network algorithm for solving the vehicle routing problem[C]//International Conference on Computational Science & Engineering. Porto, Portugal: IEEE, 2015: 246-252.
51	YOSHIIKE N, TAKEFUJI Y. Vehicle routing problem using clustering algorithm by maximum neural networks[C]//International Conference on Intelligent Processing & Manufacturing of Materials. Honolulu, USA: IEEE, 1999: 1109-1113.
52	SHENG Y, MA H, XIA W. A pointer neural network for the vehicle routing problem with task priority and limited resources[J]. Information Technology and Control, 2020, 49(2): 237-248.
53	YU J J Q, YU W, GU J. Online vehicle routing with neural combinatorial optimization and deep reinforcement learning[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(10): 3806-3817.
54	WANG H B, GU M, YU Q, et al. Adaptive and large-scale service composition based on deep reinforcement learning[J]. Knowledge-Based Systems, 2019, 180(15): 75-90.
55	高阳, 陈世福, 陆鑫. 强化学习研究综述[J]. 自动化学报, 2004, 30(1): 86-100.
	GAO Y, CHEN S F, LU X. A review of reinforcement learning[J]. Acta Automatica Sinica, 2004, 30(1): 86-100. （in Chinese）
56	PENG B, ZHANG Y, GAJPAL Y, et al. A memetic algorithm for the green vehicle routing problem[J]. Sustainability, 2019, 11(21): 6055.
57	LOPES SILVA M A, DE SOUZA S R, FREITAS SOUZA M J, et al. A reinforcement learning-based multi-agent framework applied for solving routing and scheduling problems[J]. Expert Systems with Applications, 2019, 131(10): 148-171.
58	SAMMA H, LIM C P, SALEH J M. A new reinforcement learning-based memetic particle swarm optimizer[J]. Applied Soft Computing, 2016, 43: 276-297.
59	PENG B, WANG J H, ZHANG Z Z. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems[C]//Artificial Intelligence Algorithms and Applications. Singapore: Springer, 2019: 636-650.
60	DESROCHERS M, DESROSIERS J, SOLOMON M. A new optimization algorithm for the vehicle routing problem with time windows[J]. Operations Research, 1992, 40(2): 342-354.
61	IRNICH S, DESAULNIERS G. Shortest path problems with resource constraints[C]//Column Generation. Boston, USA: Springer, 2005: 33-65.
62	SECOMANDI N. Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands[J]. Computers & Operations Research, 2000, 27(11-12): 1201-1225.
63	吴华锋, 陈信强, 毛奇凰, 等. 基于自然选择策略的蚁群算法求解TSP问题[J]. 通信学报, 2013, 34(4): 165-170.
	WU H F, CHEN X Q, MAO Q H, et al. Ant colony algorithm based on natural selection strategy for solving TSP problem[J]. Journal on Communications, 2013, 34(4): 165-170. （in Chinese）
64	王燕, 聂长海, 钮鑫涛, 等. 覆盖表生成的禁忌搜索算法[J]. 软件学报, 2018, 29(12): 3665-3691.
	WANG Y, NIE C H, NIU X T, et al. Tabu search algorithm for covering table generation[J]. Journal of Software, 2018, 29(12): 3665-3691. （in Chinese）
65	GHAZIRI H, OSMAN I H. Self-organizing feature maps for the vehicle routing problem with backhauls[J]. Journal of Scheduling, 2006, 9(2): 97-114.
66	SUTTON R S, BARTO A G. Reinforcement Learning: An Introduction[M]. Cambridge, MA, USA: MIT Press, 1998.
67	SOLOMON M M. VRPTW benchmark problems[EB/OL]. (2003). .

VRP求解算法	优点	缺点	适用规模	参考来源
分支定界法	不需要评价所有可能的可行解即可找到最优解	求解速率慢，适用性差	小规模VRP	Desrochers等^［60］ 1992
列生成法	可求解大规模线性规划问题，具有较高的求解速度	只能求解线性松弛问题，子问题的求解速度较慢	较大规模VRP	Irnich等^［61］ 2005
动态规划法	可利用实际知识和经验提高求解速率	没有统一的标准模型，数值方法求解时存在维数灾难	小规模VRP	Secomandi^［62］ 2000
蚁群算法	鲁棒性强，具有内在并行性	收敛速度慢，易陷入局部最优，初始信息素匮乏	大规模VRP	吴华锋等^［63］ 2013
禁忌搜索算法	搜索速度快，局部“爬山”能力强	对初始解具有较强的依赖性	大规模VRP	王燕等^［64］ 2018
SOM神经网络	既可以学习训练数据输入向量的分布特征，也可以学习训练数据输入向量数据的拓扑结构	收敛速度慢，泛化性能低	大规模动态VRP	Ghaziri等^［65］ 2006
强化学习	通过智能体与环境的交互可反复学习行为	维数灾难	大规模动态VRP	Sutton等^［66］ 1998

VRP求解算法	优点	缺点	适用规模	参考来源
分支定界法	不需要评价所有可能的可行解即可找到最优解	求解速率慢，适用性差	小规模VRP	Desrochers等^［60］ 1992
列生成法	可求解大规模线性规划问题，具有较高的求解速度	只能求解线性松弛问题，子问题的求解速度较慢	较大规模VRP	Irnich等^［61］ 2005
动态规划法	可利用实际知识和经验提高求解速率	没有统一的标准模型，数值方法求解时存在维数灾难	小规模VRP	Secomandi^［62］ 2000
蚁群算法	鲁棒性强，具有内在并行性	收敛速度慢，易陷入局部最优，初始信息素匮乏	大规模VRP	吴华锋等^［63］ 2013
禁忌搜索算法	搜索速度快，局部“爬山”能力强	对初始解具有较强的依赖性	大规模VRP	王燕等^［64］ 2018
SOM神经网络	既可以学习训练数据输入向量的分布特征，也可以学习训练数据输入向量数据的拓扑结构	收敛速度慢，泛化性能低	大规模动态VRP	Ghaziri等^［65］ 2006
强化学习	通过智能体与环境的交互可反复学习行为	维数灾难	大规模动态VRP	Sutton等^［66］ 1998

算法	最好解/km	最差解/km	平均解/km	平均运算时间/s	偏差 /%	求解次数/次
BAC	828.94	―	―	25.2	0	10
CG	828.94	―	―	23.7	0	10
ACA	851.46	921.49	877.21	15.1	2.7	10
TS	855.37	936.32	893.27	13.8	3.2	10
SOM	847.22	858.09	852.16	3.3	2.2	10
RL	846.82	861.51	856.47	3.6	2.1	10

算法	最好解/km	最差解/km	平均解/km	平均运算时间/s	偏差 /%	求解次数/次
BAC	828.94	―	―	25.2	0	10
CG	828.94	―	―	23.7	0	10
ACA	851.46	921.49	877.21	15.1	2.7	10
TS	855.37	936.32	893.27	13.8	3.2	10
SOM	847.22	858.09	852.16	3.3	2.2	10
RL	846.82	861.51	856.47	3.6	2.1	10

[1]	黄璐, 蔚保国, 李宏生, 李隽, 贾浩男, 程建强, 李雅宁. GNSS拒止环境下的伪卫星指纹定位方法[J]. 电子学报, 2022, 50(4): 811-822.
[2]	崔亚奇, 何友, 唐田田, 熊伟. 一种深度学习航迹关联方法[J]. 电子学报, 2022, 50(3): 759-763.
[3]	张梦, 郑建宏, 刘香燕, 何云. 基于集成学习的全双工中继系统安全中继选择方案研究[J]. 电子学报, 2021, 49(9): 1852-1856.
[4]	郑海颖, 王峰, 姜维, 王志强, 姚西文. 神经网络训练策略对高分辨率遥感图像场景分类性能影响的评估[J]. 电子学报, 2021, 49(8): 1599-1614.
[5]	柴蓉, 谢德胜, 陈前斌. 基于成本及功耗联合优化的SDN虚拟网络映射算法[J]. 电子学报, 2021, 49(8): 1615-1624.
[6]	周东明, 张灿龙, 李志欣, 王智文. 基于多层级视觉融合的图像描述模型[J]. 电子学报, 2021, 49(7): 1286-1290.
[7]	王蔚龙, 李勇军, 赵尚弘, 辛宁, 赵海燕, 张泰江. 基于两阶段帕累托优化的卫星下行链路功率分配方法[J]. 电子学报, 2021, 49(6): 1101-1107.
[8]	侯秀聪, 赖晓平, 曹九稳. 正则化超限学习机的最大分划广义交替方向乘子法[J]. 电子学报, 2021, 49(4): 625-630.
[9]	陈长青, 郭春, 崔允贺, 申国伟, 蒋朝惠. 基于API短序列的勒索软件早期检测方法[J]. 电子学报, 2021, 49(3): 586-595.
[10]	周丰顺, 胡蓉, 钱斌, 张长胜, 向凤红. 超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题[J]. 电子学报, 2021, 49(12): 2419-2427.
[11]	刘润滋, 吴伟华, 张文柱, 周笛, 张琰. 基于图学习的密集空间网络传输资源调度方法[J]. 电子学报, 2021, 49(11): 2133-2137.
[12]	仇祝令, 查宇飞, 吴敏, 王青. 基于注意力学习的正则化相关滤波跟踪算法[J]. 电子学报, 2020, 48(9): 1762-1768.
[13]	宋宇琦, 高旻, 李骏东, 荣文戈, 熊庆宇. 网络欺凌检测综述[J]. 电子学报, 2020, 48(6): 1220-1229.
[14]	蒋留兵, 周小龙, 车俐. 基于无载波超宽带雷达的小样本人体动作识别[J]. 电子学报, 2020, 48(3): 602-615.
[15]	高鹏, 陈智华. 一种基于拓扑信息的预测疾病相关的MicroRNAs方法[J]. 电子学报, 2020, 48(2): 333-340.