A Novel Optimization Method for Electric Capacitated Vehicles Routing Problem Considering Battery Degradation Based on Hybrid Neighborhood Search Algorithm

Zongao Zhang; Qian Wang; Jun Jiang; Xiaoyu Liu; Jinnan Yu

doi:10.54691/ckmqnk56

Authors

Zongao Zhang
Qian Wang
Jun Jiang
Xiaoyu Liu
Jinnan Yu

DOI:

https://doi.org/10.54691/ckmqnk56

Keywords:

Electric Capacitated Vehicle Routing Problem; Battery Degradation; Hybrid Genetic Neighborhood Search Algorithm.

Abstract

With the growing adoption of electric vehicles in logistics, the electric capacitated vehicle routing problem has become increasingly important. The battery, as a core component of electric vehicles, directly affects operational costs due to its degradation over time. Therefore, incorporating battery degradation into vehicle routing optimization is essential. This study incorporates battery degradation cost into the objective function, establishing a comprehensive mathematical model that further reduces overall transportation costs. Meanwhile, a hybrid genetic neighborhood search algorithm is developed by introducing the operator mechanism of neighborhood search into the genetic algorithm framework. This integration accelerates convergence and improves solution quality by combining the global search capability of genetic algorithms with the local refinement strength of neighborhood search. Numerical experiments demonstrate the effectiveness of the proposed algorithm, offering valuable insights and guidance for optimizing electric vehicle routing problems under realistic operational conditions.

Downloads

Download data is not yet available.

References

[1] Erdelić T, Carić T. A survey on the electric vehicle routing problem: variants and solution approaches[J]. Journal of Advanced Transportation, 2019, 2019(1): 5075671.

[2] Zhao J, Zeng Z, Liu Y. Electric vehicle routing problem considering traffic conditions and real-time loads[J]. Transportation Research Part C: Emerging Technologies, 2025, 176: 105150.

[3] Vakili S, Ölçer A I. Techno-economic-environmental feasibility of photovoltaic, wind and hybrid electrification systems for stand-alone and grid-connected port electrification in the Philippines[J]. Sustainable cities and society, 2023, 96: 104618.

[4] Zhu S, Mac Kinnon M, Soukup J, et al. Assessment of the greenhouse gas, Episodic air quality and public health benefits of fuel cell electrification of a major port complex[J]. Atmospheric Environment, 2022, 275: 118996.

[5] Zhang S, Gajpal Y, Appadoo S S, et al. Electric vehicle routing problem with recharging stations for minimizing energy consumption[J]. International journal of production economics, 2018, 203: 404-413.

[6] Kennedy B, Patterson D, Camilleri S. Use of lithium-ion batteries in electric vehicles[J]. Journal of Power Sources, 2000, 90(2): 156-162.

[7] Lai X, Chen Q, Tang X, et al. Critical review of life cycle assessment of lithium-ion batteries for electric vehicles: A lifespan perspective[J]. Etransportation, 2022, 12: 100169.

[8] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.

[9] Laporte G, Nobert Y. A branch and bound algorithm for the capacitated vehicle routing problem[J]. Operations-Research-Spektrum, 1983, 5: 77-85.

[10] Kolen A W J, Rinnooy Kan A H G, Trienekens H W J M. Vehicle routing with time windows[J]. Operations Research, 1987, 35(2): 266-273.

[11] Erdoğan S, Miller-Hooks E. A green vehicle routing problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(1): 100-114.

[12] Kucukoglu I, Dewil R, Cattrysse D. The electric vehicle routing problem and its variations: A literature review[J]. Computers & Industrial Engineering, 2021, 161: 107650.

[13] 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.

[14] Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265.

[15] He S Y, Kuo Y H, Wu D. Incorporating institutional and spatial factors in the selection of the optimal locations of public electric vehicle charging facilities: A case study of Beijing, China[J]. Transportation Research Part C: Emerging Technologies, 2016, 67: 131-148.

[16] Sadati M E H, Akbari V, Çatay B. Electric vehicle routing problem with flexible deliveries[J]. International Journal of Production Research, 2022, 60(13): 4268-4294.

[17] Erdelić T, Carić T, Erdelić M, et al. Electric vehicle routing problem with single or multiple recharges[J]. Transportation Research Procedia, 2019, 40: 217-224.

[18] Lu J, Chen Y, Hao J K, et al. The time-dependent electric vehicle routing problem: Model and solution[J]. Expert Systems with Applications, 2020, 161: 113593.

[19] Mao H, Shi J, Zhou Y, et al. The electric vehicle routing problem with time windows and multiple recharging options[J]. IEEE Access, 2020, 8: 114864-114875.

[20] Wang Y, Zhou J, Sun Y, et al. Collaborative multidepot electric vehicle routing problem with time windows and shared charging stations[J]. Expert Systems with Applications, 2023, 219: 119654.

[21] Liu K, Hu X, Yang Z, et al. Lithium-ion battery charging management considering economic costs of electrical energy loss and battery degradation[J]. Energy Conversion and Management, 2019, 195: 167-179.

[22] Wang J, Kang L, Liu Y. Optimal scheduling for electric bus fleets based on dynamic programming approach by considering battery capacity fade[J]. Renewable and Sustainable Energy Reviews, 2020, 130: 109978.

[23] Li L, Dong S, Wang L. Capacity degradation prediction of electric vehicle battery by integrating convolutional neural network with informer model[J]. Journal of Power Sources, 2025, 651: 237497.

[24] Yu K, Yan P, Liu Y, et al. Battery degradation mitigation-oriented strategy for optimizing e-hailing electric vehicle operations[J]. Transportation Research Part E: Logistics and Transportation Review, 2025, 196: 104006.

[25] Ou S. Estimate long-term impact on battery degradation by considering electric vehicle real-world end-use factors[J]. Journal of Power Sources, 2023, 573: 233133.

[26] Zhang S, Chen M, Zhang W, et al. Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations[J]. Expert Systems with Applications, 2020, 145: 113123.

[27] Hien V Q, Dao T C, Binh H T T. A greedy search based evolutionary algorithm for electric vehicle routing problem[J]. Applied Intelligence, 2023, 53(3): 2908-2922.

[28] Souza A L S, Papini M, Penna P H V, et al. A flexible variable neighbourhood search algorithm for different variants of the Electric Vehicle Routing Problem[J]. Computers & Operations Research, 2024, 168: 106713.

[29] Duman E N, Taş D, Çatay B. A bidirectional branch-and-price algorithm with Pulse procedure for the Electric Vehicle Routing Problem with flexible deliveries[J]. Transportation Research Part C: Emerging Technologies, 2024, 165: 104699.

[30] Yang S, Zhang R, Ma Y, et al. Adaptive large neighborhood search incorporating mixed-integer linear programming for electric vehicle routing problem with mobile charging and nonlinear battery degradation[J]. Applied Soft Computing, 2025, 175: 112988.

[31] İslim R B, Çatay B. An effective matheuristic approach for solving the electric traveling salesperson problem with time windows and battery degradation[J]. Engineering Applications of Artificial Intelligence, 2024, 132: 107943.

[32] Sarasketa-Zabala E, Gandiaga I, Martinez-Laserna E, et al. Cycle ageing analysis of a LiFePO4/graphite cell with dynamic model validations: Towards realistic lifetime predictions[J]. Journal of Power Sources, 2015, 275: 573-587.

[33] Rydh C J, Sandén B A. Energy analysis of batteries in photovoltaic systems. Part I: Performance and energy requirements[J]. Energy conversion and management, 2005, 46(11-12): 1957-1979.

[34] Duman E N, Taş D, Çatay B. 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.

[35] Cataldo-Díaz C, Linfati R, Escobar J W. Mathematical model for the electric vehicle routing problem considering the state of charge of the batteries[J]. Sustainability, 2022, 14(3): 1645.

[36] Miri I, Fotouhi A, Ewin N. Electric vehicle energy consumption modelling and estimation—A case study[J]. International Journal of Energy Research, 2021, 45(1): 501-520.