基于动态缩减机制的多策略单亲遗传算法求解CVRP问题

doi:10.16182/j.issn1004731x.joss.23-0662

摘要/Abstract

摘要：

针对传统遗传算法求解带容量约束的车辆路径问题(CVRP)时存在易早熟、收敛速度慢、精度低等问题，提出一种基于动态缩减机制的多策略单亲遗传算法。基于同类个体实现对寻优空间的划分，采用模拟退火准则对最低类别子空间进行淘汰或更新，构成寻优空间的缩减和移动机制；基于单亲遗传算法，综合设计了组内、组间、整体搜索，以及扰动与跳跃的多种遗传进化策略；为适应度函数设计了基于个体发展、种群进化、整体收敛3个罚因子的自适应罚函数分量，对不可行解作出更有效惩罚。通过对3组CVRP问题实例进行仿真实验分析，结果表明：该算法在种群质量、全局与局部寻优能力、求解精度和收敛速度等方面均得到改善和提升。

关键词: 车辆路径问题, 遗传算法, 动态缩减机制, 自适应罚函数, 多策略遗传进化

Abstract:

Aiming at the problems of premature, slow convergence and low accuracy of traditional genetic algorithm in solving capacitated vehicle routing problem,a multi-strategy partheno-genetic algorithm based on dynamic reduction mechanism is proposed. The algorithm divides the optimization space based on similar individuals, and uses simulated annealing criterion to eliminate or update the lowest category subspace, which constitutes the reduction and movement mechanism of the optimization space.Based on partheno-genetic algorithm,a variety of genetic evolution strategies including intra-group, inter-group, global search, disturbance and jump strategy are designedBased on the three penalty factors of individual development, population evolution and overall convergence, the adaptive penalty function component is designed for the fitness function, which is more effective to punish the infeasible solution.Through the simulation experiments on three groups of CVRP problems, the results show that DRM-MSPGA algorithm is improved in population quality, global and local optimization ability, solution accuracy and convergence speed.

Key words: vehicle routing problem, genetic algorithm, dynamic reduction mechanism, adaptive penalty function, multi-strategy genetic evolution

中图分类号:

TP391

陈加俊,谭代伦 . 基于动态缩减机制的多策略单亲遗传算法求解CVRP问题[J]. 系统仿真学报, 2024, 36(10): 2396-2412.

Chen Jiajun,Tan Dailun . Multi-strategy Partheno-genetic Algorithm Based on Dynamic Reduction Mechanism for Solving CVRP Problem[J]. Journal of System Simulation, 2024, 36(10): 2396-2412.

图/表 14

图1

图2

图3

表1

罚函数类别

罚函数类型	公式
自适应罚函数 $F$	$F = 1 / e a (r - b) ⋅ δ ⋅ (1 + (f - f o p t) / f) ⋅ t / G$
自适应罚函数 $F 1$	$F 1 = δ ⋅ (1 + (f - f o p t) / f) ⋅ t / G$
自适应罚函数 $F 2$	$F 2 = 1 / e a (r - b) ⋅ t / G$
传统罚函数 $F 3$	$F 3 = 100$

表1

表2

罚因子有效性测试 (%)

罚函数类型		A-n33-k5	A-n33-k6	A-n37-k6	A-n55-k9
$F$	P_PFS	73.91	57.70	42.87	40.64
	I_SCR	140	96.94	70.75	90.68
	I_SCRE	4.45	4.62	4.42	5.81
$F 1$	P_PFS	17.23	15.79	2.57	2.12
$F 2$	P_PFS	58.34	46.36	37.10	30.34
	I_SCR	129.28	88.50	68.75	72.20
	I_SCRE	4.09	4.08	3.95	3.72

表2

表3

自适应罚函数性能测试

CVRP		A-n33-k5(661)	A-n33-k6(742)	A-n37-k6(949)	A-n55-k9 (1073)
$T F$	Best	661	742	967	1 095
	AVG	664.33	749.17	974.92	1 109.2
	$λ B D R$ /%	0	0	1.91	2.07
	$λ M D R$ /%	0.50	0.96	2.35	3.37
	NC	277.95	222.95	442.8	499.05
$F$	Best	661	742	949	1 074
	AVG	662.70	742.15	960.10	1 080.44
	$λ B D R$ /%	0	0	0	0.18
	$λ M D R$ /%	0.26	0.02	1.16	0.69
	NC	151.35	103.40	165.65	260.8

表3

表4

缩减周期参数实验

$Ω b e s t$	周期	Max	Min	Mean	WRT	ORT
A-n33-k5 (4)	T=50	3	2	2.45	9	11
	T=100	2	1	1.85	0	17
	T=200	2	1	1.05	0	1
P-n45-k5 (7)	T=50	5	3	4.17	9	3
	T=100	4	2	3.25	0	8
	T=200	3	1	2.10	0	0

表4

表5

动态缩减机制有效性分析

分析方法	子空间 $Ω i$ 类别	迭代次数
分析方法	子空间 $Ω i$ 类别	200	400	600	800	1 000
使用DRM	1	929/47	0/0	0/0	0/0	0/0
	2	899/271	883/221	883/33	0/0	0/0
	3	920/24	886/72	886/6	886/51	0/0
	4	927/49	911/30	830/56	830/39	828/84
	5	954/2	912/29	828/122	828/57	827/57
	6	944/1	921/22	820/176	820/255	820/248
	7	910/3	910/7	8733/27	868/16	865/6
不使用DRM	1	949/50	917/168	899/119	899/129	899/47
	2	945/50	943/48	931/27	931/29	931/46
	3	938/42	938/28	938/48	938/39	938/55
	4	915/21	915/13	915/20	915/20	915/34
	5	897/38	897/8	896/12	896/12	896/12
	6	897/19	897/8	897/2	897/8	897/12
	7	863/163	856/144	854/190	854/178	854/198

表5

表6

搜索策略有效性测试

Instance (opt)	PGA			IPGA
Instance (opt)	Best	$λ B D R$ /%	$λ M D R$ /%	Best	$λ B D R$ /%	$λ M D R$ /%
A-n33-k6 (742)	824	9.95	15.86	742	0	0.17
A-n38-k5 (730)	796	9.04	23.96	730	0	0.96
P-n22-k2 (216)	216	0	5.93	216	0	0.06
P-n40-k5 (458)	501	8.58	22.43	458	0	1.25

表6

图4

表7

SetA算例测试结果

案例	OPT	CVRP-FA			ACGWOA			AS+VTPSO			DRM-MSPGA
案例	OPT	Best	$λ B D R$ /%	$λ M D R$ /%	Best	$λ B D R$ /%	$λ M D R$ /%	Best	$λ B D R$ /%	$λ M D R$ /%	Best	AVG	$λ B D R$ /%	$λ M D R$ /%
平均			0.12	0.38		0.03	0.98		10.02	\			0.08	0.54
A-n32-k5	784	796	1.53	1.77	784	0	0.43	882	12.50	\	784	788.30	0	0.51
A-n33-k5	661	661	0	0	661	0	0.08	698	5.60	\	661	661.00	0	0
A-n33-k6	742	742	0	0.09	742	0	0.09	751	1.21	\	742	742.15	0	0.02
A-n34-k5	778	778	0	0	778	0	0.62	785	0.90	\	778	778.00	0	0
A-n36-k5	799	799	0	0.65	799	0	0.94	881	10.26	\	799	810.00	0	1.36
A-n37-k5	669	669	0	0	669	0	0.54	754	12.71	\	669	669.50	0	0.07
A-n37-k6	949	949	0	0.68	949	0	1.20	1 112	17.18	\	949	960.10	0	1.16
A-n38-k5	730	730	0	0.10	730	0	0.50	813	11.37	\	730	733.10	0	0.42
A-n39-k5	822	822	0	0	822	0	0.49	877	6.69	\	822	823.00	0	0.12
A-n39-k6	831	831	0	0.43	833	0.24	0.69	972	16.97	\	832	834.50	0.12	0.42
A-n44-k6	937	937	0	0	937	0	1.26	1 056	12.70	\	937	941.90	0	0.52
A-n46-k7	914	914	0	0	914	0	1.12	975	6.67	\	914	916.15	0	0.23
A-n55-k9	1 073	1 073	0	0	1 073	0	2.40	1 190	10.90	\	1 074	1 080.44	0.09	0.69
A-n63-k10	1 314	1 314	0	1.45	1 323	0	2.36	1 477	12.40	\	1 322	1 337.05	0.61	1.72
A-n65-k9	1 174	1 178	0.34	0.57	1 178	0.34	2.05	1 317	12.18	\	1 178	1 184.20	0.34	0.86

表7

表8

SetP算例测试结果

案例	OPT	CVRP-FA			ACGWOA			AS+VTPSO			DRM-MSPGA
案例	OPT	Best	$λ B D R$ /%	$λ M D R$ /%	Best	$λ B D R$ /%	$λ M D R$ /%	Best	$λ B D R$ /%	$λ M D R$ /%	Best	AVG	$λ B D R$ /%	$λ M D R$ /%
平均			0.05	0.43		0.21	1.19		6.86	\			0.14	0.68
P-n16-k8	450	450	0	0	450	0	0	549	18.03	\	450	450.00	0	0
P-n19-k2	212	212	0	0	212	0	0	246	13.82	\	212	212.00	0	0
P-n20-k2	216	216	0	0	216	0	0	249	13.25	\	216	216.00	0	0
P-n21-k2	211	211	0	0	211	0	0	211	0	\	211	211.00	0	0
P-n22-k2	216	216	0	0	216	0	0	216	0	\	216	216.00	0	0
P-n40-k5	458	458	0	0.41	458	0	0.79	483	5.18	\	458	458.00	0	0
P-n45-k5	510	510	0	0	510	0	0.74	524	2.67	\	510	510.00	0	0
P-n50-k7	554	554	0	0.54	554	0	1.76	583	4.97	\	556	561.30	0.36	1.30
P-n50-k10	696	697	0.14	0.98	704	1.15	3.25	783	11.11	\	700	706.90	0.57	1.54
P-n60-k10	744	749	0.67	1.14	753	1.22	3.16	830	10.36	\	747	757.10	0.40	1.73
P-n65-k10	792	792	0	0.91	\	\	\	859	7.80	\	796	806.32	0.50	1.78
P-n76-k4	593	593	0	0.97	593	0	1.80	612	3.10	\	593	600.70	0	1.28
P-n76-k5	627	627	0	0.59	628	0.16	2.89	647	3.09	\	628	633.85	0.16	1.08
P-n101-k4	681	681	0	0.54	\	\	\	699	2.58	\	681	683.55	0	0.37

表8

图5

图6

参考文献 26

1	Dantzig G B, Ramser J H. The Truck Dispatching Problem[J]. Management Science, 1959, 6(1): 80-91.
2	Liu Shaokun. Research on Logistics Distribution Path Planning Based on Genetic Algorithm[J]. Journal of Physics: Conference Series, 2021, 2083(3): 032013.
3	周成昊, 吕博轩, 周翰宇, 等. 以商圈为中心的O2O动态外卖配送路径优化模型与算法[J]. 运筹学学报, 2022, 26(3): 17-30.
	Zhou Chenghao, Boxuan Lü, Zhou Hanyu, et al. Optimization Model and Algorithm for Online to Offline Dynamic Take-out Delivery Routing Problem Centered on Business Districts[J]. Operations Research Transactions, 2022, 26(3): 17-30.
4	Sciortino Monique, Lewis Rhyd, Thompson Jonathan. A School Bus Routing Heuristic Algorithm Allowing Heterogeneous Fleets and Bus Stop Selection[J]. SN Computer Science, 2022, 4(1): 74.
5	向婷, 李妍峰. 基于成本和加班时长的双目标家庭护理人员调度问题[J]. 运筹与管理, 2021, 30(8): 233-239.
	Xiang Ting, Li Yanfeng. A Bi-objective Home Health Care Scheduling Problem: Based on Costs and Overtime[J]. Operations Research and Management Science, 2021, 30(8): 233-239.
6	陈爱玲, 杨根科, 吴智铭. 轧制计划的优化模型及其算法的应用研究[J]. 系统仿真学报, 2006, 18(9): 2484-2487, 2562.
	Chen Ailing, Yang Genke, Wu Zhiming. Rolling Plan Optimization Model and Algorithm for Hot Rolling Processes[J]. Journal of System Simulation, 2006, 18(9): 2484-2487, 2562.
7	Laporte G, Nobert Y. A Branch and Bound Algorithm for the Capacitated Vehicle Routing Problem[J]. Operations-Research-Spektrum, 1983, 5(2): 77-85.
8	Laporte G. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms[J]. European Journal of Operational Research, 1992, 59(3): 345-358.
9	Gao Yuelin, Wu Hongguang, Wang Wanting. A Hybrid Ant Colony Optimization with Fireworks Algorithm to Solve Capacitated Vehicle Routing Problem[J]. Applied Intelligence, 2023, 53(6): 7326-7342.
10	Sbai Ines, Limam Olfa, Krichen Saoussen. An Effective Genetic Algorithm for Solving the Capacitated Vehicle Routing Problem with Two-dimensional Loading Constraint[J]. International Journal of Computational Intelligence Studies, 2020, 9(1/2): 85-106.
11	Israel Pereira Souza, Maria Claudia Silva Boeres, Renato Elias Nunes Moraes. A Robust Algorithm Based on Differential Evolution with Local Search for the Capacitated Vehicle Routing Problem[J]. Swarm and Evolutionary Computation, 2023, 77: 101245.
12	Liepins G E, Hilliard M R. Genetic Algorithms: Foundations and Applications[J]. Annals of Operations Research, 1989, 21(1/4): 31-58.
13	Lin Na, Shi Yanjun, Zhang Tongliang, et al. An Effective Order-aware Hybrid Genetic Algorithm for Capacitated Vehicle Routing Problems in Internet of Things[J]. IEEE Access, 2019, 7: 86102-86114.
14	Prins Christian. A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem[J]. Computers & Operations Research, 2004, 31(12): 1985-2002.
15	Sbai Ines, Krichen Saoussen, Limam Olfa. Two Meta-heuristics for Solving the Capacitated Vehicle Routing Problem: The Case of the Tunisian Post Office[J]. Operational Research, 2022, 22(1): 507-549.
16	Erfan Babaee Tirkolaee, Ali Asghar Rahmani Hosseinabadi, Soltani Mehdi, 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.
17	李茂军, 童调生. 用单亲遗传算法求解有序组合优化问题[J]. 系统工程与电子技术, 1998, (10): 59-62.
18	Shi Chenghua, Li Tonglei, Zhao Fei, et al. An Improved Partheno-genetic Algorithm for the Vehicle Routing Problem with Dynamic Demands and Time Windows[J]. ICIC Express Letters, 2016, 10(4): 849-855.
19	Zhou Honglu, Song Mingli, Pedrycz W. A Comparative Study of Improved GA and PSO in Solving Multiple Traveling Salesmen Problem[J]. Applied Soft Computing, 2018, 64: 564-580.
20	杨家平, 黎青松, 周艳梅, 等. 一种车间物料配送路径问题的优化模型及算法[J]. 控制工程, 2017, 24(2): 446-451.
	Yang Jiaping, Li Qingsong, Zhou Yanmei, et al. Optimization Model and Algorithm for the Workshop Material Distribution Routing Problem[J]. Control Engineering of China, 2017, 24(2): 446-451.
21	王海英, 黄强, 李传涛, 等. 图论算法及其MATLAB实现[M]. 北京: 北京航空航天大学出版社, 2010: 88-89.
22	Prins Christian, Lacomme Philippe, Prodhon Caroline. Order-first Split-second Methods for Vehicle Routing Problems: A Review[J]. Transportation Research Part C: Emerging Technologies, 2014, 40: 179-200.
23	陈加俊, 谭代伦. 求解旅行商问题的探索—开发—跳跃策略单亲遗传算法[J]. 计算机应用研究, 2023, 40(5): 1375-1380.
	Chen Jiajun, Tan Dailun. Partheno-genetic Algorithm Based on Explore-develop-jump Strategy for Solving Traveling Salesman Problem[J]. Application Research of Computers, 2023, 40(5): 1375-1380.
24	Altabeeb Asma M, Mohsen Abdulqader M, Ghallab Abdullatif. An Improved Hybrid Firefly Algorithm for Capacitated Vehicle Routing Problem[J]. Applied Soft Computing, 2019, 84: 105728.
25	黄戈文, 蔡延光, 戚远航, 等. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报, 2019, 47(12): 2602-2610.
	Huang Gewen, Cai Yanguang, Qi Yuanhang, et al. Adaptive Genetic Grey Wolf Optimizer Algorithm for Capacitated Vehicle Routing Problem[J]. Acta Electronica Sinica, 2019, 47(12): 2602-2610.
26	Akhand M A H, Zahrul Jannat Peya, Murase Kazuyuki. Capacitated Vehicle Routing Problem Solving Using Adaptive Sweep and Velocity Tentative PSO[J]. International Journal of Advanced Computer Science and Applications, 2017, 8(12): 288-295.

[1]	肖鹏, 谢锋, 倪海鸿, 张敏, 汤志荔, 李霓. 多机任务分配与路径规划协同优化法研究[J]. 系统仿真学报, 2024, 36(5): 1141-1151.
[2]	唐进君, 胡立鹏, 李明洋, 张璇. 基于Kriging遗传算法的高速公路应急车道管控优化[J]. 系统仿真学报, 2024, 36(5): 1165-1178.
[3]	万远鹏, 梁承姬, 王思洪, 王钰. 考虑订单替换的冷链配送-库存联合优化与仿真[J]. 系统仿真学报, 2024, 36(3): 578-594.
[4]	阎世梁, 王银玲, 路丹丹, 潘小琴. 基于深度神经网络的永磁直线电机仿真与优化[J]. 系统仿真学报, 2024, 36(3): 713-725.
[5]	申晓宁, 葛忠佩, 姚铖滨, 宋丽妍, 王玉芳. 基于离散混合蛙跳算法的地震应急物资调度[J]. 系统仿真学报, 2024, 36(1): 97-109.
[6]	张红历, 邓井双. 基于遗传算法的人工人口生成与应用研究[J]. 系统仿真学报, 2023, 35(9): 1965-1974.
[7]	张立, 贺明玲, 尹秋霜, 李宁, 余乐安. 不确定条件下多周期应急物资配送优化研究[J]. 系统仿真学报, 2023, 35(8): 1669-1680.
[8]	吴玉文, 牛智越, 李珍萍. 基于改进遗传算法的货箱机器人拣选路径规划[J]. 系统仿真学报, 2023, 35(5): 1086-1097.
[9]	李志强, 李元龙, 殷来祥, 马向平. 智能无人蜂群作战系统适应性进化模型仿真研究[J]. 系统仿真学报, 2023, 35(4): 878-886.
[10]	张颖钰, 吴立云, 贾胜钛. 带时间窗的多中心半开放式VRPSDP问题研究[J]. 系统仿真学报, 2023, 35(11): 2464-2475.
[11]	陈雪, 胡蓉, 王辉, 李作成, 钱斌, 李熠胥. 学习型蚁群算法求解一类复杂两级车辆路径问题[J]. 系统仿真学报, 2023, 35(11): 2476-2495.
[12]	张虎成, 杨镜宇. 基于GABC算法的作战体系智能优化方法研究[J]. 系统仿真学报, 2023, 35(1): 221-227.
[13]	李楠, 胡蓉, 钱斌, 金怀平, 于乃康. 时间依赖型多时间窗车辆路径问题研究[J]. 系统仿真学报, 2022, 34(8): 1775-1788.
[14]	徐佳, 韩逢庆, 刘奇鑫, 薛晓霞. 一种求解TSP的生物信息启发式遗传算法[J]. 系统仿真学报, 2022, 34(8): 1811-1819.
[15]	胡蓉, 江文, 钱斌, 于乃康. 两阶段优化算法求解绿色装箱车辆路径问题[J]. 系统仿真学报, 2022, 34(7): 1490-1505.