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

Autores

  • Mário Mestria Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo

DOI:

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

Palavras-chave:

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

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.

Downloads

Não há dados estatísticos.

Biografia do Autor

Mário Mestria, Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo

Doutor em Computação pela Universidade Federal Fluminense. Atualmente é professor do Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo lecionando na Coordenadoria do Curso de Eletrotécncia.

Publicado

16-08-2013

Como Citar

Mestria, M. (2013). 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. Revista Produção Online, 13(3), 1002–1033. https://doi.org/10.14488/1676-1901.v13i3.1350

Edição

Seção

Artigos

Artigos Semelhantes

Você também pode iniciar uma pesquisa avançada por similaridade para este artigo.