El problema del vendedor viajero (problema del vendedor ambulante, problema del agente viajero o problema del viajante, PCP, TSP por sus siglas en inglés, Travelling Salesman Problem) responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación.
El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, se conoce gran cantidad de heurísticas y métodos exactos, así que es posible resolver planteamientos concretos del problema desde cien hasta miles de ciudades.
El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y la fabricación de circuitos electrónicos. Un poco modificado, aparece como subproblema en muchos campos como la secuenciación de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem).
En la teoría de la complejidad computacional, la versión de decisión del TSP (donde, dada una longitud “L”, el objetivo es decidir si el grafo tiene un camino menor o igual que L) pertenece a la clase de los problemas NP-completos. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma exponencial con respecto al número de ciudades.
Historia
El origen de los problemas del viajante no está claro. Una guía para viajantes de 1832 menciona el problema e incluye ejemplos de viajes a través de Alemania y Suiza, pero no contiene un tratamiento matemático del mismo."Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (El viajante — cómo debe ser y lo que debería hacer para obtener comisiones y asegurar el feliz éxito en sus negocios — por una antigua ruta comercial)
miniatura|William Rowan Hamilton
El problema del viajante fue definido en los años 1800s por el matemático irlandés W. R. Hamilton y por el matemático británico Thomas Kirkman. El Juego Icosian de Hamilton fue un puzle recreativo basado en encontrar un ciclo de Hamilton.Una discusión del temprano trabajo de Hamilton y Kirkman puede ser encontrado en Graph Theory 1736-1936 Todo parece indicar que la forma general del TSP fue estudiada, por primera vez por matemáticos en Viena y Harvard, durante los años 1930s. Destacándose Karl Menger, quien definió los problemas, considerando el obvio algoritmo de fuerza bruta, y observando la no optimalidad de la heurística de vecinos más cercanos:
Hassler Whitney de la Universidad de Princeton introdujo el nombre “travelling salesman problem” poco después.Un tratamiento detallado de la conexión entre Menger y Whitney así como también el crecimiento en el estudio de TSP puede ser encontrado en Alexander Schrijver's 2005 artículo "On the history of combinatorial optimization (till 1960). Handbook of Discrete Optimization (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, 2005, pp. 1–68.PS,PDF
Durante los años 1950 a 1960, el problema fue incrementando su popularidad entre el círculo de científicos de Europa y Estados Unidos. Una notable contribución fue la de George Dantzig, Delbert Ray Fulkerson y Selmer M. Johnson de la Corporación RAND en Santa Mónica, quienes expresaron el problema como Programación Lineal en Enteros y desarrollaron para solucionarlo el método de Planos Cortantes. Con este nuevo método, resolvieron una instancia con 49 ciudades, óptimamente, mediante la construcción de un recorrido y probando que no había un recorrido que pudiera ser más corto. En las siguientes décadas, el problema fue estudiado por muchos investigadores, matemáticos, científicos de la computación, químicos, físicos, etc.
Richard M. Karp mostró en 1972 que el Problema del Ciclo de Hamilton era un problema NP-completo, lo cual implica que el TSP sea un problema NP-duro. Esto tiene su explicación matemática por la evidente dificultad computacional para encontrar recorridos óptimos.
Gran progreso tuvo a finales de los 70 y principios de los 80, donde Grötschel, Padberg, Rinaldi y otros, manejaron soluciones exactas para instancias con 2392 ciudades, usando Planos Cortantes y Ramificación y Acotación.
En los 90s, Applegate, Bixby, Chvátal, y Cook desarrollaron el programa Concorde, el cual es usado en muchos de los registros de soluciones recientes. Gerhard Reinelt publicó el TSPLIB en 1991, una colección de instancias de pruebas de dificultad variable, la cual es usada por muchos grupos investigativos para comparar resultados. En 2006, Cook y otros, obtuvieron un recorrido óptimo para 85,900 ciudades dado por un problema de diseño de microchip, actualmente TSPLIB es la instancia más larga resuelta. Para otras muchas instancias con millones de ciudades, la solución puede ser encontrada garantizando que la solución contiene un 2-3% del recorrido óptimo..
Descripción
Caso práctico En el problema se presentan N! rutas posibles, aunque se puede simplificar ya que dada una ruta nos da igual el punto de partida y esto reduce el número de rutas a examinar en un factor N quedando (N-1)!. Como no importa la dirección en que se desplace el viajante, el número de rutas a examinar se reduce nuevamente en un factor 2. Por lo tanto, hay que considerar (N-1)!/2 rutas posibles.
En la práctica, para un problema del viajante con 5 ciudades hay (5-1)!/2=12 rutas diferentes y no necesitamos un ordenador para encontrar la mejor ruta, pero apenas aumentamos el número de ciudades las posibilidades crece factorialmente: Para 10 ciudades hay (10-1)!/2=181.440 rutas diferentes Para 30 ciudades hay más de 4·10^30 rutas posibles. Un ordenador que calcule un millón de rutas por segundo necesitaría 10^17 años para resolverlo. Dicho de otra forma, si se hubiera comenzado a calcular al comienzo de la creación del universo (hace unos 13.400 millones de años) todavía no se habría terminado.
Puede comprobarse que por cada ciudad nueva que incorporemos, el número de rutas se multiplica por el factor N y crece factorialmente. Por ello el problema pertenece a la clase de problemas NP-completos.
Como un problema de grafos
miniatura|TSP simétrico con 4 ciudades El TSP puede ser modelado como un grafo ponderado no dirigido, de manera que las ciudades sean los vértices del grafo, los caminos son las aristas y las distancias de los caminos son los pesos de las aristas. Esto es un problema de minimización que comienza y termina en un vértice específico y se visita el resto de los vértices exactamente una vez. Con frecuencia, el modelo es un grafo completo (cada par de vértices es conectado por una arista). Si no existe camino entre un par de ciudades, se añade arbitrariamente una arista larga para completar el grafo sin afectar el recorrido óptimo.
Asimétrico y simétrico
En el ‘’’TSP simétrico’’’, la distancia entre un par de ciudades es la misma en cada dirección opuesta, formando un grafo no dirigido. Este problema reduce a la mitad el número de soluciones posibles. En el ‘’’TSP asimétrico’’’, pueden no existir caminos en ambas direcciones o las distancias pueden ser diferentes, formando un grafo dirigido. Los accidentes de tráfico, las calles de un solo sentido y las tarifas aéreas para ciudades con diferentes costos de partida y arribo, son ejemplos de cómo esta simetría puede ser quebrada.
Problemas relacionados
Una formulación equivalente en términos de Teoría de grafos es: dado una grafo ponderado completo (donde los vértices representan las ciudades, las aristas representan los caminos y los pesos son el costo o las distancias de estos caminos), encontrar un ciclo Hamiltoniano con menor peso.
Las restricciones de retorno a la ciudad de comienzo no cambia la complejidad computacional del problema, vea Problema del camino Hamiltoniano.
Otro problema relacionado es el Problema del viajante con cuello de botella (bottleneck TSP): Encontrar un ciclo de Hamilton en un grafo ponderado con el mínimo peso de las aristas más pesadas. El problema es de una considerable importancia en la práctica, en las áreas del transporte y la logística. Un ejemplo clásico es en la fabricación de circuitos impresos: planificando una ruta de la máquina perforadora para perforar los huecos en un PCB. Otras son, las aplicaciones de perforado o maquinado en la robótica: las “ciudades” son los huecos de diferentes tamaños a perforar y el “costo de viaje” incluye el tiempo para reequipar el robot (problema del secuenciado del trabajo de una máquina simple).
La generalización del TSP trata con “estados” que tienen (una o más) “ciudades” y el viajante tiene que visitar exactamente una ciudad de cada “estado”. También se conoce como el Problema del Político Viajero. Como una aplicación se considera, el perforado en la fabricación de semiconductores, vea e.g., . Sorprendentemente, Behzad y Modarres demostraron que el problema generalizado del viajante puede ser transformado en el problema del viajante estándar con el mismo número de ciudades, pero modificando la Matriz de distancias
El problema de ordenamiento secuencial trata con el problema de visitar un conjunto de ciudades donde se tiene en cuenta las relaciones de precedencias entre las ciudades.
El problema del viajante comprador trata con un comprador que está cargado con un conjunto de productos. Él puede comprar estos productos en varias ciudades, pero tienen diferentes precios y no todas las ciudades ofrecen los mismos productos. El objetivo es encontrar una ruta entre un subconjunto de ciudades, los cuales minimicen el costo total (costo de viaje + costo de la compra) y habilite la compra de todos los productos requeridos.
Formulación de la programación lineal en enteros
El TSP puede ser formulado por la programación lineal en enteros., pp.308-309.Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)Dantzig, George B. (1963), Linear Programming and Extensions, Princeton, NJ: PrincetonUP, pp. 545–7, ISBN 0-691-08000-3, sixth printing, 1974. Sea igual 1, si existe el camino de ir de la i a la ciudad j, y 0 en otro caso, para el conjunto de ciudades 0,..., n. Sean para i = 1,..., n variables artificiales y sea la distancia desde la ciudad i a la ciudad j. Entonces el modelo de programación lineal en enteros puede ser escrito como:
El primer conjunto de igualdades asegura que cada ciudad 0,..., n de salida llegue exactamente a una ciudad, y el segundo conjunto de igualdades aseguran que desde cada ciudad 1,..., n se salga exactamente hacia una ciudad (ambas restricciones también implican que exista exactamente una salida desde la ciudad 0.) La última restricción obliga a que un solo camino cubra todas las ciudades y no dos o más caminos disjuntos cubran conjuntamente todas las ciudades. Para probar esto se muestra en (1) que toda solución factible contiene solamente una secuencia cerrada de ciudades, y en (2) que para cada uno de los recorridos que cubren todas las ciudades, hay valores para todas las variables que satisfacen las restricciones.