Electric Vehicle Routing Problem: A Review of Recent Approaches and Algorithms
DOI:
https://doi.org/10.24193/subbi.2024.2.05Keywords:
Electric vehicle routing problem, Classification, Literature reviewAbstract
With the rapid advancement of new energy vehicles, electric vehicles (EVs) have become integral to modern transportation systems. Compared with traditional fuel vehicles, EVs are limited by their limited battery capacity and require reasonable charging planning to complete the designated routes efficiently. Therefore, the effective routing of EVs has emerged as a critical research focus in transportation and logistics. This study comprehensively reviews recent advancements in the Electric Vehicle Routing Problem (EVRP) over the past three years. First, the concepts of EVRP are introduced. Then, the problem is classified according to energy consumption models, charging strategies, and constraints. Subsequently, various algorithms employed in these studies are analyzed and summarized. Finally, based on the current state of development in this field, the main challenges faced by EVRP and future research directions are discussed.
Received by editors: 27 January 2025
2010 Mathematics Subject Classification. 90B06, 90C11, 90C59
1998 CR Categories and Descriptors. G.1.6 [Optimization]; I.2.8 [Problem Solving, Control Methods, and Search]: Heuristic methods
References
[1] Co2 emissions from cars: facts and figures (infographics), 2019. URL https://www.europarl.europa.eu/topics/en/article/20190313STO31218/co2-emissions-from-cars-facts-and-figures-infographics.
[2] Fit for 55: zero co2 emissions for new cars and vans in 2035, 2023. URL https://www.europarl.europa.eu/news/en/press-room/20230210IPR74715/fit-for-55-zero-co2-emissions-for-new-cars-and-vans-in-2035.
[3] Cansu Agrali and Seokcheon Lee. The multi-depot pickup and delivery problem with capacitated electric vehicles, transfers, and time windows. Computers & Industrial Engineering, 179:109207, May 2023. ISSN 03608352. doi: 10.1016/j. cie.2023.109207.
[4] Vahid Akbari, Bülent Çatay, and İhsan Sadati. Route optimization of battery electric vehicles using dynamic charging on electrified roads. Sustainable Cities and Society, 109:105532, August 2024. ISSN 22106707. doi:10.1016/j.scs.2024.105532.
[5] Afsane Amiri, Hossein Zolfagharinia, and Saman Hassanzadeh Amin. A robust multi-objective routing problem for heavy-duty electric trucks with uncertain energy consumption. Computers & Industrial Engineering, 178:109108, April 2023. ISSN 03608352. doi: 10.1016/j.cie.2023.109108.
[6] Dario Bezzi, Alberto Ceselli, and Giovanni Righini. A route-based algorithm for the electric vehicle routing problem with multiple technologies. Transportation Research Part C: Emerging Technologies, 157:104374, December 2023. ISSN 0968090X. doi: 10.1016/j.trc.2023.104374.
[7] Yanguang Cai, Yanlin Wu, and Chuncheng Fang. Double-assistant evolutionary multitasking algorithm for enhanced electric vehicle routing with backup batteries and battery swapping stations. Expert Systems with Applications, 237:121600, March 2024. ISSN 09574174. doi: 10.1016/j.eswa.2023.121600.
[8] Bülent Çatay and İhsan Sadati. An improved matheuristic for solving the electric vehicle routing problem with time windows and synchronized mobile charging/battery swapping. Computers & Operations Research, 159:106310, November 2023. ISSN 03050548. doi: 10.1016/j.cor.2023.106310.
[9] Tao Chen, Bowen Zhang, Hajir Pourbabak, Abdollah Kavousi-Fard, and Wencong Su. Optimal routing and charging of an electric vehicle fleet for high-efficiency dynamic transit systems. IEEE Transactions on Smart Grid, 9(4): 3563–3572, 2016.
[10] Serap Ercan Comert and Harun Resit Yazgan. A new approach based on hybrid ant colony optimization-artificial bee colony algorithm for multi-objective electric vehicle routing problems. Engineering Applications of Artificial Intelligence, 123: 106375, August 2023. ISSN 09521976. doi: 10.1016/j.engappai.2023.106375.
[11] Jinting Dong, Hongfeng Wang, and Shuzhu Zhang. Dynamic electric vehicle routing problem considering mid-route recharging and new demand arrival using an improved memetic algorithm. Sustainable Energy Technologies and Assessments, 58:103366, August 2023. ISSN 22131388. doi: 10.1016/j.seta.2023.103366.
[12] Ece Naz Duman, Duygu Taş, and Bülent Çatay. 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, August 2024. ISSN 0968090X. doi: 10.1016/j.trc.2024.104699.
[13] Mehmet Erdem, Çağrı Koç, and Eda Yücel. The electric home health care routing and scheduling problem with time windows and fast chargers. Computers & Industrial Engineering, 172:108580, October 2022. ISSN 03608352. doi: 10. 1016/j.cie.2022.108580.
[14] Lijun Fan. A two-stage hybrid ant colony algorithm for multi-depot half-open time-dependent electric vehicle routing problem. Complex & Intelligent Systems, 10(2):2107–2128, April 2024. ISSN 2198-6053. doi: 10.1007/s40747-023-01259-1.
[15] Lijun Fan, Changshi Liu, Bo Dai, Junyu Li, Zhang Wu, and Yuting Guo. Electric vehicle routing problem considering energy differences of charging stations. Journal of Cleaner Production, 418:138184, September 2023. ISSN 09596526. doi: 10.1016/j.jclepro.2023.138184.
[16] Dominik Goeke and Michael Schneider. Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research, 245(1):81–99, 2015.
[17] Raci Berk İslim and Bülent Çatay. An effective matheuristic approach for solving the electric traveling salesperson problem with time windows and battery degradation. Engineering Applications of Artificial Intelligence, 132:107943, June 2024. ISSN 09521976. doi: 10.1016/j.engappai.2024.107943.
[18] Ya-Hui Jia, Yi Mei, and Mengjie Zhang. Confidence-based ant colony optimization for capacitated electric vehicle routing problem with comparison of different encoding schemes. IEEE Transactions on Evolutionary Computation, 26(6): 1394–1408, December 2022. ISSN 1941-0026. doi: 10.1109/TEVC.2022.3144142.
[19] Can Berk Kalaycı and Yusuf Yılmaz. A review on the electric vehicle routing problems. Pamukkale University Journal of Engineering Sciences-Pamukkale Universitesi Muhendislik Bilimleri Dergisi, 2023.
[20] Gitae Kim, Yew-Soon Ong, Chen Kim Heng, Puay Siew Tan, and Nengsheng Allan Zhang. City vehicle routing problem (city vrp): A review. IEEE Transactions on Intelligent Transportation Systems, 16(4):1654–1666, 2015. doi: 10.1109/TITS.2015.2395536.
[21] Yong Jun Kim and Byung Do Chung. Energy consumption optimization for the electric vehicle routing problem with state-of-charge-dependent discharging rates. Journal of Cleaner Production, 385:135703, January 2023. ISSN 09596526. doi: 10.1016/j.jclepro.2022.135703.
[22] Ilker Kucukoglu, Reginald Dewil, and Dirk Cattrysse. The electric vehicle routing problem and its variations: A literature review. Computers & Industrial Engineering, 161:107650, 2021.
[23] Edward Lam, Guy Desaulniers, and Peter J. Stuckey. Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations. Computers & Operations Re- search, 145:105870, September 2022. ISSN 03050548. doi: 10.1016/j.cor.2022.105870.
[24] Gonzalo Lera-Romero, Juan José Miranda Bront, and Francisco J. Soulignac. 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, February 2024. ISSN 03772217. doi: 10.1016/j.ejor.2023.06.037.
[25] Wenheng Liu, Mahjoub Dridi, Jintong Ren, Amir Hajjam El Hassani, and Shuying Li. A double-adaptive general variable neighborhood search for an unmanned electric vehicle routing and scheduling problem in green manufacturing systems. Engineering Applications of Artificial Intelligence, 126:107113, November 2023. ISSN 09521976. doi: 10.1016/j.engappai.2023.107113.
[26] Xiaochang Liu, Dujuan Wang, Yunqiang Yin, and T.C.E. Cheng. Robust optimization for the electric vehicle pickup and delivery problem with time windows and uncertain demands. Computers & Operations Research, 151:106119, March 2023. ISSN 03050548. doi: 10.1016/j.cor.2022.106119.
[27] Pedro Dias Longhitano, Christophe Bérenguer, and Benjamin Echard. Joint electric vehicle routing and battery health management integrating an explicit state of charge model. Computers & Industrial Engineering, 188:109892, February 2024. ISSN 03608352. doi: 10.1016/j.cie.2024.109892.
[28] Bingshan Ma, Dawei Hu, Yin Wang, Qian Sun, Linwei He, and Xiqiong Chen. Time-dependent vehicle routing problem with departure time and speed optimization for shared autonomous electric vehicle service. Applied Mathematical Modelling, 113:333–357, January 2023. ISSN 0307904X. doi: 10.1016/j.apm. 2022.09.020.
[29] Hongguang Ma, Rongchao Yang, and Xiang Li. Delivery routing for a mixed fleet of conventional and electric vehicles with road restrictions. International Journal of Production Research, pages 1–24, 2024.
[30] Nima Moradi and Niloufar Mirzavand Boroujeni. Prize-collecting electric vehicle routing model for parcel delivery problem. Expert Systems with Applications, 259:125183, January 2025. ISSN 09574174. doi: 10.1016/j.eswa.2024.125183.
[31] Kechen Ouyang and David Z.W. Wang. Optimal operation strategies for freight transport with electric vehicles considering wireless charging lanes. Transportation Research Part E: Logistics and Transportation Review, 193:103852, January 2025. ISSN 13665545. doi: 10.1016/j.tre.2024.103852.
[32] David Peña, Bernabé Dorronsoro, and Patricia Ruiz. Sustainable waste collection optimization using electric vehicles. Sustainable Cities and Society, 105:105343, June 2024. ISSN 22106707. doi: 10.1016/j.scs.2024.105343.
[33] Bin Qian, Fei-Long Feng, Nai-Kang Yu, Rong Hu, and Yu-Wang Chen. An alternating direction multiplier method with variable neighborhood search for electric vehicle routing problem with time windows and battery swapping stations. Applied Soft Computing, 166:112141, November 2024. ISSN 15684946. doi: 10.1016/j.asoc.2024.112141.
[34] Hu Qin, Xinxin Su, Teng Ren, and Zhixing Luo. A review on the electric vehicle routing problems: Variants and algorithms. Frontiers of Engineering Management, 8:370–389, 2021.
[35] Xiao-Xue Ren, Hou-Ming Fan, Ming-Xin Bao, and Hao Fan. The time-dependent electric vehicle routing problem with drone and synchronized mobile battery swapping. Advanced Engineering Informatics, 57:102071, August 2023. ISSN 14740346. doi: 10.1016/j.aei.2023.102071.
[36] Erick Rodríguez-Esparza, Antonio D. Masegosa, Diego Oliva, and Enrique Onieva. 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, October 2024. ISSN 09574174. doi: 10.1016/j.eswa.2024.124197.
[37] Mir Ehsan Hesam Sadati, Vahid Akbari, and Bülent Çatay. Electric vehicle routing problem with flexible deliveries. International Journal of Production Research, 60(13):4268–4294, July 2022. ISSN 0020-7543. doi: 10.1080/00207543. 2022.2032451.
[38] Michael Schneider, Andreas Stenger, and Dominik Goeke. The electric vehicle-routing problem with time windows and recharging stations. Transportation science, 48(4):500–520, 2014.
[39] André L.S. Souza, Marcella Papini, Puca H.V. Penna, and Marcone J.F. Souza. A flexible variable neighbourhood search algorithm for different variants of the electric vehicle routing problem. Computers & Operations Research, 168:106713, August 2024. ISSN 03050548. doi: 10.1016/j.cor.2024.106713.
[40] Marios Thymianis, Alexandros Tzanetos, Eneko Osaba, Georgios Dounias, and Javier Del Ser. Electric vehicle routing problem: Literature review, instances and results with a novel ant colony optimization method. In 2022 IEEE Congress on Evolutionary Computation (CEC), pages 1–8. IEEE, 2022.
[41] Weiquan Wang and Jingyi Zhao. Partial linear recharging strategy for the electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research, 308(2):929–948, July 2023. ISSN 03772217. doi: 10.1016/j.ejor.2022.12.011.
[42] Xin Wang, Yijing Liang, Xiangbo Tang, and Xiyan Jiang. 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, December 2023. ISSN 09574174. doi: 10.1016/j.eswa.2023.120974.
[43] Yong Wang, Jingxin Zhou, Yaoyao Sun, Jianxin Fan, Zheng Wang, and Haizhong Wang. Collaborative multidepot electric vehicle routing problem with time windows and shared charging stations. Expert Systems with Applications, 219: 119654, June 2023. ISSN 09574174. doi: 10.1016/j.eswa.2023.119654.
[44] Soomin Woo, Eric Yongkeun Choi, Scott J. Moura, and Francesco Borrelli. Saving energy with eco-friendly routing of an electric vehicle fleet. Transportation Research Part E: Logistics and Transportation Review, 189:103644, September 2024. ISSN 13665545. doi: 10.1016/j.tre.2024.103644.
[45] Xiaoyun Xia, Helin Zhuang, Zijia Wang, and Zefeng Chen. Two-stage heuristic algorithm with pseudo node-based model for electric vehicle routing problem. Applied Soft Computing, 165:112102, November 2024. ISSN 15684946. doi: 10. 1016/j.asoc.2024.112102.
[46] Jianhua Xiao, Jingguo Du, Zhiguang Cao, Xingyi Zhang, and Yunyun Niu. A diversity-enhanced memetic algorithm for solving electric vehicle routing problems with time windows and mixed backhauls. Applied Soft Computing, 134: 110025, February 2023. ISSN 15684946. doi: 10.1016/j.asoc.2023.110025.
[47] Jianhua Xiao, Xiaoyang Liu, Tao Liu, Na Li, and Antonio Martinez-Sykora. The electric vehicle routing problem with synchronized mobile partial recharging and non-strict waiting strategy. Annals of Operations Research, June 2024. ISSN 1572-9338. doi: 10.1007/s10479-024-06069-3.
[48] Yiyong Xiao, Yue Zhang, Ikou Kaku, Rui Kang, and Xing Pan. Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption. Renewable and Sustainable Energy Reviews, 151:111567, 2021.
[49] Hao Xiong, Yumiao Xu, Huili Yan, Haoying Guo, and Chen Zhang. Optimizing electric vehicle routing under traffic congestion: A comprehensive energy consumption model considering drivetrain losses. Computers & Operations Research, 168:106710, August 2024. ISSN 03050548. doi: 10.1016/j.cor.2024.106710.
[50] Canqi Yao, Shibo Chen, Mauro Salazar, and Zaiyue Yang. Joint routing and charging problem of electric vehicles with incentive-aware customers considering spatio-temporal charging prices. IEEE Transactions on Intelligent Transportation Systems, 24(11):12215–12226, November 2023. ISSN 1558-0016. doi: 10.1109/TITS.2023.3286952.
[51] Chong Ye, Wenjie He, and Hanqi Chen. Electric vehicle routing models and solution algorithms in logistics distribution: A systematic review. Environmental Science and Pollution Research, 29(38):57067–57090, 2022.
[52] Shuai Zhang, Tong Zhou, Cheng Fang, and Sihan Yang. A novel collaborative electric vehicle routing problem with multiple prioritized time windows and time- dependent hybrid recharging. Expert Systems with Applications, 244:122990, June 2024. ISSN 09574174. doi: 10.1016/j.eswa.2023.122990.
[53] Binghai Zhou and Zhe Zhao. Multi-objective optimization of electric vehicle routing problem with battery swap and mixed time windows. Neural Computing and Applications, 34(10):7325–7348, May 2022. ISSN 1433-3058. doi: 10.1007/ s00521-022-06967-2.
[54] Saiqi Zhou, Dezhi Zhang, Bin Ji, Shaoyu Zhou, Shuangyan Li, and Likun Zhou. 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, January 2024. ISSN 09596526. doi: 10.1016/j.jclepro.2023.140188.
[55] Saiqi Zhou, Dezhi Zhang, Wen Yuan, Zhenjie Wang, Likun Zhou, and Michael G.H. Bell. Pickup and delivery problem with electric vehicles and time windows considering queues. Transportation Research Part C: Emerging Technologies, 167:104829, October 2024. ISSN 0968090X. doi: 10.1016/j.trc.2024. 104829.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Studia Universitatis Babeș-Bolyai Informatica
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
