Um algoritmo simples e eficiente para resolução do problema do caixeiro viajante generalizado

Este trabalho tem seu foco no Problema do Caixeiro Viajante Generalizado, uma variante do Problema do Caixeiro Viajante clássico, onde as cidades são agrupadas em partições, sendo necessária a visita de apenas uma cidade em cada partição. Dada a dificuldade de resolvê-lo na otimalidade no caso geral, desenvolve-se neste trabalho um algoritmo híbrido, que combina as metaheurísticas Multi-Start e Iterated Local Search (ILS). O ILS é apoiado por duas buscas locais e um método de perturbação que aumenta, gradativamente, o nível de perturbação após um certo número de iterações sem melhora na solução corrente. Resultados demostram que o algoritmo é competitivo quando comparado com os melhores algoritmos da literatura.