EXPERIMENTOS COMPUTACIONAIS COM UM ALGORITMO DE ROLLOUT PARA O PROBLEMA DO CAIXEIRO VIAJANTE COM JANELAS DE TEMPO

Abstract

Inspirado na necessidade dos vendedores em realizar entregas em diversas cidades, o problema do caixeiro viajante é um problema que tenta determinar a menor rota para percorrer uma série de cidades e retornar ao ponto de partida visitando cada uma apenas uma vez. Uma variação muito recorrente em problemas práticos é a que há uma janela de tempo atrelada a cada entrega, onde o vendedor está restrito a realizar a entrega apenas nos horários estipulados. Os métodos de resolução clássicos para o problema do caixeiro viajante tradicional são computacionalmente custosos ou até intratáveis para obter a solução exata. Naturalmente a variação com janelas de tempo sofre dos mesmos problemas, porém com o agravante do problema não ser tão explorado quanto o problema clássico. Além disso, a restrição de tempo acrescenta uma série de dificuldades. No entanto para tentar suprir esses problemas, utilizamos técnicas heurísticas para obter soluções em tempo viável. O objetivo deste projeto é explorar e desenvolver uma aplicação de um algoritmo de rollout ao problema do caixeiro viajante com janelas de tempo. Um algoritmo de rollout é uma técnica que garante um resultado tão bom ou melhor que uma heurística base. Para alcançar esses objetivos, inicialmente foi feito um levantamento bibliográfico quanto à utilização dessa técnica nas mais diversas áreas. Foi proposto então um modelo para a tomada de decisão dinâmica quanto a próxima cidade no qual o caixeiro irá percorrer, usando como heurística base uma combinação de algoritmo do vizinho mais próximo e backtracking. O modelo foi implementado computacionalmente com o uso da linguagem Python e as bibliotecas Numpy e Numba. Foram feitos experimentos computacionais e os resultados evidenciaram que o algoritmo de rollout foi capaz de obter boas soluções em boa parte das instâncias de 20 cidades, e soluções viáveis em certas instâncias de até 40 cidades.