Métodos heurísticos usando busca local aleatória 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.v14i4.1721

Palavras-chave:

Pesquisa Operacional. Otimização Combinatória. Métodos Heurísticos. Método de Descida Aleatória em Vizinhança Variável. Iterated Local Search.

Resumo

Nesse artigo, são propostos novos métodos heurísticos para resolver o Problema do Caixeiro Viajante com Grupamentos (PCVG). O PCVG é uma generalização do Problema do Caixeiro Viajante (PCV), onde os vértices são particionados em grupos disjuntos e o objetivo é encontrar um ciclo hamiltoniano de custo mínimo tal que os vértices de cada grupo são visitados de forma contígua. Nós desenvolvemos dois Métodos de Descida Aleatória em Vizinhança Variável com Iterated Local Search para resolver o PCVG. Os métodos heurísticos propostos foram testados em tipos de instâncias com dados em níveis diferentes de granularidade para o número de vértices e grupos. Resultados computacionais mostraram que os métodos heurísticos se sobrepõem aos métodos recentes existentes na literatura e são competitivos com um método exato usando o software CPLEX Paralelo.

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 e Coordenador do Curso de Engenharia Elétrica, Campus Vitória, do Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo.

Publicado

15-11-2014

Como Citar

Mestria, M. (2014). Métodos heurísticos usando busca local aleatória em vizinhança variável para o problema do caixeiro viajante com grupamentos. Revista Produção Online, 14(4), 1511–1536. https://doi.org/10.14488/1676-1901.v14i4.1721

Edição

Seção

Artigos