Algoritmos heuristicos para o prize collecting traveling salesman problem
AUTOR(ES)
Wesley Elias Ribeiro
DATA DE PUBLICAÇÃO
1997
RESUMO
This dissertation deals with the Prize Collecting Traveling Salesman Problem (PCTSP). This problem is a generalization of the well-known Traveling Salesman Problem (TSP), where the salesman does not need to visit all the cities, but has to visit enough cities in order to obtain a minimum prize. Besides that, the objective function is given by the minimization of the tour lenght plus the penalties paid for unvisited cities. The formulation of the PCTSP was made based on a pratical application of the problem, the scheduling of production units in a steel plant. The present work presents a study of the heuristic algorithms available in the literature about the problem. It then shows new construction and improvement heuristics developed for the PCTSP, and presents a comparison between those new heuristics and the best performance guarantee algorithm found in the literature. This work also presents a Asynchronous Team developed for the PCTSP. Asynchronous Teams are a meta-heuristic approach already succesfully applied to many other Combinatorial Optimization problems. Its basic principle is the sinergic combination of many algorithms (agents), communicating through shared memories. The Asynchronous Team was implemented using distributed processing, by using the message-passing based PVM (Parallel Virtual Machine) package. Many instances of different sizes were randomically generated, and, for comparison, lower bounds for these instances were calculated using the Cplex linear /integer programming package, applied to relaxations of the problem
ASSUNTO(S)
algoritmos heuristica problema do caixeiro viajante otimização combinatoria
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000123080Documentos Relacionados
- A SOLVABLE CASE OF THE TRAVELING SALESMAN PROBLEM*
- A HYBRID HEURISTIC ALGORITHM FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM
- QUANTUM INSPIRED PARTICLE SWARM COMBINED WITH LIN-KERNIGHAN-HELSGAUN METHOD TO THE TRAVELING SALESMAN PROBLEM
- O problema do caixeiro viajante com restrições de empacotamento tridimensional
- ESTRATÉGIAS PARALELAS INTELIGENTES PARA O MÉTODO BRANCH-AND-BOUND APLICADAS AO PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO