Research Advances on Electric Vehicle Routing Problem Models and Algorithms

doi:10.16182/j.issn1004731x.joss.22-1161

Abstract

Abstract:

The development of electric vehicle provides an alternative to conventional fuel vehicles for logistics companies. Using electric vehicles has the merits of less pollution and low noise, but the characteristics of limited cruising range and limited number of charging stations are new challenges. Electric vehicle routing problems(EVRPs) have been widely used in transportation, logistics and other fields, and have received much attention. A comprehensive survey of EVRP and its many variants are presented and the respective backgrounds and applicable conditions are analyzed. The solving approaches of EVRPs are categorized, the strengths and weaknesses of each algorithm are analyzed, and the related practical applications are reviewed. The basic information and some node distribution maps of EVRP benchmark dataset and EVRP with time windows benchmark dataset are given, and the algorithms that have been applied in EVRP benchmark dataset are compared and analyzed. The future development trends of EVRPs is depicted.

Key words: electric vehicle, vehicle routing problem, low carbon, heuristic algorithms, logistics

CLC Number:

TP18

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.

Figures/Tables 12

Fig. 1

Fig. 2

Fig. 3

Table 1

Table 2

Fig. 4

Fig. 5

Fig. 6

Table 3

Table 4

Table 5

Table 6

References 56

1	Schiffer Maximilian, Walther Grit. The Electric Location Routing Problem with Time Windows and Partial Recharging[J]. European Journal of Operational Research, 2017, 260(3): 995-1013.
2	杨涛, 孙晓莉. 气候暖化和"双碳"目标约束下的大城市交通发展策略[J]. 交通与港航, 2021, 8(6): 2-7.
	Yang Tao, Sun Xiaoli. Transportation Development Strategy of Big Cities Under the Constraints of Climate Warming and "Carbon Peaking and Carbon Neutrality" Goal[J]. Communication & Shipping, 2021, 8(6): 2-7.
3	Bunsen T, Cazzola P, Gorner M, et al. Global EV Outlook 2018: Towards Cross-Modal Electrification[C]. International Energy Agency, Paris, France, 2018.
4	刘丽丽, 刘同礼, 金小香. 电动汽车碳排放计算与跟踪评估的探讨[J]. 内燃机与配件, 2022(1): 196-198.
	Liu Lili, Liu Tongli, Jin Xiaoxiang. The Discussion of Calculation Method of Electric Vehicle Carbon Emission and Tracking Evaluation[J]. Internal Combustion Engine & Parts, 2022(1): 196-198.
5	Afroditi Anagnostopoulou, Boile Maria, Theofanis S, et al. Electric Vehicle Routing Problem with Industry Constraints: Trends and Insights for Future Research[J]. Transportation Research Procedia, 2014, 3: 452-459.
6	Dantzig G B, Ramser J H. The Truck Dispatching Problem[J]. Management Science, 1959, 6(1): 80-91.
7	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.
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	Qin Hu, Su Xinxin, Ren Teng, et al. A Review on the Electric Vehicle Routing Problems: Variants and Algorithms[J]. Frontiers of Engineering Management, 2021, 8(3): 370-389.
10	Bard J F, Huang Liu, Dror M, et al. A Branch and Cut Algorithm for the VRP with Satellite Facilities[J]. IIE Transactions, 1998, 30(9): 821-834.
11	Poonthalir G, Nadarajan R. A Fuel Efficient Green Vehicle Routing Problem with varying Speed Constraint (F-GVRP)[J]. Expert Systems with Applications, 2018, 100: 131-144.
12	Yu Yang, Wang Sihan, Wang Junwei, et al. A Branch-and-price Algorithm for the Heterogeneous Fleet Green Vehicle Routing Problem with Time Windows[J]. Transportation Research Part B: Methodological, 2019, 122: 511-527.
13	狄卫民, 杜慧莉, 张鹏阁. 考虑动态拥堵的多车型绿色车辆路径问题优化[J]. 计算机工程与设计, 2021, 42(9): 2614-2620.
	Di Weimin, Du Huili, Zhang Pengge. Optimization of Multi-vehicle Green Vehicle Routing Problem Considering Dynamic Congestion[J]. Computer Engineering and Design, 2021, 42(9): 2614-2620.
14	Lin J, Zhou Wei, Wolfson O. Electric Vehicle Routing Problem[J]. Transportation Research Procedia, 2016, 12: 508-521.
15	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) [2022-09-23]. .
16	Jia Yahui, Mei Yi, Zhang Mengjie. Confidence-Based Ant Colony Optimization for Capacitated Electric Vehicle Routing Problem with Comparison of Different Encoding Schemes[J]. IEEE Transactions on Evolutionary Computation, 2022, 26(6): 1394-1408.
17	齐元豪, 王凯, 付亚平. 基于头脑风暴算法的电动货车路径优化问题[J]. 计算机技术与发展, 2020, 30(4): 74-78.
	Qi Yuanhao, Wang Kai, Fu Yaping. Path Optimization Problem of Electric Freight Car Based on Brainstorming Algorithm[J]. Computer Technology and Development, 2020, 30(4): 74-78.
18	Bruglieri Maurizio, Pezzella Ferdinando, Pisacane Ornella, et al. A Variable Neighborhood Search Branching for the Electric Vehicle Routing Problem with Time Windows[J]. Electronic Notes in Discrete Mathematics, 2015, 47: 221-228.
19	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.
20	Cortés-Murcia David L, Prodhon Caroline, Murat Afsar H. The Electric Vehicle Routing Problem with Time Windows, Partial Recharges and Satellite Customers[J]. Transportation Research Part E: Logistics and Transportation Review, 2019, 130: 184-206.
21	Schneider M, Stenger A, Goeke D. The Electric Vehicle-routing Problem with Time Windows and Recharging Stations[J]. Transportation Science, 2014, 48(4): 500-520.
22	王琪瑛, 李英, 李惠. 带软时间窗的电动车换电站选址路径问题研究[J]. 工业工程与管理, 2019, 24(3): 99-106.
	Wang Qiying, Li Ying, Li Hui. Battery Swap Station Location-routing Problem of Electric Vehicles with Soft Time Windows[J]. Industrial Engineering and Management, 2019, 24(3): 99-106.
23	Montoya Alejandro, Guéret Christelle, Jorge E Mendoza, et al. The Electric Vehicle Routing Problem with Partial charging and Nonlinear Charging Function[D]. University of Angers: LARIS, 2015.
24	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.
25	Keskin Merve, Çatay Bülent. Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows[J]. Transportation Research Part C: Emerging Technologies, 2016, 65: 111-127.
26	Zuo Xiaorong, Zhu Chuan, Huang Changhao, et al. Using AMPL/CPLEX to Model and Solve the Electric Vehicle Routing Problem (EVRP) with Heterogeneous Mixed Fleet[C]//2017 29th Chinese Control and Decision Conference (CCDC). Piscataway, NJ, USA: IEEE, 2017: 4666-4670.
27	Granada-Echeverri Mauricio, Luis Carlos Cubides, Jésus Orlando Bustamante. The Electric Vehicle Routing Problem with Backhauls[J]. International Journal of Industrial Engineering Computations, 2020, 11(1): 131-152.
28	Goeke Dominik, Schneider Michael. Routing a Mixed Fleet of Electric and Conventional Vehicles[J]. European Journal of Operational Research, 2015, 245(1): 81-99.
29	Mancini Simona. The Hybrid Vehicle Routing Problem[J]. Transportation Research Part C: Emerging Technologies, 2017, 78: 1-12.
30	陈其赛, 倪静. 基于同时送取货电动车选址路径问题优化研究[J]. 上海理工大学学报, 2021, 43(5): 515-522.
	Chen Qisai, Ni Jing. Optimization of Location and Routing Problem for Electric Vehicles Based on Simultaneous Delivery and Pickup[J]. Journal of University of Shanghai for Science and Technology, 2021, 43(5): 515-522.
31	Wang Liying, Song Yuanbin. Multiple Charging Station Location-routing Problem with Time Window of Electric Vehicle[J]. Journal of Engineering Science and Technology Review, 2015, 8(5): 190-201.
32	Paz Juan, Granada-Echeverri Mauricio, John Willmer Escobar. The Multi-depot Electric Vehicle Location Routing Problem with Time Windows[J]. International Journal of Industrial Engineering Computations, 2018, 9(1): 123-136.
33	Yang Jun, Sun Hao. Battery Swap Station Location-routing Problem with Capacitated Electric Vehicles[J]. Computers & Operations Research, 2015, 55: 217-232.
34	Almouhanna A, Quintero-Araujo Carlos L, Panadero Javier, et al. The Location Routing Problem Using Electric Vehicles with Constrained Distance[J]. Computers & Operations Research, 2020, 115: 104864.
35	Surendra Reddy Kancharla, Ramadurai Gitakrishnan. Electric Vehicle Routing Problem with Non-linear Charging and Load-dependent Discharging[J]. Expert Systems with Applications, 2020, 160: 113714.
36	Christofides N, Eilon S. An Algorithm for the Vehicle-dispatching Problem[J]. Journal of the Operational Research Society, 1969, 20(3): 309-318.
37	Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research, 1987, 35(2): 254-265.
38	Keskin Merve, Çatay Bülent. A Matheuristic Method for the Electric Vehicle Routing Problem with Time Windows and Fast Chargers[J]. Computers & Operations Research, 2018, 100: 172-188.
39	Keskin Merve, Laporte Gilbert, Çatay Bülent. Electric Vehicle Routing Problem with Time-dependent Waiting Times at Recharging Stations[J]. Computers & Operations Research, 2019, 107: 77-94.
40	Ceselli Alberto, Felipe Ángel, Teresa Ortuño M, et al. A Branch-and-cut-and-price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies[J]. Operations Research Forum, 2021, 2(1): 8.
41	揭婉晨, 杨珺, 杨超. 多车型电动汽车车辆路径问题的分支定价算法研究[J]. 系统工程理论与实践, 2016, 36(7): 1795-1805.
	Wanchen Jie, Yang Jun, Yang Chao. Branch-and-price Algorithm for Heterogeneous Electric Vehicle Routing Problem[J]. Systems Engineering-Theory & Practice, 2016, 36(7): 1795-1805.
42	Wu Zhiguo, Zhang Juliang. A Branch-and-price Algorithm for Two-echelon Electric Vehicle Routing Problem[J]. Complex & Intelligent Systems, 2023, 9(3): 2475-2490.
43	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.
44	Ece Naz Duman, Taş Duygu, Çatay Bülent. Branch-and-price-and-cut Methods for the Electric Vehicle Routing Problem with Time Windows[J]. International Journal of Production Research, 2022, 60(17): 5332-5353.
45	Deng Jiawen, Li Junqing, Li Chengyou, et al. A Hybrid Algorithm for Electric Vehicle Routing Problem with Nonlinear Charging[J]. Journal of Intelligent & Fuzzy Systems, 2021, 40(3): 5383-5402.
46	吴廷映, 孙灏. 考虑载重影响耗电率的电动车车辆路径问题[J]. 控制与决策, 2023, 38(2): 483-491.
	Wu Tingying, Sun Hao. Electric Vehicle Routing Problem with Time Window and Linear Weight-related Discharging[J]. Control and Decision, 2023, 38(2): 483-491.
47	Zhu Yanfei, Lee K Y, Wang Yonghua. Adaptive Elitist Genetic Algorithm with Improved Neighbor Routing Initialization for Electric Vehicle Routing Problems[J]. IEEE Access, 2021, 9: 16661-16671.
48	Mavrovouniotis Michalis, Ellinas Georgios, Polycarpou Marios. Ant Colony Optimization for the Electric Vehicle Routing Problem[C]//2018 IEEE Symposium Series on Computational Intelligence (SSCI). Piscataway, NJ, USA: IEEE, 2018: 1234-1241.
49	张佳蕊. 半开放式燃油车和电动车混合车辆路径优化问题研究[J]. 汽车实用技术, 2022, 47(3): 55-63.
	Zhang Jiarui. The Mixed Fleet Vehicle Routing Problem Optimization of Multi-depot Distribution with Time Windows[J]. Automobile Applied Technology, 2022, 47(3): 55-63.
50	Cheng Yiran, Szeto W Y. Artificial Bee Colony Approach to Solving the Electric Vehicle Routing Problem[J]. Journal of the Eastern Asia Society for Transportation Studies, 2017, 12: 975-990.
51	张惠珍, 姜晶. 多车场多车型电动汽车路径优化研究[J]. 软件导刊, 2021, 20(8): 75-81.
	Zhang Huizhen, Jiang Jing. Research on the Optimization of Multi-depot Heterogeneous Electric Vehicle Route[J]. Software Guide, 2021, 20(8): 75-81.
52	Wang Qing, Peng Shuai, Liu Shuan. Optimization of Electric Vehicle Routing Problem Using Tabu Search[C]//2020 Chinese Control and Decision Conference (CCDC). Piscataway, NJ, USA: IEEE, 2020: 2220-2224.
53	Karakatič Sašo. Optimizing Nonlinear Charging Times of Electric Vehicle Routing with Genetic Algorithm[J]. Expert Systems with Applications, 2021, 164: 114039.
54	胡尚民, 沈惠璋. 基于强化学习的电动车路径优化研究[J]. 计算机应用研究, 2020, 37(11): 3232-3235.
	Hu Shangmin, Shen Huizhang. Research on Electric Vehicle Routing Problem Based on Reinforcement Learning[J]. Application Research of Computers, 2020, 37(11): 3232-3235.
55	Sassi Ons, Ramdane Cherif-Khettaf W, Oulamara Ammar. Multi-start Iterated Local Search for the Mixed Fleet Vehicle Routing Problem with Heterogenous Electric Vehicles[C]//Evolutionary Computation in Combinatorial Optimization. Cham: Springer International Publishing, 2015: 138-149.
56	Zhao Mengting, Lu Yuwei. A Heuristic Approach for a Real-world Electric Vehicle Routing Problem[J]. Algorithms, 2019, 12(2): 45.

算例	客户数	充电站数	电池容量	车辆容量
E22	21	8	94	6 000
E23	22	9	190	4 500
E30	29	6	178	4 500
E33	32	6	209	8 000
E51	50	9	105	160
E76	75	9	98	220
E101	100	9	103	200

算例	客户数	充电站数	电池容量	车辆容量
X143	142	4	2 243	1 190
X214	213	9	987	944
X351	350	35	649	436
X459	458	20	929	1 106
X573	572	6	1 691	210
X685	684	25	911	408
X749	748	30	790	396
X819	818	25	926	358
X916	915	9	1 591	33
X1001	1 000	9	1 684	131

文献	模型	求解方法	优化目标
[7]	GVRP	混合启发式算法	距离最短
[26]	EVRP	AMPL/CPLEX	距离最短
[38]	EVRPTW	ALNS	耗电最少
[39]	EVRPTW	CPLEX，ALNS	成本最小 (运输、车辆、司机和时间窗惩罚成本)
[40]	多充电技术的电动车路径问题	分支定价法	自定义总充电代价最小
[41]	多车型电动车辆问题	分支定价法	成本最小(运输和车辆成本)
[42]	MEVRP	分支定价法，双向标记算法	成本最小(运输和车辆成本)
[43]	EVRPNL	分支定价法	时间最短
[44]	EVRPTW	分支定价法	距离最短
[15]	EVRP	VNS，SA，GA	距离最短
[45]	EVRPTWNL	改进差分进化混合算法	成本最小(运输和时间窗惩罚成本)
[46]	考虑载重影响耗电率的电动车路径问题	改进自适应大邻域搜索	成本最小(运输、充电和车辆成本)
[47]	EVRPTW	精英遗传算法	耗电最少
[22]	EVRPSTW	结合变邻域搜索算法的粒子群优化算法	成本最小
[48]	EVRP	蚁群优化算法	时间最短
[49]	MEVRP	改进粒子群优化算法	成本最小 (运输、碳排放和时间窗惩罚成本)
[50]	EVRP	增强人工蜂群算法	距离最短
[51]	多车场多车型的电动车路径问题	K-means，改进蚁群算法	成本最小(运输、车辆和电池成本)
[52]	EVRP	禁忌搜索算法	距离最短
[53]	EVRPTWNL	两层遗传算法	时间最短
[8]	EVRP	双层蚁群优化算法	距离最短
[16]	EVRP	基于置信度的双层蚁群算法	距离最短
[54]	EVRP	强化学习	距离最短
[19]	EVRPTW	深度强化学习	距离最短

方法类型	难易程度	灵活性	性能	使用情况
数学软件	容易	低	限小规模算例	较少
精确算法	较容易	中	限小规模算例	较少
启发式算法	较困难	高	可搜索到小规模算例的最优解、大规模算例的优质解	当前主流
机器学习算法	困难	中	训练完成后求解速度快，求解质量一般	有发展前景

算例	统计	VNS	SA	GA	BACO	CBACO
E22	min	384.67	384.67	384.67	384.67	384.67
	max	384.67	384.67	384.67	\	\
	mean	384.67	384.67	384.67	384.67	384.67
	stdev	0	0	0	0	0
E23	min	571.94	571.94	571.94	571.94	571.94
	max	571.94	571.94	571.94	\	\
	mean	571.94	571.94	571.94	571.94	571.94
	stdev	0	0	0	0	0
E30	min	509.47	509.47	509.47	509.47	509.47
	max	509.47	509.47	509.47	\	\
	mean	509.47	509.47	509.47	509.47	509.47
	stdev	0	0	0	0	0
E33	min	840.14	840.57	844.25	840.57	840.57
	max	840.46	873.33	846.21	\	\
	mean	840.43	854.07	845.62	842.30	840.57
	stdev	1.18	12.80	0.92	1.42	0.00
E51	min	529.90	533.66	529.90	529.90	529.90
	max	548.98	533.66	553.23	\	\
	mean	543.26	533.66	542.08	529.90	529.90
	stdev	3.52	0	8.57	0	0
E76	min	692.64	701.03	697.27	692.64	692.64
	max	707.49	716.77	730.92	\	\
	mean	697.89	712.17	717.30	692.85	692.88
	stdev	3.09	5.78	9.58	0.81	0.92
E101	min	839.29	845.84	852.69	840.25	838.84
	max	\	856.74	887.14	\	\
	mean	\	852.48	872.69	845.95	840.56
	stdev	\	3.44	9.58	4.58	0.42