Heurísticas e Metaheurísticas para o Problema do Caixeiro Viajante com Grupamentos
Autores
|
2032 |
44,591
|
|
|
2033 |
44,591
|
Informações:
Publicações do PESC
Neste trabalho é considerada uma das generalizações mais estudadas do Problema do Caixeiro Viajante: o Problema do Caixeiro Viajante com Grupamento (PCVG) onde o conjunto de vértices é particionado em conjuntos disjuntos denominados grupamentos e o objetivo é encontrar um ciclo hamiltoniano de custo mínimo de maneira que todos os vértices de um mesmo grupamento sejam visitados contiguamente. Para solucionar o PCVG foram elaborados algoritmos híbridos baseados nas metaheurísticas GRASP e VNS. Os procedimentos de construção de solução e de busca local adotados foram baseados em GENlUS. Os resultados obtidos foram comparados a outros métodos de solução do PCVG encontrados na literatura.
This work addresses the Traveling Salesman Problem with Clustering (TSPC), a generalization of the Salesman Problem in which the set of nades is partitioned into disjoint subsets called clusters. The TSPC has been widely studied in the literature, and its goal is to find the tour with minimum cost in which all the nades of the same cluster can be visited in a contiguous manner. To solve the TSPC problem, we developed hybrid algorithms based on the GRASP and VNS metaheuristics. We algo applied GENI and US as our solution construction and local search procedures, respectively. We present our results and compare them to other approaches that may be found in the literature.