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

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

2013; UNIVERSIDADE FEDERAL DE SANTA CATARINA; Volume: 13; Issue: 3 Linguagem: Português

10.14488/1676-1901.v13i3.1350

ISSN

1676-1901

Autores

Mário Mestria,

Tópico(s)

Vehicle Routing Optimization Methods

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.

Referência(s)