Skip to main content

Advertisement

Log in

Electric vehicle routing models and solution algorithms in logistics distribution: A systematic review

  • Review Article
  • Published:
Environmental Science and Pollution Research Aims and scope Submit manuscript

Abstract

With the development of green logistics and the promotion of new energy vehicle development policies domestically and abroad, electric vehicles have been put into logistics and distribution as an alternative to traditional fuel vehicles. The Electric Vehicle Routing Problem (EVRP) has attracted widespread attention from the academic community. This paper comprehensively examines the latest research progress on electric vehicle routing models and solution algorithms in logistics and distribution. Firstly briefly introduces EVRP models considering battery losses; secondly, based on the composition of the EVRP objective function and constraints, EVRP models are classified into four types: EVRP considering load and battery life constraints, EVRP with a time window and considering charging strategies, the study of vehicle routing problems for hybrid fleets, and EVRP combined with charging/swapping station location. Then, briefly introduce exact algorithms, traditional heuristics, meta-heuristics, and hybrid algorithms for solving EVRP models. Moreover, it analyzes the main meta-heuristics that are more widely used. Finally, this review points out the development trend of EVRP theoretical methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1

Similar content being viewed by others

Data availability

The datasets generated and/or analyzed during the current study are not publicly available due to the restriction of data but are available from the corresponding author on reasonable request.

References

  • Abdoli B, MirHassani SA, Hooshmand F (2017) Model and algorithm for bi-fuel vehicle routing problem to reduce GHG emissions. Environ Sci Pollut Res 24(27):21610–21624

    Article  CAS  Google Scholar 

  • Almouhanna A, Quintero-Araujo CL, Panadero J, Juan AA, Khosravi B, Ouelhadj D (2019) The location routing problem using electric vehicles with the location routing problem using electric vehicles with constrained distance. Comput Oper Res 115

  • Alamatsaz K, Ahmadi A, Mirzapour Al-e-hashem SMJ (2022) A multiobjective model for the green capacitated location-routing problem considering drivers’ satisfaction and time window with uncertain demand. Environ Sci Pollut Res 29(4):5052–5071

    Article  Google Scholar 

  • Alejandro M, Christelle G, Mendoza JE, Villegas JG (2017) The Electric Vehicle Routing Problem with nonlinear charging function. Transp Res Part B 103:87–110

    Google Scholar 

  • Andelmin J, Bartolini E (2017) An exact algorithm for the green vehicle routing problem. Transp Sci 51(4):1288–130

  • Artmeier A, Haselmayr J, Leucker M, Sachenbacher M (2010) The optimal routing problem in the context of battery-powered electric vehicles.

  • Asamer J, Graser A, Heilmann B, Ruthmair M (2016) Sensitivity analysis for energy demand estimation of electric vehicles. Transp Res Part D Transp Environ 46:182–199

  • Ashkrof P, Correia G, Arem BV (2020) Analysis of the effect of charging needs on battery electric vehicle drivers' route choice behaviour: a case study in the netherlands. Transp Res Part D Transp Environ 78

  • Bakker JJ (2011) Contesting range anxiety: the role of electric vehicle charging infrastructure in the transportation transition

  • Bruglieri M, Pezzella F, Pisacane O, Suraci S (2015) A Variable Neighborhood Search Branching for the Electric Vehicle Routing Problem with Time Windows. Electronic Notes in Discrete Mathematics 47:221–228

    Article  Google Scholar 

  • Chen Y, Li D, Zhang Z, Wahab MIM, Jiang Y (2021) Solving the battery swap station location-routing problem with a mixed fleet of electric and conventional vehicles using a heuristic branch-and-price algorithm with an adaptive selection scheme. Exp Syst Appl 186:115683. https://doi.org/10.1016/j.eswa.2021.115683

  • Cheng Y, Szeto W (2017) Artificial bee colony approach to solving the electric vehicle routing problem. J East Asia Soc Transp Stud

  • Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568–581

  • Conrad RG, Figliozzi MA (2011) The Recharging Vehicle Routing Problem.

  • Davis BA, Figliozzi MA (2013) A methodology to evaluate the competitiveness of electric delivery trucks. Transp Res 49:8–23

    Google Scholar 

  • Dorokhova MF, Ballif C, Wyrsch N (2021) Routing of electric vehicles with intermediary charging stations: a reinforcement learning approach. Front Big Data 4

  • Dündar H, Soysal M, Ömürgönülşen M, Kanellopoulos A (2022) A green dynamic TSP with detailed road gradient dependent fuel consumption estimation. Comput Ind Eng 168:108024

    Article  Google Scholar 

  • Erdelić T, Carić T, Erdelić M, Tišljarić L (2019) Electric vehicle routing problem with single or multiple recharges. Transp Res Procedia 40:217–224

    Article  Google Scholar 

  • Erdelić T, Carić T (2019) A Survey on the Electric Vehicle Routing Problem: Variants and Solution Approaches. J Adv Transp 2019:1–48

    Article  Google Scholar 

  • Erdelić T, Carić T (2022) Goods Delivery with Electric Vehicles: Electric Vehicle Routing Optimization with Time Windows and Partial or Full Recharge. Energies 15(1):285

    Article  Google Scholar 

  • Erdoğan S, Miller-Hooks E (2012) A Green Vehicle Routing Problem. Transp Res Part E 48(1):100–114

    Article  Google Scholar 

  • Felipe Á, Ortuño MT, Righini G, Tirado G (2014) A heuristic approach for the Green Vehicle Routing Problem with multiple technologies and partial recharges. Transp Res Part E 71:111–128

    Article  Google Scholar 

  • Froger A, Mendoza JE, Laporte G, Jabali O (2018) The electric vehicle routing problem with partial charge, nonlinear charging function, and capacitated charging stations. Annual Workshop of the EURO Working Group on Vehicle Routing and Logistics optimization (VeRoLog), Amsterdam, Netherlands

  • Froger A, Mendoza JE, Jabali O, Laporte G (2019) Improved formulations and algorithmic components for the Electric Vehicle Routing Problem with nonlinear charging functions. Comput Oper Res 104:256–294

    Article  Google Scholar 

  • Gao J, Zheng X, Gao F, Tong X, Han Q (2022) Heterogeneous Multitype Fleet Green Vehicle Path Planning of Automated Guided Vehicle with Time Windows in Flexible Manufacturing System. Machines 10(3):197

    Article  Google Scholar 

  • Ge XL, Li ZW (2018) Summary of research on Logistics Distribution Optimization Based on electric vehicle. Practice Understanding Math 48(13):33–42

    Google Scholar 

  • Ge XL, Li ZW, Ge XB (2020) Research on logistics distribution routing optimization with time window considering flexible charging strategy. Control Theory and Application 37(6):9 (Chinese)

    Google Scholar 

  • Genikomsakis KN, Mitrentsis G (2017) A computationally efficient simulation model for estimating energy consumption of electric vehicles in the context of route planning applications. Transp Res Part D Transp Environ 50:98–118

  • Goeke D, Schneider M (2015) Routing a mixed fleet of electric and conventional vehicles. Eur J Oper Res 245(1):81–99

  • Golden B, Assad A, Levy L (1984) The fleet size and mix vehicle routing problem. Comput Oper Res 11(1):49–66

    Article  Google Scholar 

  • Gonçalves F, Cardoso SR, Relvas S (2011) Optimization of a distribution network using electric vehicles: A VRP problem. Proceedings of the IO2011–15 Congresso da associação Portuguesa de Investigação Operacional, Coimbra, Portugal, 18–20

  • Guo F, Yang J, Yang C (2018) Research on electric vehicle routing optimization considering charging strategy and battery loss. Chinese Management Science 26(9):106–118 (Chinese)

    Google Scholar 

  • Guo F, Yang J, Yang C (2019) Research on routing optimization and charging strategy of multi model electric vehicle considering differentiated service time. Chin Manag Sci 27(08):118–128 (Chinese)

    Google Scholar 

  • Guo G, Zhang ZL (2018) Research and progress of electric vehicle routing optimization. Control Decis Making 33(10):1729–1739 (Chinese)

    Google Scholar 

  • Guo Z, Yang L, Jiang X, Sheng G (2017) The electric vehicle routing problem with time windows using genetic algorithm. 2017 IEEE 2nd advanced information technology, Electronic and Automation Control Conference (IAEAC). IEEE

  • Guy D, Fausto E, Stefan I, Michael S (2016) Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows. Oper Res J Oper Res Soc Am 64(6):1388–1405

    Google Scholar 

  • Hiermann G, Puchinger J, Ropke S, Hartl RF (2016) The electric fleet size and mix vehicle routing problem with time windows and recharging stations. Eur J Oper Res 252(3):995–1018

    Article  Google Scholar 

  • 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. Transp Res Part B Methodol 97:102–112

  • Hu XP, Zeng XP, Wang Z (2019) A review of network and distribution management. Syst Sci Math 39(10):1583–1596 (Chinese)

    Google Scholar 

  • Jie WC, Yang J, Yang C (2016) Branch-and-price algorithm for heterogeneous Electric Vehicle Routing Problem. Syst Eng Theory Prac 36(7):1795–1805 (Chinese)

    Google Scholar 

  • Jing L (2014) Transit Bus Scheduling with Limited Energy. Transp Sci 48:521–539

    Article  Google Scholar 

  • Jonathan DA, Pitu BM (2014) Online routing and battery reservations for electric vehicles with swappable batteries. Transp Res Part B 70:285–302

    Article  Google Scholar 

  • Juan AA, Goentzel J, Bektaş T (2014) Routing fleets with multiple driving ranges: is it possible to use greener fleet configurations? Appl Soft Comput J 21:84–94

  • Kancharla SR, Ramadurai G (2020) Electric Vehicle Routing Problem with nonlinear charging and load-dependent discharging. Expert Syst Appl 160:113714

    Article  Google Scholar 

  • Karakatič S (2020) Optimizing nonlinear charging times of electric vehicle routing with genetic algorithm. Expert Syst Appl 164

  • Keskin M, Bülent C (2018) A matheuristic method for the Electric Vehicle Routing Problem with time windows and fast chargers. Comput Oper Res 100:172–188

    Article  Google Scholar 

  • Keskin M, Çatay B (2016) Partial recharge strategies for the electric vehicle routing problem with time windows. Transp Res Part C Emerg Technol 65:111–127

  • Keskin M, Çatay B, Laporte G (2021) A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations. Comput Oper Res 125:105060

    Article  Google Scholar 

  • Koç Ç, Jabali O, Mendoza JE, Laporte G (2018) The electric vehicle routing problem with shared charging stations. Int Trans Oper Res

  • Kullman N, Goodson J, Mendoza JE (2017) Electric vehicle routing with uncertain charging station availability & dynamic decision making. INFORMS Transp Logist Soc Trienn Conf

  • Lee C (2020) An exact algorithm for the electric-vehicle routing problem with nonlinear charging time. J Oper Res Soc 1–24

  • Li DC, Chen YR, Zhang ZC (2021a) A branch-and-price algorithm for Electric Vehicle Routing Problem with time windows and mixed fleet. Syst Eng Theory Pract 41(4):995–1009 (Chinese)

    Google Scholar 

  • Li DC, Chen YR, Zhang ZC (2021b) Research on hybrid vehicle routing problem of electric vehicle and fuel vehicle based on branch pricing algorithm. Syst Eng Theory Pract 41(04):995–1009 (Chinese)

    Google Scholar 

  • Li J, Zhang JH (2014) Vehicle routing problem with time window based on carbon emission and speed optimization. Syst Eng Theory Pract 34(12):3063–3072 (Chinese)

    Google Scholar 

  • Li WJ, Bi YZ, Zhu XF, Yuan CA, Zhang XB (2016) Hybrid swarm intelligent parallel algorithm research based on multi-core clusters. Microprocess Microsyst 47:151–160

  • Li Y, Zhang PW, Wu YF (2020a) Vehicle configuration and route optimization model of electric vehicle/traditional vehicle hybrid fleet. J Syst Manag 29(03):522–531

    Google Scholar 

  • Li Z, Cao L, Li H, Wang R, Muren M (2020) Research on optimization of electric vehicle routing problem with time window. IEEE Access PP(99):1–1

  • Li Y, Soleimani H, Zohal M (2019) An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. J Clean Prod 227:1161–1172

  • Lin J, Zhou W, Wolfson O (2016) Electric Vehicle Routing Problem. Transp Res Proc 12:508–521

    Google Scholar 

  • Liu J, Lin G, Huang S, Zhou Y, Rehtanz C, Li Y (2022) Collaborative ev routing and charging scheduling with power distribution and traffic networks interaction. IEEE Trans Power Syst. https://doi.org/10.1109/TPWRS.2022.3142256

  • Mancini S (2017) The Hybrid Vehicle Routing Problem. Transp Res Part C 78:1–12

    Article  Google Scholar 

  • Mao H, Shi J, Zhou Y (2020) The Electric Vehicle Routing Problem With Time Windows and Multiple Recharging Options. IEEE Access 8:64–75

    Google Scholar 

  • Martinez-Lao J, Montoya FG, Montoya MG, Manzano-Agugliaro F (2017) Electric vehicles in Spain: An overview of charging systems. Renew Sust Energ Rev 77:970–983

  • Masmoudi MA, Hosny M, Demir E, Genikomsakis KN, Cheikhrouhou N (2018) The dial-a-ride problem with electric vehicles and battery swapping stations. Transp Res Part E Logist Transp Rev 118:392–420

  • Mavrovouniotis M, Menelaou C, Timotheou S, Ellinas G, Polycarpou MM (2020) A benchmark test suite for the electric capacitated vehicle routing problem. In: 2020 IEEE Congress on Evolutionary Computation (CEC). IEEE. pp 1–8. https://doi.org/10.1109/CEC48606.2020.9185753

  • Morteza M, Amir P, Babak G (2006) Application of Genetic Algorithm for optimization of control strategy in parallel hybrid electric vehicles. J Franklin Inst, 343(4)

  • Omidvar A, Tavakkoli-Moghaddam R (2012) Sustainable vehicle routing: Strategies for congestion management and refueling scheduling. In: Energy Conference & Exhibition. IEEE, pp 1089–1094

  • Pelletier S, Jabali O, Laporte G (2019) The electric vehicle routing problem with energy consumption uncertainty. Transp Res Part B Methodol 126

  • Penna P, Afsar HM, Prins C, Prodhon C (2016) A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations. IFAC-Papers OnLine 49( 12):955–960

  • Philippe L, Cedric DC, Joeri VM, Cathy M, Wouter V, Thierry C (2015) Conventional, hybrid, or electric vehicles: which technology for an urban distribution centre? Sci World J 2015:302867

  • Pinto K, Bansal HO, Goyal P (2022) A comprehensive assessment of the techno-socio-economic research growth in electric vehicles using bibliometric analysis. Environ Sci Pollut Res 29(2):1788–1806

    Article  Google Scholar 

  • Portela BMO, Bernardino HS, Goncalves LB, Soares SSRF (2021) Cheapest insertion and disruption of routes operators for solving multi-depot electric vehicle location routing problem with time windows and battery swapping via GRASP and RVND. IEEE, pp 2133–2140. https://doi.org/10.1109/CEC45853.2021.9504799

  • Preis H, Frank S, Nachtigall K (2014) Energy-optimized routing of electric vehicles in urban delivery Systems. Springer, Procof Operations Research. Cham, pp 583–588

    Google Scholar 

  • Ren X, Huang H, Feng S, Liang G (2020) An improved Variable Neighborhood Search for bi-objective mixed-energy fleet vehicle routing problem. J Clean Prod, 124–155

  • Pelletier S, Jabali O, Laporte G, Veneroni M (2017) Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models. Transp Res Part B: Methodol 103:158–187

  • Salhi S, Graham KR (1989) The effect of ignoring routes when locating depots. Eur J Oper Res 39:150–156

    Article  Google Scholar 

  • Sassi O, Cherif WR, Oulamara A (2014) Vehicle routing problem with mixed fleet of conventional and heterogenous electric vehicles and time dependent charging costs

  • Sassi O, Cherif-Khettaf WR, Oulamara A (2015) Multi-start iterated local search for the mixed fleet vehicle routing problem with heterogenous Electric Vehicles. In: Ochoa G, Chicano F (eds) Evolutionary computation in combinatorial optimization. EvoCOP 2015. Lecture notes in computer science, vol 9026. Springer, Cham. https://doi.org/10.1007/978-3-319-16468-7_12

  • Schiffer M, Walther G (2018) Strategic planning of electric logistics fleet networks: A robust location-routing approach. Omega 80:31–42

    Article  Google Scholar 

  • Schiffer M, Schneider M, Walther G, Laporte G (2019) Vehicle routing and location-routing with intermediate stops: a review. Transp Sci 53(2):319–343

  • Schneider M, Stenger A, Goeke D (2014) The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations. Transp Sci 48(4):500–520

    Article  Google Scholar 

  • Sherzod B, Francis GP (2016) Exponentially weighted moving average charts for correlated multivariate Poisson processes. Commun Stat Theory Methods 10:46

    Google Scholar 

  • Sweda T, Dolinskaya M, Klabjan D (2017) Adaptive Routing and Recharging Policies for Electric Vehicles. Transp Sci 51(4):1326–1348

    Article  Google Scholar 

  • Tahami H, Rabadi G, Haouari M (2020) Exact approaches for routing capacitated electric vehicles. Transp Res Part E Logist Transp Rev 144:102126

  • Verma A (2018) Electric Vehicle Routing Problem with time windows, recharging stations and battery swapping stations. EURO J Transp Logistics 7(4):415–451

    Article  Google Scholar 

  • Wang Y, Bi J, Wei G, Zhao X (2018) Optimising route choices for the travelling and charging of battery electric vehicles by considering multiple objectives. Transp Res Part D Transp Environ 64(OCT.):246–261

  • Wang LG, Hong Y, Zhao FQ, Yu DM (2008) A hybrid optimization algorithm of Simulated Annealing and Particle Swarm Optimization. Comput Simul 11:179–182

    Google Scholar 

  • Wang QY, Li Y, Li H (2019) Research on location routing problem of electric vehicle replacement station with soft time window. Ind Eng Manag 24(3):99–106. https://doi.org/10.19495/j.cnki.1007-5429.2019.03.013. (Chinese)

  • Wang SY, Zhao QH, Xia GP (2000) Research on positioning transportation route arrangement in integrated logistics management system. J Manag Sci, 3(2)

  • Worley O, Klabjan D, Sweda TM (2016) Simultaneous vehicle routing and charging station siting for commercial Electric Vehicles. In: 2012 IEEE international electric vehicle conference. IEEE.

  • Xiao Y, Zhang Y, Kaku I ,Kang, R , Pan, X (2021) Electric vehicle routing problem: a systematic review and a new comprehensive model with nonlinear energy recharging and consumption. Renew Sustain Energy Rev 151(9):111567

  • Xiao YY, Konak A (2016) A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem. J Clean Prod 167(nov.20):1450–1463

  • Xin Q, Chen Z, Len ZY, Lu Y (2020) Electric vehicle routing planning and charging navigation strategy based on real-time traffic information. Chin J Electr Eng 40(02):534–550

    Google Scholar 

  • Xing LN, Chen YW, Yang KW (2011) Multi-population interactive coevolutionary algorithm for flexible job shop scheduling problems. Comput Optim Appl 48(1):139–155

  • Xue GQ, Ge XL (2019) A review of research on vehicle routing problem of electric vehicle. Practice and Knowledge of Mathematics 49(14):150–159 (Chinese)

    Google Scholar 

  • Yang H, Yang S, Xu Y (2015a) Electric vehicle route optimization considering time-of-use electricity price by learnable partheno-Genetic Algorithm. IEEE Trans on Smart Grid 6(2):657–666

    Article  Google Scholar 

  • Yang J, Feng PX, Sun H, Yang C (2015b) Research on site selection and route optimization of electric vehicle logistics distribution system. Chin Manag Sci 23(09):87–96 (Chinese)

    CAS  Google Scholar 

  • Yang L, Hao CX, Tang RH (2019) Location models of charging and battery swapping facilities based on electric vehicles. Syst Eng Theory Practice 39(7). (Chinese)

  • Yang J, Sun H (2015) Battery swap station location-routing problem with capacitated electric vehicles. Comput Oper Res 55:217–232

  • Ying Z, Baltabay A, Zhou Y (2018) Shortest feasible routings with partial charging for battery-powered electric vehicles in smart cities. Pervasive Mob Comput 50:S1574119218302396

    Google Scholar 

  • Zhang JH, Nan Y (2016) Electric vehicle charging routing planning under the influence of traffic information. Computer Application 36(S2):282–285

    Google Scholar 

  • Zhang M, Yang C, Yang C, Ma YF (2008) Research on combined location-routing problems in integrated hazardous materials logistics systems. J Manag Sci 11(01):59–67 (Chinese)

  • Zhang S, Chen M, Zhang WA (2019) A novel location-routing problem in electric vehicle transportation with stochastic demands. J Clean Prod 221(JUN.1):567–581

  • Zhang S, Gajpal Y, Appadoo S (2018) Electric Vehicle Routing Problem with recharging stations for minimizing energy consumption. Int J Prod Econ 203:404–413

    Article  Google Scholar 

  • Zhou XC, Zhou KJ, Wang L (2021a) Overview of green vehicle routing model and solution algorithm in logistics distribution. Syst Eng Theory Practice 41(1):213–230

    Google Scholar 

  • Zhou Y, Huang J, Shi J, Wang R, Huang K (2021) The electric vehicle routing problem with partial recharge and vehicle recycling. Complex Intell Syst

  • Zhu X, Yan R, Huang Z (2020) Logistic optimization for multi depots loading capacitated Electric Vehicle Routing Problem from low carbon perspective. IEEE Access 8:34–47

    Google Scholar 

  • Zou C, Manzie C, Nešić D (2018) Model predictive control for lithium-ion battery optimal charging. IEEE/ASME Trans Mechatron 23(2):947–957

    Article  Google Scholar 

  • Zündorf T (2014) Electric vehicle routing with realistic recharging models (Master's thesis). Karlsruhe Institute of Technology, Karlsruhe, Germany, pp 15–20

  • Zuo X, Xiao Y, Zhu C (2018) A linear MIP model for the electric vehicle routing problem with time windows considering linear charging. In: 2018 annual reliability and maintainability symposium. pp 1–5. https://doi.org/10.1109/RAM.2018.8463021

Download references

Funding

The authors gratefully acknowledge the National Social Science Foundation of China (Grant No. 19FJYB043) and the project of Innovation Strategy Research Program of Fujian Province (Grant No. 2021R0019).

Author information

Authors and Affiliations

Authors

Contributions

Wenjie He: Conceptualization, Literature curation, and Writing—Original Draft.

Chong Ye: Writing—Reviewing and Editing; Supervisor.

Hanqi Chen: Methodology and Formal analysis.

Corresponding author

Correspondence to Hanqi Chen.

Ethics declarations

Ethics approval and consent to participate

Not applicable.

Consent for publication

Not applicable.

Competing interests

The authors declare that they have no competing interests.

Additional information

Responsible Editor: Philippe Garrigues

Publisher's note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ye, C., He, W. & Chen, H. Electric vehicle routing models and solution algorithms in logistics distribution: A systematic review. Environ Sci Pollut Res 29, 57067–57090 (2022). https://doi.org/10.1007/s11356-022-21559-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11356-022-21559-2

Keywords

Navigation