Metaheurísticas del TSP: Un recorrido didáctico y computacional

Abstract

Durante la historia de la computación, los problemas de rutas han suscitado un gran interés debido a sus múltiples aplicaciones en diferentes campos, como son la planificación y la logística. Este trabajo se centra en el problema del viajante de comercio o TSP. En concreto, en las técnicas para resolverlo de forma aproximada en un tiempo polinómico, las metaheurísticas. El objetivo principal de este estudio es proporcionar una guía para comprender cuatro de las más importantes, tanto en el ámbito teórico como en el computacional. Para ello, se realizó una revisión bibliográfica, encontrando información relevante de ellas y sintetizándola. Estas son: la búsqueda tabú, el templado simulado, el algoritmo genético y la optimización de la colonia de hormigas. Para la parte computacional, se realizaron implementaciones en R de todas las metaheurísticas y se evaluaron con distintas instancias de la librería TSPLIB. Como resultado, se obtuvo que no hay una metaheurística mejor que el resto en todos los aspectos. La búsqueda tabú y la optimización de la colonia de hormigas obtienen resultados muy prometedores en términos de distancia al coste óptimo; sin embargo, son temporalmente más costosas que las otras dos. El templado simulado obtiene unos resultados algo peores que los anteriores, pero de forma muy rápida. Por último, el algoritmo genético obtiene muy malos resultados en un tiempo, relativamente, aceptable. En conclusión, este trabajo sirve como guía a las personas que quieran comprender estos conceptos.During the history of computing, routing problems have attracted great interest due to their multiple applications in different fields, such as planning and logistics. This study focuses on the traveling salesman problem or TSP. Specifically, on the techniques to solve it in an approximate way in polynomial time, the metaheuristics. The main objective of this study is to provide a guide to understand four of the most important ones, both theoretically and computationally. For this purpose, a literature review was performed, finding relevant information of them and synthesizing it. They are: tabu search, simulated annealing, genetic algorithm and ant colony optimization. For the computational part, R implementations of all metaheuristics were performed and evaluated with different instances of the TSPLIB library. As a result, it was obtained that there is no metaheuristic better than the rest in all aspects. Tabu search and ant colony optimization obtain very promising results in terms of distance to optimal cost, however, they are temporarily more expensive than the other two. Simulated annealing obtains somewhat worse results than the previous ones, but in a very fast way. Finally, the genetic algorithm obtains very bad results in a relatively acceptable time. In conclusion, this work serves as a guide to people who want to understand these concepts.