A review on the electric vehicle routing problems: Variants and algorithms

Abstract

Over the past decade, electric vehicles (EVs) have been considered in a growing number of models and methods for vehicle routing problems (VRPs). This study presents a comprehensive survey of EV routing problems and their many variants. We only consider the problems in which each vehicle may visit multiple vertices and be recharged during the trip. The related literature can be roughly divided into nine classes: Electric traveling salesman problem, green VRP, electric VRP, mixed electric VRP, electric location routing problem, hybrid electric VRP, electric dial-a-ride problem, electric two-echelon VRP, and electric pickup and delivery problem. For each of these nine classes, we focus on reviewing the settings of problem variants and the algorithms used to obtain their solutions.

Graphical abstract

Keywords

electric vehicles / routing / recharging stations / exact algorithms / metaheuristics

References

[1] Affi M, Derbel H, Jarboui B (2018). Variable neighborhood search algorithm for the green vehicle routing problem. International Journal of Industrial Engineering Computations, 9(2): 195–204

[2] Afroditi A, Boile M, Theofanis S, Sdoukopoulos E, Margaritis D (2014). Electric vehicle routing problem with industry constraints: Trends and insights for future research. Transportation Research Procedia, 3: 452–459

[3] Al-Kanj L, Nascimento J, Powell W B (2020). Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles. European Journal of Operational Research, 284(3): 1088–1106

[4] Andelmin J, Bartolini E (2017). An exact algorithm for the green vehicle routing problem. Transportation Science, 51(4): 1288–1303

[5] Andelmin J, Bartolini E (2019). A multi-start local search heuristic for the green vehicle routing problem based on a multigraph reformulation. Computers & Operations Research, 109: 43–63

[6] Archetti C, Speranza M G (2012). Vehicle routing problems with split deliveries. International Transactions in Operational Research, 19(1–2): 3–22

[7] Baldacci R, Christofides N, Mingozzi A (2008). An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming, 115(2): 351–385

[8] Baldacci R, Mingozzi A, Roberti R (2011). New route relaxation and pricing strategies for the vehicle routing problem. Operations Research, 59(5): 1269–1283

[9] Baldacci R, Mingozzi A, Roberti R, Wolfler Calvo R (2013). An exact algorithm for the two-echelon capacitated vehicle routing problem. Operations Research, 61(2): 298–314

[10] Beasley J E (1983). Route first–Cluster second methods for vehicle routing. Omega, 11(4): 403–408

[11] Bongiovanni C, Kaspi M, Geroliminis N (2019). The electric autonomous dial-a-ride problem. Transportation Research Part B: Methodological, 122: 436–456

[12] Braekers K, Ramaekers K, van Nieuwenhuyse I (2016). The vehicle routing problem: State-of-the-art classification and review. Computers & Industrial Engineering, 99: 300–313

[13] Bräysy O, Gendreau M (2005a). Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Science, 39(1): 104–118

[14] Bräysy O, Gendreau M (2005b). Vehicle routing problem with time windows, part II: Metaheuristics. Transportation Science, 39(1): 119–139

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

[16] Campbell A M, Wilson J H (2014). Forty years of periodic vehicle routing. Networks, 63(1): 2–15

[17] Clarke G, Wright J W (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4): 568–581

[18] Corberán A, Prins C (2010). Recent results on Arc Routing Problems: An annotated bibliography. Networks, 56(1): 50–69

[19] Cordeau J F, Laporte G (2007). The dial-a-ride problem: Models and algorithms. Annals of Operations Research, 153(1): 29–46

[20] Cortés-Murcia D L, Prodhon C, Murat Afsar H (2019). The electric vehicle routing problem with time windows, partial recharges and satellite customers. Transportation Research Part E: Logistics and Transportation Review, 130: 184–206

[21] Crevier B, Cordeau J F, Laporte G (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2): 756–773

[22] da Silva R F, Urrutia S (2010). A general VNS heuristic for the traveling salesman problem with time windows. Discrete Optimization, 7(4): 203–211

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

[24] Dascioglu B G, Tuzkaya G (2019). A literature review for hybrid vehicle routing problem. In: Calisir F, Cevikcan E, Camgoz Akdag H, eds. Industrial Engineering in the Big Data Era. Cham: Springer, 249–257

[25] Desaulniers G (2010). Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Operations Research, 58(1): 179–192

[26] Desaulniers G, Errico F, Irnich S, Schneider M (2016). Exact algorithms for electric vehicle-routing problems with time windows. Operations Research, 64(6): 1388–1405

[27] Doppstadt C, Koberstein A, Vigo D (2016). The hybrid electric vehicle – traveling salesman problem. European Journal of Operational Research, 253(3): 825–842

[28] Dror M (2000). Arc Routing: Theory, Solutions and Applications. Springer

[29] Eksioglu B, Vural A V, Reisman A (2009). The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57(4): 1472–1483

[30] Environmental Protection Agency (2018). Inventory of US greenhouse gas emissions and sinks: 1990–2016.

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

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

[33] Escobar J W, Linfati R, Baldoquin M G, Toth P (2014). A granular variable tabu neighborhood search for the capacitated location-routing problem. Transportation Research Part B: Methodological, 67: 344–356

[34] Ester M, Kriegel H P, Sander J, Xu X (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. AAAI Press, 96: 226–231

[35] Eusuff M, Lansey K, Pasha F (2006). Shuffled frog-leaping algorithm: A memetic meta-heuristic for discrete optimization. Engineering Optimization, 38(2): 129–154

[36] Felipe A, Ortuño M T, Righini G, Tirado G (2014). 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

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

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

[39] Goeke D, Schneider M (2015). Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research, 245(1): 81–99

[40] Golden B L, Raghavan S, Wasil E A (2008). The Vehicle Routing Problem: Latest Advances and New Challenges. Boston, MA: Springer

[41] Granada-Echeverri M, Cubides L C, Bustamante J O (2020). The electric vehicle routing problem with backhauls. International Journal of Industrial Engineering Computations, 11(1): 131–152

[42] Gutin G, Punnen A P (2007). The Traveling Salesman Problem and Its Variations. Springer

[43] Hiermann G, Hartl R F, Puchinger J, Vidal T (2019). Routing a mix of conventional, plug-in hybrid, and electric vehicles. European Journal of Operational Research, 272(1): 235–248

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

[45] Ho S C, Szeto W Y, Kuo Y H, Leung J M Y, Petering M, Tou T W H (2018). A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological, 111: 395–421

[46] Hof J, Schneider M, Goeke D (2017). 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

[47] International Energy Agency (2018). Global EV outlook 2018.

[48] Jepsen M, Spoorendonk S, Ropke S (2013). A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Transportation Science, 47(1): 23–37

[49] Jie W, Yang J, Zhang M, Huang Y (2019). 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

[50] Kancharla S R, Ramadurai G (2018). An adaptive large neighborhood search approach for electric vehicle routing with load-dependent energy consumption. Transportation in Developing Economies, 4(2): 10

[51] Kempton W, Letendre S E (1997). Electric vehicles as a new power source for electric utilities. Transportation Research Part D: Transport and Environment, 2(3): 157–175

[52] Keskin M, Çatay B (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 65: 111–127

[53] Keskin M, Çatay B (2018). A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Computers & Operations Research, 100: 172–188

[54] Koç Ç, Jabali O, Mendoza J E, Laporte G (2019). The electric vehicle routing problem with shared charging stations. International Transactions in Operational Research, 26(4): 1211–1243

[55] Koç Ç, Karaoglan I (2016). The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing, 39: 154–164

[56] Küçükoğlu I, Dewil R, Cattrysse D (2019). Hybrid simulated annealing and tabu search method for the electric travelling salesman problem with time windows and mixed charging rates. Expert Systems with Applications, 134: 279–303

[57] Leggieri V, Haouari M (2017). A practical solution approach for the green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 104: 97–112

[58] Li C, Ding T, Liu X, Huang C (2018). An electric vehicle routing optimization model with hybrid plug-in and wireless charging systems. IEEE Access, 6: 27569–27578

[59] Li Y, Soleimani H, Zohal M (2019). An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. Journal of Cleaner Production, 227: 1161–1172

[60] Lin J, Zhou W, Wolfson O (2016). Electric vehicle routing problem. Transportation Research Procedia, 12: 508–521

[61] Liu M, Luo Z, Lim A (2015). A branch-and-cut algorithm fora realistic dial-a-ride problem. Transportation Research Part B: Methodological, 81(Part1): 267–288

[62] Liu T, Luo Z, Qin H, Lim A (2018). A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints. European Journal of Operational Research, 266(2): 487–497

[63] Luo Z, Liu M, Lim A (2019). A two-phase branch-and-price-and-cut for a dial-a-ride problem in patient transportation. Transportation Science, 53(1): 113–130

[64] Luo Z, Qin H, Che C H, Lim A (2015). On service consistency in multi-period vehicle routing. European Journal of Operational Research, 243(3): 731–744

[65] Luo Z, Qin H, Zhu W, Lim A (2017). Branch and price and cut for the split-delivery vehicle routing problem with time windows and linear weight-related cost. Transportation Science, 51(2): 668–687

[66] Macrina G, Di Puglia Pugliese L, Guerriero F, Laporte G (2019a). The green mixed fleet vehicle routing problem with partial battery recharging and time windows. Computers & Operations Research, 101: 183–199

[67] Macrina G, Laporte G, Guerriero F, Di Puglia Pugliese L (2019b). An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows. European Journal of Operational Research, 276(3): 971–982

[68] Mancini S (2017). The hybrid vehicle routing problem. Transportation Research Part C: Emerging Technologies, 78: 1–12

[69] Masmoudi M A, Hosny M, Demir E, Genikomsakis K N, Cheikhrouhou N (2018). The dial-a-ride problem with electric vehicles and battery swapping stations. Transportation Research Part E: Logistics and Transportation Review, 118: 392–420

[70] Mladenović N, Hansen P (1997). Variable neighborhood search. Computers & Operations Research, 24(11): 1097–1100

[71] Mladenović N, Todosijević R, Urošević D (2012). An efficient GVNS for solving traveling salesman problem with time windows. Electronic Notes in Discrete Mathematics, 39: 83–90

[72] Molenbruch Y, Braekers K, Caris A (2017). Typology and literature review for dial-a-ride problems. Annals of Operations Research, 259(1–2): 295–325

[73] Montoya A, Guéret C, Mendoza J E, Villegas J G (2016). A multi-space sampling heuristic for the green vehicle routing problem. Transportation Research Part C: Emerging Technologies, 70: 113–128

[74] Montoya A, Guéret C, Mendoza J E, Villegas J G (2017). The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological, 103: 87–110

[75] Murakami K (2017). A new model and approach to electric and diesel-powered vehicle routing. Transportation Research Part E: Logistics and Transportation Review, 107: 23–37

[76] Murakami K (2018). Formulation and algorithms for route planning problem of plug-in hybrid electric vehicles. Operational Research, 18(2): 497–519

[77] Nagy G, Salhi S (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2): 649–672

[78] Nagy G, Wassan N A, Speranza M G, Archetti C (2015). The vehicle routing problem with divisible deliveries and pickups. Transportation Science, 49(2): 271–294

[79] Nejad M M, Mashayekhy L, Grosu D, Chinnam R B (2017). Optimal routing for plug-in hybrid electric vehicles. Transportation Science, 51(4): 1304–1325

[80] Pelletier S, Jabali O, Laporte G (2019). The electric vehicle routing problem with energy consumption uncertainty. Transportation Research Part B: Methodological, 126: 225–255

[81] Perboli G, Tadei R, Vigo D (2011). The two-echelon capacitated vehicle routing problem: Models and math-based heuristics. Transportation Science, 45(3): 364–380

[82] Prins C, Lacomme P, Prodhon C (2014). Order-first split-second methods for vehicle routing problems: A review. Transportation Research Part C: Emerging Technologies, 40: 179–200

[83] Prodhon C, Prins C (2014). A survey of recent research on location-routing problems. European Journal of Operational Research, 238(1): 1–17

[84] Roberti R, Wen M (2016). The electric traveling salesman problem with time windows. Transportation Research Part E: Logistics and Transportation Review, 89: 32–52

[85] Ropke S, Pisinger D (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4): 455–472

[86] Sassi O, Oulamara A (2017). Electric vehicle scheduling and optimal charging problem: Complexity, exact and heuristic approaches. International Journal of Production Research, 55(2): 519–535

[87] Savelsbergh M W P, Sol M (1995). The general pickup and delivery problem. Transportation Science, 29(1): 17–29

[88] Schiffer M, Walther G (2017). The electric location routing problem with time windows and partial recharging. European Journal of Operational Research, 260(3): 995–1013

[89] Schneider F, Thonemann U W, Klabjan D (2018). Optimization of battery charging and purchasing at electric vehicle battery swap stations. Transportation Science, 52(5): 1211–1234

[90] Schneider M, Stenger A, Goeke D (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(4): 500–520

[91] Schneider M, Stenger A, Hof J (2015). An adaptive VNS algorithm for vehicle routing problems with intermediate stops. OR-Spektrum, 37(2): 353–387

[92] Schneider M, Drexl M (2017). A survey of the standard location-routing problem. Annals of Operations Research, 259(1−2): 389–414

[93] Shao S, Guan W, Bi J (2018). Electric vehicle-routing problem with charging demands and energy consumption. IET Intelligent Transport Systems, 12(3): 202–212 doi:10.1049/iet-its.2017.0008

[94] Shi J, Gao Y, Yu N (2018). Routing electric vehicle fleet for ride-sharing. In: 2nd IEEE Conference on Energy Internet and Energy System Integration (EI2). Beijing, 1–6

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

[96] Sweda T M, Dolinskaya I S, Klabjan D (2017a). Adaptive routing and recharging policies for electric vehicles. Transportation Science, 51(4): 1326–1348

[97] Sweda T M, Dolinskaya I S, Klabjan D (2017b). Optimal recharging policies for electric vehicles. Transportation Science, 51(2): 457–479

[98] Toth P, Vigo D (2002). The Vehicle Routing Problem. Philadelphia: Society for Industrial and Applied Mathematics

[99] Toth P, Vigo D (2003). The granular tabu search and its application to the vehicle-routing problem. INFORMS Journal on Computing, 15(4): 333–346

[100] Verma A (2018). Electric vehicle routing problem with time windows, recharging stations and battery swapping stations. EURO Journal on Transportation and Logistics, 7(4): 415–451

[101] Wang Y, Assogba K, Fan J, Xu M, Liu Y, Wang H (2019). Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost. Journal of Cleaner Production, 232: 12–29

[102] Wen M, Linde E, Ropke S, Mirchandani P, Larsen A (2016). An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem. Computers & Operations Research, 76: 73–83

[103] Yang J, Sun H (2015). Battery swap station location-routing problem with capacitated electric vehicles. Computers & Operations Research, 55: 217–232

[104] Yavuz M (2017). An iterated beam search algorithm for the green vehicle routing problem. Networks, 69(3): 317–328

[105] Yavuz M, Çapar I (2017). Alternative-fuel vehicle adoption in service fleets: Impact evaluation through optimization modeling. Transportation Science, 51(2): 480–493

[106] Yu M, Jin X, Zhang Z, Qin H, Lai Q (2019a). The split-delivery mixed capacitated arc-routing problem: Applications and a forest-based tabu search approach. Transportation Research Part E: Logistics and Transportation Review, 132: 141–162

[107] Yu V F, Redi A A N P, Hidayat Y A, Wibowo O J (2017). A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 53: 119–132

[108] Yu Y, Wang S, Wang J, Huang M (2019b). A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows. Transportation Research Part B: Methodological, 122: 511–527

[109] Zhang S, Chen M, Zhang W (2019). A novel location-routing problem in electric vehicle transportation with stochastic demands. Journal of Cleaner Production, 221: 567–581

[110] Zhang S, Gajpal Y, Appadoo S S (2018a). A meta-heuristic for capacitated green vehicle routing problem. Annals of Operations Research, 269(1): 753–771

[111] Zhang S, Gajpal Y, Appadoo S S, Abdulkader M M S (2018b). Electric vehicle routing problem with recharging stations for minimizing energy consumption. International Journal of Production Economics, 203: 404–413

[112] Zhang Z, Che O, Cheang B, Lim A, Qin H (2013). A memetic algorithm for the multiperiod vehicle routing problem with profit. European Journal of Operational Research, 229(3): 573–584

[113] Zhang Z, Qin H, Zhu W, Lim A (2012). The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach. European Journal of Operational Research, 220(2): 295–304

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

[115] Zhen L, Xu Z, Ma C, Xiao L (2020). Hybrid electric vehicle routing problem with mode selection. International Journal of Production Research, 58(2): 562–576

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

Acknowledgments

This study was written in early 2020, when the first author was infected with COVID-19. Fortunately, he received timely free treatment and recovered in time to submit this review paper. We are grateful to the Chinese government and all the people who supported the first author.

Open Access

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

RIGHTS & PERMISSIONS

2021 The Author(s) 2021. This article is published with open access at link.springer.com and journal.hep.com.cn