求解车辆路径问题的改进离散差分进化算法

于凯营; 徐斌

doi:10.12299/jsues.23-0215

求解车辆路径问题的改进离散差分进化算法

doi: 10.12299/jsues.23-0215

于凯营,
徐斌^,

上海工程技术大学机械与汽车工程学院, 上海 201620

基金项目: 国家自然科学基金资助（61703268）

详细信息

作者简介:
于凯营（1995 − ），男，硕士生，研究方向为车辆路径优化。E-mail：kmkying@foxmail.com

通讯作者:
徐　斌（1984 − ），男，副教授，博士，研究方向为智能计算及应用。E-mail：bxu@sues.edu.cn

中图分类号: TP183
计量
- 文章访问数: 16
- HTML全文浏览量: 13
- PDF下载量: 0
- 被引次数: 0
出版历程
- 收稿日期: 2023-10-11
- 刊出日期: 2024-12-31

Improved discrete differential evolution algorithm for solving vehicle routing problem

YU Kaiying,
XU Bin^,

School of Mechanical and Automotive Engineering, Shanghai University of Engineering Science, Shanghai 201620, China

摘要

摘要: 针对带容量约束的车辆路径问题易受客户位置和需求等不确定因素影响，导致最优解不可行或非最优等问题，提出一种改进的离散差分进化算法。利用贪心法构建初始解，提高初始解质量；根据整数排列特征重新设计变异算子，并对问题模型改进交叉算子，提高了算法性能；设计融合局部重定位、条件交换及最大贡献度移除机制的局部搜索策略，提高了算法的探索能力。基准测试集仿真试验表明，在33个测试算例中，改进算法能找到31个算例的最优值，较对比算法有更好的求解能力，能有效解决带容量约束的车辆路径问题。
- 车辆路径问题 /
- 差分进化算法 /
- 贪心法 /
- 离散优化 /
- 局部搜索
Abstract: Given that the vehicle routing problem with capacity constraints is easily influenced by uncertain factors such as customer location and demand, and leads to the infeasible or non-optimal solution, an improved discrete differential evolution algorithm was proposed. The greedy method was employed to construct the initial solution, thereby enhancing its quality of the initial solution. The mutation operator was redesigned according to the integer permutation characteristics, and the crossover operator was adapted for problem model, which improved the algorithm performance effectively. A local search strategy that incorporates local relocation, conditional exchange and a maximum contribution removal mechanism were designed, enhancing algorithm's exploration capabilities. Simulation experiments on the benchmark test set show that the improved algorithm can find the optimal value for 31 out of 33 test cases, indicating superior solution capabilities compared to other algorithms and effectively addressing the vehicle routing problem with capacity constraints.
- vehicle routing problem /
- differential evolution algorithm /
- greedy algorithm /
- discrete optimization /
- local search

HTML全文

图 1 路径内客户重定位过程

Figure 1. Customer repositioning process within path

下载: 全尺寸图片幻灯片

图 2 路径间客户交换过程

Figure 2. Customer exchange process between paths

下载: 全尺寸图片幻灯片

图 3 改进差分进化算法流程图

Figure 3. Flow chart of IDDELS

下载: 全尺寸图片幻灯片

图 4 最优配送路径

Figure 4. Optimal delivery path

下载: 全尺寸图片幻灯片

图 5 最优解的偏差累计

Figure 5. Accumulated deviation of the optimal solution

下载: 全尺寸图片幻灯片

表 1 基准测试集中算例的测试结果

Table 1. Test results of examples in benchmark set

算例	BKR	SEGDE		MDE		ABC-ALNS		AGGWOA		IDDELS
算例	BKR	BEST	DEV/%	BEST	DEV/%	BEST	DEV/%	BEST	DEV/%	BEST	DEV/%
A-n32-k5	784	813	3.70	784	0.00	784	0.00	784	0.00	784	0.00
A-n33-k5	661	680	2.87	661	0.00	661	0.00	661	0.00	661	0.00
A-n33-k6	742	746	0.54	742	0.00	742	0.00	742	0.00	742	0.00
A-n34-k5	778	789	1.41	778	0.00	778	0.00	778	0.00	778	0.00
A-n36-k5	799	805	0.75	799	0.00	799	0.00	799	0.00	799	0.00
A-n37-k5	669	685	2.39	669	0.00	669	0.00	669	0.00	669	0.00
A-n37-k6	949	954	0.53	949	0.00	953	0.42	949	0.00	949	0.00
A-n38-k5	730	734	0.55	—	—	730	0.00	730	0.00	730	0.00
A-n39-k6	831	852	2.53	—	—	834	0.36	833	0.24	831	0.00
A-n44-k6	937	943	0.64	—	—	948	1.17	937	0.00	937	0.00
A-n45-k7	1146	1203	4.97	1146	0.00	1153	0.61	1146	0.00	1146	0.00
A-n46-k7	914	935	2.30	—	—	917	0.33	914	0.00	914	0.00
A-n48-k7	1073	1129	5.22	1073	0.00	1073	0.00	1073	0.00	1073	0.00
A-n53-k7	1010	—	—	—	—	1014	0.40	1017	0.69	1016	0.59
A-n54-k7	1167	—	—	1167	0.00	1174	0.60	1176	0.77	1167	0.00
A-n55-k9	1073	—	—	—	—	1074	0.09	1074	0.09	1073	0.00
B-n31-k5	672	679	1.04	—	—	672	0.00	—	—	672	0.00
B-n34-k5	788	790	0.25	788	0.00	788	0.00	—	—	788	0.00
B-n35-k5	955	970	1.57	955	0.00	955	0.00	—	—	955	0.00
B-n38-k6	805	825	2.48	—	—	805	0.00	—	—	805	0.00
B-n39-k5	549	563	2.55	549	0.00	549	0.00	—	—	549	0.00
B-n43-k6	742	775	4.45	742	0.00	742	0.00	—	—	742	0.00
B-n44-k7	909	931	2.42	909	0.00	909	0.00	—	—	909	0.00
B-n45-k5	751	755	0.53	754	0.00	751	0.00	—	—	751	0.00
B-n50-k7	741	766	3.37	741	0.00	741	0.00	—	—	741	0.00
B-n52-k7	747	—	—	747	0.00	749	0.27	—	—	748	0.13
P-n16-k8	450	451	0.22	450	0.00	450	0.00	450	0.00	450	0.00
P-n19-k2	212	213	0.47	—	—	212	0.00	212	0.00	212	0.00
P-n20-k2	216	217	0.46	216	0.00	216	0.00	216	0.00	216	0.00
P-n22-k2	216	218	0.93	216	0.00	216	0.00	216	0.00	216	0.00
P-n23-k8	529	531	0.38	529	0.00	529	0.00	529	0.00	534	0.90
P-n40-k5	458	508	10.92	458	0.00	458	0.00	458	0.00	458	0.00
P-n45-k5	510	563	10.39	510	0.00	510	0.00	510	0.00	510	0.00
P-n50-k7	554	—	—	554	0.00	555	0.18	554	0.00	557	0.54

下载: 导出CSV

表 2 随机法和贪心法对比

Table 2. Comparison between random and greedy methods

算例	随机法	贪心法
A-n32-k5	1.26	0.19
A-n34-k5	1.12	0.16
A-n45-k7	0.99	0.17
A-n54-k7	1.44	0.20
A-n61-k9	1.61	0.26
A-n65-k9	1.85	0.23

下载: 导出CSV

表 3 IDDE算法与DE算法对比

Table 3. Comparison between IDDE and DE algorithms

算例	DE	IDDE
A-n32-k5	0.19	0.10
A-n34-k5	0.15	0.04
A-n45-k7	0.19	0.05
A-n54-k7	0.22	0.06
A-n61-k9	0.25	0.09
A-n65-k9	0.23	0.10

下载: 导出CSV

参考文献(14)

[1]	张景玲, 冯勤炳, 赵燕伟, 等. 基于强化学习的超启发算法求解有容量车辆路径问题[J] . 计算机集成制造系统,2020,26(4):1118 − 1129.
[2]	SOUZA I P, BOERES M C S, MORAES R E N. A robust algorithm based on differential evolution with local search for the capacitated vehicle routing problem[J] . Swarm and Evolutionary Computation,2023,77:101245. doi: 10.1016/j.swevo.2023.101245
[3]	李珺, 郝丽艳, 何奕涛, 等. 求解带时间窗车辆路径优化问题的改进细菌觅食算法[J] . 计算机工程,2021,47(11):44 − 53.
[4]	BOUZID M C, HADDADENE H A, SALHI S. An integration of Lagrangian split and VNS: The case of the capacitated vehicle routing problem[J] . Computers & Operations Research,2017,78:513 − 525.
[5]	贺智明, 郑丽, 梁文. 基于自适应动态搜索蚁群算法的车辆路径规划[J] . 计算机工程与设计, 2021, 42(2): 543 − 551.
[6]	汪海, 刘升, 赵齐辉. 基于差分进化的水波优化算法[J] . 上海工程技术大学学报,2018,32(3):261 − 266. doi: 10.3969/j.issn.1009-444X.2018.03.012
[7]	TEOH B E, PONNAMBALAM S G, KANAGARAJ G. Differential evolution algorithm with local search for capacitated vehicle routing problem[J] . International Journal of Bio-Inspired Computation,2015,7(5):321 − 342. doi: 10.1504/IJBIC.2015.072260
[8]	SONG L, DONG Y. An improved differential evolution algorithm with local search for capacitated vehicle routing problem[C] //Proceedings of 2018 tenth International Conference on Advanced Computational Intelligence (ICACI). Xiamen: IEEE, 2018.
[9]	林剑, 叶璟轩, 刘雯雯, 等. 求解带容量约束车辆路径问题的多模态差分进化算法[J] . 计算机应用,2023,43(7):2248 − 2254.
[10]	AHMED Z H. Adaptive sequential constructive crossover operator in a genetic algorithm for solving the traveling salesman problem[J] . International Journal of Advanced Computer Science and Applications, 2020, 11(2):943 − 958.
[11]	TSAI C H, LIN Y D, YANG C H, et al. A biogeography-based optimization with a greedy randomized adaptive search procedure and the 2-opt algorithm for the traveling salesman problem[J] . Sustainability,2023,15(6):5111. doi: 10.3390/su15065111
[12]	WANG J, SHANG S, JING H, et al. A novel multistrategy-based differential evolution algorithm and its application[J] . Electronics,2022,11(21):3476. doi: 10.3390/electronics11213476
[13]	夏小云, 庄鹤林, 杨火根, 等. 自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题[J] . 计算机集成制造系统,2022,28(11):3545 − 3557.
[14]	黄戈文, 蔡延光, 戚远航, 等. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J] . 电子学报,2019,47(12):2602 − 2610.