基于混合遗传搜索求解载重约束的电动车辆路径问题

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

摘要/Abstract

摘要：

载重约束的电动车辆路径问题（capacitated electric vehicle routing problem，CEVRP）是物流配送中的一种NP困难的组合优化问题，要求满足车辆的载重和电量约束条件，最小化总配送距离。提出一种混合遗传搜索算法来解决CEVRP，将其分解为两个子问题：载重约束的车辆路径问题和固定路径车辆充电问题。设计了双层染色体结构的编码方案，表示两个子问题的决策变量。采用Split操作生成满足载重约束的车辆路径，使用Relocate、2-Opt、2-Opt*、SWAP和SWAP*邻域搜索算子对其进行局部优化；提出一种基于回溯的充电策略，将合适的充电站编号插入车辆路径，以满足电量约束。本文算法与五种方法实验比较的结果表明，本文算法在多数CEVRP测试问题上能找到比其它方法更好的解，尤其适合于求解大规模的CEVRP。

关键词: 电动车辆路径问题, 组合优化, 混合遗传搜索, 充电策略, 邻域搜索

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

中图分类号:

TP391.9

金东遥,刘敏,朱烨娜等 . 基于混合遗传搜索求解载重约束的电动车辆路径问题[J]. 系统仿真学报, 2024, 36(11): 2528-2541.

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

图/表 11

图1

图2

图3

图4

表1

表2

表3

图5

图6

图7

图8

参考文献 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]	李高扬, 黎向锋, 赵康, 金玉超, 易志东, 左敦稳. 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.
[2]	徐宜刚, 陈勇, 王宸, 彭运贤. 改进NSGA-III求解高维多目标绿色柔性作业车间调度问题[J]. 系统仿真学报, 2024, 36(10): 2314-2329.
[3]	张腾飞, 胡蓉, 钱斌, 吕阳. 学习型变邻域搜索算法求解运输-装配协同优化问题[J]. 系统仿真学报, 2023, 35(6): 1260-1277.
[4]	余佳英, 张宏立, 董颖超. 基于离散状态转移算法的无等待流水车间调度研究[J]. 系统仿真学报, 2023, 35(5): 1034-1045.
[5]	范厚明, 咸富山, 王怀奇. 动态需求下考虑订单聚类的外卖配送路径优化[J]. 系统仿真学报, 2023, 35(2): 396-407.
[6]	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
[7]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
[8]	王伟权, 丁鼎, 颜林莎. 线性充电策略下多车型电动车辆路径模型研究[J]. 系统仿真学报, 2022, 34(3): 614-623.
[9]	胡蓉, 陈文博, 钱斌, 郭宁, 向凤红. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
[10]	陈魁, 毕利. 改进粒子群算法在考虑运输时间下的FJSP研究[J]. 系统仿真学报, 2021, 33(4): 845-853.
[11]	王霄汉, 张霖, 任磊, 谢堃钰, 王昆玉, 叶飞, 陈真. 基于强化学习的车间调度问题研究简述[J]. 系统仿真学报, 2021, 33(12): 2782-2791.
[12]	蔡敏, 王艳, 纪志成. 基于多策略融合量子粒子群算法的MOFFJSP研究[J]. 系统仿真学报, 2021, 33(11): 2615-2626.
[13]	李珍萍, 赵雨薇, 张煜炜, 邢立宁, 任腾. 共同配送选址-路径问题及大邻域搜索算法[J]. 系统仿真学报, 2021, 33(10): 2518-2531.
[14]	孙灿, 周新宇, 王明文. 一种融合邻域搜索的多策略差分进化算法[J]. 系统仿真学报, 2020, 32(6): 1071-1084.
[15]	谢旦岚, 郭笛, 纪媛, 高志蓬. 自动化码头运输设备充电策略优化的仿真研究[J]. 系统仿真学报, 2020, 32(10): 1927-1935.