Meta-Heurísticas em Pesquisa Operacional – Capítulo 10

  • Título: Métodos Penalizados e Não-Penalizados para o Problema do Caixeiro Viajante com Grupamentos
  • Autor: Mário Mestria
  • DOI:10.7436/2013.mhpo.10
  • Resumo: Este capítulo propõe diversos métodos heurísticos para resolver o Problema do Caixeiro Viajante com Grupamentos (PCVG). No PCVG 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 no GRASP, Iterated Local Search, Reconexão de Caminhos, Método de Descida em Vizinhança Variável e Inserção mais Próxima. Os resultados mostraram que os métodos heurísticos utilizando a penalização nas arestas intergrupos apresentam os melhores resultados. O desempenho dos métodos heurísticos foi comparado com um algoritmo exato usando o software CPLEX paralelo e um Algoritmo Genético da literatura.
  • Palavras-chave: Meta-heurísticas, Reconexão de caminhos, Método de descida em vizinhança variável, Problema do caixeiro viajante com grupamentos.
  • Abstract: This chapter proposes several heuristic methods to solve the Clustered Traveling Salesman Problem (CTSP). In the CTSP the vertices are partitioned into clusters and all vertices of each cluster must be visited continuously. The developed approaches were based on the GRASP, Iterated Local Search, Path Relinking, Variable Neighborhood Descent, and Nearest Insertion. The results showed that the heuristic methods using a penalization for inter-clusters edges achieve the best results. The performance of the heuristic methods was compared with an exact algorithm using the Parallel CPLEX software and a Genetic Algorithm of literature..
  • Keywords: Metaheuristics, Path relinking, Variable neighborhood descent, Clustered traveling salesman problem.
PDF do capítulo (0,509 MB):
BIBTEX do capítulo:

 

Os comentários estão encerrados.