Título: RESOLVENDO O PROBLEMA DO CAIXEIRO VIAJANTE VIA GRASP COM CONSTRUÇÕES BASEADA EM REDES NEURAIS AUTO-ORGANIZAVEIS
Autores: Batista, Lucas de S.; Freitas, Alan R. R.; Guimarães, Frederico G.; Ramírez, Jaime
Resumo: A maioria dos problemas de otimização combinatória pertencem à classe NP, o que significa que a sua solução ótima por meio de métodos enumerativos pode exigir um tempo de processamento inviável. Assim, o uso de heurísticas é frequentemente mais interessante, pois são capazes de encontrar uma relação custo/benefício aceitável entre a qualidade da solução e o tempo de processamento. Este artigo propõe uma meta-heurística para a solução do problema do caixeiro viajante (TSP), em que um procedimento de busca adaptativa aleatória gulosa (GRASP) é implementado, empregando-se um mapa auto-organizável (SOM) na fase construtiva, e a heurística Lin-Kernighan para a busca local. Os resultados para 15 instâncias testadas apresentam um erro médio de aproximadamente 1% em relação aos ótimos conhecidos na literatura.
Palavras-chave: Problema do caixeiro viajante; Redes auto-organizáveis; Otimização combinatória
Páginas: 5
Código DOI: 10.21528/CBRN2009-144
Artigo em PDF: 144_CBRN2009.pdf
Arquivo BibTex: 144_CBRN2009.bib