多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

doi:10.11772/j.issn.1001-9081.2023060760

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (6): 1897-1904.DOI: 10.11772/j.issn.1001-9081.2023060760

所属专题：先进计算

多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

李焱¹^,², 潘大志¹^,²(), 郑思情¹

^1.西华师范大学数学与信息学院, 四川南充 637009
^2.最优化理论与应用四川省高校重点实验室(西华师范大学), 四川南充 637009

收稿日期:2023-06-14 修回日期:2023-09-16 接受日期:2023-09-20 发布日期:2023-10-07 出版日期:2024-06-10
通讯作者: 潘大志
作者简介:李焱（1997—），男（苗族），四川泸州人，硕士研究生，主要研究方向：智能计算、组合优化
郑思情（2000—），女，四川南充人，硕士研究生，主要研究方向：均匀凸优化。
基金资助:
国家自然科学基金资助项目(11871059);西华师范大学英才科研基金资助项目(17YC385)

Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window

Yan LI¹^,², Dazhi PAN¹^,²(), Siqing ZHENG¹

^1.School of Mathematics & Information，China West Normal University，Nanchong Sichuan 637009，China
^2.Sichuan Colleges and Universities Key Laboratory of Optimization Theory and Applications （China West Normal University），Nanchong Sichuan 637009，China

Received:2023-06-14 Revised:2023-09-16 Accepted:2023-09-20 Online:2023-10-07 Published:2024-06-10
Contact: Dazhi PAN
About author:LI Yan， born in 1997， M. S. candidate. His research interests include intelligent computing， combinatorial optimization.
ZHENG Siqing， born in 2000， M. S. candidate. Her research interests include uniform convex optimization.
Supported by:
National Natural Science Foundation of China(11871059);Talent Research Fund of China West Normal University(17YC385)

摘要/Abstract

摘要：

针对多车场带时间窗车辆路径问题（MDVRPTW），提出一种改良自适应大邻域搜索算法（IALNS）。首先，在构造初始解阶段改进一种路径分割算法；其次，在优化阶段利用设计的移除和修复启发式算子相互竞争择优选取算子，为各算子引入评分机制，采用轮盘赌方式选取启发式算子；同时，将迭代周期分段，动态调整各周期内的算子权重信息，有效避免算法陷入局部最优；最后，采取模拟退火机制作为解的接受准则。在Cordeau规范算例上进行实验，确定IALNS的相关参数，将所提算法求解结果与该领域其他代表性研究成果对比。实验结果表明，所提算法与变邻域搜索（VNS）算法的求解误差不超过0.8%，在某些算例上甚至更优；与多相位改进的蛙跳算法相比，算法的平均耗时减少12.8%，所提算法在绝大多数算例上运行时间更短。因此，验证了所提算法是求解MDVRPTW的有效算法。

关键词: 多车场带时间窗车辆路径问题, 自适应大邻域搜索, 序列分割, 自适应权重, 模拟退火

Abstract:

Aiming at the Multi-Depot Vehicle Routing Problem with Time Window （MDVRPTW）， an Improved Adaptive Large Neighborhood Search algorithm （IALNS） was proposed. Firstly， a path segmentation algorithm was improved in the stage of constructing the initial solution. Then， in the optimization stage， the designed removal and repair heuristic operators were used to compete with each other to select the optimal operator， a scoring mechanism was introduced for the operators， and the heuristic operator was selected by roulette. At the same time， the iteration cycle was segmented and the operator weight information was dynamically adjusted in each cycle， effectively to prevent the algorithm from falling into local optimum. Finally， simulated annealing mechanism was adopted as the acceptance criterion of the solution. The relevant parameters of the IALNS were determined by experiments on the Cordeau normative instances， and the solution results of the proposed algorithm were compared with other representative research results in this field. The experimental results show that the solution error between IALNS and Variable Neighborhood Search （VNS） algorithm does not exceed 0.8%， even better in some cases； compared with the multi-phase improved shuffled frog leaping algorithm， the average time-consuming of the proposed algorithm is reduced by 12.8%， and the runtime is shorter for most instances. So the above results verify IALNS is an effective algorithm for solving MDVRPTW.

Key words: Multi-Depot Vehicle Routing Problem with Time Window （MDVRPTW）, Adaptive Large Neighborhood Search （ALNS）, sequence segmentation, adaptive weight, simulated annealing

中图分类号:

TP301.6

李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 计算机应用, 2024, 44(6): 1897-1904.

Yan LI, Dazhi PAN, Siqing ZHENG. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window[J]. Journal of Computer Applications, 2024, 44(6): 1897-1904.

图/表 10

参考文献 25

1	DANTZIG G B， RAMSER J H. The truck dispatching problem［J］. Management Science， 1959， 6（1）：80-91.
2	J-F CORDEAU， LAPORTE G， MERCIER A， et al. A unified tabu search heuristic for vehicle routing problems with time windows ［J］. Journal of the Operational Research Society， 2001， 52： 928-936.
3	J-F CORDEAU， LAPORTE G， MERCIER A. Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows［J］. Journal of the Operational Research Society， 2004， 55： 542-546.
4	POLACEK M， HARTL R F， DOERNER K，et al. A variable neighborhood search for the multi depot vehicle routing problem with time windows ［J］. Journal of Heuristics， 2004， 10： 613-627.
5	DONDO R， CERDÁ J. A cluster-based optimization approach for the multi- depot heterogeneous fleet vehicle routing problem with time windows［J］. European Journal of Operational Research， 2007，176：1478-1507.
6	洪联系，董绍华.MDVRPTW问题多阶段迭代启发式算法［J］.计算机工程与应用， 2007， 43（26）： 217-222.
	HONG L X， DONG S H. Multi-phase iterative heuristic approach for MDVRPTW ［J］. Computer Engineering and Applications， 2007， 43（26）： 217-222.
7	王征，张俊，王旭坪.多车场带时间窗车辆路径问题的变邻域搜索算法［J］.中国管理科学，2011，19（2）：99-109.
	WANG Z， ZHANG J， WANG X P. A modified variable neighborhood search algorithm for the multi depot vehicle routing problem with time windows［J］.Chinese Journal of Management Science， 2011，19（2）：99-109.
8	GENDREAU M， HERTZ A， LAPORTE G， et al. A generalized insertion heuristic for the traveling salesman problem with time windows ［J］. Operations Research， 1998，46（3）：330-335.
9	于滨，靳鹏欢，杨忠振.两阶段启发式算法求解带时间窗的多中心车辆路径问题［J］.系统工程理论与实践，2012，32（8）：1793-1800.
	YU B， JIN P H， YANG Z Z. Two-stage heuristic algorithm for multi-depot vehicle routing problem with time window［J］.System Engineering — Theory & Practice，2012，32（8）：1793-1800.
10	LUO J， CHEN M. Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW［J］. Computers & Industrial Engineering， 2014，72：84-97.
11	TAMASHIRO H， NAKAMURA M， OKAZAKI T， et al. A tabu search approach combined with an extended saving method for multi-depot vehicle routing problems with time windows （TOTAL OPERATIONS MENAGEMENT）［J］. International Journal of Biomedical Soft Computing and Human Sciences： the Official Journal of the Biomedical Fuzzy Systems Association，2010，15（1）：29-37.
12	SADATI M E H， ATAY B， AKSEN D. An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems［J］. Computers and Operations Research， 2021，133： 105269.
13	刘小兰，郝志峰，汪国强，等.有时间窗的车辆路径问题的近似算法研究［J］. 计算机集成制造系统， 2004， 10（7）： 825-831.
	LIU X L， HAO Z F， WANG G Q， et al. Improved large neighborhood search algorithm for vehicle routing problem with time windows［J］. Computer Integrated Manufacturing Systems， 2004， 10（7）： 825-831.
14	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.
15	CHENG L. A genetic algorithm for the vehicle routing problem with time windows［D］. Wilmington， North Carolina： University of North Carolina Wilmington， 2009：105-121.
16	陈小玲. 蚁群算法及其在车辆路径问题中的应用研究［D］.成都：电子科技大学， 2009：16-34.
	CHEN X L. Ant colony algorithm and its application research in vehicle routing problems［D］.Chengdu：University of Electronic Science and Technology of China， 2009：16-34.
17	CHEN C-M， LV S， NING J， et al. A genetic algorithm for the waitable time-varying multi-depot green vehicle routing problem［J］. Symmetry， 2023，15（1）： 124.
18	吕垚远. 混合差分进化算法在多目标车辆路径问题中的应用［D］. 太原：太原科技大学， 2021：23-42.
	LU Y Y. Application of hybrid differential evolution algorithm in multi-objective vehicle routing problem［D］. Taiyuan： Taiyuan University of Science and Technology， 2021：23-42.
19	周蓉，沈维蕾.软硬时间窗共存装卸一体化车辆路径问题的混合离散粒子群优化算法［J］.合肥工业大学学报（自然科学版），2016，39（8）：1022-1026.
	ZHOU R， SHEN W L. Hybrid discrete particle swarm optimization algorithm for vehicle routing problem with simultaneous delivery and pickup under coexistence of soft and hard time windows［J］. Journal of Hefei University of Technology （Natural Science）， 2016，39（8）：1022-1026.
20	WANG Y， WEI Y， WANG X， et al. A clustering-based extended genetic algorithm for the multidepot vehicle routing problem with time windows and three-dimensional loading constraints［J］. Applied Soft Computing， 2023，133：109922.
21	FAIED M， MOSTAFA A， GIRARD A. Dynamic optimal control of multiple depot vehicle routing problem with metric temporal logic［C］// Proceedings of the 2009 American Control Conference. Piscataway： IEEE， 2009： 3268-3273.
22	RAJMOHAN M， SHAHABUDEEN P. Metaheuristic for solving routing problem in logistics management［J］. International Journal of Operational Research， 2009， 6（2）： 223-246.
23	向婷，潘大志.求解需求可拆分车辆路径问题的聚类算法［J］.计算机应用，2016，36（11）：3141-3145.
	XIANG T， PAN D Z. Clustering algorithm for split delivery vehicle routing problem［J］. Journal of Computer Applications， 2016，36（11）：3141-3145.
24	MUNARI P， SAVELSBERGH M. A column generation-based heuristic for the split delivery vehicle routing problem with time windows［J］. SN Operations Research Forum， 2020， 1： 26.
25	FONTAINE P. The vehicle routing problem with load-dependent travel times for cargo bicycles［J］. European Journal of Operational Research， 2022，300：1005-1016.

算子类型	Avg.gap/%	Fails	Times/s
遗憾-1	36.2	4	0.02
遗憾-2	29.3	3	0.02
遗憾-3	27.6	3	0.02
遗憾-4	26.4	3	0.02
遗憾-5	25.7	2	0.02
遗憾-m	27.8	0	0.03

算子类型	Avg.gap/%	Fails	Times/s
遗憾-1	36.2	4	0.02
遗憾-2	29.3	3	0.02
遗憾-3	27.6	3	0.02
遗憾-4	26.4	3	0.02
遗憾-5	25.7	2	0.02
遗憾-m	27.8	0	0.03

ξ	Avg.gap/%	LOT	ξ	Avg.gap/%	LOT
0.1	22.4	14	0.6	17.2	10
0.2	16.8	11	0.7	19.3	11
0.3	12.6	7	0.8	18.0	10
0.4	5.2	4	0.9	24.3	16
0.5	13.5	5

ξ	Avg.gap/%	LOT	ξ	Avg.gap/%	LOT
0.1	22.4	14	0.6	17.2	10
0.2	16.8	11	0.7	19.3	11
0.3	12.6	7	0.8	18.0	10
0.4	5.2	4	0.9	24.3	16
0.5	13.5	5

Instance			TS		VNS		MPMSFLA		IALNS
name	N	D	KBS	TIME/min	AVE	TIME/min	AVE	TIME/min	AVE	TIME/min	GAP/%
pr01	48	4	1 074.12	28	1 074.12	9.49	1 074.34	0.45	1 074.28	0.39	0.01
pr02	96	4	1 762.48	79	1 763.66	27.63	1 768.23	1.42	1 766.41	0.68	0.16
pr03	144	4	2 397.06	115	2 388.73	75.88	2 378.23	2.96	2 399.52	3.15	0.45
pr04	192	4	2 865.71	144	2 847.56	93.53	2 858.35	4.21	2 852.41	3.26	0.17
pr05	240	4	3 050.80	181	3 015.27	89.36	3 021.56	4.89	3 027.97	3.95	0.42
pr06	288	4	3 670.13	221	3 674.60	96.63	3 685.28	6.33	3 686.14	6.85	0.31
pr07	72	6	1 418.22	53	1 418.22	7.66	1 418.78	1.89	1 421.21	1.72	0.21
pr08	144	6	2 118.50	102	2 103.21	54.92	2 111.47	3.07	2 110.36	2.87	0.34
pr09	216	6	2 760.46	160	2 753.61	69.11	2 770.61	3.85	2 760.23	2.96	0.24
pr10	288	6	3 507.26	227	3 541.01	65.70	3 555.86	6.97	3 534.27	6.38	-0.19
pr11	48	4	1 016.59	32	1 011.65	18.30	1 009.70	0.48	1 019.35	0.35	0.76
pr12	96	4	1 486.26	81	1 488.32	89.40	1 489.11	1.90	1 487.15	1.36	-0.08
pr13	144	4	2 028.85	143	2 012.37	82.30	2 026.47	3.25	2 025.65	2.59	0.66
pr14	192	4	2 228.64	188	2 239.02	106.51	2 242.89	4.16	2 251.23	3.29	0.55
pr15	240	4	2 527.60	227	2 498.85	89.39	2 508.28	4.88	2 503.14	3.15	0.17
pr16	288	4	2 960.93	261	2 909.45	99.69	2 930.14	6.86	2 918.35	6.92	0.31
pr17	72	6	1 241.25	61	1 247.51	62.15	1 240.19	1.60	1 251.31	1.36	0.30
pr18	144	6	1 823.24	146	1 809.25	99.24	1 815.74	3.07	1 814.35	2.56	0.28
pr19	216	6	2 288.38	262	2 294.19	90.84	2 300.65	4.29	2 310.12	3.88	0.69
pr20	288	6	3 120.32	263	3 093.51	86.38	3 109.12	6.64	3 107.25	6.12	0.44

多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 25

相关文章 15

编辑推荐

Metrics

[1]	周毅, 高华, 田永谌. 基于裁剪优化和策略指导的近端策略优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2334-2341.
[2]	韦修喜, 彭茂松, 黄华娟. 基于多策略改进蝴蝶优化算法的无线传感网络节点覆盖优化[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1009-1017.
[3]	欧云, 周恺卿, 尹鹏飞, 刘雪薇. 双收敛因子策略下的改进灰狼优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2679-2685.
[4]	高昊, 张庆科, 卜降龙, 李俊青, 张化祥. 基于协同变异与莱维飞行策略的教与学优化算法及其应用[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1355-1364.
[5]	马学森, 许雪梅, 蒋功辉, 乔焰, 周天保. 混合自适应粒子群工作流调度优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 474-483.
[6]	肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2926-2935.
[7]	张伟康, 刘升, 黄倩, 郭雨鑫. 考虑距离因素与精英进化策略的平衡优化器[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1844-1851.
[8]	陈昇, 周隽, 胡小兵, 马霁. 基于混合模拟退火算法的机场进场程序优化[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 606-615.
[9]	郭潇, 李春山, 张宇跃, 初佃辉. 基于自适应多目标强化学习的服务集成方法[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3500-3505.
[10]	李智, 薛建彬. C‑V2X车联网中基于模拟退火算法的任务卸载与资源分配[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3140-3147.
[11]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[12]	时永鹏, 张俊杰, 夏玉杰, 高雅, 张尚伟. 基于NOMA的5G超密网计算迁移与资源分配策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3319-3324.
[13]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[14]	王博, 刘连生, 韩绍程, 祝世兴. 基于多策略融合的混合多目标蝗虫优化算法[J]. 计算机应用, 2020, 40(9): 2670-2676.
[15]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.