Hybrid Optimization Algorithm for Vehicle Routing Problem with Simultaneous Delivery-Pickup

doi:10.3778/j.issn.1673-9418.2105024

Abstract

Abstract:

In order to provide reasonable and effective decision support for logistics enterprises in vehicle distribu-tion path planning, this paper studies the vehicle routing problem with simultaneous delivery-pickup and time windows (VRPSDPTW) for single distribution center distribution mode, and establishes a mathematical model with the objective of minimizing the total distribution cost. According to the characteristics of the model, a hybrid optimization algorithm (SA-ALNS) based on the combination of simulated annealing (SA) and adaptive large-scale neighborhood search (ALNS) is proposed. An insertion heuristic algorithm based on time and distance weighting is used to construct the initial solution of the problem. A variety of delete and insert operators are introduced to optimize the path with adaptive selection strategy. Through the feedback mechanism, the probability of each operator being selected is gradually adjusted to make the algorithm more inclined to choose the operator with better optimization effect. The Metropolis criterion of simulated annealing mechanism is used to control the solution updating. In the simulation experiment, 56 large-scale examples are tested, and other intelligent optimization algori-thms such as p-SA algorithm, DCS algorithm and VNS-BSTS are compared and statistically analyzed. The results show that the algorithm is feasible and superior in solving the vehicle routing problem with simultaneous delivery-pickup and time windows. The research results greatly enrich the related research of vehicle routing problem (VRP).

Key words: vehicle routing problem (VRP), simultaneous delivery-pickup, simulated annealing (SA), adaptive large-scale neighborhood search (ALNS), time windows

摘要：

为了给各物流企业在车辆配送路径规划方面提供合理有效的决策支持,针对单配送中心的配送模式,研究带时间窗约束的同时送取货车辆路径问题（VRPSDPTW）,建立以总配送成本最小化为目标的数学模型。根据模型的特征,提出基于模拟退火（SA）与自适应大规模邻域搜索（ALNS）相结合的混合优化算法（SA-ALNS）。采用基于时间与距离加权的插入启发式算法构造问题的初始解;引入多种删除、插入算子,以自适应选择策略进行路径优化,并通过反馈机制,逐渐调整各操作算子被选择的概率,使算法更倾向于选择寻优效果较好的算子;使用模拟退火机制的Metropolis准则控制解的更新。仿真实验中测试了56个大规模算例,对比了p-SA算法、DCS算法和VNS-BSTS等其他智能优化算法并进行统计分析,结果证明该算法在求解带时间窗约束的同时送取货车辆路径问题的可行性和优越性,研究成果极大丰富了车辆路径问题（VRP）的相关研究。

关键词: 车辆路径问题（VRP）, 同时送取货, 模拟退火算法（SA）, 自适应大规模邻域搜索算法（ALNS）, 时间窗

CLC Number:

TP301

LI Jun, DUAN Yurong, HAO Liyan, ZHANG Weiwei. Hybrid Optimization Algorithm for Vehicle Routing Problem with Simultaneous Delivery-Pickup[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1623-1632.

李珺, 段钰蓉, 郝丽艳, 张维维. 混合优化算法求解同时送取货车辆路径问题[J]. 计算机科学与探索, 2022, 16(7): 1623-1632.

Figures/Tables 7

References 15

[1]	ANGELELLI E, MANSINI R. The vehicle routing problem with time windows and simultaneous pick-up and delivery[M]. Berlin, Heidelberg: Springer, 2002.
[2]	CAO E B, LAI M Y. Vehicle routing problem with simul-taneous delivery and pick-up with time windows[C]// Procee-dings of the 1st International Conference on Transportation Engineering, Chengdu, Jan 1, 2007: 160-166.
[3]	BOUBAHRI L, ADDOUCHE S A.El MHAMEDI A. Multi-ant colonies algorithms for the VRPSPDTW[C]// Proceedings of the 2011 International Conference on Communications, Computing and Control Applications, Hammamet, Mar 3-5,2011. Piscataway: IEEE, 2011: 1-6.
[4]	WANG H F, CHEN Y Y. A genetic algorithm for the simul-taneous delivery and pickup problems with time window[J]. Computers & Industrial Engineering, 2012, 62(1): 84-95. DOI URL
[5]	王超, 高扬, 刘超, 等. 基于回溯搜索优化算法求解带时间窗和同时送取货的车辆路径问题[J]. 计算机集成制造系统, 2019, 25(9): 2237-2247.
	WANG C, GAO Y, LIU C, et al. Vehicle routing problem with simultaneous delivery and pickup problem solving by backtracking search optimization algorithm[J]. Computer Integ-rated Manufacturing Systems, 2019, 25(9): 2237-2247.
[6]	王超, 刘超, 穆东, 等. 基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[J]. 计算机集成制造系统, 2018, 24(3): 570-582.
	WANG C, LIU C, MU D, et al. VRPSPDTW problem solving by discrete cuckoo search[J]. Computer Integrated Manufacturing Systems, 2018, 24(3): 570-582.
[7]	黄务兰, 张涛. 基于改进全局人工鱼群算法的VRPSPDTW研究[J]. 计算机工程与应用, 2016, 52(21): 21-29.
	HUANG W L, ZHANG T. Vehicle routing problem with simul-taneous pick-up and delivery and time-windows based on improved global a.pngicial fish swarm algorithm[J]. Com-puter Engineering and Applications, 2016, 52(21): 21-29.
[8]	程谦, 张大力, 侯立文. 具有时间窗的取送货问题建模和大邻域搜索算法[J]. 哈尔滨商业大学学报(自然科学版), 2016, 32(6): 734-739.
	CHENG Q, ZHANG D L, HOU L W. Study on model for pickup and delivery problem with time windows and large neighborhood search algorithm[J]. Journal of Harbin Univer-sity of Commerce (Natural Sciences Edition), 2016, 32(6): 734-739.
[9]	ROPKE S, PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4): 455-472. DOI URL
[10]	SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Ope-rations Research, 1987, 35(2): 254-265.
[11]	WANG C, MU D, ZHAO F, et al. A parallel simulated annealing method for the vehicle routing problem with simul-taneous pickup-delivery and time windows[J]. Computers & Industrial Engineering, 2015, 83(C): 111-122.
[12]	SHI Y, BOUDOUH T, GRUNDER O. An efficient tabu search based procedure for simultaneous delivery and pick-up problem with time window[J]. IFAC-PapersOnLine, 2018, 51(11): 241-246.
[13]	HOF J, SCHNEIDER M. An adaptive large neighborhood search with path relinking for a class of vehicle-routing pro-blems with simultaneous pickup and delivery[J]. Networks, 2019, 74(3): 207-250. DOI URL
[14]	SHI Y, ZHOU Y J, BOUDOUH T, et al. A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup-delivery and time window[J]. Enginee-ring Applications of A.pngicial Intelligence, 2020, 95(2): 103901.
[15]	ZHANG S Q, MU D, WANG C. A solution for the full-load collection vehicle routing problem with multiple trips and demands: an application in Beijing[J]. IEEE Access, 2020, 8: 89381-89394. DOI URL

算例	p-SA	DCS	VNS-BSTS	ETSP	ALNS-PR	SA-ALNS
Cdp101	992.88	998.29	976.04	—	976.04	963.96
Cdp102	955.31	954.31	942.45	—	941.49	935.30
Cdp103	958.66	923.05	896.28	—	892.98	888.52
Cdp104	944.73	931.26	872.39	—	871.40	881.94
Cdp105	989.86	981.45	1 080.63	—	1 053.12	983.10
Cdp106	878.29	878.29	963.45	—	967.71	878.29
Cdp107	911.90	912.37	987.64	—	987.64	908.99
Cdp108	1 063.73	978.82	934.41	—	932.88	936.10
Cdp109	947.90	940.49	909.27	—	910.95	932.69
Cdp201	591.56	591.56	591.56	591.56	591.56	591.56
Cdp202	591.56	591.56	591.56	591.56	591.56	591.56
Cdp203	591.17	591.17	591.17	591.17	591.17	591.17
Cdp204	594.07	590.60	599.33	599.87	590.60	591.17
Cdp205	588.88	588.88	588.88	588.88	588.88	588.88
Cdp206	588.49	588.49	588.49	588.49	588.49	588.49
Cdp207	588.29	588.29	588.29	588.29	588.29	588.29
Cdp208	599.32	588.32	588.32	588.32	588.32	588.32

算例	p-SA	DCS	VNS-BSTS	ETSP	ALNS-PR	SA-ALNS
Cdp101	992.88	998.29	976.04	—	976.04	963.96
Cdp102	955.31	954.31	942.45	—	941.49	935.30
Cdp103	958.66	923.05	896.28	—	892.98	888.52
Cdp104	944.73	931.26	872.39	—	871.40	881.94
Cdp105	989.86	981.45	1 080.63	—	1 053.12	983.10
Cdp106	878.29	878.29	963.45	—	967.71	878.29
Cdp107	911.90	912.37	987.64	—	987.64	908.99
Cdp108	1 063.73	978.82	934.41	—	932.88	936.10
Cdp109	947.90	940.49	909.27	—	910.95	932.69
Cdp201	591.56	591.56	591.56	591.56	591.56	591.56
Cdp202	591.56	591.56	591.56	591.56	591.56	591.56
Cdp203	591.17	591.17	591.17	591.17	591.17	591.17
Cdp204	594.07	590.60	599.33	599.87	590.60	591.17
Cdp205	588.88	588.88	588.88	588.88	588.88	588.88
Cdp206	588.49	588.49	588.49	588.49	588.49	588.49
Cdp207	588.29	588.29	588.29	588.29	588.29	588.29
Cdp208	599.32	588.32	588.32	588.32	588.32	588.32

算例	p-SA	DCS	VNS-BSTS	ETSP	ALNS-PR	Par-SAA	SA-ALNS
Rdp101	1 660.98	1 658.65	1 650.80	—	1 650.80	1 659.76	1 650.20
Rdp102	1 491.75	1 490.13	1 486.12	—	1 486.12	1 490.25	1 485.47
Rdp103	1 226.77	1 228.48	1 294.75	—	1 297.01	1 307.37	1 228.10
Rdp104	1 000.65	1 005.99	984.81	—	984.81	1 000.65	1 011.50
Rdp105	1 399.81	1 340.06	1 377.11	—	1 377.11	1 399.81	1 366.87
Rdp106	1 275.69	1 270.29	1 261.40	—	1 252.03	1 271.95	1 260.90
Rdp107	1 082.92	1 084.00	1 144.02	—	1 121.86	1 172.60	1 085.40
Rdp108	962.48	964.38	968.32	—	965.54	1 003.78	967.40
Rdp109	1 181.92	1 156.90	1 224.86	—	1 194.73	1 177.75	1 155.75
Rdp110	1 106.52	1 108.81	1 101.33	—	1 148.20	1 106.52	1 095.23
Rdp111	1 073.62	1 077.65	1 117.76	—	1 098.84	1 073.62	1 069.50
Rdp112	966.06	977.59	961.29	—	1 010.42	966.06	963.77
Rdp201	1 286.55	1 281.63	1 254.57	1 268.52	1 253.23	—	1 181.73
Rdp202	1 150.31	1 152.65	1 202.27	1 099.61	1 191.70	—	1 065.16
Rdp203	997.84	950.79	949.42	981.48	946.28	—	927.65
Rdp204	848.01	776.00	837.13	775.93	833.09	—	790.96
Rdp205	1 046.06	1 051.38	1 027.49	1 045.12	994.43	—	1 000.14
Rdp206	959.94	957.81	938.63	973.44	913.68	—	948.28
Rdp207	899.82	890.52	912.26	841.24	890.61	—	849.44
Rdp208	739.06	737.05	737.26	740.82	726.82	—	728.83
Rdp209	947.80	930.26	940.29	999.06	909.16	—	909.35
Rdp210	1 005.11	1 005.11	945.97	964.59	939.37	—	939.80
Rdp211	812.44	819.88	805.22	805.53	904.44	—	774.99

算例	p-SA	DCS	VNS-BSTS	ETSP	ALNS-PR	Par-SAA	SA-ALNS
Rdp101	1 660.98	1 658.65	1 650.80	—	1 650.80	1 659.76	1 650.20
Rdp102	1 491.75	1 490.13	1 486.12	—	1 486.12	1 490.25	1 485.47
Rdp103	1 226.77	1 228.48	1 294.75	—	1 297.01	1 307.37	1 228.10
Rdp104	1 000.65	1 005.99	984.81	—	984.81	1 000.65	1 011.50
Rdp105	1 399.81	1 340.06	1 377.11	—	1 377.11	1 399.81	1 366.87
Rdp106	1 275.69	1 270.29	1 261.40	—	1 252.03	1 271.95	1 260.90
Rdp107	1 082.92	1 084.00	1 144.02	—	1 121.86	1 172.60	1 085.40
Rdp108	962.48	964.38	968.32	—	965.54	1 003.78	967.40
Rdp109	1 181.92	1 156.90	1 224.86	—	1 194.73	1 177.75	1 155.75
Rdp110	1 106.52	1 108.81	1 101.33	—	1 148.20	1 106.52	1 095.23
Rdp111	1 073.62	1 077.65	1 117.76	—	1 098.84	1 073.62	1 069.50
Rdp112	966.06	977.59	961.29	—	1 010.42	966.06	963.77
Rdp201	1 286.55	1 281.63	1 254.57	1 268.52	1 253.23	—	1 181.73
Rdp202	1 150.31	1 152.65	1 202.27	1 099.61	1 191.70	—	1 065.16
Rdp203	997.84	950.79	949.42	981.48	946.28	—	927.65
Rdp204	848.01	776.00	837.13	775.93	833.09	—	790.96
Rdp205	1 046.06	1 051.38	1 027.49	1 045.12	994.43	—	1 000.14
Rdp206	959.94	957.81	938.63	973.44	913.68	—	948.28
Rdp207	899.82	890.52	912.26	841.24	890.61	—	849.44
Rdp208	739.06	737.05	737.26	740.82	726.82	—	728.83
Rdp209	947.80	930.26	940.29	999.06	909.16	—	909.35
Rdp210	1 005.11	1 005.11	945.97	964.59	939.37	—	939.80
Rdp211	812.44	819.88	805.22	805.53	904.44	—	774.99

算例	p-SA	DCS	VNS-BSTS	ETSP	ALNS-PR	SA-ALNS
RCdp101	1 659.59	1 654.32	1 708.21	—	1 776.58	1 666.12
RCdp102	1 522.76	1 522.76	1 526.36	—	1 583.62	1 494.01
RCdp103	1 344.62	1 344.63	1 336.05	—	1 283.52	1 351.66
RCdp104	1 268.43	1 269.31	1 177.21	—	1 171.65	1 182.42
RCdp105	1 581.54	1 581.26	1 548.38	—	1 548.96	1 566.96
RCdp106	1 418.16	1 419.26	1 408.19	—	1 392.47	1 424.07
RCdp107	1 360.17	1 360.17	1 295.43	—	1 255.06	1 295.88
RCdp108	1 169.57	1 170.12	1 207.60	—	1 198.36	1 164.45
RCdp201	1 513.72	1 520.56	1 437.48	1 441.52	1 406.94	1 326.19
RCdp202	1 273.26	1 242.92	1 412.52	1 216.59	1 414.55	1 159.19
RCdp203	1 123.58	1 087.37	1 064.95	1 106.72	1 050.64	959.17
RCdp204	897.14	822.02	813.74	900.65	798.46	796.12
RCdp205	1 357.44	1 357.44	1 316.06	1 253.44	1 297.65	1 188.50
RCdp206	1 166.88	1 166.88	1 154.36	1 161.89	1 146.32	1 139.60
RCdp207	1 089.85	1 093.37	1 098.64	1 125.50	1 061.84	1 023.51
RCdp208	862.89	862.89	843.30	873.28	828.14	793.98