面向多行程取送货车辆路径问题的混合NSGA-Ⅱ

doi:10.11772/j.issn.1001-9081.2023101512

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (4): 1187-1194.DOI: 10.11772/j.issn.1001-9081.2023101512

• 先进计算 • 上一篇

面向多行程取送货车辆路径问题的混合NSGA-Ⅱ

李建强, 何舟()

陕西科技大学电气与控制工程学院，西安 710021

收稿日期:2023-11-06 修回日期:2024-01-10 接受日期:2024-01-12 发布日期:2024-04-22 出版日期:2024-04-10
通讯作者: 何舟
作者简介:李建强（1998—），男，甘肃定西人，硕士研究生，主要研究方向：车辆路径规划、组合优化
何舟（1990—），男，陕西安康人，副教授，博士，主要研究方向：多移动机器人系统协同控制与优化、离散型智能制造系统建模和仿真、生产管控决策优化。hezhou@sust.edu.cn
基金资助:
国家自然科学基金资助项目(62373234)

Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery

Jianqiang LI, Zhou HE()

College of Electrical and Control Engineering，Shaanxi University of Science and Technology，Xi’an Shaanxi 710021，China

Received:2023-11-06 Revised:2024-01-10 Accepted:2024-01-12 Online:2024-04-22 Published:2024-04-10
Contact: Zhou HE
About author:LI Jianqiang， born in 1998， M. S. candidate. His research interests include vehicle path planning， combinatorial optimization.
HE Zhou， born in 1990， Ph. D.， associate professor. His research interests include cooperative control and optimization of multiple mobile robot system， modeling and simulation of discrete intelligent manufacturing system， optimization of production management and control decision making.
Supported by:
National Natural Science Foundation of China(62373234)

摘要/Abstract

摘要：

针对多行程取送货车辆路径问题（VRP）收敛性与多样性相互制约的问题，提出一种融合自适应大邻域搜索（ALNS）算法和自适应邻域选择（ANS）的混合快速非支配排序遗传算法（NSGA-Ⅱ-ALNS-ANS）。首先，考虑初始解对算法收敛速度的影响，提出一种改进的后悔插入法以获得高质量初始解；其次，结合取送货问题特性，设计多组破坏和修复算子，以及多种邻域结构，提高算法的全局搜索能力和局部搜索能力；最后，设计基于随机采样的最佳拟合下降（BFD）算法与高效的可行解评价标准，生成路径分配方案。采用不同规模的标准公开算例进行仿真实验，与模因算法（MA）相比，所提算法的最优解质量提升了27%。实验结果表明，所提算法可快速得到满足多重约束的高质量车辆多行程路径分配方案，并在收敛性与多样性上优于对比算法。

关键词: 路径规划, 车辆路径问题, 取送货, 多行程, 多目标优化, NSGA-Ⅱ

Abstract:

Concerning the trade-off between convergence and diversity in solving the multi-trip pickup and delivery Vehicle Routing Problem （VRP）， a hybrid Non-dominated Sorting Genetic Algorithm Ⅱ （NSGA-Ⅱ） combining Adaptive Large Neighborhood Search （ALNS） algorithm and Adaptive Neighborhood Selection （ANS）， called NSGA-Ⅱ-ALNS-ANS， was proposed. Firstly， considering the influence of the initial population on the convergence speed of the algorithm， an improved regret insertion method was employed to obtain high-quality initial population. Secondly， to improve global and local search capabilities of the algorithm， various destroy-repair operators and neighborhood structures were designed， according to the characteristics of the pickup and delivery problem. Finally， a Best Fit Decreasing （BFD） algorithm based on random sampling and an efficient feasible solution evaluation criterion were proposed to generate vehicle routing schemes. The simulation experiments were conducted on public benchmark instances of different scales， in the comparison experiments with the MA （Memetic Algorithm）， the optimal solution quality of the proposed algorithm increased by 27%. The experimental results show that the proposed algorithm can rapidly generate high-quality vehicle routing schemes that satisfy multiple constraints， and outperform the existing algorithms in terms of both convergence and diversity.

Key words: path planning, Vehicle Routing Problem (VRP), pickup and delivery, multi-trip, multi-objective optimization, NSGA-Ⅱ (Non-dominated Sorting Genetic Algorithm Ⅱ)

中图分类号:

TP301

李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 计算机应用, 2024, 44(4): 1187-1194.

Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery[J]. Journal of Computer Applications, 2024, 44(4): 1187-1194.

图/表 7

参考文献 27

1	DANTZIG G B， RAMSER J H. The truck dispatching problem［J］. Management Science， 1959， 6（1）： 80-91. 10.1287/mnsc.6.1.80
2	SALEHI SARBIJAN M， BEHNAMIAN J. Emerging research fields in vehicle routing problem： a short review［J］. Archives of Computational Methods in Engineering， 2023， 30： 2473-2491. 10.1007/s11831-022-09874-w
3	SAJID M， SINGH J， HAIDRI R A， et al. A novel algorithm for capacitated vehicle routing problem for smart cities［J］. Symmetry， 2021， 13： 1923. 10.3390/sym13101923
4	夏小云，庄鹤林，杨火根，等. 自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题［J］. 计算机集成制造系统， 2022， 28（11）： 3545-3557. 10.13196/j.cims.2022.11.018
	XIA X Y， ZHUANG H L， YANG H G， et al. Adaptive large neighborhood search based artificial bee colony algorithm for CVRP［J］. Computer Integrated Manufacturing Systems， 2022， 28（11）： 3545-3557. 10.13196/j.cims.2022.11.018
5	ALTMAN C， DESAULNIERS G， ERRICO F. The fragility-constrained vehicle routing problem with time windows［J］. Transportation Science， 2023， 57（2）： 552-572. 10.1287/trsc.2022.1168
6	ZHANG Z， LUO Z， QIN H， et al. Exact algorithms for the vehicle routing problem with time windows and combinatorial auction［J］. Transportation Science， 2019， 53（2）： 427-441. 10.1287/trsc.2018.0835
7	李焱，潘大志，郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法［J/OL］. 计算机应用， 2023： 1-11 ［2023-11-25］. . 10.11772/j.issn.1001-9081.2023060760
	LI Y， PAN D Z， ZHENG S Q. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window［J/OL］. Journal of Computer Applications， 2023： 1-11 ［2023-11-25］.. 10.11772/j.issn.1001-9081.2023060760
8	DENG F， QIN H， LI J， et al. The pickup and delivery problem with time windows and incompatibility constraints in cold chain transportation［J］. Transportation Science， 2023， 57（2）： 444-462. 10.1287/trsc.2022.1167
9	CHEVRIER R， LIEFOOGHE A， JOURDAN L， et al. Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach： application to demand responsive transport［J］. Applied Soft Computing， 2012， 12（4）： 1247-1258. 10.1016/j.asoc.2011.12.014
10	SITEK P， WIKAREK J， RUTCZYŃSKA-WDOWIAK K， et al. Optimization of capacitated vehicle routing problem with alternative delivery， pick-up and time windows： a modified hybrid approach［J］. Neurocomputing， 2021， 423： 670-678. 10.1016/j.neucom.2020.02.126
11	CATTARUZZA D， ABSI N， FEILLET D， et al. An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows［J］. Computers & Operations Research， 2014， 51： 257-267. 10.1016/j.cor.2014.06.006
12	DESPAUX F， BASTERRECH S. A study of the multi-trip vehicle routing problem with time windows and heterogeneous fleet［C］// Proceedings of the 2014 14th International Conference on Intelligent Systems Design and Applications. Piscataway： IEEE， 2014： 7-12. 10.1109/isda.2014.7066280
13	宋强. 改进混合遗传算法在MTVRPTW中的建模与优化［J］. 重庆交通大学学报（自然科学版）， 2018， 37（9）： 79-86，134.
	SONG Q. Application of improved hybrid genetic algorithm in the modeling and optimization of multi-trip vehicle routing problem with time windows［J］. Journal of Chongqing Jiaotong University （Natural Sciences）， 2018， 37（9）： 79-86，134.
14	高海龙，谢勇，马吉祥，等. 多行程多交货期的成品油配送优化［J］. 控制与决策， 2022， 37（10）： 2714-2722. 10.13195/j.kzyjc.2021.0190
	GAO H L， XIE Y， MA J X， et al. Optimization of refined oil distribution with multiple trips and multiple due time［J］. Control and Decision， 2022， 37（10）： 2714-2722. 10.13195/j.kzyjc.2021.0190
15	FRANÇOIS V， ARDA Y， CRAMA Y， et al. Large neighborhood search for multi-trip vehicle routing［J］. European Journal of Operational Research， 2016， 255（2）： 422-441. 10.1016/j.ejor.2016.04.065
16	ZHANG Z， LIU M， LIM A. A memetic algorithm for the patient transportation problem［J］. Omega， 2015， 54： 60-71. 10.1016/j.omega.2015.01.011
17	MASMOUDI M A， HOSNY M， BRAEKERS K， et al. Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem［J］. Transportation Research Part E： Logistics and Transportation Review， 2016， 96： 60-80. 10.1016/j.tre.2016.10.002
18	LIM A， ZHANG Z， QIN H. Pickup and delivery service with manpower planning in Hong Kong public hospitals［J］. Transportation Science， 2017， 51（2）： 688-705. 10.1287/trsc.2015.0611
19	WANG J， SUN Y， ZHANG Z， et al. Solving multitrip pickup and delivery problem with time windows and manpower planning using multiobjective algorithms［J］. IEEE/CAA Journal of Automatica Sinica， 2020， 7（4）： 1134-1153. 10.1109/jas.2020.1003204
20	DUMEZ D， LEHUÉDÉ F， PÉTON O. A large neighborhood search approach to the vehicle routing problem with delivery options［J］. Transportation Research Part B： Methodological， 2021， 144： 103-132. 10.1016/j.trb.2020.11.012
21	BELHOR M， El-AMRAOUI A， JEMAI A， et al. Multi-objective evolutionary approach based on K-means clustering for home health care routing and scheduling problem［J］. Expert Systems with Applications， 2023， 213： 119035. 10.1016/j.eswa.2022.119035
22	EL-ASHMAWI W H， ELMINAAM D S ABD. A modified squirrel search algorithm based on improved best fit heuristic and operator strategy for bin packing problem［J］. Applied Soft Computing， 2019， 82： 105565. 10.1016/j.asoc.2019.105565
23	ABBASI M， RAFIEE M， KHOSRAVI M R， et al. An efficient parallel genetic algorithm solution for vehicle routing problem in cloud implementation of the intelligent transportation systems［J］. Journal of Cloud Computing： Advances， Systems and Applications， 2020， 9（1）： No.6. 10.1186/s13677-020-0157-4
24	SOMAN J T， PATIL R J. A scatter search method for heterogeneous fleet vehicle routing problem with release dates under lateness dependent tardiness costs［J］. Expert Systems with Applications， 2020， 150： 113302. 10.1016/j.eswa.2020.113302
25	CHRISTIAENS J， VANDEN BERGHE G. Slack induction by string removals for vehicle routing problems［J］. Transportation Science， 2020， 54（2）： 417-433. 10.1287/trsc.2019.0914
26	CHEN C， DEMIR E， HUANG Y. An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots［J］. European Journal of Operational Research， 2021， 294（3）： 1164-1180. 10.1016/j.ejor.2021.02.027
27	FRANÇOIS V， ARDA Y， CRAMA Y. Adaptive large neighborhood search for multi-trip vehicle routing with time windows［J］. Transportation Science， 2019， 53（6）： 1706-1730. 10.1287/trsc.2019.0909

算例名称	K	n	不同算法的距离成本
算例名称	K	n	MA	ILS-ANS	混合NSGA-Ⅱ
101	2	29	296	305	281
102	2	32	286	290	267
103	2	37	314	320	280
108	3	50	408	415	398

算例名称	K	n	不同算法的距离成本
算例名称	K	n	MA	ILS-ANS	混合NSGA-Ⅱ
101	2	29	296	305	281
102	2	32	286	290	267
103	2	37	314	320	280
108	3	50	408	415	398

算例名称	K	n	NSGA-Ⅱ		NSGA-Ⅱ-ALNS		NSGA-Ⅱ-ANS		混合NSGA-Ⅱ
算例名称	K	n	距离成本	CPU运行时间/s	距离成本	CPU运行时间/s	距离成本	CPU运行时间/s	距离成本	CPU运行时间/s
1	2	10	189	317.50	133	10.15	133	19.17	133	2.49
2	2	10	211	132.73	157	9.48	178	12.82	157	4.21
3	2	10	223	461.30	160	15.96	158	19.11	158	2.39
4	2	10	178	478.18	155	13.69	155	3.97	155	3.28
5	2	11	165	223.26	133	29.88	133	45.39	133	5.06
6	2	11	223	168.30	147	48.93	147	36.16	147	3.78
7	2	11	219	387.07	162	16.68	162	28.86	162	3.90
8	2	11	192	403.62	142	25.36	134	28.29	134	4.09
9	2	11	251	266.20	159	7.89	175	54.00	159	0.75
10	2	11	244	384.16	184	25.69	184	32.42	184	4.58
11	2	11	238	519.06	161	13.95	156	22.75	156	4.01
12	2	12	172	202.14	144	33.47	144	34.48	144	5.09
13	2	12	196	486.79	149	38.43	165	18.57	149	4.34
14	2	12	161	492.86	143	30.75	142	38.21	142	4.58
15	2	12	206	182.43	151	24.15	172	19.98	151	5.44
16	2	12	277	493.42	198	19.87	221	32.05	198	3.79
17	2	12	221	210.41	160	14.95	160	38.86	160	5.29
18	2	13	197	463.42	142	41.16	174	20.60	142	4.21
19	2	13	170	310.66	136	2.51	136	17.09	136	1.71
20	2	13	214	287.47	139	6.01	200	32.05	139	3.09
21	2	13	179	412.47	154	28.20	171	49.26	154	4.33
22	2	13	234	592.10	160	26.45	161	39.63	154	4.86
23	2	13	178	248.56	139	30.49	156	34.86	139	3.46
24	2	14	134	341.21	124	60.85	151	36.69	124	4.82
25	2	14	207	404.90	124	16.70	154	29.96	124	2.19
26	2	14	225	410.43	139	13.30	162	39.88	139	6.09
27	2	14	248	544.61	152	21.76	220	47.50	152	10.71
28	2	14	198	433.33	121	12.66	121	21.59	121	3.05
29	2	15	242	345.63	137	31.50	137	84.03	137	7.29
30	2	15	277	213.21	138	9.61	163	33.11	138	2.39
101	2	29	—	—	298	1 677.83	315	818.23	280	408.16
102	2	32	—	—	268	1 953.97	283	946.05	267	617.52
103	2	37	—	—	310	2 108.71	322	1 093.89	280	441.31
108	3	50	—	—	421	2 508.71	433	1 779.71	398	907.53

算例名称	K	n	NSGA-Ⅱ		NSGA-Ⅱ-ALNS		NSGA-Ⅱ-ANS		混合NSGA-Ⅱ
算例名称	K	n	距离成本	CPU运行时间/s	距离成本	CPU运行时间/s	距离成本	CPU运行时间/s	距离成本	CPU运行时间/s
1	2	10	189	317.50	133	10.15	133	19.17	133	2.49
2	2	10	211	132.73	157	9.48	178	12.82	157	4.21
3	2	10	223	461.30	160	15.96	158	19.11	158	2.39
4	2	10	178	478.18	155	13.69	155	3.97	155	3.28
5	2	11	165	223.26	133	29.88	133	45.39	133	5.06
6	2	11	223	168.30	147	48.93	147	36.16	147	3.78
7	2	11	219	387.07	162	16.68	162	28.86	162	3.90
8	2	11	192	403.62	142	25.36	134	28.29	134	4.09
9	2	11	251	266.20	159	7.89	175	54.00	159	0.75
10	2	11	244	384.16	184	25.69	184	32.42	184	4.58
11	2	11	238	519.06	161	13.95	156	22.75	156	4.01
12	2	12	172	202.14	144	33.47	144	34.48	144	5.09
13	2	12	196	486.79	149	38.43	165	18.57	149	4.34
14	2	12	161	492.86	143	30.75	142	38.21	142	4.58
15	2	12	206	182.43	151	24.15	172	19.98	151	5.44
16	2	12	277	493.42	198	19.87	221	32.05	198	3.79
17	2	12	221	210.41	160	14.95	160	38.86	160	5.29
18	2	13	197	463.42	142	41.16	174	20.60	142	4.21
19	2	13	170	310.66	136	2.51	136	17.09	136	1.71
20	2	13	214	287.47	139	6.01	200	32.05	139	3.09
21	2	13	179	412.47	154	28.20	171	49.26	154	4.33
22	2	13	234	592.10	160	26.45	161	39.63	154	4.86
23	2	13	178	248.56	139	30.49	156	34.86	139	3.46
24	2	14	134	341.21	124	60.85	151	36.69	124	4.82
25	2	14	207	404.90	124	16.70	154	29.96	124	2.19
26	2	14	225	410.43	139	13.30	162	39.88	139	6.09
27	2	14	248	544.61	152	21.76	220	47.50	152	10.71
28	2	14	198	433.33	121	12.66	121	21.59	121	3.05
29	2	15	242	345.63	137	31.50	137	84.03	137	7.29
30	2	15	277	213.21	138	9.61	163	33.11	138	2.39
101	2	29	—	—	298	1 677.83	315	818.23	280	408.16
102	2	32	—	—	268	1 953.97	283	946.05	267	617.52
103	2	37	—	—	310	2 108.71	322	1 093.89	280	441.31
108	3	50	—	—	421	2 508.71	433	1 779.71	398	907.53

[1]	黄海新, 于广威, 程寿山, 李春明. 基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 966-971.
[2]	邓辅秦, 官桧锋, 谭朝恩, 付兰慧, 王宏民, 林天麟, 张建民. 基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 432-438.
[3]	宋紫阳, 李军怀, 王怀军, 苏鑫, 于蕾. 基于路径模仿和SAC强化学习的机械臂路径规划算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 439-444.
[4]	马勇健, 史旭华, 王佩瑶. 基于两阶段搜索与动态资源分配的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 269-277.
[5]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.
[6]	林剑, 叶璟轩, 刘雯雯, 邵晓雯. 求解带容量约束车辆路径问题的多模态差分进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2248-2254.
[7]	金苍宏, 邵育华, 何琴芳. 基于自适应群组重排的长尾推荐模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1122-1128.
[8]	李永迪, 李彩虹, 张耀玉, 张国胜. 基于改进SAC算法的移动机器人路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 654-660.
[9]	黄霖, 符强, 童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3840-3847.
[10]	柳隽琰, 江沸菠, 彭于波, 董莉. 基于分解法与轨迹搜索的无人机群轨迹多目标优化模型[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3806-3815.
[11]	王龙宝, 栾茵琪, 徐亮, 曾昕, 张帅, 徐淑芳. 基于动态簇粒子群优化的无人机集群路径规划方法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3816-3823.
[12]	柳春锋, 李峥, 王居凤. 分布式工厂中微型制造单元多目标优化[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3824-3832.
[13]	李二超, 张生辉. 基于新评价指标自适应预测的动态多目标优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3178-3187.
[14]	刘晨, 陈洋, 符浩. 基于值函数迭代的持续监测无人机路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3290-3296.
[15]	李兴佳, 杨秋辉, 洪玫, 潘春霞, 刘瑞航. 基于历史数据和多目标优化的测试用例排序方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 221-226.

面向多行程取送货车辆路径问题的混合NSGA-Ⅱ

Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 27

相关文章 15

编辑推荐

Metrics