Trade-off entre Complexidade e Desempenho no TSPTW: Avaliação de Algoritmos para Minimização de Distância e Makespan

O Problema do Caixeiro Viajante com Janelas de Tempo é fundamental em logística, onde restrições de tempo são críticas. Este artigo analisa comparativamente três abordagens: algoritmo guloso, refinamento com VND e meta-heurística GVNS, aplicadas a instâncias benchmark assimétricas para minimização de distância total e makespan, com limite de 1000 iterações ou 300 segundos de execução. Os resultados indicam que a eficácia dos métodos é sensivelmente influenciada pela função objetivo. O algoritmo guloso destacou-se na minimização do makespan (alcançando 71,4% das melhores soluções conhecidas), enquanto o GVNS sobressaiu-se na distância total (69,4%). Conclui-se que o GVNS é competitivo frente a algoritmos consolidados na literatura, como o Beam-ACO, validando o uso de vizinhanças variáveis na otimização de custos logísticos.