Voltar
Artigo Acesso aberto Produção Nacional Revisado por pares
BIBTEX RIS

Métodos heurísticos usando busca local aleatória em vizinhança variável para o problema do caixeiro viajante com grupamentos

2014; UNIVERSIDADE FEDERAL DE SANTA CATARINA; Volume: 14; Issue: 4 Linguagem: Português

10.14488/1676-1901.v14i4.1721

ISSN

1676-1901

Autores

Mário Mestria,

Tópico(s)

Business and Management Studies

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.

Referência(s)