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

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.