A Hybrid Genetic Search Algorithm for Capacitated Electric Vehicle Routing Problem

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

Abstract

Abstract:

The capacitated electric vehicle routing problem (CEVRP) is an NP-hard combinatorial optimization problem in logistics distribution, aiming to minimize the total delivery distance of electric vehicles while satisfying carrying capacity and battery charge constraints. A hybrid genetic search algorithm is proposed to solve CEVRP by decomposing it into two subproblems: capacitated vehicle routing problem (CVRP) and fixed-route vehicle charging problem (FRVCP). A coding scheme with a two-layer chromosome structure is designed to represent the decision variables of these two subproblems. A Split operation is employed to generate vehicle routes for solving CVRP, and five neighborhood search operators, including Relocate, 2-Opt, 2-Opt*, SWAP, and SWAP*, are adopted to perform local optimization on the routes. To solve the FRVCP, a backtracking-based charging strategy is proposed to insert the appropriate charging station number into the routes. The proposed algorithm is compared with five methods on CEVRP benchmark instances. Experimental results show that the proposed algorithm can find better solutions than the other methods in most instances and is especially suitable for solving large-scale CEVRP.

Key words: electric vehicle routing problem, combinatorial optimization, hybrid genetic search, charging strategy, neighborhood search

CLC Number:

TP391.9

Jin Dongyao, Liu Min, Zhu Yena, Zhao Yijiang. A Hybrid Genetic Search Algorithm for Capacitated Electric Vehicle Routing Problem[J]. Journal of System Simulation, 2024, 36(11): 2528-2541.

Figures/Tables 11

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Table 2

Table 3

Fig. 5

Fig. 6

Fig. 7

Fig. 8

References 31

1	Montoya-Torres Jairo R, Julián López Franco, Santiago Nieto Isaza, et al. A Literature Review on the Vehicle Routing Problem with Multiple Depots[J]. Computers & Industrial Engineering, 2015, 79: 115-129.
2	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.
3	Wang Jiahai, Weng Taiyao, Zhang Qingfu. A Two-stage Multiobjective Evolutionary Algorithm for Multiobjective Multidepot Vehicle Routing Problem with Time Windows[J]. IEEE Transactions on Cybernetics, 2019, 49(7): 2467-2478.
4	Koç Çağrı, Laporte Gilbert, Tükenmez İlknur. A Review of Vehicle Routing with Simultaneous Pickup and Delivery[J]. Computers & Operations Research, 2020, 122: 104987.
5	Tan Fei, Chai Zhengyi, Li Yalun. Multi-objective Evolutionary Algorithm for Vehicle Routing Problem with Time Window Under Uncertainty[J]. Evolutionary Intelligence, 2023, 16(2): 493-508.
6	巫威眺, 王殿雷, 马昌喜. 液化天然气库存路径问题建模与算法[J]. 中国公路学报, 2022, 35(11): 252-270.
	Wu Weitiao, Wang Dianlei, Ma Changxi. Model and Algorithm for Inventory Routing Problem of Liquified Natural Gas[J]. China Journal of Highway and Transport, 2022, 35(11): 252-270.
7	郭戈, 张振琳. 电动车辆路径优化研究与进展[J]. 控制与决策, 2018, 33(10): 1729-1739.
	Guo Ge, Zhang Zhenlin. Status and Development of Electric Vehicle Routing Optimization[J]. Control and Decision, 2018, 33(10): 1729-1739.
8	Jia Yahui, Mei Yi, Zhang Mengjie. A Bilevel Ant Colony Optimization Algorithm for Capacitated Electric Vehicle Routing Problem[J]. IEEE Transactions on Cybernetics, 2022, 52(10): 10855-10868.
9	Mavrovouniotis Michalis, Menelaou Charalambos, Timotheou Stelios, et al. Benchmark Set for the IEEE WCCI-2020 Competition on Evolutionary Computation for the Electric Vehicle Routing Problem[EB/OL]. (2020-03-18) [2023-01-16]. .
10	Schneider Michael, Stenger Andreas, Goeke Dominik. The Electric Vehicle-routing Problem with Time Windows and Recharging Stations[J]. Transportation Science, 2014, 48(4): 500-520.
11	Yang Senyan, Ning Lianju, Tong Lu, et al. Optimizing Electric Vehicle Routing Problems with Mixed Backhauls and Recharging Strategies in Multi-dimensional Representation Network[J]. Expert Systems with Applications, 2021, 176: 114804.
12	Xiao Yiyong, Zhang Yue, Kaku Ikou, et al. Electric Vehicle Routing Problem: A Systematic Review and a New Comprehensive Model with Nonlinear Energy Recharging and Consumption[J]. Renewable and Sustainable Energy Reviews, 2021, 151: 111567.
13	Lee Chungmok. An Exact Algorithm for the Electric-vehicle Routing Problem with Nonlinear Charging Time[J]. Journal of the Operational Research Society, 2021, 72(7): 1461-1485.
14	Montoya Alejandro, Guéret Christelle, Jorge E Mendoza, et al. The Electric Vehicle Routing Problem with Nonlinear Charging Function[J]. Transportation Research Part B: Methodological, 2017, 103: 87-110.
15	黄建华, 刘方翔. 动态负载下电动汽车充电策略及路径优化问题[J]. 计算机集成制造系统, 2023, 29(11): 3909-3921.
	Huang Jianhua, Liu Fangxiang. Charging Strategy and Routing Optimization of Electric Vehicles Under Dynamic Load[J]. Computer Integrated Manufacturing Systems, 2023, 29(11): 3909-3921.
16	杨珺, 冯鹏祥, 孙昊, 等. 电动汽车物流配送系统的换电站选址与路径优化问题研究[J]. 中国管理科学, 2015, 23(9): 87-96.
	Yang Jun, Feng Pengxiang, Sun Hao, et al. Battery Exchange Station Location and Vehicle Routing Problem in Electric Vehicles Distribution System[J]. Chinese Journal of Management Science, 2015, 23(9): 87-96.
17	李得成, 陈彦如, 张宗成. 基于分支定价算法的电动车与燃油车混合车辆路径问题研究[J]. 系统工程理论与实践, 2021, 41(4): 995-1009.
	Li Decheng, Chen Yanru, Zhang Zongcheng. A Branch-and-price Algorithm for Electric Vehicle Routing Problem with Time Windows and Mixed Fleet[J]. Systems Engineering-Theory & Practice, 2021, 41(4): 995-1009.
18	Froger Aurélien, Jabali Ola, Mendoza J E, et al. The Electric Vehicle Routing Problem with Capacitated Charging Stations[J]. Transportation Science, 2022, 56(2): 460-482.
19	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
	Wang Weiquan, Ding Ding, Cao Shuyan. Hybrid Variable Neighborhood Search Algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem[J]. Journal of System Simulation, 2022, 34(4): 910-919.
20	Guo Zhenfeng, Li Yang, Jiang Xiaodan, et al. The Electric Vehicle Routing Problem with Time Windows Using Genetic Algorithm[C]//2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC). Piscataway: IEEE, 2017: 635-639.
21	Lin Bo, Ghaddar Bissan, Nathwani Jatin. Deep Reinforcement Learning for the Electric Vehicle Routing Problem with Time Windows[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(8): 11528-11538.
22	Kozák Viktor, Woller David, Vávra Václav, et al. Initial Solution Constructors for Capacitated Green Vehicle Routing Problem[C]//Modelling and Simulation for Autonomous Systems. Cham: Springer International Publishing, 2021: 250-268.
23	Woller David, Kozák Viktor, Kulich Miroslav. The GRASP Metaheuristic for the Electric Vehicle Routing Problem[C]//Modelling and Simulation for Autonomous Systems. Cham: Springer International Publishing, 2021: 189-205.
24	Vu Quoc Hien, Tran Cong Dao, Huynh Thi Thanh Binh. A Greedy Search Based Evolutionary Algorithm for Electric Vehicle Routing Problem[J]. Applied Intelligence, 2023, 53(3): 2908-2922.
25	Vidal Thibaut. Hybrid Genetic Search for the CVRP: Open-source Implementation and SWAP* Neighborhood[J]. Computers & Operations Research, 2022, 140: 105643.
26	Uchoa Eduardo. VRPTW Competition Updates[EB/OL]. (2022-04-08) [2023-01-31]. .
27	Erdoğan Sevgi, Miller-Hooks E. A Green Vehicle Routing Problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(1): 100-114.
28	Vidal Thibaut. Technical Note: Split Algorithm in O(n) for the Capacitated Vehicle Routing Problem[J]. Computers & Operations Research, 2016, 69: 40-47.
29	Vidal Thibaut, Teodor Gabriel Crainic, Gendreau Michel, et al. A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems[J]. Operations Research, 2012, 60(3): 611-624.
30	Prins Christian. A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem[J]. Computers & Operations Research, 2004, 31(12): 1985-2002.
31	Mavrovouniotis. CEC-12 Competition on Electric Vehicle Routing Problem[EB/OL]. [2023-01-28]. .

名称	客户数	配送中心数	充电站数	路径数
E22	21	1	8	4
E23	22	1	9	3
E30	29	1	6	4
E33	32	1	6	4
E51	50	1	9	5
E76	75	1	9	7
E101	100	1	9	8
X143	142	1	4	7
X214	213	1	9	11
X351	350	1	35	40
X459	458	1	20	26
X573	572	1	6	30
X685	684	1	25	75
X749	748	1	30	98
X819	818	1	25	171
X916	915	1	9	207
X1001	1 000	1	9	43

实例	指标	BHGS	VNS	SA	GA	BACO	CPLEX
E22	最小值	385.38	384.67	384.67	384.67	384.67	384.67
	平均值	385.38	384.67	384.67	384.67	384.67	384.67
	标准差	0	0	0	0	0	0
E23	最小值	571.94	571.94	571.94	571.94	571.94	571.94
	平均值	571.94	571.94	571.94	571.94	571.94	571.94
	标准差	0	0	0	0	0	0
E30	最小值	509.47	509.47	509.47	509.47	509.47	509.47
	平均值	509.47	509.47	509.47	509.47	509.47	509.47
	标准差	0	0	0	0	0	0
E33	最小值	840.57	840.14	840.57	844.25	845.70	849.87
	平均值	840.57	840.43	854.07	845.62	846.16	878.51
	标准差	0	1.18	12.80	0.92	0.38	22.24
E51	最小值	529.90	529.90	533.66	529.90	533.11	568.45
	平均值	529.90	543.26	533.66	542.08	540.17	638.24
	标准差	0.01	3.52	0	8.57	5.27	69.22
E76	最小值	693.23	692.64	701.03	697.27	710.97	813.10
	平均值	693.31	697.89	712.17	717.30	726.03	845.36
	标准差	0.34	3.09	5.78	9.58	5.31	30.06
E101	最小值	841.94	839.29	845.84	852.69	890.72	994.00
	平均值	842.03	853.34	852.48	872.69	900.73	1 079.79
	标准差	0.37	4.73	3.44	9.58	5.32	84.07

实例	指标	BHGS	VNS	SA	GA	BACO
X143	最小值	15 825.17	16 028.05	16 610.37	16 488.60	16 926.80
	平均值	15 873.11	16 459.31	17 188.90	16 911.50	17 103.80
	标准差	88.36	242.59	170.44	282.30	95.69
X214	最小值	11 059.03	11 323.56	11 404.44	11 762.07	12 163.20
	平均值	11 105.29	11 482.20	11 680.35	12 007.06	12 256.78
	标准差	80.49	76.14	116.47	156.69	26.19
X351	最小值	27 299.13	27 064.88	27 222.96	28 008.09	28 295.20
	平均值	27 367.90	27 217.77	27 498.03	28 336.07	28 485.46
	标准差	187.66	86.20	155.62	205.29	82.06
X459	最小值	24 915.02	25 370.08	25 809.47	26 048.21	27 192.50
	平均值	24 929.44	25 582.27	27 222.96	26 345.12	27 349.70
	标准差	62.89	106.89	157.97	185.14	54.41
X573	最小值	52 182.56	52 181.51	51 929.24	54 189.62	55 815.10
	平均值	52 251.05	52 548.09	52 793.66	55 327.62	56 381.06
	标准差	68.54	278.85	577.24	548.05	206.64
X685	最小值	70 696.61	71 345,40	72 549.90	73 925.56	77 927.20
	平均值	71 308.51	71 770.57	73 124.98	74 508.03	78 040.06
	标准差	214.25	197.08	320.07	409.43	25.89
X749	最小值	79 517.82	81 002.01	81 392.78	84 034.73	85 360.10
	平均值	80 027.13	81 327.39	81 848.13	84 759.79	85 658.66
	标准差	461.93	176.19	275.26	376.10	126.39
X819	最小值	164 021.01	164 289.95	165 069.77	170 965.68	173 295.04
	平均值	164 165.75	164 926.41	165 895.78	172 410.12	173 747.05
	标准差	119.42	318.62	403.70	568.58	264.70
X916	最小值	340 476.03	341 649.91	342 796.88	357 391.51	358 867.01
	平均值	340 692.75	342 460.70	343 533.85	360 269.94	360 690.55
	标准差	240.88	510.66	556.98	229.19	643.09
X1001	最小值	74 867.60	77 476.36	78 053.86	78 832.90	80 523.20
	平均值	75 582.91	77 920.52	78 593.50	79 163.34	80 523.19
	标准差	766.48	234.73	306.27	229.19	0.00

[1]	Li Gaoyang, Li Xiangfeng, Zhao Kang, Jin Yuchao, Yi Zhidong, Zuo Dunwen. Three-Dimensional Path Planning of UAV Based on All Particles Driving Wild Horse Optimizer Algorithm [J]. Journal of System Simulation, 2024, 36(3): 595-607.
[2]	Xu Yigang, Chen Yong, Wang Chen, Peng Yunxian. Improving NSGA-III Algorithm for Solving High-dimensional Many-objective Green Flexible Job Shop Scheduling Problem [J]. Journal of System Simulation, 2024, 36(10): 2314-2329.
[3]	Tengfei Zhang, Rong Hu, Bin Qian, Lü Yang. Learning Variable Neighborhood Search Algorithm for Transportation-assembly Collaborative Optimization Problem [J]. Journal of System Simulation, 2023, 35(6): 1260-1277.
[4]	Jiaying Yu, Hongli Zhang, Yingchao Dong. Research on No-Wait Flow Shop Scheduling Based on Discrete State Transition Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1034-1045.
[5]	Kaiqing Zhang, Qichun Ji. Research on Multi-depot Half-open Vehicle Routing Problem with Time-varying Speed [J]. Journal of System Simulation, 2022, 34(4): 836-846.
[6]	Weiquan Wang, Ding Ding, Shuyan Cao. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem [J]. Journal of System Simulation, 2022, 34(4): 910-919.
[7]	Weiquan Wang, Ding Ding, Linsha Yan. Path-Based Model for the Heterogeneous-Fleet Electric Vehicle Routing Problem with Partial Linear Recharging [J]. Journal of System Simulation, 2022, 34(3): 614-623.
[8]	Hu Rong, Chen Wenbo, Qian Bin, Guo Ning, Xiang Fenghong. Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem [J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
[9]	Chen Kui, Bi Li. Research on FJSP of Improved Particle Swarm Optimization Algorithm Considering Transportation Time [J]. Journal of System Simulation, 2021, 33(4): 845-853.
[10]	Wang Xiaohan, Zhang Lin, Ren Lei, Xie Kunyu, Wang Kunyu, Ye Fei, Chen Zhen. Brief Review on Applying Reinforcement Learning to Job Shop Scheduling Problems [J]. Journal of System Simulation, 2021, 33(12): 2782-2791.
[11]	Cai Min, Wang Yan, Ji Zhicheng. Research on MOFFJSP Based on Multi-strategy Fusion Quantum Particle Swarm Optimization [J]. Journal of System Simulation, 2021, 33(11): 2615-2626.
[12]	Li Zhenping, Zhao Yuwei, Zhang Yuwei, Xing Lining, Ren Teng. Joint Distribution Location-routing Problem and Large Neighborhood Search Algorithm [J]. Journal of System Simulation, 2021, 33(10): 2518-2531.
[13]	Sun Can, Zhou Xinyu, Wang Mingwen. A Multi-strategy Differential Evolution Algorithm Combined with Neighborhood Search [J]. Journal of System Simulation, 2020, 32(6): 1071-1084.
[14]	Xie Danlan, Guo Di, Ji Yuan, Gao Zhipeng. Simulation Research on Optimization of AGV Charging Strategy for Automated Terminal [J]. Journal of System Simulation, 2020, 32(10): 1927-1935.
[15]	Dong Ze, Ma Ning. Differential Evolution Quantum Particle Swarm Optimization for Parameter Estimation of Fractional-order Chaotic System [J]. Journal of System Simulation, 2019, 31(8): 1664-1673.