Espacio literario relevante sobre el problema del vendedor viajero (TSP): contenido, clasificación, métodos y campos de inspiración
Relevant literary space on travelling salesman problem (TSP): contents, classification, methods and fields of inspiration
Rave, Jorge Iván P.; Álvarez, Gloria Patricia J.
http://dx.doi.org/10.1590/S0103-65132013005000003
Prod, vol.23, n4, p.866-876, 2013
Resumen
Se describe y se analiza un espacio literario relevante sobre el Problema del Vendedor Viajero (TSP) en términos de contenido, clases de TSP, métodos y campos de inspiración. Los datos empleados provinieron de los trabajos más citados en Scopus sobre el TSP, tanto a través de la historia como en el período 2006-2010. Se encontró que el TSP prevalece en las investigaciones, con enfoques tanto en el problema original como en sus variantes, entre las cuales se identificaron el TSP Múltiple y el TSP Probabilístico. Entre los principales campos de inspiración para resolver el TSP están la evolución biológica y su base genético-molecular, el comportamiento de hormigas reales, la termodinámica, las estrategias sistemáticas para combinar reglas de decisión y la búsqueda de vecindades. Hoy día se tiende a desarrollar métodos híbridos, especialmente integrando enfoques globales con búsquedas locales, y se identifica la necesidad de introducir nuevos campos de inspiración.
Palabras clave
Problema del vendedor viajero. Revisión sistemática. Métodos heurísticos. Optimización combinatoria
Abstract
This paper describes and analyzes, in terms of content, the types of TSP, methods and fields of inspiration - the most relevant "literary space" on TSP. It is built based on the top most cited on the TSP history and the Top 10 cited from 2006 to 2010. The study of TSP still prevails in Research, focusing on the original problem and its variants: Multiple TSP (m-TSP) and Probabilistic TSP (PTSP). Evidence shows that there has been progress in the development of TSP solving methods, highlighted by various inspiration fields: biological evolution, behavior of real ants, thermodynamics, systematic strategies for combining decision rules, and neighborhood search. There is a tendency to develop hybrid methods, in particular by integrating global approaches to local search. There is need to introduce new fields of inspiration.
Keywords
Travelling salesman problem. Systematic review. Heuristic method. Combinatorial optimization
References
ÁLVAREZ, R.; CORBERÁN, A.; TAMARIT, J. La combinatoria poliédrica y el problema del viajante. Aplicación al caso de ciento tres ciudades Españolas. Qüestió, v. 9, n. 3, p. 199-213, 1985.
ANGÉNIOL, B.; DE LA CROIX, V.; LE TEXIER, J. Self-organizing feature maps and the travelling salesman problem. Neural Networks, v. 1, n. 4, p. 289-293, 1988. http://dx.doi.org/10.1016/0893-6080(88)90002-0
APPLEGATE, D. et al. The traveling salesman problem: a computational study. New Jersey: Princeton University Press, 2006. p. 1-593.
BEKTAS, T. The multiple traveling salesman problem: An overview of formulations and solution procederes. Omega, v. 34, n. 3, p. 209-219, 2006. http://dx.doi.org/10.1016/j.omega.2004.10.004
BENTLEY, J. Fast algorithms for geometric traveling salesman problems. ORSA journal on computing, v. 4, n. 4, p. 387-411, 1992.
BOESE, K.; KAHNG, A.; MUDDU, S. A new Adaptive Multi-Start Technique for Combinatorial Global Optimization. Operations Research Center, v. 16, p. 101-113, 1994. http://dx.doi.org/10.1016/0167-6377(94)90065-5
CAMPBELL, A. Aggregation for the probabilistic traveling salesman problem. Computers and Operations Research, v. 33, n. 9, p. 2703-2724, 2006. http://dx.doi.org/10.1016/j.cor.2005.02.024
CARRABS, F.; CORDEAU, J.; LAPORTE, G. Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS Journal on Computing, v. 19, n. 4, p. 618-632, 2007. http://dx.doi.org/10.1287/ijoc.1060.0202
CARTER, A.; RAGSDALE, C. A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, v. 175, n. 1, p. 246-257, 2006. http://dx.doi.org/10.1016/j.ejor.2005.04.027
CASAZZA, M.; CESELLI, A.; NUNKESSER, M. Efficient algorithms for the double traveling salesman problem with multiple stacks. Computers and Operations Research, v. 39, n. 5, p. 1044-1053, 2012. http://dx.doi.org/10.1016/j.cor.2011.06.008
CASSANI, L.; RIGHINI, G. Heuristic algorithms for the TSP with rear-loading. In: ANNUAL CONFERENCE OF THE ITALIAN OPERATIONAL RESEARCH SOCIETY (AIRO XXXV), 35., 2004, Lecce, Italy. Proceedings... Lecce, 2004.
CERNÝ, V. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, v. 45, n. 1, p. 41-51, 1985. http://dx.doi.org/10.1007/BF00940812
CHEN S.; CHIEN, C. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Systems with Applications, v. 38, n. 12, p. 14439-14450, 2011. http://dx.doi.org/10.1016/j.eswa.2011.04.163
CHEN, N. An ant colony optimization and Bayesian network structure application for the asymmetric traveling salesman problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7198 LNAI (Part 3), p. 74-78, 2012.
CHEN, X. et al. Chaotic taboo fish algorithm for traveling salesman problem. Lecture Notes in Electrical Engineering, 143 LNEE, v. 1, p. 697-704, 2012b.
CHEN, X. et al. Chaotic immune PSO algorithm for traveling salesman problem. Lecture Notes in Electrical Engineering, 143 LNEE, v.1, p. 689-695, 2012c.
CHEN, X. et al. A hybrid algorithm to solve traveling salesman problem. Lecture Notes in Electrical Engineering, 139 LNEE, p. 99-105, 2012d.
CHENG, J. et al. Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems. Soft Computing, v. 16, n. 4, p. 597-614, 2012a. http://dx.doi.org/10.1007/s00500-011-0759-3
CODINA, L. El mayor navegador científico de la Web. El profesional de la información, v. 14, n. 1, p. 44-49, 2005. http://dx.doi.org/10.3145/epi.2005.feb.07
DANTZIG, G.; FULKERSON, R.; JOHNSON, S. Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, v. 2, n, 4, p. 393-410, 1954.
DAVIS, D. et al. Changing physician performance: A systematic review of the effect of continuing medical education strategies. Journal of the American Medical Association, v. 274, n. 9, p. 700-705, 1995. http://dx.doi.org/10.1001/jama.1995.03530090032018
DONG, G.; GUO, W.; TICKLE, K. Solving the traveling salesman problem using cooperative genetic ant systems. Expert Systems with Applications, v. 39, n. 5, p. 5006-5011, 2012. http://dx.doi.org/10.1016/j.eswa.2011.10.012
DORIGO, M.; GAMBARDELLA, L. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, v. 1, n. 1, p. 53-66, 1997. http://dx.doi.org/10.1109/4235.585892
DORIGO, M.; GAMBARDELLA, M. Ant-q: A reinforcement learning approach to the traveling salesman problem. In: INTERNATIONAL CONFERENCE ON MACHINE LEARNING, 12., 1995, Tahoe City. Proceedings... Tahoe City, 1995. p. 252-260.
DUAN, H.; YU, X. Hybrid ant colony optimization using memetic algorithm for traveling salesman problem. IEEE ADPRL 2007, art. n. 4220819, p. 92-95, 2007.
ERDOGAN, G. et al. Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs. Computers and Operations Research, v. 39, n. 5, p. 1074-1086, 2012. http://dx.doi.org/10.1016/j.cor.2011.07.013
FOGEL, D. Applying evolutionary programming to selected traveling salesman problems. Cybernetics and Systems, v. 24, n. 1, p. 27-36, 1993. http://dx.doi.org/10.1080/01969729308961697
GLOMVIK, J. et al. The Traveling salesman problem with draft limits. Computers and Operations Research, v. 39, n. 9, p. 2161-2167, 2012. http://dx.doi.org/10.1016/j.cor.2011.10.025
GONZÁLEZ, J.; RÍOS, R. Investigación de operaciones en acción: Aplicación del TSP en problemas de manufactura y logística. Ingenierías, v. 2, n. 4, p. 18-23, 1999.
HELD, M.; KARP, R. The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, v. 1, n. 1, p. 6-25, 1971. http://dx.doi.org/10.1007/BF01584070
HELSGAUN, K. An effective implementation of the Lin-Kernighan Traveling Salesman Heuristic. Datalogiske Skrifter (Writings on Computer Science), n. 81, p. 1-71, 1998.
JOHNSON, D.; McGEOCH, L. The Traveling Salesman Problem: A Case Study in Local Optimization. In: AARTS, E.; LENSTRA, J. (Eds.). Local Search in Combinatorial Optimization. Chichester: Wiley, 1997. chapt. 8, p. 215-310.
KARAPETYAN, D.; GUTIN, G. Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problema. European Journal of Operational Research, v. 219, n. 2, p. 234-251, 2012. http://dx.doi.org/10.1016/j.ejor.2012.01.011
KITCHENHAM, B. et al. Systematic literature reviews in software engineering - A systematic literature review. Information and Software Technology, v. 51, n. 1, p. 7-15, 2009. http://dx.doi.org/10.1016/j.infsof.2008.09.009
LAPORTE, G. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, v. 59, n. 2, p. 231-247, 1992. http://dx.doi.org/10.1016/0377-2217(92)90138-Y
LARRAÑAGA, P. et al. Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, v. 13, n. 2, p. 129-170, 1999. http://dx.doi.org/10.1023/A:1006529012972
LIN, S.; KERNIGHAN, B. An effective heuristic algorithm for the Traveling-Salesman Problem. Operations Research, v. 21, n. 2, p. 498-516, 1973. http://dx.doi.org/10.1287/opre.21.2.498
LIU, Y. A hybrid scatter search for the probabilistic traveling salesman problem. Computers and Operations Research, v. 34, n. 10, p. 2949-2963, 2007. http://dx.doi.org/10.1016/j.cor.2005.11.008
MARINAKIS, Y.; MARINAKI, M. A Hybrid Multi-Swarm Particle Swarm Optimization algorithm for the Probabilistic Traveling Salesman Problem. Computers y Operations Research, v. 37, n. 3, p. 432-442, 2010. http://dx.doi.org/10.1016/j.cor.2009.03.004
MARINAKIS, Y., MARINAKI, M.; DOUNIAS, G. Honey bees mating optimization algorithm for the Euclidean traveling salesman problem. Information Sciences, v. 181, n. 20, p. 4684-4698, 2011. http://dx.doi.org/10.1016/j.ins.2010.06.032
MARTI, R. Procedimientos metaheurísticos en optimización combinatoria. Matemátiques, v. 1, n. 1, p. 1-60, 2003.
MLADENOVIĆ, N. et al. A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem European Journal of Operational Research, v. 220, n. 1, p. 270-285, 2012. http://dx.doi.org/10.1016/j.ejor.2012.01.036
MONTOYA, J.; PATERNINA, C.; FREIN, Y. Minimización del tiempo total de flujo de tareas en una sola máquina: Estado del arte. Ingeniería Desarrollo, v. 12, p. 118-129, 2002.
NGUYEN, H. et al. Implementation of an effective hybrid GA for large-scale traveling salesman problems. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, v. 37, n. 1, p. 92-99, 2007. http://dx.doi.org/10.1109/TSMCB.2006.880136
NY, J.; FERON, E.; FRAZZOLI, E. On the dubins traveling salesman problema. IEEE Transactions on Automatic Control, v. 57, n. 1, art. no. 5983407, p. 265-270, 2012.
OHLMANN, J.; THOMAS, B. A compressed-annealing heuristic for the traveling Salesman problem with time windows. INFORMS Journal on Computing, v. 19, n. 1, p. 80-90, 2007. http://dx.doi.org/10.1287/ijoc.1050.0145
PADBERG, M.; RINALDI, G. Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Operations Research Letters, v. 6, p. 1-7, 1987. http://dx.doi.org/10.1016/0167-6377(87)90002-2
PÉREZ, J. Heurística inspirada en el análisis sistémico del "Vecino más cercano", para solucionar instancias simétricas TSP, empleando una base comparativa multicriterio. 2011. 130 f. Tesis (Magíster en Ingeniería de Sistemas)-Facultad de Minas, Universidad Nacional de Colombia, Medellín, 2011.
QUEVEDO, D.; RÍOS, R. Uso de búsqueda Tabú en la solución del problema de asignación cuadrática. Ingenierías, v. 8, n. 48, p. 40-48, 2010.
REINELT, G. TSPLIB. A traveling salesman problem library. ORSA journal on computing, v. 3, n. 4, p. 376-384, 1991.
RÍOS, R.; BARD, J. Heurísticas para secuenciamiento de tareas en líneas de flujo. 2010. Disponível em:
RODRÍGUEZ, A.; RUIZ, R. The effect of the asymmetry of road transportation networks on the traveling salesman problem. Computers and Operations Research, v. 39, n. 7, p. 1566-1576, 2012. http://dx.doi.org/10.1016/j.cor.2011.09.005
SAVLA, K.; FRAZZOLI, E.; BULLO, F. Traveling salesperson problems for the Dubins vehicle. IEEE Transactions on Automatic Control, v. 53, n. 6, p. 1378-1391, 2008. http://dx.doi.org/10.1109/TAC.2008.925814
SCHAEFFER, E. Computación aleatorizada - probabilidad y algoritmos. RISCE - Revista Internacional de Sistemas Computacionales y Electrónicos, p. 2-4, enero 2009.
SNYDER, L.; DASKIN, M. A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research, v. 174, n. 1, p. 38-53, 2006. http://dx.doi.org/10.1016/j.ejor.2004.09.057
STAPLES, M.; NIAZI, M. Experiences using systematic review guidelines. Journal of Systems and Software, v. 80, n. 9, p. 1425-1437, 2007. http://dx.doi.org/10.1016/j.jss.2006.09.046
STUETZLE, T.; HOOS, H. MAX-MIN Ant System and local search for the traveling salesman problem. In: IEEE CONFERENCE ON EVOLUTIONARY COMPUTATION, 1997. Proceedings... ICEC, 1997. p. 309-314.
SU, S.; CAO, X.; ZUO, X. Traveling salesman problems on a cuboid using discrete particle swarm optimization. Lecture Notes in Electrical Engineering, 154 LNEE, p. 404-411, 2012.
VANSTEENWEGEN, P.; SOUFFRIAU, W.; SÖRENSEN, K. The travelling salesperson problem with hotel selection, Journal of the Operational Research Society, v. 63, n. 2, p. 207-217, 2012. http://dx.doi.org/10.1057/jors.2011.18
VAZIRANI, V. Approximation algorithms. Corr. 2nd print. New York: Springer-Verlag Inc., 2001. p. 1-380.
VÉLEZ, M.; MONTOYA, J. Metaheurísticos: una alternativa para la solución de problemas combinatorios en administración de operaciones. Revista EIA, n. 8, p. 99-115, 2007.
VERSCHAE, J. Algoritmos de aproximación para problemas de programación de ordenes en maquinas paralelas. Memoria para ingeniero civil matemático. Universidad de Chile, Facultad de ciencias físicas y matemáticas, 2008. p. ix-xiii.
WANG, R.; ZHAO, L.; ZHOU, X. Ant colony optimization with memory and its application to traveling salesman problem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E95-A, no. 3, p. 639-645. 2012.
WEYLAND, D.; MONTEMANNI, R.; GAMBARDELLA, L. Using statistical tests for improving state-of-the-art heuristics for the probabilistic traveling salesman problem with deadlines. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6927 LNCS (Part 1), p. 448-455, 2012.
WHITLEY, D.; STARKWEATHER, T.; FUQUAY, D. Scheduling Problems and Travelling Salesman: The Genetic Edge Recombination Operator. In: SCHAFFER, J. (Ed.). Proceedings on the Third International Conference on Genetic Algorithms. Los Altos: Morgan Kaufmann Publishers, 1989. p. 133-140.
WU, H.; WU, J.; LIU, A. Hybrid discrete particle swarm optimizer algorithm for traveling salesman problem. Advanced Materials Research, v. 433-440, p. 4526-4529, 2012.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email