Multi-strategy Partheno-genetic Algorithm Based on Dynamic Reduction Mechanism for Solving CVRP Problem

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

Abstract

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

CLC Number:

TP391

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.

Figures/Tables 14

Fig. 1

Fig. 2

Fig. 3

Table 1

Penalty function categories

罚函数类型	公式
自适应罚函数 $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$

Table 1

Table 2

Validity test of penalty factor

罚函数类型		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

Table 2

Table 3

Adaptive penalty function performance test

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

Table 3

Table 4

Reduced period parameter experiments

$Ω 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

Table 4

Table 5

Effectiveness analysis of dynamic reduction mechanism

分析方法	子空间 $Ω 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

Table 5

Table 6

Search strategy validity test

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

Table 6

Fig. 4

Table 7

Test results for SetA examples

案例	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

Table 7

Table 8

Test results for SetP examples

案例	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

Table 8

Fig. 5

Fig. 6

References 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]	Xiao Peng, Xie Feng, Ni Haihong, Zhang Min, Tang Zhili, Li Ni. Research on Collaborative Optimization Method of Multi-UAV Task Allocation and Path Planning [J]. Journal of System Simulation, 2024, 36(5): 1141-1151.
[2]	Tang Jinjun, Hu Lipeng, Li Mingyang, Zhang Xuan. Optimization of Highway Emergency Lane Control Based on Kriging Genetic Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1165-1178.
[3]	Wan Yuanpeng, Liang Chengji, Wang Sihong, Wang Yu. Joint Distribution-Inventory Optimization and Simulation for Cold Chain Logistics Considering Order Substitution [J]. Journal of System Simulation, 2024, 36(3): 578-594.
[4]	Yan Shiliang, Wang Yinling, Lu Dandan, Pan Xiaoqin. Simulation and Optimization of Permanent Magnet Linear Machine Based on Deep Neural Network [J]. Journal of System Simulation, 2024, 36(3): 713-725.
[5]	Zhuang Helin, Xia Xiaoyun, Li Kangshun, Chen Zefeng, Zhang Xianchao. Research Advances on Electric Vehicle Routing Problem Models and Algorithms [J]. Journal of System Simulation, 2024, 36(2): 320-337.
[6]	Shen Xiaoning, Ge Zhongpei, Yao Chengbin, Song Liyan, Wang Yufang. Emergency Material Scheduling Based on Discrete Shuffled Frog Leaping Algorithm [J]. Journal of System Simulation, 2024, 36(1): 97-109.
[7]	Zhang Hongli, Deng Jingshuang. Research on Artificial Population Generation and Application Based on Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(9): 1965-1974.
[8]	Li Zhang, Mingling He, Qiushuang Yin, Ning Li, Le'an Yu. Research on Period Emergency Supply Distribution Optimization Under Uncertainty [J]. Journal of System Simulation, 2023, 35(8): 1669-1680.
[9]	Yuwen Wu, Zhiyue Niu, Zhenping Li. Picking Path Planning of Container Robots Based on Improved Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1086-1097.
[10]	Hongliang Zhang, Jingru Xu, Bo Tan, Gongjie Xu. Dual Resource Constrained Flexible Job Shop Energy-saving Scheduling Considering Delivery Time [J]. Journal of System Simulation, 2023, 35(4): 734-746.
[11]	Zhiqiang Li, Yuanlong Li, Laixiang Yin, Xiangping Ma. Research on Unmanned Swarm Combat System Adaptive Evolution Model Simulation [J]. Journal of System Simulation, 2023, 35(4): 878-886.
[12]	Zhang Yingyu, Wu Liyun, Jia Shengtai. Multi-depot Half-open Vehicle Routing Problem with Simultaneous Delivery-pickup and Time Windows [J]. Journal of System Simulation, 2023, 35(11): 2464-2475.
[13]	Chen Xue, Hu Rong, Wang Hui, Li Zuocheng, Qian Bin, Li Yixu. Learning-based Ant Colony Optimization Algorithm for Solving a Kind of Complex 2-Echelon Vehicle Routing Problem [J]. Journal of System Simulation, 2023, 35(11): 2476-2495.
[14]	Hucheng Zhang, Jingyu Yang. Research on Intelligent Optimization Method of Combat SoS Based on GABC Algorithm [J]. Journal of System Simulation, 2023, 35(1): 221-227.
[15]	Nan Li, Rong Hu, Bin Qian, Huaiping Jin, Naikang Yu. Research on Time-dependent Vehicle Routing Problem with Multiple Time Windows [J]. Journal of System Simulation, 2022, 34(8): 1775-1788.