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.