TSP (Problema del Viajante de Comercio): definición, algoritmos y complejidad

El Problema del Vendedor Viajero (a menudo llamado TSP) es un problema algorítmico clásico en el campo de la informática y la investigación operativa. Se centra en la optimización. En este contexto, una solución mejor suele significar una solución más barata, más corta o más rápida. El TSP es un problema matemático. La forma más fácil de expresarlo es como un gráfico que describe la ubicación de un conjunto de nodos: cada nodo representa una ciudad (o punto de interés) y cada arista tiene un coste o distancia. El objetivo típico es encontrar un recorrido cerrado (un ciclo Hamiltoniano) que visite cada nodo exactamente una vez y minimice la suma de los costes de las aristas recorridas.

Historia y orígenes

El problema del viajante de comercio fue definido en el siglo XIX por el matemático irlandés W. R. Hamilton y por el matemático británico Thomas Kirkman. El Juego Icósico de Hamilton era un rompecabezas recreativo basado en encontrar un ciclo hamiltoniano. La forma general del TSP parece haber sido estudiada por primera vez por matemáticos durante la década de 1930 en Viena y en Harvard, especialmente por Karl Menger. Menger define el problema, considera el algoritmo obvio de fuerza bruta y observa la no optimización de la heurística del vecino más cercano:

Denotamos por problema del mensajero (ya que en la práctica esta cuestión debería ser resuelta por cada cartero, de todos modos también por muchos viajeros) la tarea de encontrar, para finitamente muchos puntos cuyas distancias entre pares son conocidas, la ruta más corta que conecta los puntos. Por supuesto, este problema se puede resolver con un número finito de pruebas. No se conocen reglas que hagan que el número de ensayos sea inferior al número de permutaciones de los puntos dados. La regla de que primero hay que ir del punto de partida al punto más cercano, luego al punto más cercano a éste, etc., en general no da la ruta más corta.

Hassler Whitney, de la Universidad de Princeton, introdujo poco después el nombre de problema del vendedor ambulante. Desde entonces el TSP ha sido un banco de pruebas central para técnicas de optimización combinatoria y teoría de la complejidad.

Formulación matemática

Formalmente, dadas n ciudades y una matriz de costes C = (c_ij) que indica el coste de ir de la ciudad i a la j, el objetivo es encontrar una permutación π de {1,...,n} que minimice:

coste(π) = c_π(n),π(1) + Σ_k=1..n-1 c_{π(k),π(k+1)}

Si c_ij=c_ji para todos i,j, se habla de TSP simétrico; si no, de TSP asimétrico. Cuando las distancias satisfacen la desigualdad triangular (c_ik ≤ c_ij + c_jk), se habla de TSP métrico o de TSP euclidiano si las ciudades están en el plano y las distancias son euclidianas.

Complejidad computacional

• Dificultad general: El TSP es un problema NP-hard; su versión de decisión (¿existe un tour de coste ≤ K?) es NP-completa. Esto implica que no se conoce ningún algoritmo polinómico que resuelva todos los casos exactamente (a menos que P = NP).
• Implicaciones: Para instancias grandes, los algoritmos exactos de fuerza bruta (probar todas las permutaciones, O(n!)) son inviables. Sin embargo, hay algoritmos exactos exponenciales que son mucho mejores que la fuerza bruta en la práctica.
• Casos especiales: Algunas variantes o instancias particulares (por ejemplo en grafos con estructura especial) pueden resolverse más eficientemente, y para el TSP métrico existen algoritmos de aproximación con cotas de garantía.

Algoritmos exactos

• Fuerza bruta: Enumerar todas las permutaciones, coste O(n!).
• Programación dinámica (Held–Karp): algoritmo clásico con complejidad O(n^2 2^n) en tiempo y O(n 2^n) en memoria; es mucho mejor que O(n!) pero sigue siendo exponencial.
• Branch-and-bound y ramificación: exploran el espacio de soluciones recortando ramas mediante cotas inferiores y superiores.
• Programación entera y cortes (branch-and-cut): formulación como problema de programación lineal entera con subtour elimination constraints (cortes de subtours). El enfoque de Dantzig–Fulkerson–Johnson y los avances posteriores forman la base de solvers prácticos.
• Solveores prácticos: Concorde es un ejemplo destacado de solver exacto que ha resuelto instancias grandes mediante técnicas avanzadas de branch-and-cut y heurísticas integradas.

Algoritmos aproximados y heurísticos

Debido a la dureza del TSP, se usan con frecuencia aproximaciones y heurísticas que ofrecen buenas soluciones en tiempo razonable.

• Heurísticas rápidas sin garantía: vecino más cercano, inserción (nearest/cheapest/insertion), heurísticas golosas.
• Optimización local: 2-opt, 3-opt, k-opt; intercambian aristas para mejorar un tour dado.
• Lin–Kernighan: heurística muy efectiva y ampliamente usada (y su versión iterada LKH).
• Metaheurísticas: recocido simulado, algoritmos genéticos, búsqueda tabú, optimización por colonias de hormigas.
• Algoritmos de aproximación con garantía: para el TSP métrico simétrico existe el algoritmo de Christofides (1976) que garantiza una solución con coste ≤ 1.5 veces la óptima. Para variantes de grafo y otros casos especiales hay resultados diferentes y mejoras puntuales.

Variantes importantes

• TSP asimétrico (ATSP): costes direccionales distintos entre pares de ciudades.
• Euclidiano TSP: puntos en el plano con distancia euclidiana; es métrico y suele comportarse bien con heurísticas.
• Multiple TSP (mTSP): varios vendedores/salesmen.
• TSP con ventanas de tiempo (TSPTW): restricciones temporales para visitar cada nodo.
• Prize-collecting / Orienteering: variantes con recompensas y límites de distancia.
• Vehicle Routing Problem (VRP): generalización práctica del TSP para flotas de vehículos y capacidades.

Aplicaciones

• Planificación de rutas y logística (reparto, recogida de residuos, rutas de ventas).
• Diseño de circuitos impresos y optimización de movimientos de herramientas en manufactura.
• Bioinformática: problemas relacionados con ensamblaje de secuencias (relación aproximada con el problema de la supercadena común más corta).
• Robótica y exploración (planificación de recorridos para robots o drones).
• Problemas teóricos: el TSP sirve como caso test para algoritmos de optimización y técnicas de investigación operativa.

Consejos prácticos

• Para instancias pequeñas (n ≤ 20–25) la programación dinámica o branch-and-bound pueden ser suficientes.
• Para instancias medianas y grandes, combinar heurísticas efectivas (Lin–Kernighan, 2/3-opt) con algoritmos de mejora local y, si se requiere optimalidad, utilizar un solver de branch-and-cut.
• Si el problema real satisface la desigualdad triangular, aproveche algoritmos de aproximación con garantía; si no, considere transformar o rediseñar la métrica si es posible.

En resumen, el TSP es simple de enunciar pero extraordinariamente rico y complejo en su comportamiento algorítmico. Su estudio ha generado técnicas de amplio alcance en optimización combinatoria, programación entera y metaheurísticas, con aplicaciones prácticas en muchos sectores industriales y científicos.