Título: METAHEURÍSTICAS COM MEM ORIA ADAPTATIVA PARA O PROBLEMA DE RECOBRIMENTO DE ROTAS
Autores: Motta, Luciene C. S.; Ochi, Luiz S.
Resumo: Dado um grafo não direcionado G = (V ∪ W, E), onde V ∪ W é o conjunto de vértices e E é o conjunto de arestas, o Problema de Recobrimento de Rotas (PRR) consiste em determinar uma rota de comprimento mínimo sobre V , contendo todos os vértices de T ⊆ V e com cada vértice de W coberto por esta rota. Sendo uma generalização do Problema do Caixeiro Viajante (PCV), o PRR é considerado um problema N P-Difícil o que, em via de regra, restringe a obtenção de soluções ótimas através de métodos exatos as instˆ àncias do problema de pequenas dimensões. Neste trabalho são propostos dois novos algoritmos heurísticos para o PRR, sendo um baseado na metaheurística GRASP e o outro baseado na metaheurística ILS. Experimentos computacionais são reportados, comparando comportamento dos algoritmos propostos
Palavras-chave: Problema de Recobrimento de Rotas; Inteligência Computacional; Metaheurísticas
Páginas: 5
Código DOI: 10.21528/CBRN2009-085
Artigo em PDF: 085_CBRN2009.pdf
Arquivo BibTex: 085_CBRN2009.bib