Métodos heurísticos usando grasp, reconexão de caminhos e busca em vizinhança variável para o problema do caixeiro viajante com grupamentos

Mário Mestria

Resumo


O Problema do Caixeiro Viajante com Grupamentos (PCVG) é uma generalização do Problema do Caixeiro Viajante (PCV) em que o conjunto de vértices é particionado em grupos disjuntos e o objetivo é encontrar um ciclo Hamiltoniano de custo mínimo tal que os vértices em cada grupo são visitados na forma contígua. O PCVG é NP-difícil e nesse contexto são propostos métodos heurísticos para o PCVG usando GRASP, Reconexão de Caminhos e Método de Descida em Vizinhança Variável (MDVV). Os métodos heurísticos foram testados usando instancias Euclidianas com até 2000 vértices e grupos variando entre 4 a 15 vértices. Os testes computacionais foram executados para comparar o desempenho dos métodos heurísticos com um algoritmo exato usando o software CPLEX Paralelo. Os resultados computacionais mostraram que o método heurístico híbrido usando MDVV sobressaiu em relação aos outros métodos.

Palavras-chave


Pesquisa Operacional. Inteligência Computacional. Heurísticas. Reconexão de Caminhos. Método de Descida em Vizinhança Variável

Texto completo:

ARTIGO ♪ÁUDIO♪


DOI: https://doi.org/10.14488/1676-1901.v13i3.1350

Métricas do artigo

Carregando Métricas ...

Metrics powered by PLOS ALM


R. Eletr. de Eng. de Produção e Correlatas - ISSN 1676-1901 Creative Commons License
Esta obra está licenciada sob uma Licença Creative Commons. © 2002 / Todos os direitos reservados Associação Brasileira de Engenharia de Produção (ABEPRO) Universidade Federal de Santa Catarina (UFSC).                           Contato: producaoonline@gmail.com