A tabu search algorithm for the periodic vehicle routing problem

Resumo: Este trabalho aborda o problema de roteamento periódico de veículos, que consiste em designar uma combinação de dias de visitas a cada cliente, e definir as rotas de veículos em cada dia de um horizonte de planejamento, de forma a minimizar o custo ou a duração total das rotas. Um algoritmo de busca tabu é proposto para a resolução do problema. A história da busca tabu, usada para guiar o processo de busca, é representada através de memórias de curto e longo prazo. A eficiência das estratégias sugeridas para diversificação e intensificação, associadas à memória de logo prazo, são verificadas experimentalmente. O desempenho do algoritmo de busca tabu é testado computacionalmente em problemas da literatura. Um procedimento de busca tabu proposto na literatura é implementado e comparado com o algoritmo aqui propostoAbstract: This work addresses the periodic vehicle routing problem that consists of assigning a combination of visiting days to each client, and defining the routes every day of a planning horizon, in such a way as to minimize the cost or duration of the routes. A tabu search algorithm is proposed for solving this problem. The history of the tabu search, used to guide the search process, is represented by short and long term memories. The efficacy of the suggested strategies for diversification and intensification, associated to the long term memory, is verified experimentally. The performance of the tabu search algorithm is tested computationally in instances from the literature. A tabu search procedure suggested in the literature is implemented and its performance is tested against the tabu search algorithm developed in this wor