GENILS-TS-CL-PR : um algoritmo heurístico para resolução do problema de roteamento de veículos com coleta e entrega simultânea.

Abstract

Este trabalho tem seu foco no Problema de Roteamento de Veículos com Coleta e Entrega Simultânea (PRVCES). Dada a dificuldade de solução deste problema, é proposto um algoritmo heurístico nomeado GENILS-TS-CL-PR, que combina os procedimentos heurísticos Inserção Mais Barata, Inserção Mais Barata Múltiplas Rotas, GENIUS, Iterated Local Search (ILS), Variable Neighborhood Descent (VND), Busca Tabu (TS, do inglês Tabu Search) e Reconexão por Caminhos (PR, do inglês Path Relinking). Os três primeiros procedimentos visam a obtenção de uma solução inicial, enquanto os procedimentos VND e TS são usados como métodos de busca local para o ILS. A Busca Tabu somente é acionada após certo número de iterações sem sucesso do VND. As buscas locais fazem uso de uma Lista de Candidatos de forma a evitar o uso de movimentos desnecessários e, assim, reduzir o espaço de busca. O algoritmo proposto foi testado em problemas-teste disponíveis na literatura e se mostrou capaz de gerar soluções de alta qualidade, sendo o algoritmo sequencial mais eficiente da literatura com relação à capacidade de encontrar melhores soluções e com pouca variabilidade.