A review on the electric vehicle routing problems

Yıl 2023, Cilt: 29 Sayı: 8, 855 - 869, 31.12.2023

Can Berk Kalaycı , Yusuf Yılmaz

Öz

The Electric Vehicle Routing Problem (EVRP) is an extension of the Vehicle Routing Problem (VRP), wherein electric vehicles (EVs) are utilized instead of internal combustion engine vehicles (ICEVs). Electric vehicles have a limited driving range due to their battery capacity and require recharging to complete their routes. Charging can take place at any battery level and can be done up to the battery capacity. Furthermore, the charging speed may vary depending on the technical infrastructure of the charging station (CS). In certain real-life applications, battery swap stations (BSSs) are used in conjunction with charging stations. This study specifically focuses on articles that discuss the use of electric vehicles in logistics activities, where they are charged during the route or through battery swapping. Firstly, the electric vehicle routing problem is introduced, explaining the evolution from the vehicle routing problem to the electric vehicle routing problem. Subsequently, a mathematical model for the electric vehicle routing problem is presented. The literature on the electric vehicle routing problem is then summarized using data and visuals, and classified based on different characteristics such as assumptions, constraints, problem types, and solution approaches. The emphasis is placed on the notable aspects and solution approaches within each category. Finally, future research opportunities are summarized.

Anahtar Kelimeler

Electric vehicle routing problem, Heuristic algorithms, Literature review

Elektrikli araç rotalama problemleri üzerine bir literatür incelemesi

Öz

Elektrikli Araç Rotalama Problemi (EARP), içten yanmalı motorlu araçların yerine elektrikli araçların (EA) kullanıldığı Araç Rotalama Problemi'nin (ARP) bir genişlemesidir. Elektrikli araçlar, pil kapasitesi nedeniyle sınırlı bir menzile sahiptir ve rotayı tamamlamak için şarj edilmeleri gerekmektedir. Şarj, pil seviyesine bağlı olarak ve pil kapasitesine kadar herhangi bir miktarda gerçekleştirilebilir. Ayrıca, şarj istasyonunun (Şİ) teknik altyapısına bağlı olarak şarj hızı değişebilir. Gerçek hayatta bazı uygulamalarda, şarj istasyonları yanında pil değiştirme istasyonları (PDI) kullanıldığı durumlar bulunmaktadır. Bu çalışma sadece lojistik faaliyetlerde elektrikli araçların kullanıldığı ve rota üzerinde şarj edildiği veya pil değiştirme yöntemiyle şarj edildiği makaleleri ele almaktadır. İlk olarak, elektrikli araç rota problemi tanıtılmış ve araç rota probleminden elektrikli araç rota problemine geçişin evrimi açıklanmıştır. Ardından, elektrikli araç rota problemi için matematiksel bir model sunulmuştur. Sonra, elektrikli araç rota problemi literatürü, veriler ve görseller kullanılarak özetlenmiş ve varsayımlar, kısıtlamalar, problem tipleri ve çözüm yaklaşımları gibi farklı özelliklere göre sınıflandırılmıştır. Odak noktası, her sınıfa dahil olan önemli yönler ve çözüm yaklaşımları üzerindedir. Son olarak, gelecekteki araştırma fırsatları özetlenmiştir.

Anahtar Kelimeler

Elektrikli araç rotalama problemi, Sezgisel algoritmalar, Literatür incelemesi

Kaynakça

• [1] Hill N, Amaral S, Price SM, Nokes T, Bates J, Helms H, Fehrenbach H, Biemann K, Abdalla N, Jöhrens J, Cotton E, German L, Harris A, Ziem-Milojevic S, Haye S, Bauen C S a A. “Determining the environmental impacts of conventional and alternatively fuelled vehicles through LCA”. European Commission, Report, ED11344, 2020.
• [2] Nesterova N, Quak H. “State of the art of the electric freight vehicles implementation in city logistics-Update 2015”. Report, EU/321622, 2015.
• [3] Nesterova N, Quak H, Balm S, Roche-Ceraso I, Tretvik T. “State of the art of the electric freight vehicles implementation in city logistics”. E. Comission, Report, EU/321622, 2013.
• [4] Schiffer M, Walther G. “The electric location routing problem with time windows and partial recharging”. European Journal of Operational Research, 260(3), 995-1013, 2017.
• [5] Pelletier S, Jabali O, Laporte G. “50th Anniversary ınvited article goods distribution with electric vehicles: review and research perspectives”. Transportation Science, 50(1), 3-22, 2016.
• [6] Davis B A, Figliozzi M A. “A methodology to evaluate the competitiveness of electric delivery trucks”. Transportation Research Part E-Logistics and Transportation Review, 49(1), 8-23, 2013.
• [7] Afroditi A, Boile M, Theofanis S, Sdoukopoulos E, Margaritis D. “Electric vehicle routing problem with industry constraints: trends and insights for future research”. 17th Meeting of the Euro Working Group on Transportation (Ewgt2014), Sevilla, Spain, 02-04 July 2014.
• [8] Erdoğan S, Miller-Hooks E. “A Green vehicle routing problem”. Transportation Research Part E: Logistics and Transportation Review, 48(1), 100-114, 2012.
• [9] Schneider M, Stenger A, Goeke D. “The electric vehiclerouting problem with time windows and recharging stations”. Transportation Science, 48(4), 500-520, 2014.
• [10] Yilmaz Y, Kalayci C B. “Variable neighborhood search algorithms to solve the electric vehicle routing problem with simultaneous pickup and delivery”. Mathematics, 10(17), 1-24, 2022.
• [11] Xiao Y Y, Zhang Y, Kaku I, Kang R, Pan X. “Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption”. Renewable & Sustainable Energy Reviews, 151, 1-21, 2021.
• [12] Qin H, Su X X, Ren T, Luo Z X. “A review on the electric vehicle routing problems: Variants and algorithms”. Frontiers of Engineering Management, 8(3), 370-389, 2021.
• [13] Erdelić T, Carić T. “A survey on the electric vehicle routing problem: variants and solution approaches”. Journal of Advanced Transportation, 2019, 1-48, 2019.
• [14] Abid M, Tabaa M, Chakir A, Hachimi H. “Routing and charging of electric vehicles: Literature review”. Energy Reports, 8, 556-578, 2022.
• [15] Agrawal S, Zheng H, Peeta S, Kumar A. “Routing aspects of electric vehicle drivers and their effects on network performance”. Transportation Research Part D-Transport and Environment, 46, 246-266, 2016.
• [16] De Cauwer C, Verbeke W, Coosemans T, Faid S, Van Mierlo J. “A data-driven method for energy consumption prediction and energy-efficient routing of electric vehicles in real-world conditions”. Energies,10(5), 1-18, 2017.
• [17] Genikomsakis K N, Mitrentsis G. “A computationally efficient simulation model for estimating energy consumption of electric vehicles in the context of route planning applications”. Transportation Research Part D: Transport and Environment, 50, 98-118, 2017.
• [18] Larsson V, Mårdh L J, Egardt B, Karlsson S. “Commuter route optimized energy management of hybrid electric vehicles”. IEEE transactions on intelligent transportation systems, 15(3), 1145-1154, 2014.
• [19] Tianheng F, Lin Y, Qing G, Yanqing H, Ting Y, Bin Y. “A supervisory control strategy for plug-in hybrid electric vehicles based on energy demand prediction and route preview”. IEEE Transactions on Vehicular Technology, 64(5), 1691-1700, 2014.
• [20] Wang Y, Jiang J, 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.
• [21] Zeng X, Wang J. “A two-level stochastic approach to optimize the energy management strategy for fixed-route hybrid electric vehicles”. Mechatronics, 38, 93-102, 2016.
• [22] Froger A, Mendoza J E, Jabali O, Laporte G. “Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions”. Computers & Operations Research, 104, 256-294, 2019.
• [23] Kancharla S R, Ramadurai G. “Electric vehicle routing problem with non-linear charging and load-dependent discharging”. Expert Systems with Applications, 160, 1-17, 2020.
• [24] Keskin M, Laporte G, Catay B. “Electric vehicle routing problem with time-dependent waiting times at recharging stations”. Computers & Operations Research, 107, 77-94, 2019.
• [25] Koç Ç, Jabali O, Mendoza J E, Laporte G. “The electric vehicle routing problem with shared charging stations”. International Transactions in Operational Research, 26(4), 1211-1243, 2019.
• [26] Montoya A, Gueret C, Mendoza J E, Villegas J G. “The electric vehicle routing problem with nonlinear charging function”. Transportation Research Part B-Methodological, 103, 87-110, 2017.
• [27] Strehler M, Merting S, Schwan C. “Energy-efficient shortest routes for electric and hybrid vehicles”. Transportation Research Part B-Methodological, 103, 111-135, 2017.
• [28] Riemann R, Wang D Z, Busch F. “Optimal location of wireless charging facilities for electric vehicles: flowcapturing location model with stochastic user equilibrium”. Transportation Research Part C: Emerging Technologies, 58, 1-12, 2015.
• [29] Manshadi S D, Khodayar M E, Abdelghany K, Üster H. “Wireless charging of electric vehicles in electricity and transportation networks”. IEEE Transactions on Smart Grid, 9(5), 4503-4512, 2017.
• [30] Kosmanos D, Maglaras L A, Mavrovouniotis M, Moschoyiannis S, Argyriou A, Maglaras A, Janicke H. “Route optimization of electric vehicles based on dynamic wireless charging”. IEEE Access, 6, 42551-42565, 2018.
• [31] Li C, Ding T, Liu X, Huang C. “An electric vehicle routing optimization model with hybrid plug-in and wireless charging systems”. IEEE Access, 6, 27569-27578, 2018.
• [32] Mouhrim N, El Hilali Alaoui A, Boukachour J. “Pareto efficient allocation of an in-motion wireless charging infrastructure for electric vehicles in a multipath network”. International journal of sustainable transportation, 13(6), 419-432, 2019.
• [33] Zhou B-h, Tan F. “Electric vehicle handling routing and battery swap station location optimisation for automotive assembly lines”. International Journal of Computer Integrated Manufacturing, 31(10), 978-991, 2018.
• [34] Jung J, Jayakrishnan R, Choi K. “Dually sustainable urban mobility option: Shared-taxi operations with electric vehicles”. International Journal of Sustainable Transportation, 11(8), 567-581, 2017.
• [35] Iacobucci R, McLellan B, Tezuka T. “Optimization of shared autonomous electric vehicles operations with charge scheduling and vehicle-to-grid”. Transportation Research Part C: Emerging Technologies, 100, 34-52, 2019.
• [36] Birrell SA, Wilson D, Yang C P, Dhadyalla G, Jennings P. “How driver behaviour and parking alignment affects inductive charging systems for electric vehicles”. Transportation Research Part C: Emerging Technologies, 58, 721-731, 2015.
• [37] Yang Y, Yao E, Yang Z, Zhang R. “Modeling the charging and route choice behavior of BEV drivers”. Transportation Research Part C: Emerging Technologies, 65, 190-204, 2016.
• [38] Marmaras C, Xydas E, Cipcigan L. “Simulation of electric vehicle driver behaviour in road transport and electric power networks”. Transportation Research Part C: Emerging Technologies, 80, 239-256, 2017.
• [39] Hiermann G, Puchinger J, Ropke S, 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.
• [40] Vaz Penna P H, Afsar H M, Prins C, Prodhon C. “A hybrid ıterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations”. IFAC-PapersOnLine, 49(12), 955-960, 2016.
• [41] Goeke D, Schneider M. “Routing a mixed fleet of electric and conventional vehicles”. European Journal of Operational Research, 245(1), 81-99, 2015.
• [42] Bruglieri M, Pezzella F, Pisacane O, Suraci S. “A variable neighborhood search branching for the electric vehicle routing problem with time windows”. Electronic Notes in Discrete Mathematics, 47, 221-228, 2015.
• [43] Yang H, Yang S, Xu Y, Cao E, Lai M, 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.
• [44] Yang J, Sun H. “Battery swap station location-routing problem with capacitated electric vehicles”. Computers & Operations Research, 55, 217-232, 2015.
• [45] Felipe A, Ortuno M T, Righini G, 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.
• [46] Li-Ying W, Yuan-Bin S. “Multiple charging station locationrouting problem with time window of electric vehicle”. Journal of Engineering Science and Technology Review, 8(5), 190-201, 2015.
• [47] Desaulniers G, Errico F, Irnich S, Schneider M. “Exact algorithms for electric vehicle-routing problems with time windows”. Operations Research, 64(6), 1388-1405, 2016.
• [48] Grandinetti L, Guerriero F, Pezzella F, Pisacane O. “A pickup and delivery problem with time windows by electric vehicles”. International Journal of Productivity and Quality Management, 18(2/3), 403-423, 2016.
• [49] Keskin M, Catay B. “Partial recharge strategies for the electric vehicle routing problem with time windows”. Transportation Research Part C-Emerging Technologies, 65, 111-127, 2016.
• [50] Lin J, Zhou W, Wolfson O. “Electric vehicle routing problem”. Ninth International Conference on City Logistics, 12, 508-521, 2016.
• [51] Barco J, Guerra A, Munoz L, Quijano N. “Optimal routing and scheduling of charge for electric vehicles: a case study”. Mathematical Problems in Engineering, 2017, 1-17, 2017.
• [52] Bruglieri M, Mancini S, Pezzella F, Pisacane O, 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.
• [53] Hof J, Schneider M, 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.
• [54] Shao S, Guan W, Ran B, He Z B, Bi J. “Electric vehicle routing problem with charging time and variable travel time”. Mathematical Problems in Engineering, 2017, 1-14, 2017.
• [55] Gatica G, Ahumada G, Escobar J W, Linfati R. “Efficient heuristic algorithms for location of charging stations in electric vehicle routing problems”. Studies in Informatics and Control, 27(1), 73-82, 2018.
• [56] Keskin M, Catay B. “A matheuristic method for the electric vehicle routing problem with time windows and fast chargers”. Computers & Operations Research, 100, 172-188, 2018.
• [57] Paz J C, Granada-Echeverri M, Escobar J W. “The multidepot electric vehicle location routing problem with time windows”. International Journal of Industrial Engineering Computations, 9(1), 123-136, 2018.
• [58] Shao S, Guan W, Bi J. “Electric vehicle-routing problem with charging demands and energy consumption”. Iet Intelligent Transport Systems, 12(3), 202-212, 2018.
• [59] Zhang S, Gajpal Y, Appadoo S S, Abdulkader M M S. “Electric vehicle routing problem with recharging stations for minimizing energy consumption”. International Journal of Production Economics, 203, 404-413, 2018.
• [60] Agárdi A, Kovács L, Bányai T. “Two-Echelon vehicle routing problem with recharge stations”. Transport and Telecommunication Journal, 20(4), 305-317, 2019.
• [61] Basso R, Kulcsar B, Egardt B, Lindroth P, Sanchez-Diaz I. “Energy consumption estimation integrated into the Electric Vehicle Routing Problem”. Transportation Research Part D-Transport and Environment, 69, 141-167, 2019.
• [62] Breunig U, Baldacci R, Hartl R F, Vidal T. “The electric twoechelon vehicle routing problem”. Computers & Operations Research, 103, 198-210, 2019.
• [63] Cortés-Murcia D L, Prodhon C, Murat Afsar H. “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.
• [64] 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.
• [65] Jie W C, Yang J, Zhang M, Huang Y X. “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.
• [66] Zhao M T, Lu Y W. “A heuristic approach for a real-world electric vehicle routing problem”. Algorithms, 2(12), 45, 2019.
• [67] Zuo X R, Xiao Y Y, You M, Kaku I, Xu Y C. “A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function”. Journal of Cleaner Production, 236, 1-18, 2019.
• [68] 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, 2020.
• [69] Lu J, Chen Y N, Hao J K, He R J. “The time-dependent electric vehicle routing problem: model and solution”. Expert Systems with Applications, 161, 1-17, 2020.
• [70] Mao HT, Shi J M, Zhou YZ, Zhang GQ. “The electric vehicle routing problem with time windows and multiple recharging options”. Ieee Access, 8, 114864-114875, 2020.
• [71] Meng M, Ma Y. “Route optimization of electric vehicle considering soft time windows and two ways of power replenishment”. Advances in Operations Research, 2020, 1- 10, 2020.
• [72] Raeesi R, Zografos K G. “The electric vehicle routing problem with time windows and synchronised mobile battery swapping”. Transportation Research Part BMethodological, 140, 101-129, 2020.
• [73] Soysal M, Cimen M, Belbag S. “Pickup and delivery with electric vehicles under stochastic battery depletion”. Computers & Industrial Engineering, 146, 1-14, 2020.
• [74] Tahami H, Rabadi G, Haouari M. “Exact approaches for routing capacitated electric vehicles”. Transportation Research Part E-Logistics and Transportation Review, 144, 1-29, 2020.
• [75] Taş D. “Electric vehicle routing with flexible time windows: a column generation solution approach”. Transportation Letters, 13(2), 97-103, 2020.
• [76] Wang L, Gao S, Wang K, Li T, Li L, Chen Z Y. “Timedependent electric vehicle routing problem with time windows and path flexibility”. Journal of Advanced Transportation, 2020, 1-26, 2020.
• [77] Zhang S, Chen M Z, Zhang W Y, Zhuang X Y. “Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations”. Expert Systems with Applications, 145, 1-12, 2020.
• [78] Zhao Z X, Li X M, Zhou X C. “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-17, 2020.
• [79] Ghobadi A, Tavakkoli Moghadam R, Fallah M, 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.
• [80] Karakatič S. “Optimizing nonlinear charging times of electric vehicle routing with genetic algorithm”. Expert Systems with Applications, 164, 1-14, 2021.
• [81] Keskin M, Catay B, 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, 1-15, 2021.
• [82] Lin B, Ghaddar B, Nathwani J. “Electric vehicle routing with charging/discharging under time-variant electricity prices”. Transportation Research Part C-Emerging Technologies, 130, 1-22, 2021.
• [83] Akbay M A, Kalayci C B, Blum C, Polat O. “Variable Neighborhood Search for the Two-Echelon Electric Vehicle Routing Problem with Time Windows”. Applied Sciences, 3(12), 1-29, 2022.
• [84] Duman E N, Tas D, Catay B. “Branch-and-price-and-cut methods for the electric vehicle routing problem with time windows”. International Journal of Production Research, 60(17), 5332-5353, 2022.
• [85] Guo F, Zhang J J, Huang Z H, Huang W L. “Simultaneous charging station location-routing problem for electric vehicles: Effect of nonlinear partial charging and battery degradation”. Energy, 250, 1-17, 2022.
• [86] Raeesi R, Zografos K G. “Coordinated routing of electric commercial vehicles with intra-route recharging and enroute battery swapping”. European Journal of Operational Research, 301(1), 82-109, 2022.
• [87] Sánchez D G, Tabares A, Faria L T, Rivera J C, Franco J F. “A clustering approach for the optimal siting of recharging stations in the electric vehicle routing problem with time windows”. Energies, 7(15), 1-19, 2022.
• [88] Yang S Y, Ning L J, Tong L, Shang P. “Integrated electric logistics vehicle recharging station location-routing problem with mixed backhauls and recharging strategies”. Transportation Research Part C-Emerging Technologies, 140, 1-27, 2022.
• [89] Zhang R Y, Guo J M, Wang J W. “A Time-dependent electric vehicle routing problem with congestion tolls”. Ieee Transactions on Engineering Management, 69(4), 861-873, 2022.
• [90] Sun Z, Zhou X. “To save money or to save time: Intelligent routing design for plug-in hybrid electric vehicle”. Transportation Research Part D: Transport and Environment, 43, 238-250, 2016.
• [91] Xu W, Zhang C, Cheng M, Huang Y. “Electric vehicle routing problem with simultaneous pickup and delivery: mathematical modeling and adaptive large neighborhood search heuristic method”. Energies, 15(23), 1-25, 2022.
• [92] Pelletier S, Jabali O, Laporte G, Veneroni M. “Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models”. Transportation Research Part B: Methodological, 103, 158- 187, 2017.
• [93] Jie W, Yang J, Zhang M, 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.