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
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
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
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