Iterated Greedy for The Two-Echelon Electric Vehicle Routing Problem with Time Windows

• Igor de Andrade Junqueira Federal University of Juiz de Fora
• Heder Soares Bernardino Federal University of Juiz de Fora
• Lorenza Leão Oliveira Moreno Federal University of Juiz de Fora
• Luciana Brugiolo Gonçalves Federal University of Juiz de Fora
• Stênio Sã Rosário F. Soares Federal University of Juiz de Fora

DOI: https://doi.org/10.5753/eniac.2023.234252

Abstract

Cargo transportation can be very challenging in big cities due to congestion, pollution, and the prohibition of circulation at certain times of the day. Many transportation models can help to improve these issues. An example is the Two-Echelon Electric Vehicle Routing Problem with Time Windows (2E-EVRP-TW), which combines Electric Vehicles (EVs) with small capacity and Combustion Vehicles (CVs) with large capacity and range. These types of vehicles are combined in the solution using satellites, which are intermediary depots. The satellites attend to customers using EVs, and the satellites are attended by CVs that leave the central depot. As EVs have a limited range due to their batteries, recharging stations can be used. We propose here an Iterated Greedy (IG) with destroy and repair operators only. We compare the proposed IG with two Variable Neighborhood Search approaches from the literature, and the proposal obtained better results, both concerning distance (objective function) and CPU time.

Keywords: electric vehicle routing, two-echelon routing, iterated greedy, green routing

References

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

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

Jie, W., Yang, J., Zhang, M., and 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.

López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., and Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58.

Marte, R. et al. (2018). Handbook of heuristics. Springer,.

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

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

Romm, J. J. (2022). Climate change: What everyone needs to know. Oxford University Press.

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

Sluijk, N., Florio, A. M., Kinable, J., Dellaert, N., and Van Woensel, T. (2022). Two-echelon vehicle routing problems: A literature review. European Journal of Operational Research.

Souza, M. J., Coelho, I. M., Ribas, S., Santos, H. G., and Merschmann, L. H. d. C. (2010). A hybrid heuristic algorithm for the open-pit-mining operational planning problem. European Journal of Operational Research, 207(2):1041–1051.

Subramanian, A., Drummond, L. M., Bentes, C., Ochi, L. S., and Farias, R. (2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 37(11):1899–1911.

Toth, P. and Vigo, D. (2014). Vehicle routing: problems, methods, and applications. SIAM.

Wang, D. and Zhou, H. (2021). A two-echelon electric vehicle routing problem with time windows and battery swapping stations. Applied Sciences, 11(22):10779.