Electric vehicle routing problem: a comprehensive review

Mohit Kumar Kakkar; Priyanka

doi:10.5269/bspm.76326

Mohit Kumar Kakkar
Priyanka Chitkara University Institute of Engineering and Technology, Chitkara University, Rajpura, Punjab

Abstract

Transportation plays an important role in today’s era. To manage the on-time delivery in logistics, it is crucial to manage the fleet for the delivery. Because of environmental concerns and new regulations, green vehicles and electric vehicles are becoming more famous in logistics. Due to their limited driving range, the authors need to be recharge again and again. The vehicle routing problem (VRP) is extended to electric vehicle routing problem (EVRP) having different characteristics. The problem is NP hard and computationally challenging to solve large scale instances. To solve such problems, algorithms were introduced such as exact algorithms, metaheuristics, and machine learning to solve real-life problems, energy consumption and environmental considerations. EVRP is applicable in urban logistics, fleet management, and goods distribution. Research in EVRP combined with sustainable development goals give solutions to optimization problems that aim to manage the social, economic, and environmental objectives. EVRPs increase the operational efficiency as well as contribute as a greener and more sustainable future by promoting eco-friendly logistics practices. From all this, we can conclude that EVRPs are a strong tool to support the SDGs, particularly for the clean environment, sustainable infrastructure, and logistics. In this paper, a literature review on electric vehicle routing problem is given and research gaps along with future directions are also discussed. To deal with the new and complex routing challenges in EVRP, heuristics and metaheuristics approaches are developed and adapted by different researchers. Research publications from the past 13 years has been taken into consideration including 95 research articles, that deal with EVRP. An overview on these procedures has been introduced in this review article.

Downloads

Download data is not yet available.

References

Agardi, A and Kovacs, L and Banyai, T, Two-echelon vehicle routing problem with recharge stations, Transport and Telecommunication 20(4), 305-317, (2019).

Akbay, M. A. and Kalayci, C.B. and Blum, C and Polat, O, Variable neighborhood search for the two-echelon electric vehicle routing problem with time windows, Applied Sciences 12(3), 1014, (2022).

Aghalari, A and Salamah, D and Kabli, M and Marufuzzaman, M, A two-stage stochastic location–routing problem for electric vehicles fast charging, Computers & Operations Research 158, 106286,(2023).

Azadi, A. H. S. and Khalilzadeh, M and Antucheviciene, J and Heidari, A and Soon, A, A sustainable multi-objective model for capacitated-electric-vehicle-routing-problem considering hard and soft time windows as well as partial recharging, Biomimetics 9(4), 242, (2024).

Akbay, M. A. and Blum, C, Mathematical Formulations And Results Regarding Two Echelon Electric Vehicle Routing Problems, arXiv preprint arXiv:2412.06671, (2024).

Abid, M and Tabaa, M and Hachimi, H, Electric vehicle routing problem with an enhanced vehicle dispatching approach considering real-life data, Energies 17(7), 1596 (2024).

Bruglieri, M and Pezzella, F and Pisacane, O and Suraci, S, A variable neighborhood search branching for the electric vehicle routing problem with time windows, Electronic Notes in Discrete Mathematics 41, 221-228 (2015).

Barco, J and Guerra, A and Munoz, L and Quijano, N, Optimal routing and scheduling of charge for electric vehicles: A case study,Mathematical Problems in Engineering 2017(1), 8509783 (2017).

Bruglieri, M and Mancini, S and Pezzella, F and Pisacane, O and Suraci, S, A three-phase matheuristic for the time-effective electric vehicle routing problem with partial recharges, Electronic Notes in Discrete Mathematics 58, 95-102 (2017).

Basso, R and Kulcsar, B and Egardt, B and Lindroth, P and Sanchez-Diaz, I, Energy consumption estimation integrated into the electric vehicle routing problem, Transportation Research Part D: Transport and Environment 69, 141-167 (2019)

Breunig, U and Baldacci, R and Hartl, R. F. and Vidal, T, The electric two-echelon vehicle routing problem, Computers & Operations Research 103, 198-210 (2019)

Bovet, D. P. and Crescenzi, P and Silvestri, R, A uniform approach to define complexity classes, Theoretical Computer Science 104(2), 263-283 (1992)

Cortes-M, David L and Prodhon, C and Afsar, H. M. , The electric vehicle routing problem with time windows, partial recharges and satellite customers, Transportation Research Part E: Logistics and Transportation Review 130, 184-206 (2019)

Catay, B and Sadati, I, An improved matheuristic for solving the electric vehicle routing problem with time windows and synchronized mobile charging/battery swapping, Computers & Operations Research 159, 106310 (2023)

Caillard, S and Chabane, R. B. , Evolutionary-Based Ant System Algorithm to Solve the Dynamic Electric Vehicle Routing Problem, ICORES, 285-293 (2024)

Chen, Y and Xue, J and Zhou, Y and Wu, Q, An efficient threshold acceptance-based multi-layer search algorithm for capacitated electric vehicle routing problem, IEEE Transactions on Intelligent Transportation Systems 25(6), 5867-5879 (2024)

Chen, Y and Xue, J and Zhou, Y and Wu, Q, Double-assistant evolutionary multitasking algorithm for enhanced electric vehicle routing with backup batteries and battery swapping stations, Expert Systems with Applications 237, 121600 (2024)

Cobham, A, The intrinsic computational difficulty of functions, (1965)

Dantzig, G. B. and Ramser, J. H. , The truck dispatching problem, Management science 6(1), 80-91(1959)

Ding, N and Batta, R and Kwon, C and others, Conflict-free electric vehicle routing problem with capacitated charging stations and partial recharge, SUNY, Buffalo, (2015)

Desaulniers, G and Errico, F and Irnich, S and Schneider, M, Exact algorithms for electric vehiclerouting problems with time windows, Operations Research 64(6), 1388-1405 (2016)

Catay, B and Duman, E. N. and Tas, D, Branch-And Methods for the Electric Vehicle Routing Problem With Time Windows, (2021)

Duman, E. N. and Tas, D and Catay, B, A bidirectional branch-and-price algorithm with Pulse procedure for the Electric Vehicle Routing Problem with flexible deliveries, Transportation Research Part C: Emerging Technologies 165, 104699 (2024)

Delimata, P and Marsza l-Paszek, B and Moshkov, M and Paszek, P and Skowron, A and Suraj, Z, Comparison of some classification algorithms based on deterministic and nondeterministic decision rules, Transactions on Rough Sets 12, 90-105 (2010)

Erdogan, S and Miller-Hooks, E, A green vehicle routing problem, Transportation research part E: logistics and transportation review 48(1), 100-114 (2012)

Felipe, A and Ortu˜no, M. T. and Righini, G and Tirado, G, A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges, Transportation Research Part E: Logistics and Transportation Review 71, 111-128 (2014)

Froger, A and Mendoza, J. E. and Jabali, O and Laporte, G, Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions, Computers & Operations Research 104, 256-294 (2019)

Fan, L, A hybrid adaptive large neighborhood search for time-dependent open electric vehicle routing problem with hybrid energy replenishment strategies, PLoS One 18(9), e0291473 (2023)

Fu, B and Li, H, Closeness of NP-hard sets to other complexity classes, SIAM Journal on Computing 23(2), 255-260 (1994)

Goeke, D and Schneider, M, Routing a mixed fleet of electric and conventional vehicles, European Journal of Operational Research 245(1), 81-99 (2015)

Grandinetti, L and Guerriero, F and Pezzella, F and Pisacane, O, A pick-up and delivery problem with time windows by electric vehicles, International Journal of Productivity and Quality Management 18(2-3), 403-423 (2016)

Gatica, G and Ahumada, G and Escobar, J. W. and Linfati, R, Efficient heuristic algorithms for location of charging stations in electric vehicle routing problems, Stud. Inform. Control 27(1), 2018

Goeke, D, Granular tabu search for the pickup and delivery problem with time windows and electric vehicles, European Journal of Operational Research 278(3), 821-836 (2019)

Ghobadi, A and Tavakkoli M, Reza and F. M. and Kazemipoor, H, Multi-depot electric vehicle routing problem with fuzzy time windows and pickup/delivery constraints, Journal of applied research on industrial engineering 8(1), 1-18(2021)

Guo, F and Zhang, J and Huang, Z and Huang, W, Simultaneous charging station location-routing problem for electric vehicles: Effect of nonlinear partial charging and battery degradation, Energy 250, 123724 (2022)

Goli, A and Golmohammadi, A. M. and Verdegay, J. L., RETRACTED ARTICLE: Two-echelon electric vehicle routing problem with a developed moth-flame meta-heuristic algorithm, Operations Management Research 15(3), 891-912 (2022)

Hiermann, G and Puchinger, J and Ropke, S and Hartl, R. F. , The electric fleet size and mix vehicle routing problem with time windows and recharging stations, European Journal of Operational Research 252(3), 995-1018 (2016)

Hof, J and Schneider, M and Goeke, D, Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops, Transportation research part B: methodological 97, 102-112 (2017)

Hartmanis, J and Hopcroft, J. E. , An overview of the theory of computational complexity, Journal of the ACM (JACM) 18(3), 444-475 (1971)

Jie, W and Yang, J and Zhang, M and Huang, Y, The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology, European Journal of Operational Research 272(3), 879-904 (2019)

Jeong, J and Ghaddar, B and Zufferey, N and Nathwani, J, Adaptive robust electric vehicle routing under energy consumption uncertainty, Transportation Research Part C: Emerging Technologies 160, 104529 (2024)

Keskin, M and Catay, B, artial recharge strategies for the electric vehicle routing problem with time windows, Transportation research part C: emerging technologies 65, 111-127 (2016)

Keskin, M and Catay, B, A matheuristic method for the electric vehicle routing problem with time windows and fast chargers, Computers & operations research 100, 172-188 (2018)

Keskin, M and Laporte, G and Catay, B, Electric vehicle routing problem with time-dependent waiting times at recharging stations, Computers & Operations Research 107, 77-94 (2019)

Koc, C and Jabali, O and Mendoza, J. E. and Laporte, G, The electric vehicle routing problem with shared charging stations, International Transactions in Operational Research 26(4), 1211-1243 (2019)

Kancharla, S. R. and Ramadurai, G, Electric vehicle routing problem with non-linear charging and load-dependent discharging, Expert Systems with Applications 160, 113714 (2020)

Karakatic, S, Optimizing nonlinear charging times of electric vehicle routing with genetic algorithm, Expert Systems with Applications 164, 114039 (2021)

Keskin, M and Catay, B and Laporte, G, A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations, Computers & Operations Research 125, 105060 (2021)

Li-ying, W and Yuan-bin, S, Multiple charging station location-routing problem with time window of electric vehicle, Journal of Engineering Science & Technology Review 8(5) (2015)

Lin, J and Zhou, W and Wolfson, O, Electric vehicle routing problem, Transportation research procedia 12, 508- 521 (2016)

Lu, J and Chen, Y and Hao, J. K. and He, R, The time-dependent electric vehicle routing problem: Model and solution, Expert Systems with Applications 161, 113593 (2020)

Lee, C, An exact algorithm for the electric-vehicle routing problem with nonlinear charging time, Journal of the Operational Research Society 72(7), 1461-1485 (2021)

Lin, B and Ghaddar, B and Nathwani, J, Electric vehicle routing with charging/discharging under time-variant electricity prices, Transportation Research Part C: Emerging Technologies 130, 103285 (2021)

Lech, N and Nikonczuk, P, The method of route optimization of electric vehicle, Procedia Computer Science 207, 4454-4462 (2022)

Li, Y and Lim, M. K. and Xiong, W and Huang, X and Shi, Y and Wang, S, An electric vehicle routing model with charging stations consideration for sustainable logistics, Industrial Management & Data Systems 124(3), 1076-1106 (2024)

Liu, Z and Li, Y and Xu, J and Bai, D, Multi-compartment electric vehicle routing problem for perishable products, International Journal of Crowd Science 8(1), 38-48 (2024)

Lera-Romero, G and Bront, J. J. M. and Soulignac, F. J. , A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows, European Journal of Operational Research 312(3), 978-995 (2024)

Montoya, A and Gueret, C and Mendoza, J. E. and Villegas, J.G. , The electric vehicle routing problem with nonlinear charging function, Transportation Research Part B: Methodological 103, 87-110 (2017)

Macrina, G and Pugliese, L. D. P. and Guerriero, F and Laporte, G, The green mixed fleet vehicle routing problem with partial battery recharging and time windows, Computers & Operations Research 101, 183-199 (2019)

Mao, H and Shi, J and Zhou, Y and Zhang, G, The electric vehicle routing problem with time windows and multiple recharging options, Ieee Access 8, 114864-114875 (2020)

Meng, M and Ma, Y Route optimization of electric vehicle considering soft time windows and two ways of power replenishment, Advances in Operations Research 2020(1), 5612872 (2020)

Penna, P. H. V. and Afsar, H. M. and Prins, C and Prodhon, C, A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations,

Paz, J. C. and Granada-Echeverri, M and Escobar, J, The multi-depot electric vehicle location routing problem with time windows, International journal of industrial engineering computations 9(1), 123-136 (2018)

Pan, G and Guan, X and Jiang, H and Liu, Y and Wu, H and Chen, H and Ohtsuki, T and Han, Z, Joint intelligent optimizing economic dispatch and electric vehicles charging in 5G vehicular networks, Computer Networks 255, 110872 (2024)

Raeesi, R and Zografos, K. G. , The electric vehicle routing problem with time windows and synchronised mobile battery swapping, Transportation Research Part B: Methodological 140, 101-129 (2020)

Raeesi, R and Zografos, K. G. , Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping, European Journal of Operational Research 30(1), 82-109 (2022)

Ren, X.X. and Fan, H. M. and Bao, M. X. and Fan, H, The time-dependent electric vehicle routing problem with drone and synchronized mobile battery swapping, Advanced Engineering Informatics 57, 102071 (2023)

Rodrıguez-Esparza, E and Masegosa, A. D. and Oliva, D and Onieva, E, A new Hyper-heuristic based on Adaptive Simulated Annealing and Reinforcement Learning for the Capacitated Electric Vehicle Routing Problem, Expert Systems with Applications 252, 124197 (2024)

Schneider, M and Stenger, A and Goeke, D, The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations, Transportation Science 48(4), 500-520 (2014)

Strehler, M and Merting, S and Schwan, C, Energy-efficient shortest routes for electric and hybrid vehicles, Transportation Research Part B: Methodological 103, 111-135 (2017)

Schiffer, M and Walther, G, The electric location routing problem with time windows and partial recharging, European journal of operational research 260(3), 995-1013 (2017)

Shao, S and Guan, W and Bi, J, Electric vehicle-routing problem with charging demands and energy consumption, IET Intelligent Transport Systems 12(3), 202-212 (2018)

Soysal, M and C¸ imen, M and Belbag, S, Pickup and delivery with electric vehicles under stochastic battery depletion, Computers & Industrial Engineering 146, 106512 (2020)

Sanchez, D.G. and Tabares, A and Faria, L. T. and Rivera, J. C. and Franco, J. F. , A clustering approach for the optimal siting of recharging stations in the electric vehicle routing problem with time windows , Energies 15(7), 2372 (2022)

Shi, J and Mao, H and Zhou, Z and Zheng, L, Adaptive large neighborhood search algorithm for the Unmanned aerial vehicle routing problem with recharging, Applied Soft Computing 147, 110831 (2023)

Schulz, A, Using infeasible path cuts to solve Electric Vehicle Routing Problems with realistic charging functions exactly within a branch-and-cut framework, EURO Journal on Transportation and Logistics 13, 100131 (2024)

Tahami, H and Rabadi, G and Haouari, M, Exact approaches for routing capacitated electric vehicles, Transportation Research Part E: Logistics and Transportation Review 122, 102126 (2020)

Tas, D, Electric vehicle routing with flexible time windows: a column generation solution approach, Transportation Letters 13(2), 97-103 (2021)

Wang, Y and Jiang, J and Mu, T, Context-aware and energy-driven route optimization for fully electric vehicles via crowdsourcing, IEEE Transactions on Intelligent Transportation Systems 14(3), 1331-1345 (2013)

Wang, X and Liang, Y and Tang, X and Jiang, X, A multi-compartment electric vehicle routing problem with time windows and temperature and humidity settings for perishable product delivery, Expert Systems with Applications 233, 120974 (2023)

Wang, Y and Zhou, J and Sun, Y and Fan, J and Wang, Z and Wang, H, Collaborative multidepot electric vehicle routing problem with time windows and shared charging stations, Expert Systems with Applications 219 , 119654 (2023)

Wu, Z and Zhang, J, A branch-and-price algorithm for two-echelon electric vehicle routing problem, Complex & Intelligent Systems 9(3), 2475-2490 (2023)

Xiao, J and Du, J and Cao, Z and Zhang, X and Niu, Y, A diversity-enhanced memetic algorithm for solving electric vehicle routing problems with time windows and mixed backhauls, Applied Soft Computing 134, 110025 (2023)

Yang, J and Sun H, Battery swap station location-routing problem with capacitated electric vehicles, Computers & operations research 55, 217-232 (2015)

Yang, H and Yang, S and Xu, Y and Cao, E and Lai, M and Dong, Z, Electric vehicle route optimization considering time-of-use electricity price by learnable partheno-genetic algorithm, IEEE Transactions on smart grid 6(2), 657-666 (2015)

Yilmaz, Y and Kalayci, C. B. , Variable neighborhood search algorithms to solve the electric vehicle routing problem with simultaneous pickup and delivery, Mathematics 10(17), 3108 (2022)

Zhang, S and Gajpal, Y and Appadoo, SS and Abdulkader, MMS, Electric vehicle routing problem with recharging stations for minimizing energy consumption, International journal of production economics 203, 404-413 (2018)

Zhao, M and Lu, Y, A heuristic approach for a real-world electric vehicle routing problem, Algorithms 12(2), 45 (2019)

Zuo, X and Xiao, Y and You, M and Kaku, I and Xu, Y, A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function, Journal of Cleaner Production 236, 117687 (2019)

Zhang, S and Chen, M and Zhang, W and Zhuang, X, Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations, Expert systems with applications 145, 113123 (2020)

Zhao, Z and Li, X and Zhou, X, Distribution Route Optimization for Electric Vehicles in Urban Cold Chain Logistics for Fresh Products under Time-Varying Traffic Conditions, Mathematical Problems in Engineering 2020(1), 9864935 (2020)

Zhang, R and Guo, J and Wang, J, A time-dependent electric vehicle routing problem with congestion tolls,IEEE Transactions on Engineering Management 69(4), 861-873 (2020)

Zhang, B and Yan, Q and Zhang, H and Zhang, L, Optimization of Charging/Battery-Swap Station Location of Electric Vehicles with an Improved Genetic Algorithm-BasedModel, CMES-Computer Modeling in Engineering & Sciences 134(2), (2023)

Zhang, S and Zhou, T and Fang, C and Yang, S, A novel collaborative electric vehicle routing problem with multiple prioritized time windows and time-dependent hybrid recharging, Expert Systems with Applications 224, 122990 (2024)

Zhou, S and Zhang, D and Ji, B and Zhou, S and Li, S and Zhou, L, A MILP model and heuristic method for the time-dependent electric vehicle routing and scheduling problem with time windows, Journal of Cleaner Production 434, 140188 (2024)