Avaliação de heurísticas para um problema do caixeiro viajante com veículos elétricos

Abstract

O problema do caixeiro viajante, clássico da otimização, busca determinar a rota mais curta para que um caixeiro visite um conjunto de cidades e retorne ao ponto de origem. No entanto, em um cenário mais moderno, essa questão ganha novas dimensões com o uso de veículos elétricos e a imposição de restrições de tempo para a visitação aos cli- entes, como no problema do caixeiro viajante com veículos elétricos e janelas de tempo (ETSPTW). Essa variante do problema não só leva em conta as limitações de autono- mia das baterias, mas também a necessidade de recarga dos veículos e a organização das visitas dentro de horários específicos. Devido aos desafios envolvidos, soluções rápidas e eficientes são essenciais. Nesse contexto, este trabalho explora métodos heu- rísticos, especificamente a Busca Local e a Busca Local Iterada (ILS). A investigação avalia comparativamente os operadores de vizinhança 2-opt e 3-opt, e os resultados de- monstram que o 3-opt, por possuir uma estrutura de vizinhança mais rica, é mais eficaz para encontrar soluções factíveis. Conclui-se que a combinação da ILS com o operador 3-opt gera as soluções de maior qualidade, apresentando uma abordagem robusta para cenários de transporte sustentável e logística moderna.