Metaheurísticas híbridas para a resolução do problema do caixeiro viajante com grupamentos

Abstract

Este trabalho propõe diversas heurísticas para resolver o Problema do Caixeiro Viajante com Grupamentos (PCVG). O PCVG é uma generalização do Problema do Caixeiro Viajante (PCV), em que os vértices são divididos em grupos e todos os vértices de cada grupo devem ser visitados de forma contígua. As abordagens desenvolvidas foram baseadas nas metaheurísticas GRASP e Iterated Local Search (ILS). Uma versão corresponde ao GRASP tradicional, três incluem módulos de Reconexão de Caminhos (RC), três combinam a RC e o Método de Descida em Vizinhança Variável (VND), enquanto outras duas heurísticas híbridas combinam VND com ILS. As heurísticas propostas foram testadas em instâncias com até 2000 vértices e número de grupos variando de dois a 150 vértices. Os resultados computacionais mostraram que as heurísticas híbridas que utilizam ILS e VND apresentam os melhores resultados. O desempenho dos algoritmos propostos foi comparado com um algoritmo exato usando o software CPLEX e um Algoritmo Genético da literatura.