Um Algoritmo Híbrido para a Resoluςão do Problema de Roteamento de Veículos com Janelas de Tempo

Abstract

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.