Soluções factíveis para o problema do caixeiro viajante com veículo elétrico e janelas de tempo

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

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

Resumo

Problemas de roteamento com veículos elétricos têm ganhado atenção na literatura de otimização. No entanto, uma variante menos estudada é o problema do caixeiro viajante com veículos elétricos e janelas de tempo. Um dos desafios dessa variante está na obtenção de soluções iniciais factíveis para serem utilizadas em resolvedores baseados em branch-and-cut. Para geração dessas soluções, este trabalho propõe uma heurística de busca local simples e eficaz. A heurística foi capaz de gerar soluções factíveis para 49 (das 50) instâncias utilizadas na avaliação.

Referências

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.