El problema del viajante , también conocido como problema del viajante ( TSP ), plantea la siguiente pregunta: "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa?" a la ciudad de origen?" Es un problema NP-difícil en optimización combinatoria , importante en informática teórica e investigación de operaciones .
El problema del comprador viajero y el problema de la ruta del vehículo son generalizaciones del TSP.
En la teoría de la complejidad computacional , la versión de decisión del TSP (donde dada una longitud L , la tarea es decidir si el gráfico tiene un recorrido cuya longitud sea como máximo L ) pertenece a la clase de problemas NP-completos . Por lo tanto, es posible que el tiempo de ejecución en el peor de los casos para cualquier algoritmo para el TSP aumente superpolinomialmente (pero no más que exponencialmente ) con el número de ciudades.
El problema se formuló por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Se utiliza como punto de referencia para muchos métodos de optimización. Aunque el problema es computacionalmente difícil, se conocen muchas heurísticas y algoritmos exactos , de modo que algunos casos con decenas de miles de ciudades pueden resolverse completamente, e incluso problemas con millones de ciudades pueden aproximarse dentro de una pequeña fracción del 1%. [1]
El TSP tiene varias aplicaciones incluso en su formulación más pura, como la planificación , la logística y la fabricación de microchips . Ligeramente modificado, aparece como un subproblema en muchas áreas, como la secuenciación del ADN . En estas aplicaciones, el concepto ciudad representa, por ejemplo, clientes, puntos de soldadura o fragmentos de ADN, y el concepto distancia representa tiempos o costes de viaje, o una medida de similitud entre fragmentos de ADN. El TSP también aparece en astronomía, ya que los astrónomos que observan muchas fuentes quieren minimizar el tiempo dedicado a mover el telescopio entre las fuentes; En tales problemas, el TSP puede integrarse dentro de un problema de control óptimo . En muchas aplicaciones, se pueden imponer restricciones adicionales, como recursos limitados o ventanas de tiempo.
Los orígenes del problema del viajante no están claros. Un manual para vendedores ambulantes de 1832 menciona el problema e incluye viajes de ejemplo por Alemania y Suiza , pero no contiene ningún tratamiento matemático. [2]
El TSP fue formulado matemáticamente en el siglo XIX por el matemático irlandés William Rowan Hamilton y por el matemático británico Thomas Kirkman . El juego icosiano de Hamilton era un rompecabezas recreativo basado en encontrar un ciclo hamiltoniano . [3] 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 , en particular por Karl Menger , quien define el problema, considera el obvio algoritmo de fuerza bruta y observa la no optimización. de la heurística del vecino más cercano:
Llamamos problema del mensajero (ya que en la práctica esta cuestión debe ser resuelta por cada cartero, al menos también por muchos viajeros) la tarea de encontrar, para un número finito de puntos cuyas distancias por pares se conocen, la ruta más corta que conecte los puntos. Por supuesto, este problema se puede resolver mediante un número finito de ensayos. Se desconocen las reglas que reducirían el número de ensayos por debajo del número de permutaciones de los puntos dados. La regla de que primero se debe ir desde el punto de partida al punto más cercano, luego al punto más cercano a éste, etc., en general no da como resultado la ruta más corta. [4]
Fue considerado matemáticamente por primera vez en la década de 1930 por Merrill M. Flood, quien buscaba resolver un problema de ruta de autobuses escolares. [5] Hassler Whitney de la Universidad de Princeton generó interés en el problema, al que llamó el "problema de los 48 estados". La primera publicación que utilizó la frase "problema del viajante [o viajante]" fue el informe de RAND Corporation de 1949 de Julia Robinson , "Sobre el juego hamiltoniano (un problema del viajante)". [6] [7]
En las décadas de 1950 y 1960, el problema se hizo cada vez más popular en los círculos científicos de Europa y Estados Unidos después de que la Corporación RAND de Santa Mónica ofreciera premios por las medidas adoptadas para resolver el problema. [5] George Dantzig , Delbert Ray Fulkerson y Selmer M. Johnson de RAND Corporation hicieron contribuciones notables , quienes expresaron el problema como un programa lineal entero y desarrollaron el método del plano de corte para su solución. Escribieron lo que se considera el artículo fundamental sobre el tema en el que, con estos nuevos métodos, resolvieron un caso con 49 ciudades hasta el punto óptimo construyendo un recorrido y demostrando que ningún otro recorrido podría ser más corto. Dantzig, Fulkerson y Johnson, sin embargo, especularon que, dada una solución casi óptima, uno podría encontrar la optimización o demostrarla añadiendo un pequeño número de desigualdades adicionales (recortes). Usaron esta idea para resolver su problema inicial de 49 ciudades usando un modelo de cuerdas. Descubrieron que sólo necesitaban 26 recortes para encontrar una solución al problema de sus 49 ciudades. Si bien este artículo no proporcionó un enfoque algorítmico para los problemas de TSP, las ideas que contenía fueron indispensables para crear posteriormente métodos de solución exactos para el TSP, aunque se necesitarían 15 años para encontrar un enfoque algorítmico para crear estos cortes. [5] Además de los métodos de plano de corte, Dantzig, Fulkerson y Johnson utilizaron algoritmos de ramificación y unión quizás por primera vez. [5]
En 1959, Jillian Beardwood , JH Halton y John Hammersley publicaron un artículo titulado "El camino más corto a través de muchos puntos" en la revista de la Sociedad Filosófica de Cambridge . [8] El teorema de Beardwood-Halton-Hammersley proporciona una solución práctica al problema del viajante. Los autores derivaron una fórmula asintótica para determinar la longitud de la ruta más corta para un vendedor que comienza en una casa u oficina y visita un número fijo de lugares antes de regresar al punto de partida.
En las décadas siguientes, el problema fue estudiado por muchos investigadores de matemáticas , informática , química , física y otras ciencias. En la década de 1960, sin embargo, se creó un nuevo enfoque que, en lugar de buscar soluciones óptimas, produciría una solución cuya longitud estuviera demostrablemente limitada por un múltiplo de la longitud óptima y, al hacerlo, crearía límites inferiores para el problema; Estos límites inferiores se utilizarían luego con enfoques de ramificación y límite. Un método para hacer esto era crear un árbol de expansión mínimo del gráfico y luego duplicar todos sus bordes, lo que produce el límite de que la longitud de un recorrido óptimo es como máximo el doble del peso de un árbol de expansión mínimo. [5]
En 1976, Christofides y Serdyukov (independientemente uno del otro) hicieron un gran avance en esta dirección: [9] el algoritmo de Christofides-Serdyukov produce una solución que, en el peor de los casos, es como máximo 1,5 veces más larga que la solución óptima. Como el algoritmo era simple y rápido, muchos esperaban que diera paso a un método de solución casi óptimo. Sin embargo, esta esperanza de mejora no se materializó de inmediato, y Christofides-Serdyukov siguió siendo el método con el peor de los casos hasta 2011, cuando se desarrolló un algoritmo de aproximación (muy) ligeramente mejorado para el subconjunto de TSP "gráficos". [10] En 2020, esta pequeña mejora se extendió al TSP completo (métrico). [11] [12]
Richard M. Karp demostró en 1972 que el problema del ciclo hamiltoniano era NP-completo , lo que implica la dureza NP de TSP. Esto proporcionó una explicación matemática para la aparente dificultad computacional de encontrar recorridos óptimos.
A finales de los años 1970 y en 1980 se lograron grandes avances, cuando Grötschel, Padberg, Rinaldi y otros lograron resolver exactamente casos con hasta 2.392 ciudades utilizando planos de corte y ramificaciones .
En la década de 1990, Applegate , Bixby , Chvátal y Cook desarrollaron el programa Concorde que se ha utilizado en muchas soluciones discográficas recientes. Gerhard Reinelt publicó en 1991 el TSPLIB, una colección de instancias de referencia de diferente dificultad, que ha sido utilizada por muchos grupos de investigación para comparar resultados. En 2006, Cook y otros calcularon un recorrido óptimo a través de una instancia de 85.900 ciudades dada por un problema de diseño de microchip, actualmente la instancia TSPLIB resuelta más grande. Para muchos otros casos con millones de ciudades, se pueden encontrar soluciones que garantizan estar entre el 2% y el 3% de un recorrido óptimo. [13]
TSP se puede modelar como un gráfico ponderado no dirigido , de modo que las ciudades son los vértices del gráfico , las rutas son los bordes del gráfico y la distancia de una ruta es el peso del borde. Es un problema de minimización que comienza y termina en un vértice específico después de haber visitado cada vértice exactamente una vez. A menudo, el modelo es un gráfico completo (es decir, cada par de vértices está conectado por una arista). Si no existe ningún camino entre dos ciudades, agregar un borde suficientemente largo completará el gráfico sin afectar el recorrido óptimo.
En el TSP simétrico , la distancia entre dos ciudades es la misma en cada dirección opuesta, formando un gráfico no dirigido . Esta simetría reduce a la mitad el número de soluciones posibles. En el TSP asimétrico , es posible que no existan caminos en ambas direcciones o que las distancias sean diferentes, formando un gráfico dirigido . La congestión del tráfico, las calles de sentido único y las tarifas aéreas para ciudades con diferentes tarifas de salida y llegada son consideraciones del mundo real que podrían generar un problema de TSP en forma asimétrica.
El TSP se puede formular como un programa lineal entero . [16] [17] [18] Se conocen varias formulaciones. Dos formulaciones notables son la formulación de Miller-Tucker-Zemlin (MTZ) y la formulación de Dantzig-Fulkerson-Johnson (DFJ). La formulación DFJ es más fuerte, aunque la formulación MTZ sigue siendo útil en ciertos entornos. [19] [20]
Lo común a ambas formulaciones es que se etiquetan las ciudades con números y se toma como el costo (distancia) de una ciudad a otra . Las principales variables en las formulaciones son:
Debido a que se trata de variables 0/1, las formulaciones se convierten en programas enteros; todas las demás restricciones son puramente lineales. En particular, el objetivo del programa es minimizar la duración del recorrido.
Sin más restricciones, abarcará efectivamente todos los subconjuntos del conjunto de aristas, lo que está muy lejos de los conjuntos de aristas en un recorrido, y permite un mínimo trivial donde todos . Por lo tanto, ambas formulaciones también tienen la restricción de que, en cada vértice, hay exactamente una arista entrante y una arista saliente, que pueden expresarse como las ecuaciones lineales
Esto garantiza que el conjunto de aristas elegido localmente se parezca al de un recorrido, pero aún permite soluciones que violan el requisito global de que haya un recorrido que visite todos los vértices, ya que los aristas elegidas podrían formar varios recorridos, cada uno de los cuales visitaría solo un subconjunto. de los vértices; Podría decirse que es este requisito global el que hace que TSP sea un problema difícil. Las formulaciones de MTZ y DFJ difieren en cómo expresan este requisito final como restricciones lineales.
Además de las variables mencionadas anteriormente, existe para cada una una variable ficticia que realiza un seguimiento del orden en que se visitan las ciudades, contando desde la ciudad ; la interpretación es que implica que la ciudad se visita antes que la ciudad. Para un recorrido determinado (codificado en valores de las variables), se pueden encontrar valores satisfactorios para las variables igualando el número de aristas a lo largo de ese recorrido, cuando se va de ciudad en ciudad. [21]
Debido a que la programación lineal favorece las desigualdades no estrictas ( ) sobre las estrictas ( ), nos gustaría imponer restricciones en el sentido de que
Simplemente exigir no lograría eso, porque esto también requiere cuándo , lo cual no es correcto. En lugar de eso, MTZ utiliza las restricciones lineales.
donde el término constante proporciona suficiente holgura que no impone una relación entre y
La forma en que las variables imponen que un solo recorrido visite todas las ciudades es que aumentan al menos en cada paso a lo largo del recorrido, con una disminución solo permitida cuando el recorrido pasa por la ciudad. Esa restricción sería violada por cada recorrido que no lo haga. pasa por la ciudad, por lo que la única forma de satisfacerlo es que el recorrido que pasa por la ciudad también pase por todas las demás ciudades.
La formulación MTZ de TSP es, por tanto, el siguiente problema de programación lineal entera:
El primer conjunto de igualdades requiere que se llegue a cada ciudad exactamente desde otra ciudad, y el segundo conjunto de igualdades requiere que desde cada ciudad haya una salida hacia exactamente otra ciudad. La última restricción impone que haya un solo recorrido que cubra todas las ciudades, y no dos o más recorridos inconexos que solo cubran colectivamente todas las ciudades.
Etiqueta las ciudades con los números 1, ..., n y define:
Considere la distancia de la ciudad i a la ciudad j . Entonces TSP se puede escribir como el siguiente problema de programación lineal entera:
La última restricción de la formulación DFJ, llamada restricción de eliminación de subgiro , garantiza que ningún subconjunto Q adecuado pueda formar un subgiro, por lo que la solución devuelta es un solo recorrido y no la unión de recorridos más pequeños. Debido a que esto conduce a un número exponencial de posibles restricciones, en la práctica se resuelve con generación de filas . [22]
Las líneas de ataque tradicionales para los problemas NP-difíciles son las siguientes:
La solución más directa sería probar todas las permutaciones (combinaciones ordenadas) y ver cuál es más barata (usando la búsqueda de fuerza bruta ). El tiempo de ejecución de este enfoque se encuentra dentro de un factor polinómico de , el factorial del número de ciudades, por lo que esta solución resulta poco práctica incluso para sólo 20 ciudades.
Una de las primeras aplicaciones de la programación dinámica es el algoritmo de Held-Karp , que resuelve el problema a tiempo . [23] Este límite también lo ha alcanzado Exclusión-Inclusión en un intento anterior al enfoque de programación dinámica.
Mejorar estos plazos parece difícil. Por ejemplo, no se ha determinado si existe un algoritmo exacto clásico para TSP que se ejecute en el tiempo . [24] El mejor algoritmo cuántico exacto actualmente para TSP debido a Ambainis et al. corre en el tiempo . [25]
Otros enfoques incluyen:
En 2001 se encontró una solución exacta para 15.112 ciudades alemanas a partir de TSPLIB utilizando el método del plano de corte propuesto por George Dantzig , Ray Fulkerson y Selmer M. Johnson en 1954, basado en programación lineal . Los cálculos se realizaron en una red de 110 procesadores ubicados en la Universidad Rice y la Universidad de Princeton . El tiempo total de cálculo fue equivalente a 22,6 años en un único procesador Alpha de 500 MHz . En mayo de 2004 se resolvió el problema del viajante de recorrer las 24.978 ciudades de Suecia: se encontró un recorrido de aproximadamente 72.500 kilómetros y se demostró que no existe ningún recorrido más corto. [28] En marzo de 2005, el problema del viajante de visitar los 33.810 puntos de una placa de circuito se resolvió utilizando Concorde TSP Solver : se encontró un recorrido de 66.048.945 unidades de longitud y se demostró que no existe un recorrido más corto. El cálculo tomó aproximadamente 15,7 años-CPU (Cook et al. 2006). En abril de 2006, se resolvió una instancia con 85.900 puntos utilizando Concorde TSP Solver , ocupando más de 136 años de CPU; véase Applegate et al. (2006).
Se han ideado varias heurísticas y algoritmos de aproximación que rápidamente dan buenas soluciones. Estos incluyen el algoritmo multifragmento . Los métodos modernos pueden encontrar soluciones para problemas extremadamente grandes (millones de ciudades) en un tiempo razonable que, con una alta probabilidad, están a sólo un 2-3% de la solución óptima. [13]
Se reconocen varias categorías de heurísticas.
El algoritmo del vecino más cercano (NN) (un algoritmo codicioso ) permite al vendedor elegir la ciudad no visitada más cercana como su próximo movimiento. Este algoritmo produce rápidamente una ruta efectivamente corta. Para N ciudades distribuidas aleatoriamente en un plano, el algoritmo produce en promedio un camino 25% más largo que el camino más corto posible; [29] sin embargo, existen muchas distribuciones de ciudades especialmente organizadas que hacen que el algoritmo NN proporcione la peor ruta. [30] Esto es cierto tanto para los TSP asimétricos como para los simétricos. [31] Rosenkrantz et al. [32] demostró que el algoritmo NN tiene el factor de aproximación para los casos que satisfacen la desigualdad del triángulo. Una variación del algoritmo NN, llamada operador de fragmento más cercano (NF), que conecta un grupo (fragmento) de ciudades no visitadas más cercanas, puede encontrar rutas más cortas con iteraciones sucesivas. [33] El operador NF también se puede aplicar a una solución inicial obtenida por el algoritmo NN para mejorar aún más en un modelo elitista, donde solo se aceptan mejores soluciones.
El recorrido bitónico de un conjunto de puntos es el polígono monótono de perímetro mínimo que tiene los puntos como vértices; se puede calcular de manera eficiente con programación dinámica .
Otra heurística constructiva , Match Twice and Stitch (MTS), realiza dos coincidencias secuenciales , donde la segunda coincidencia se ejecuta después de eliminar todos los bordes de la primera coincidencia, para producir un conjunto de ciclos. Luego, los ciclos se unen para producir el recorrido final. [34]
El algoritmo de Christofides y Serdyukov sigue un esquema similar pero combina el árbol de expansión mínimo con una solución de otro problema, el emparejamiento perfecto de peso mínimo . Esto da un recorrido de TSP que es como máximo 1,5 veces el óptimo. Fue uno de los primeros algoritmos de aproximación y fue en parte responsable de llamar la atención sobre los algoritmos de aproximación como un enfoque práctico para problemas intratables . De hecho, el término "algoritmo" no se extendió comúnmente a los algoritmos de aproximación hasta más tarde; El algoritmo de Christofides se denominó inicialmente heurística de Christofides. [9]
Este algoritmo ve las cosas de manera diferente al utilizar un resultado de la teoría de grafos que ayuda a mejorar el límite inferior del TSP que se originó al duplicar el costo del árbol de expansión mínimo. Dado un gráfico Euleriano , podemos encontrar un recorrido Euleriano en el tiempo, [5] así que si tuviéramos un gráfico Euleriano con ciudades de un TSP como vértices, entonces podemos ver fácilmente que podríamos usar ese método para encontrar un recorrido Euleriano hasta encontrar una solución TSP. Por la desigualdad del triángulo , sabemos que el recorrido del TSP no puede ser más largo que el recorrido de Euler y, por lo tanto, tenemos un límite inferior para el TSP. Un método de este tipo se describe a continuación.
Para mejorar el límite inferior, se necesita una mejor forma de crear un gráfico euleriano. Por la desigualdad del triángulo, el mejor gráfico euleriano debe tener el mismo costo que el recorrido del mejor viajante de comercio; por lo tanto, encontrar gráficos eulerianos óptimos es al menos tan difícil como TSP. Una forma de hacerlo es haciendo coincidir el peso mínimo utilizando algoritmos con una complejidad de . [5]
Convertir un gráfico en un gráfico euleriano comienza con el árbol de expansión mínimo; todos los vértices de orden impar deben ser pares, por lo que se debe agregar una coincidencia para los vértices de grado impar, lo que aumenta el orden de cada vértice de grado impar en 1. [5] Esto nos deja con un gráfico donde cada vértice es de orden par, que por tanto es euleriana. Adaptando el método anterior se obtiene el algoritmo de Christofides y Serdyukov:
El intercambio por pares o técnica de 2 opciones implica eliminar iterativamente dos bordes y reemplazarlos con dos bordes diferentes que reconectan los fragmentos creados por la eliminación de bordes en un recorrido nuevo y más corto. De manera similar, la técnica de 3 opciones elimina 3 bordes y los vuelve a conectar para formar un recorrido más corto. Estos son casos especiales del método k -opt. La etiqueta Lin-Kernighan es un nombre inapropiado que se escucha a menudo para 2-opt; Lin-Kernighan es en realidad el método k -opt más general.
Para los casos euclidianos, las heurísticas de 2 opciones dan en promedio soluciones que son aproximadamente un 5% mejores que las arrojadas por el algoritmo de Christofides. Si comenzamos con una solución inicial hecha con un algoritmo codicioso , entonces el número promedio de movimientos vuelve a disminuir considerablemente y es ; sin embargo, para inicios aleatorios, el número promedio de movimientos es . Si bien se trata de un pequeño aumento de tamaño, el número inicial de movimientos para problemas pequeños es 10 veces mayor para un inicio aleatorio en comparación con uno realizado a partir de una heurística codiciosa. Esto se debe a que estas heurísticas de 2 opciones explotan partes "malas" de una solución, como los cruces. Estos tipos de heurísticas se utilizan a menudo dentro de las heurísticas de problemas de rutas de vehículos para volver a optimizar las soluciones de ruta. [29]
La heurística de Lin-Kernighan es un caso especial de la técnica V -opt o variable-opt. Implica los siguientes pasos:
El más popular de los métodos k -opt es el de 3-opt, introducido por Shen Lin de Bell Labs en 1965. Un caso especial de 3-opt es cuando los bordes no están separados (dos de los bordes son adyacentes entre sí) . En la práctica, a menudo es posible lograr una mejora sustancial con respecto a 2-opt sin el costo combinatorio de la 3-opt general restringiendo los cambios de 3 a este subconjunto especial donde dos de los bordes eliminados son adyacentes. Esta llamada opción de dos y media normalmente se sitúa aproximadamente a medio camino entre la opción 2 y la 3, tanto en términos de la calidad de los recorridos logrados como del tiempo necesario para realizarlos.
El método variable-opt está relacionado con el método k -opt y es una generalización del mismo. Mientras que los métodos k -opt eliminan un número fijo ( k ) de bordes del recorrido original, los métodos de opción variable no fijan el tamaño del conjunto de bordes a eliminar. En cambio, hacen crecer el conjunto a medida que continúa el proceso de búsqueda. El método más conocido de esta familia es el método Lin-Kernighan (mencionado anteriormente como un nombre inapropiado para 2-opt). Shen Lin y Brian Kernighan publicaron por primera vez su método en 1972, y fue la heurística más confiable para resolver problemas de vendedores ambulantes durante casi dos décadas. David Johnson y su equipo de investigación desarrollaron métodos más avanzados de opción variable en los Laboratorios Bell a finales de la década de 1980. Estos métodos (a veces llamados Lin-Kernighan-Johnson) se basan en el método Lin-Kernighan y agregan ideas de la búsqueda tabú y la computación evolutiva . La técnica básica de Lin-Kernighan proporciona resultados que garantizan al menos 3 opciones. Los métodos de Lin-Kernighan-Johnson calculan un recorrido de Lin-Kernighan y luego perturban el recorrido mediante lo que se ha descrito como una mutación que elimina al menos cuatro aristas y reconecta el recorrido de una manera diferente, optando luego por el nuevo recorrido. La mutación suele ser suficiente para desplazar el recorrido del mínimo local identificado por Lin-Kernighan. Los métodos V -opt se consideran ampliamente como las heurísticas más poderosas para el problema y pueden abordar casos especiales, como el problema del ciclo de Hamilton y otros TSP no métricos en los que otras heurísticas fallan. Durante muchos años, Lin-Kernighan-Johnson había identificado soluciones óptimas para todos los TSP en los que se conocía una solución óptima y había identificado las soluciones mejor conocidas para todos los demás TSP en los que se había probado el método.
Los algoritmos de cadena de Markov optimizados que utilizan subalgoritmos heurísticos de búsqueda local pueden encontrar una ruta extremadamente cercana a la ruta óptima para entre 700 y 800 ciudades.
TSP es una piedra de toque para muchas heurísticas generales ideadas para la optimización combinatoria, como los algoritmos genéticos , el recocido simulado , la búsqueda tabú , la optimización de colonias de hormigas , la dinámica de formación de ríos (ver inteligencia de enjambre ) y el método de entropía cruzada .
Esto comienza con un subgiro como el casco convexo y luego inserta otros vértices. [35]
El investigador de inteligencia artificial Marco Dorigo describió en 1993 un método para generar heurísticamente "buenas soluciones" para el TSP mediante una simulación de una colonia de hormigas llamada ACS ( ant colony system ). [36] Modela el comportamiento observado en hormigas reales para encontrar caminos cortos entre las fuentes de alimento y su nido, un comportamiento emergente que resulta de la preferencia de cada hormiga de seguir el rastro de feromonas depositadas por otras hormigas.
ACS envía una gran cantidad de agentes hormiga virtuales para explorar muchas rutas posibles en el mapa. Cada hormiga elige probabilísticamente la siguiente ciudad a visitar basándose en una heurística que combina la distancia a la ciudad y la cantidad de feromona virtual depositada en el borde de la ciudad. Las hormigas exploran, depositando feromonas en cada borde que cruzan, hasta que todas hayan completado un recorrido. En este punto, la hormiga que completó el recorrido más corto deposita feromonas virtuales a lo largo de su recorrido completo ( actualización global del recorrido ). La cantidad de feromona depositada es inversamente proporcional a la duración del recorrido: cuanto más corto es el recorrido, más se deposita.
En la métrica TSP , también conocida como delta-TSP o Δ-TSP, las distancias interurbanas satisfacen la desigualdad del triángulo .
Una restricción muy natural del TSP es exigir que las distancias entre ciudades formen una métrica para satisfacer la desigualdad del triángulo ; es decir, la conexión directa de A a B nunca está más lejos que la ruta por el intermedio C :
Luego, los bordes construyen una métrica en el conjunto de vértices. Cuando las ciudades se ven como puntos en el plano, muchas funciones de distancia natural son métricas y muchas instancias naturales de TSP satisfacen esta restricción.
Los siguientes son algunos ejemplos de TSP métricos para varias métricas.
Las dos últimas métricas aparecen, por ejemplo, al enrutar una máquina que perfora un conjunto determinado de agujeros en una placa de circuito impreso . La métrica de Manhattan corresponde a una máquina que ajusta primero una coordenada, y luego la otra, por lo que el tiempo para desplazarse a un nuevo punto es la suma de ambos movimientos. La métrica máxima corresponde a una máquina que ajusta ambas coordenadas simultáneamente, por lo que el tiempo para desplazarse a un nuevo punto es el más lento de los dos movimientos.
En su definición, el TSP no permite que las ciudades sean visitadas dos veces, pero muchas aplicaciones no necesitan esta restricción. En tales casos, una instancia simétrica y no métrica se puede reducir a una métrica. Esto reemplaza el gráfico original con un gráfico completo en el que la distancia entre ciudades se reemplaza por la longitud del camino más corto entre A y B en el gráfico original.
Para puntos en el plano euclidiano , la solución óptima al problema del viajante forma un polígono simple que pasa por todos los puntos, una poligonalización de los puntos. [37] Cualquier solución no óptima con cruces se puede convertir en una solución más corta sin cruces mediante optimizaciones locales. La distancia euclidiana obedece a la desigualdad del triángulo, por lo que el TSP euclidiano forma un caso especial de TSP métrico. Sin embargo, incluso cuando los puntos de entrada tienen coordenadas enteras, sus distancias generalmente toman la forma de raíces cuadradas y la longitud de un recorrido es una suma de radicales , lo que dificulta realizar el cálculo simbólico necesario para realizar comparaciones exactas de las longitudes de diferentes recorridos.
Al igual que el TSP general, el TSP euclidiano exacto es NP-duro, pero el problema con las sumas de radicales es un obstáculo para demostrar que su versión de decisión está en NP y, por lo tanto, NP-completa. Una versión discretizada del problema con distancias redondeadas a números enteros es NP-completa. [38] Con coordenadas racionales y la métrica euclidiana real, se sabe que el TSP euclidiano está en la Jerarquía de conteo, [39] una subclase de PSPACE. Con coordenadas reales arbitrarias, el TSP euclidiano no puede estar en tales clases, ya que hay innumerables entradas posibles. A pesar de estas complicaciones, el TSP euclidiano es mucho más fácil de aproximar que el caso métrico general. [40] Por ejemplo, el árbol de expansión mínimo del gráfico asociado con una instancia del TSP euclidiano es un árbol de expansión mínimo euclidiano y, por lo tanto, se puede calcular en el tiempo esperado O ( n log n ) para n puntos (considerablemente menor que el número de aristas). Esto permite que el algoritmo simple de 2 aproximaciones para TSP con la desigualdad triangular anterior funcione más rápidamente.
En general, para cualquier c > 0, donde d es el número de dimensiones en el espacio euclidiano, existe un algoritmo de tiempo polinomial que encuentra un recorrido de longitud como máximo (1 + 1/ c ) veces el óptimo para instancias geométricas de TSP en
tiempo; esto se denomina esquema de aproximación en tiempo polinomial (PTAS). [41] Sanjeev Arora y Joseph SB Mitchell recibieron el Premio Gödel en 2010 por su descubrimiento simultáneo de un PTAS para el TSP euclidiano.
En la práctica, se siguen utilizando heurísticas más simples con garantías más débiles.
En la mayoría de los casos, la distancia entre dos nodos de la red TSP es la misma en ambas direcciones. El caso en el que la distancia de A a B no es igual a la distancia de B a A se denomina TSP asimétrico. Una aplicación práctica de un TSP asimétrico es la optimización de rutas utilizando rutas a nivel de calle (que se vuelven asimétricas mediante calles de un solo sentido, vías de acceso, autopistas, etc.).
Resolver un gráfico TSP asimétrico puede resultar algo complejo. La siguiente es una matriz de 3 × 3 que contiene todos los pesos de ruta posibles entre los nodos A , B y C. Una opción es convertir una matriz asimétrica de tamaño N en una matriz simétrica de tamaño 2 N. [42]
Para duplicar el tamaño, cada uno de los nodos en el gráfico se duplica, creando un segundo nodo fantasma , vinculado al nodo original con un borde "fantasma" de peso muy bajo (posiblemente negativo), aquí denotado − w . (Como alternativa, los bordes fantasma tienen un peso 0 y el peso w se agrega a todos los demás bordes). La matriz original de 3 × 3 que se muestra arriba es visible en la parte inferior izquierda y la transposición del original en la parte superior derecha. Se han reemplazado las diagonales de ambas copias de la matriz por rutas de salto de bajo costo, representadas por −w . En el nuevo gráfico, ningún borde vincula directamente los nodos originales y ningún borde vincula directamente los nodos fantasma.
El peso - w de los bordes "fantasma" que unen los nodos fantasma a los nodos originales correspondientes debe ser lo suficientemente bajo para garantizar que todos los bordes fantasma deben pertenecer a cualquier solución TSP simétrica óptima en el nuevo gráfico ( w = 0 no siempre es lo suficientemente bajo). ). Como consecuencia, en el recorrido simétrico óptimo, cada nodo original aparece junto a su nodo fantasma (por ejemplo, una ruta posible es ), y al fusionar nuevamente los nodos original y fantasma obtenemos una solución (óptima) del problema asimétrico original (en nuestro ejemplo, ).
Hay un problema análogo en la teoría de la medida geométrica que pregunta lo siguiente: ¿bajo qué condiciones un subconjunto E del espacio euclidiano puede estar contenido en una curva rectificable (es decir, cuándo existe una curva con longitud finita que visita cada punto en E )? Este problema se conoce como el problema del viajante del analista .
Supongamos que son variables aleatorias independientes con distribución uniforme en el cuadrado , y sea la longitud del camino más corto (es decir, la solución TSP) para este conjunto de puntos, de acuerdo con la distancia euclidiana habitual . Se sabe [8] que, casi con seguridad,
donde es una constante positiva que no se conoce explícitamente. Dado que (ver más abajo), del teorema de convergencia acotada se deduce que , por lo tanto, los límites inferior y superior se siguen de los límites en .
El límite casi seguro puede no existir si las ubicaciones independientes se reemplazan con observaciones de un proceso ergódico estacionario con marginales uniformes. [43]
donde 0,522 proviene de los puntos cercanos al límite del cuadrado que tienen menos vecinos, y Christine L. Valenzuela y Antonia J. Jones obtuvieron el siguiente otro límite inferior numérico: [50]
Se ha demostrado que el problema es NP-difícil (más precisamente, está completo para la clase de complejidad FP NP ; ver problema de función ), y la versión del problema de decisión ("dados los costos y un número x , decide si hay una ronda -ruta de viaje más barata que x ") es NP-completa . El problema del cuello de botella del viajante de comercio también es NP-difícil. El problema sigue siendo NP-duro incluso en el caso en que las ciudades se encuentran en el plano con distancias euclidianas , así como en otros casos restrictivos. Quitar la condición de visitar cada ciudad "sólo una vez" no elimina la dureza NP, ya que en el caso plano hay un recorrido óptimo que visita cada ciudad sólo una vez (de lo contrario, por la desigualdad del triángulo , un atajo que se salta una visita repetida no aumentaría la duración del recorrido).
En el caso general, encontrar el recorrido más corto de un viajante de comercio es NPO completo. [51] Si la medida de la distancia es métrica (y por lo tanto simétrica), el problema se vuelve APX completo, [52] y el algoritmo de Christofides y Serdyukov lo aproxima dentro de 1,5. [53] [54] [9]
Si las distancias están restringidas a 1 y 2 (pero aún son una métrica), entonces la relación de aproximación pasa a ser 8/7. [55] En el caso asimétrico con desigualdad triangular , hasta hace poco, [ ¿cuándo? ] sólo se conocían garantías de ejecución logarítmicas. [56] En 2018, Svensson, Tarnawski y Végh desarrollaron una aproximación de factor constante. [57] El mejor actual [ ¿cuándo? ] , de Vera Traub y Jens Vygen , logra una relación de rendimiento de . [58] El límite de inaccesibilidad más conocido es 75/74. [59]
El problema de maximización correspondiente para encontrar el recorrido más largo del viajante de comercio es aproximadamente 63/38. [60] Si la función de distancia es simétrica, entonces el recorrido más largo se puede aproximar dentro de 4/3 mediante un algoritmo determinista [61] y dentro mediante un algoritmo aleatorio. [62]
El TSP, en particular la variante euclidiana del problema, ha atraído la atención de los investigadores en psicología cognitiva . Se ha observado que los humanos son capaces de producir soluciones casi óptimas rápidamente, de forma casi lineal, con un rendimiento que va desde un 1% menos eficiente, para gráficos con 10 a 20 nodos, hasta un 11% menos eficiente para gráficos. con 120 nodos. [63] [64] La aparente facilidad con la que los humanos generan con precisión soluciones casi óptimas al problema ha llevado a los investigadores a plantear la hipótesis de que los humanos usan una o más heurísticas, siendo las dos teorías más populares la hipótesis del casco convexo y la hipótesis del cruce. -Heurística de evitación. [65] [66] [67] Sin embargo, evidencia adicional sugiere que el desempeño humano es bastante variado, y las diferencias individuales, así como la geometría del gráfico, parecen afectar el desempeño en la tarea. [68] [69] [70] Sin embargo, los resultados sugieren que el rendimiento de la computadora en el TSP puede mejorarse comprendiendo y emulando los métodos utilizados por los humanos para estos problemas, [71] y también han llevado a nuevos conocimientos sobre los mecanismos de la respuesta humana. pensamiento. [72] El primer número del Journal of Problem Solving se dedicó al tema del desempeño humano en TSP, [73] y una revisión de 2011 enumeró docenas de artículos sobre el tema. [72]
Un estudio de 2011 sobre cognición animal titulado "Deja que la paloma conduzca el autobús", que lleva el nombre del libro infantil ¡ No dejes que la paloma conduzca el autobús! , examinaron la cognición espacial en palomas estudiando sus patrones de vuelo entre múltiples comederos en un laboratorio en relación con el problema del viajante. En el primer experimento, se colocaron palomas en la esquina de una sala de laboratorio y se les permitió volar hasta comederos cercanos que contenían guisantes. Los investigadores descubrieron que las palomas utilizaban en gran medida la proximidad para determinar qué comedero seleccionarían a continuación. En el segundo experimento, los comederos se dispusieron de tal manera que volar al comedero más cercano en cada oportunidad sería en gran medida ineficaz si las palomas tuvieran que visitar todos los comederos. Los resultados del segundo experimento indican que las palomas, aunque siguen favoreciendo las soluciones basadas en la proximidad, "pueden planificar varios pasos adelante a lo largo de la ruta cuando las diferencias en los costos de viaje entre rutas eficientes y menos eficientes basadas en la proximidad se vuelven mayores". [74] Estos resultados son consistentes con otros experimentos realizados con no primates, que han demostrado que algunos no primates fueron capaces de planificar rutas de viaje complejas. Esto sugiere que los no primates pueden poseer una capacidad cognitiva espacial relativamente sofisticada.
Cuando se le presenta una configuración espacial de fuentes de alimento, el ameboide Physarum polycephalum adapta su morfología para crear un camino eficiente entre las fuentes de alimento, que también puede verse como una solución aproximada al TSP. [75]
Para la evaluación comparativa de los algoritmos TSP, se mantiene TSPLIB [76] una biblioteca de instancias de muestra del TSP y problemas relacionados; consulte la referencia externa de TSPLIB. Muchos de ellos son listas de ciudades reales y diseños de circuitos impresos reales .