El problema del viajante (también conocido como problema del viajante de comercio o por sus siglas en inglés: TSP) es uno de los problemas más famosos (y quizás el mejor estudiado) en el campo de la optimización combinatoria computacional. A pesar de la aparente sencillez de su planteamiento, el TSP es uno de los más complejos de resolver y existen demostraciones que equiparan la complejidad de su solución a la de otros problemas apartentemente mucho más complejos que han retado a los matemáticos desde hace siglos.
Definición: Sean N ciudades de un territorio. La distancia entre cada ciudad viene dada por la matriz D: NxN, donde d[x,y] representa la distancia que hay entre la ciudad X y la ciudad Y. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante. Es decir, encontrar una permutación P = {c0,c2,...,cn − 1} tal que sea mínimo.
Una formulación equivalente en términos de la teoría de grafos es la de encontrar en un grafo completamente conexo y con arcos ponderados el ciclo hamiltoniano de menor coste. En esta formulación cada vértice del grafo representa una ciudad, cada arco representa una carretera y el peso asociado a cada arco representa la longitud de la carretera.
El TSP está entre los problemas denominados NP-Completos, esto es, los problemas que no se pueden resolver en tiempo polinomial en función del tamaño de la entrada (en este caso el número N de ciudades que el viajante debe recorrer). Sin embargo, algunos casos concretos del problema sí han sido resueltos hasta su optimización, lo que le convierte en un excelente banco de pruebas para algoritmos de optimización que pertenezcan a la misma familia (lo que en jerga matemática se denominan problemas isomorfos).
La solución más directa es la que aplica la fuerza bruta: evaluar todas las posibles permutaciones y quedarse con la mejor. No obstante, el número de posibles ciclos viene dado por el factorial del número de ciudades (N!) y esto hace que la solución por fuerza bruta sea impracticable para valores de N incluso moderados. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada ciclo en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y... 77.146 años en resolver el problema para sólo 20 ciudades.
Se puede demostrar que el requerimiento de volver a la ciudad de partida no cambia la complejidad computacional del problema.
Dada la explosión combinatoria de las posibles soluciones, los algoritmos clásicos no son capaces de resolver el problema general. Por ello, a su solución se han aplicado distintas técnicas computacionales: heurísticas, evolutivas, redes de Hopefield, etc. Sin embargo, desde el punto de vista teórico, estas aproximaciones no suponen una resolución real del TSP y sólo ofrecen soluciones aproximadas suficientemente aceptables.
Hay algoritmos que se basan en una configuración concreta del problema. Por ejemplo, algunos algoritmos de ramificación y consolidación se pueden utilizar para resolver problemas de entre 40 a 60 ciudades. Otros han mejorado a éstos con técnicas reminiscentes de la programación lineal que permiten resolver el TSP para valores de N entre 120 y 200 ciudades. En el año 2001 se utilizó una red de 110 ordenadores para resolver el TSP para las 15.112 poblaciones de alemania y utilizando el equivalente computacional a 22,5 años de un PC. En mayo del 2004 se aplicaron algunas de estas técnicas para la resolución del problema aplicado a las 24.978 poblaciones suecas en un ciclo de unos 72.500 km (probándose además que no se podía encontrar un ciclo más corto).
Los algoritmos genéricos basados en heurísticas no encuentran soluciones exactas, pero permiten encontrar aproximaciones suficientemente buenas (un 97% de optimización) y se pueden aplicar a conjuntos de ciudades muy grandes (redes con millones de nodos) con tiempos de ejecución razonables en un superordenador (semanas o meses).
El problema tiene considerables aplicaciones prácticas, a parte de las más evidentes en áreas de logística de transporte. Por ejemplo, en robótica, permite resolver problemas de fabricación para minimizar el número de desplazamientos para conseguir realizar un número determinado de perforaciones en una plancha o en un circuito impreso.
