Um Método Exato para o Problema do Caixeiro Viajante com Grupamentos Euclidiano e Simétrico

Resumo

Nesse artigo, é proposto um método exato 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. A formulação para o método inclui a restrição de Chisman (1975) e uma formulação da literatura. Os testes foram realizados, através do software CPLEX Paralelo, em tipos de instâncias com diversas granularidades, com vértices e grupos de tamanhos variáveis. Resultados computacionais mostraram que o método encontrou diversas soluções ótimas e bons limites inferiores com tempo computacional relativamente baixo.