Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem

doi:10.16182/j.issn1004731x.joss.21-1133

Abstract

Abstract:

Based on the real business practice, the multi-trip and heterogeneous-fleet electric vehicle routing problem (MTHF-EVRP) with time windows in green logistics is studied. A path-based mixed-integer linear model is built for the precise solution to the small-scale instances. A hybrid variable neighborhood search algorithm (Hybrid VNS) combined the variable neighborhood search algorithm with the labeling algorithm is proposed for the large-scale instances. The algorithm generates a modified insertion heuristic with random factor to construct the initial solution, allows the time window and range violation, adopts the neighborhood operators for the local search, and applies a labeling algorithm to solve the fixed-route recharging problem precisely. The methods are tested on the real-world benchmark instances for MTHF-EVRP. The results on the small-scale instances show that Hybrid VNS can find the optimal solutions in a very short time. Compared with the state-of-the-art algorithm on the large-scale instances, the algorithm can significantly reduce the logistics cost and the great competitiveness of Hybrid VNS is showed.

Key words: heterogeneous-fleet, multi-trip, electric vehicle routing problem, variable neighborhood search, labeling algorithm

CLC Number:

TP391.9

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.

Figures/Tables 2

References 31

1	国务院. 北京打赢蓝天保卫战三年行动计划[EB/OL].(2018-09-15)[2021-11-05]..
2	Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research (S0030-364X), 1987, 35(2): 254-265.
3	Erdoğan S, Miller-Hooks E. A Green Vehicle Routing Problem[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2012, 48(1): 100-114.
4	Roberti R, Wen M. The Electric Traveling Salesman Problem with Time Windows[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2016, 89: 32-52.
5	Schneider M, Stenger A, Goeke D. The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations[J]. Transportation Science (S0041-1655), 2014, 48(4): 500-520.
6	Desaulniers G, Errico F, Irnich S, et al. Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows[J]. Operations Research (S0030-364X), 2016, 64(6): 1388-1405.
7	Hiermann G, Puchinger J, Ropke S, et al. The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations[J]. European Journal of Operational Research (S0377-2217), 2016, 252(3): 995-1018.
8	Golden B, Assad A, Levy L, et al. The Fleet Size and Mix Vehicle Routing Problem[J]. Computers & Operations Research (S0305-0548), 1984, 11(1): 49-66.
9	Hiermann G, Hartl R F, Puchinger J, et al. Routing a Mix of Conventional, Plug-In Hybrid, and Electric Vehicles[J]. European Journal of Operational Research (S0377-2217), 2019, 272(1): 235-248.
10	Macrina G, Laporte G, Guerriero F, et al. An Energy-Efficient Green-Vehicle Routing Problem with Mixed Vehicle Fleet, Partial Battery Recharging and Time Windows[J]. European Journal of Operational Research (S0377-2217), 2019, 276(3): 971-982.
11	赵灿华, 侍洪波. 基于自适应变邻域搜索的大规模电动车辆路径优化[J]. 华东理工大学学报(自然科学版), 2020, 46(5): 694-701.
	Zhao Canhua, Shi Hongbo. Large-Scale Electric Vehicle Route Optimization Based on Adaptive Variable Neighborhood Search[J]. Journal of East China University of Science and Technology (Natural Science Edition), 2020, 46(5): 694-701.
12	Zhao M, Lu Y. A Heuristic Approach for a Real-World Electric Vehicle Routing Problem[J]. Algorithms (S1999-4893), 2019, 12(2): 45.
13	Zhou Y, Huang J, Shi J, et al. The Electric Vehicle Routing Problem with Partial Recharge and Vehicle Recycling[J]. Complex & Intelligent Systems (S2199-4536), 2021, 7(3): 1-14.
14	Li H, Li Z, Cao L, et al. Research on Optimization of Electric Vehicle Routing Problem with Time Window[J]. IEEE Access(S2169-3536), 2020, 8: 146707-146718.
15	Liu H, Zhang Z, Guo X. Restricted Neighborhood Search for Large Scale Vehicle Routing Problems[C]//2019 IEEE 16th International Conference on Networking, Sensing and Control (ICNSC). IEEE, 2019: 98-103.
16	Goeke D, Schneider M. Routing a Mixed Fleet of Electric and Conventional Vehicles[J]. European Journal of Operational Research (S0377-2217), 2015, 245(1): 81-99.
17	Schiffer M, Walther G. The Electric Location Routing Problem with Time Windows and Partial Recharging[J]. European Journal of Operational Research (S0377-2217), 2017, 260(3): 995-1013.
18	揭婉晨, 杨珺, 杨超. 多车型电动汽车车辆路径问题的分支定价算法研究[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.
19	李得成, 陈彦如, 张宗成. 基于分支定价算法的电动车与燃油车混合车辆路径问题研究[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.
20	Montoya A, Guéret C, Mendoza J E, et al. The Electric Vehicle Routing Problem with Nonlinear Charging Function[J]. Transportation Research Part B: Methodological (S0191-2615), 2017, 103: 87-110.
21	Bruglieri M, Mancini S, Pezzella F, et al. A Path-Based Solution Approach for the Green Vehicle Routing Problem[J]. Computers & Operations Research (S0305-0548), 2019, 103: 109-122.
22	Froger A, Mendoza J E, Jabali O, et al. Improved Formulations and Algorithmic Components for the Electric Vehicle Routing Problem with Nonlinear Charging Functions[J]. Computers & Operations Research (S0305-0548), 2019, 104: 256-294.
23	Schiffer M, Walther G. An Adaptive Large Neighborhood Search for the Location-Routing Problem with Intra-route Facilities[J]. Transportation Science (S0041-1655), 2018, 52(2): 331-352.
24	Keskin M, Çatay B. Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows[J]. Transportation Research Part C: Emerging Technologies (S0968-090X), 2016, 65: 111-127.
25	Felipe Á, Ortuño M T, Righini G, et al. A Heuristic Approach for the Green Vehicle Routing Problem with Multiple Technologies and Partial Recharges[J]. Transportation Research Part E: Logistics and Transportation Review (S1366-5545), 2014, 71: 111-128.
26	Wen M, Linde E, Ropke S, et al. An Adaptive Large Neighborhood Search Heuristic for the Electric Vehicle Scheduling Problem[J]. Computers & Operations Research (S0305-0548), 2016, 76: 73-83.
27	Vidal T, Crainic T G, Gendreau M, et al. A Hybrid Genetic Algorithm with Adaptive Diversity Management for a Large Class of Vehicle Routing Problems with Time-Windows[J]. Computers & Operations Research (S0305-0548), 2013, 40(1): 475-489.
28	胡蓉, 陈文博, 钱斌, 等. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
	Hu Rong, Chen Wenbo, Qian Bin, et al. Learning Ant Colony Algorithm for Green Multi-Depot Vehicle Routing Problem[J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
29	范双南, 陈纪铭, 高为民, 等. 基于改进智能水滴算法的动态车辆配送路径优化[J]. 系统仿真学报, 2020, 32(9): 1808-1817.
	Fan Shuangnan, Chen Jiming, Gao Weimin, et al. Dynamic Vehicle Distribution Path Optimization Based on Improved Intelligent Water Drop Algorithm[J]. Journal of System Simulation, 2020, 32(9): 1808-1817.
30	Irnich S, Desaulniers G. Shortest Path Problems with Resource Constraints[M]// Column generation. Springer, Boston: MA, 2005: 33-65.
31	Hansen P, Mladenović N. Variable Neighborhood Search: Principles and Applications[J]. European Journal of Operational Research (S0377-2217), 2001, 130(3): 449-467.

[1]	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.
[2]	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.