Production
https://prod.org.br/article/doi/10.1590/S0103-65132013005000003
Production
Article

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.

Downloads: 0
Views: 810

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: . Acesso em: 15 fev. 2011.

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.

5883a4357f8c9da00c8b482b 1574685864 Articles
Links & Downloads

Production

Share this page
Page Sections