Estudios de algoritmos para el Problema del Viajante: Modelización y comparación del rendimiento

Abstract

[ES]El Problema del Viajante —Traveling Salesman Problem, TSP— es un desafío computacional (problema NP-hard) bien conocido y fundamental en la teoría de la optimización combinatoria. Consiste en encontrar la ruta más corta que visite un conjunto de ciudades exactamente una vez y regrese al punto de partida. El TSP tiene aplicaciones en una amplia gama de campos, desde logística y planificación de rutas hasta diseño de circuitos y bioinformática. Este trabajo tiene como objetivo principal investigar y analizar diferentes algoritmos para resolver el TSP, tanto aquellos que buscan soluciones óptimas (algoritmos exactos) como los enfoques heurísticos que buscan soluciones aproximadas. Se explorarán algoritmos exactos, como el algoritmo de ramificación y poda, y heurísticos populares, como el algoritmo de colonia de hormigas. Se llevará a cabo un análisis exhaustivo de los algoritmos seleccionados, evaluando su rendimiento y complejidad computacional en función de diferentes instancias del problema y tamaños de redes. Además, se desarrollará un programa en el entorno de programación R para implementar y ejecutar estos algoritmos en ejemplos concretos.

[EN]The Traveling Salesman Problem (TSP) is a well-known and fundamental computational challenge (NP-hard problem) in the theory of combinatorial optimization. It involves finding the shortest route that visits a set of cities exactly once and returns to the starting point. The TSP has applications in a wide range of fields, from logistics and route planning to circuit design and bioinformatics. This work aims to investigate and analyze different algorithms to solve the TSP, including those seeking optimal solutions (exact algorithms) as well as heuristic approaches aiming for approximate solutions. Exact algorithms such as the branch and bound algorithm will be explored, alongside popular heuristics like the ant colony algorithm. An exhaustive analysis of the selected algorithms will be conducted, evaluating their performance and computational complexity based on different instances of the problem and network sizes. Additionally, a program will be developed in the R programming environment to implement and execute these algorithms on specific examples