El problema del viajante de comercio

Abstract

El presente Trabajo Fin de Grado aborda el Problema del Viajante de Comercio (TSP), un desafío clásico de optimización combinatoria con amplias aplicaciones en logística, industria, inteligencia artificial o incluso el ámbito militar. Se formula el problema desde una perspectiva matemática y computacional, destacando su clasificación como problema NP-hard, lo que implica que su resolución exacta se vuelve inabordable conforme crece el número de nodos. El trabajo analiza en profundidad métodos exactos como la fuerza bruta y la programación dinámica, aproximaciones como el algoritmo de Christófides y métodos heurísticos cómo el método de inserción más cercana. También se mencionan métodos metaheurísticos, como el recocido simulado o la colonia de hormigas. Se presta especial atención a la aplicabilidad práctica de algunos de estos algoritmos, evaluando su rendimiento en escenarios reales con apoyo de la herramienta SageMath. Como caso práctico, se modela una misión de patrulla aérea en la zona del golfo de Cádiz y mar de Alborán, aplicando diferentes técnicas para minimizar la distancia recorrida. Este estudio busca proporcionar una visión clara sobre la efectividad de cada enfoque, sirviendo como guía para futuras implementaciones del TSP en contextos operativos más complejos, incluyendo el entorno de las Fuerzas Armadas.