Título: DESENVOLVIMENTO E ANÁLISE EXPERIMENTAL DE HEURÍSTICAS GRASP PARA O PROBLEMA DO CAIXEIRO VIAJANTE COM GRUPAMENTOS
Autores: Mestria, Mário; Ochi, Luiz Atoru; Martins, Simone de Lima
Resumo: Neste artigo são propostas heurísticas GRASP para obter soluções aproximadas para uma generalização do Problema do Caixeiro Viajante (PCV) conhecido na literatura como Problema do Caixeiro Viajante com Grupamentos (PCVG). Neste problema, os vértices são particionados em grupos e todos os vértices de cada grupo têm que ser visitados de forma contígua. São propostas cinco heurísticas GRASP para resolver o PCVG incluindo um GRASP tradicional (G1), GRASP com módulos de memória adaptativa (MMA) (G2, G3 e G4) e uma versão híbrida GRASP incluindo MMA e a metaheurística VND. Compara-se o desempenho dos algoritmos propostos entre eles e com um algoritmo exato usando o software CPLEX. Resultados computacionais mostram que as versões com memória adaptativa superam o GRASP tradicional no tocante a qualidade das soluções geradas.
Palavras-chave: Inteligência Computacional; Metaheurísticas; Algoritmos com Memória Adaptativa
Páginas: 5
Código DOI: 10.21528/CBRN2009-008
Artigo em PDF: 008_CBRN2009.pdf
Arquivo BibTex: 008_CBRN2009.bib