Feasible solutions for the traveling salesman problem with electric vehicle and time windows

• Pedro Belin Castellucci UFSC
• Álvaro Junio Pereira Franco UFSC
• Rafael de Santiago UFSC

DOI: https://doi.org/10.5753/etc.2024.3034

Abstract

Recently, electric vehicle routing problems have being explored in the optimization literature more and more. However, the electric traveling salesman problem with time windows remains one of the less explored variants. One challenge of this variant is in generating initial solutions for branch-and-cut solvers. To this end, we propose a simple and effective local search heuristic. The heuristic was able to find feasible solutions for 49 (of 50) benchmark instances.

References

Abdallah, K. S. e Adel, Y. (2020). Electric vehicles routing problem with variable speed and time windows. Industry, Engineering & Conference Management Systems Conference.

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

Doppstadt, C., Koberstein, A., e Vigo, D. (2020). The hybrid electric vehicle—traveling salesman problem with time windows. European Journal of Operational Research, 284(2):675–692.

Erdoğdu, K. e Karabulut, K. (2021). A new model for minimizing the electric vehicle battery capacity in electric travelling salesman problem with time windows. Turkish Journal of Electrical Engineering and Computer Sciences, 29(5):2545–2560.

Felipe, Á., Ortuño, M. T., Righini, G., e 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.

Helsgaun, K. (2000). An effective implementation of the lin–kernighan traveling salesman heuristic. European journal of operational research, 126(1):106–130.

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

Kucukoglu, I., Dewil, R., e Cattrysse, D. (2021). The electric vehicle routing problem and its variations: A literature review. Computers & Industrial Engineering, 161:107650.

Lahyani, R., Khemakhem, M., e Semet, F. (2015). Rich vehicle routing problems: From a taxonomy to a definition. European Journal of Operational Research, 241(1):1–14.

Laporte, G. (2009). Fifty years of vehicle routing. Transportation science, 43(4):408–416.

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

Rastani, S. (2020). Route planning of electric freight vehicles by considering internal and environmental conditions. PhD thesis.

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

Wang, D., Ding, A., Chen, G., e Zhang, L. (2023). A combined genetic algorithm and A* search algorithm for the electric vehicle routing problem with time windows. Advances in Production Engineering & Management, 18(4).

Zhang, H., Ge, H., Yang, J., e Tong, Y. (2022). Review of vehicle routing problems: Models, classification and solving algorithms. Archives of Computational Methods in Engineering, pages 1–27.