Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios
Hybrid metaheuristics for solve the prize collecting traveling salesman problem
Chaves, Antonio Augusto; Biajoli, Fabricio Lacerda; Mine, Otavio Massashi; Souza, Marcone Jamilson F.
http://dx.doi.org/10.1590/S0103-65132007000200004
Prod, vol.17, n2, p.263-272, 2007
Resumo
O Problema do Caixeiro Viajante com Coleta de Prêmios (PCVCP) pode ser associado a um caixeiro que coleta um prêmio em cada cidade visitada e paga uma penalidade para cada cidade não visitada, com um custo de deslocamento entre as cidades. O problema encontra-se em minimizar o somatório dos custos da viagem e penalidades, enquanto inclui na sua rota um número suficiente de cidades que lhe permita coletar um prêmio mínimo preestabelecido. Este trabalho contribui com o desenvolvimento de metaheurísticas híbridas para o PCVCP, baseadas em GRASP e métodos de busca em vizinhança variável (VNS/VND) para solucionar aproximadamente o PCVCP. De forma a validar as soluções obtidas, propõe-se uma formulação matemática a ser resolvida por um solver comercial, objetivando encontrar a solução ótima para o problema, sendo este solver aplicado a problemas de pequeno porte. Resultados computacionais demonstram a eficiência da abordagem híbrida proposta, tanto em relação à qualidade da solução final obtida quanto em relação ao tempo de execução.
Palavras-chave
Problema do caixeiro viajante, metaheurísticas, GRASP, VNS, VND
Abstract
The Prize Collecting Traveling Salesman Problem (PCTSP) can be associated to a salesman who collects a prize in each city visited and pays a penalty for each city not visited, with travel costs among the cities. The objective is to minimize the sum of the travel costs and penalties, including in the tour enough number of cities that allow collecting a minimum prize. This paper contributes with the development of a hybrid metaheuristic to PCTSP, based on GRASP and search methods in variable neighborhood (VNS/VND) to solve PCTSP approximately. In order to validate the obtained solutions, we proposed a mathematical formulation to be solved by a commercial solver to find the best solution to the problem, being this solver applied to small problems. Computational results demonstrate the efficiency of the proposed method, as much in relation to the quality of the obtained final solution as in relation to the time of execution.
Keywords
Traveling salesman problem, metaheuristic, GRASP, VNS, VND
References
BALAS, E. The prize collecting traveling salesman problem. Networks, 19, p. 621-636, 1989.
_________. The Prize Collecting Traveling Salesman Problem and Its Applications, Management Science Research Report, MSRR-664, 2001.
BEASLEY, J. E. OR-Library: distributing test problems by eletronic mail. Journal of the Operational Research Society, v. 41, p. 1069-1072, 1990.
CHAVES, A. A.; et al. Modelagens Exata e Heurística para Resolução do Problema do Caixeiro Viajante com Coleta de Prêmios. Relatório Técnico – Universidade Federal de Ouro Preto, Ouro Preto, 2003. Disponível em http://www.decom.ufop.br/prof/marcone/Orientacoes/OrientacoesConcluidas .htm.
CROES, G. A method for solving travelling salesman problems. Operations Research, v. 6, p. 791-812, 1958.
DELLAMICO, M.; MAFFIOLI, F. e SCIOMANCHEN, A. A Lagrangian Heuristic for the Prize Collecting Travelling Salesman Problem. Annals of Operations Research, v. 81, p. 289-305, 1998.
DORIGO, M.; MANIEZZO, V.; COLORNI, A. The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, v. 26, n. 1, p. 29-41, 1996.
FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures, Journal of Global Optimization, v. 6, p. 109-133, 1995.
GOEMANS, M.; WILLIANSON, D. A General Approximation Tchnique for Constrained Forest Problems. In: Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, p. 307-315, 1992.
GOLDBARG, M. C.; LUNA, H. P. Otimização combinatória e programação linear: modelos e algoritmos. Rio de Janeiro: Campus, 2000.
GOLDBERG, D. E. Genetic Algorithms in Search. In: Optimization and Machine Learning. Berkeley: Addison-Wesley, 1989.
GOMES, L.; DINIZ, V.; MARTINHON, C. A. An Hybrid GRASP+VND Metaheuristic for the Prize-Collecting Traveling Salesman Problem. In: XXXII Simpósio Brasileiro de Pesquisa Operacional, p. 1657-1665, 2000.
GLOVER, F. Future Paths for Integer Programming and links to Artificial Intelligence. Computers and Operations Research, v. 5, p. 553-549, 1986.
KIRKPATRICK, S.; GELLAT, D. C.; VECCHI, M. P. Optimization by Simulated Annealing, Science, v. 220, p. 671-68, 1983.
MELO, V. A. Metaheurísticas para o Problema do Caixeiro Viajante com Coleta de Prêmios. Dissertação de Mestrado, Instituto de Computação, Universidade Federal Fluminense, Niterói, 2001.
MLADENOVIC, N.; HANSEN, P. Variable Neighborhood Search. Computers and Operations Research, v. 24, p. 1097-1100, 1997.
SHRAGE, L. Users Manual for LINGO. Chicago, IL: LINDO Systems Inc, 1991.
TSPLIB. Disponível em http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95. Acesso em: 12 jul. 2006.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email