GENILS-TS-CL-PR : um algoritmo heurístico para resolução do problema de roteamento de veículos com coleta e entrega simultânea.
Nenhuma Miniatura disponível
Data
2012
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Programa de Pós-Graduação em Ciência da Computação. Departamento de Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
Resumo
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.
Descrição
Palavras-chave
Iterated local search, Descida em vizinhança variável, Inserção mais barata, Busca Tabu, Matemática da computação
Citação
SILVA, T. C. B. da. GENILS-TS-CL-PR : um algoritmo heurístico para resolução do problema de roteamento de veículos com coleta e entrega simultânea. 2012. 88 f. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal de Ouro Preto, Ouro Preto, 2012.