其他摘要：Este trabalho trata do Problema de Roteamento de Veículos com Janelas de Tempo. Tal problema consiste em uma variante do roteamento de veículos clássico, em que a demanda de cada cliente deve ser atendida durante um intervalo temporal pré-estabelecido. Dado o caráter altamente combinatório do problema, que pertence à classe NP-Difícil, sua resolução por abordagens puramente exatas é, em muitos casos, computacionalmente impraticável. Este fato motiva o desenvolvimento de algoritmos heurísticos para sua resolução, que são mais rápidos, porém não garantem a obtenção da melhor solução para o problema. Neste trabalho é proposto um algoritmo heurístico híbrido, que combina os métodos Iterated Local Search, Variable Neighborhood Descent e um procedimento exato de particionamento de conjunto. Esse procedimento de programação matemática é acionado periodicamente com vistas a combinar da melhor forma as rotas geradas ao longo do algoritmo. Os resultados computacionais obtidos mostram que o algoritmo é promissor, visto que ele obteve soluções melhores ou iguais aos da literatura em quarenta e dois dos cinquenta e seis problemas-teste analisados. Além disso, o algoritmo melhorou os resultados da literatura em 21,4% dos problemas tratados.
Loading...
