Problema del vendedor ambulante

Problema NP-difícil en optimización combinatoria

Solución del problema de un agente ambulante: la línea negra muestra el bucle más corto posible que conecta cada punto rojo.

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.

Historia

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]

William Rowan Hamilton

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]

Descripción

Como un problema de grafos

TSP simétrico con cuatro ciudades.

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.

Asimétrico y simétrico

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.

Problemas relacionados

• Una formulación equivalente en términos de teoría de grafos es: Dado un gráfico ponderado completo (donde los vértices representarían las ciudades, los bordes representarían las carreteras y los pesos serían el costo o la distancia de esa carretera), encuentre un ciclo hamiltoniano con el menor peso. Esto es más general que el problema de la ruta hamiltoniana , que solo pregunta si existe una ruta (o ciclo) hamiltoniana en un gráfico no ponderado incompleto.
• El requisito de regresar a la ciudad inicial no cambia la complejidad computacional del problema; ver problema del camino hamiltoniano .
• Otro problema relacionado es el problema del cuello de botella del viajante : encontrar un ciclo hamiltoniano en un gráfico ponderado con el peso mínimo del borde más pesado . Un ejemplo del mundo real es evitar calles estrechas con autobuses grandes. ^[14] El problema tiene una importancia práctica considerable, aparte de los ámbitos evidentes del transporte y la logística. Un ejemplo clásico es la fabricación de circuitos impresos : programación de una ruta de la máquina perforadora para perforar agujeros en una PCB. En aplicaciones de mecanizado o perforación robótica, las "ciudades" son piezas para mecanizar o agujeros (de diferentes tamaños) para perforar, y el "costo del viaje" incluye el tiempo para reequipar el robot (problema de secuenciación de trabajos de una sola máquina). ^[15]
• El problema generalizado del vendedor ambulante , también conocido como "problema del político viajero", trata de "estados" que tienen (una o más) "ciudades", y el vendedor debe visitar exactamente una ciudad de cada estado. Una aplicación se encuentra al solicitar una solución al problema del material de corte para minimizar los cambios de cuchillas. Otro se refiere a la perforación en la fabricación de semiconductores ; véase, por ejemplo, la patente estadounidense 7.054.798 . Noon y Bean demostraron que el problema generalizado del viajante de comercio se puede transformar en un TSP estándar con el mismo número de ciudades, pero con una matriz de distancia modificada .
• El problema del orden secuencial aborda el problema de visitar un conjunto de ciudades, donde existen relaciones de precedencia entre las ciudades.
• Una pregunta común en las entrevistas en Google es cómo enrutar datos entre nodos de procesamiento de datos; las rutas varían según el tiempo para transferir los datos, pero los nodos también difieren en su potencia informática y almacenamiento, lo que agrava el problema de dónde enviar los datos.
• El problema del comprador viajero se refiere a un comprador que se encarga de adquirir un conjunto de productos. Puede adquirir estos productos en varias ciudades, pero a diferentes precios, y no todas las ciudades ofrecen los mismos productos. El objetivo es encontrar una ruta entre un subconjunto de ciudades que minimice el costo total (costo de viaje + costo de compra) y permita la compra de todos los productos requeridos.

Formulaciones de programación lineal entera

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: ${\displaystyle 1,\ldots ,n}$ ${\displaystyle c_{ij}>0}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise.}}\end{cases}}}$

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.

${\displaystyle \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}.}$

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 ${\displaystyle \{x_{ij}\}_{i,j}}$ ${\displaystyle x_{ij}=0}$ ${\displaystyle 2n}$

${\displaystyle \sum _{i=1,i\neq j}^{n}x_{ij}=1}$por y para ${\displaystyle j=1,\ldots ,n}$ ${\displaystyle \sum _{j=1,j\neq i}^{n}x_{ij}=1}$ ${\displaystyle i=1,\ldots ,n.}$

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.

Formulación de Miller-Tucker-Zemlin

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] ${\displaystyle x_{ij}}$ ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle u_{i}}$ ${\displaystyle 1}$ ${\displaystyle u_{i}<u_{j}}$ ${\displaystyle i}$ ${\displaystyle j.}$ ${\displaystyle x_{ij}}$ ${\displaystyle u_{i}}$ ${\displaystyle u_{i}}$ ${\displaystyle 1}$ ${\displaystyle i.}$

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 ${\displaystyle \geq }$ ${\displaystyle >}$

${\displaystyle u_{j}\geq u_{i}+1}$si ${\displaystyle x_{ij}=1.}$

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. ${\displaystyle u_{j}\geq u_{i}+x_{ij}}$ ${\displaystyle u_{j}\geq u_{i}}$ ${\displaystyle x_{ij}=0,}$ ${\displaystyle n(n-1)}$

${\displaystyle u_{i}-u_{j}+1\leq (n-1)(1-x_{ij})}$para todos los distintos ${\displaystyle i,j\in \{2,\dotsc ,n\},}$

donde el término constante proporciona suficiente holgura que no impone una relación entre y ${\displaystyle n-1}$ ${\displaystyle x_{ij}=0}$ ${\displaystyle u_{j}}$ ${\displaystyle u_{i}.}$

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. ${\displaystyle u_{i}}$ ${\displaystyle 1}$ ${\displaystyle 1.}$ ${\displaystyle 1,}$ ${\displaystyle 1}$

La formulación MTZ de TSP es, por tanto, el siguiente problema de programación lineal entera:

${\displaystyle {\begin{aligned}\min \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}&\colon &&\\x_{ij}\in {}&\{0,1\}&&i,j=1,\ldots ,n;\\\sum _{i=1,i\neq j}^{n}x_{ij}={}&1&&j=1,\ldots ,n;\\\sum _{j=1,j\neq i}^{n}x_{ij}={}&1&&i=1,\ldots ,n;\\u_{i}-u_{j}+1\leq {}&(n-1)(1-x_{ij})&&2\leq i\neq j\leq n;\\2\leq u_{i}\leq {}&n&&2\leq i\leq n.\end{aligned}}}$

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.

Formulación de Dantzig-Fulkerson-Johnson

Etiqueta las ciudades con los números 1, ..., n y define:

${\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise.}}\end{cases}}}$

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: ${\displaystyle c_{ij}>0}$

${\displaystyle {\begin{aligned}\min &\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}\colon &&\\&\sum _{i=1,i\neq j}^{n}x_{ij}=1&&j=1,\ldots ,n;\\&\sum _{j=1,j\neq i}^{n}x_{ij}=1&&i=1,\ldots ,n;\\&\sum _{i\in Q}{\sum _{j\neq i,j\in Q}{x_{ij}}}\leq |Q|-1&&\forall Q\subsetneq \{1,\ldots ,n\},|Q|\geq 2.\\\end{aligned}}}$

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]

Calcular una solución

Las líneas de ataque tradicionales para los problemas NP-difíciles son las siguientes:

• Diseñar algoritmos exactos , que funcionen razonablemente rápido sólo para problemas de pequeño tamaño.
• Idear algoritmos "subóptimos" o heurísticos , es decir, algoritmos que entreguen soluciones aproximadas en un tiempo razonable.
• Encontrar casos especiales para el problema ("subproblemas") para los cuales sea posible una heurística mejor o más exacta.

Algoritmos exactos

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. ${\displaystyle O(n!)}$

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. ${\displaystyle O(n^{2}2^{n})}$

Solución a un TSP simétrico con 7 ciudades mediante búsqueda de fuerza bruta. Nota: Número de permutaciones: (7−1)!/2 = 360

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] ${\displaystyle O(1.9999^{n})}$ ${\displaystyle O(1.728^{n})}$

Otros enfoques incluyen:

• Varios algoritmos de ramificación y vinculación , que se pueden utilizar para procesar TSP que contienen miles de ciudades.

Solución de un TSP con 7 ciudades usando un algoritmo simple de Branch andbound. Nota: El número de permutaciones es mucho menor que el de la búsqueda por fuerza bruta.

• Algoritmos de mejora progresiva, que utilizan técnicas que recuerdan a la programación lineal . Esto funciona bien para hasta 200 ciudades.
• Implementaciones de generación de cortes de ramificación y encuadernación y de problemas específicos ( ramificación y corte ^[26] ); ^[27] este es el método elegido para resolver instancias grandes. Este enfoque tiene el récord actual, resolviendo un caso con 85.900 ciudades, ver Applegate et al. (2006).

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).

Algoritmos heurísticos y de aproximación.

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.

Heurística constructiva

Algoritmo de vecino más cercano para un TSP con 7 ciudades. La solución cambia a medida que se cambia el punto de partida.

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. ${\displaystyle \Theta (\log |V|)}$

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

Creando una coincidencia

Usando una heurística de acceso directo en el gráfico creado por la coincidencia anterior

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. ${\displaystyle O(n)}$

1. Encuentre un árbol de expansión mínimo para el problema.
2. Cree duplicados para cada borde para crear un gráfico euleriano.
3. Encuentre un recorrido euleriano para este gráfico.
4. Convertir a TSP: si una ciudad se visita dos veces, cree un acceso directo desde la ciudad anterior a esta en el recorrido hasta la siguiente.

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] ${\displaystyle O(n^{3})}$

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:

1. Encuentre un árbol de expansión mínimo para el problema.
2. Cree una coincidencia para el problema con el conjunto de ciudades de orden impar.
3. Encuentre un recorrido euleriano para este gráfico.
4. Convierta a TSP usando atajos.

Intercambio por pares

Un ejemplo de una iteración de 2 opciones

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 dichas 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] ${\displaystyle O(n)}$ ${\displaystyle O(n\log(n))}$

k -opt heurística o heurística de Lin-Kernighan

La heurística de Lin-Kernighan es un caso especial de la técnica V -opt o variable-opt. Implica los siguientes pasos:

1. Dado un recorrido, eliminar k aristas mutuamente disjuntas.
2. Vuelva a ensamblar los fragmentos restantes en un recorrido, sin dejar subtours separados (es decir, no conecte los puntos finales de un fragmento). En efecto, esto simplifica el TSP bajo consideración y lo convierte en un problema mucho más simple.
3. Cada punto final de fragmento se puede conectar a 2 k  − 2 otras posibilidades: de un total de 2 k puntos finales de fragmento disponibles, los dos puntos finales del fragmento bajo consideración no están permitidos. Un TSP de 2 k ciudades tan restringido se puede resolver con métodos de fuerza bruta para encontrar la recombinación de menor costo de los fragmentos originales.

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.

Heurística V -opt

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.

Mejora aleatoria

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 .

Heurística de inserción restrictiva

Esto comienza con un subgiro como el casco convexo y luego inserta otros vértices. ^[35]

Optimización de colonias de hormigas

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.

1) Una hormiga elige un camino entre todos los caminos posibles y deja un rastro de feromonas en él. 2) Todas las hormigas viajan por caminos diferentes, dejando un rastro de feromonas proporcional a la calidad de la solución. 3) Cada arista del mejor camino está más reforzada que otras. 4) La evaporación asegura que las malas soluciones desaparezcan. El mapa es obra de Yves Aubry [2].

Algoritmo de optimización de colonias de hormigas para un TSP con 7 ciudades: las líneas rojas y gruesas en el mapa de feromonas indican la presencia de más feromonas

Casos especiales

Métrico

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 :

${\displaystyle d_{AB}\leq d_{AC}+d_{CB}}$.

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.

• En el TSP euclidiano (ver más abajo), la distancia entre dos ciudades es la distancia euclidiana entre los puntos correspondientes.
• En el TSP rectilíneo, la distancia entre dos ciudades es la suma de los valores absolutos de las diferencias de sus coordenadas xey . Esta métrica a menudo se denomina distancia de Manhattan o métrica de manzana.
• En la métrica máxima , la distancia entre dos puntos es el máximo de los valores absolutos de las diferencias de sus coordenadas xey .

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. ${\displaystyle d_{AB}}$

euclidiano

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

${\displaystyle O{\left(n(\log n)^{O(c{\sqrt {d}})^{d-1}}\right)}}$

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.

Asimétrico

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.).

Conversión a simétrica

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, ). ${\displaystyle \mathrm {A\to A'\to C\to C'\to B\to B'\to A} }$ ${\displaystyle \mathrm {A\to C\to B\to A} }$

El problema del analista

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 .

Longitud del camino para conjuntos aleatorios de puntos en un cuadrado

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, ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle n}$ ${\displaystyle [0,1]^{2}}$ ${\displaystyle L_{n}^{\ast }}$

${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta \qquad {\text{when }}n\to \infty ,}$

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 . ${\displaystyle \beta }$ ${\displaystyle L_{n}^{*}\leq 2{\sqrt {n}}+2}$ ${\displaystyle \beta =\lim _{n\to \infty }\mathbb {E} [L_{n}^{*}]/{\sqrt {n}}}$ ${\displaystyle \beta }$ ${\displaystyle \mathbb {E} [L_{n}^{*}]}$

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] ${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta }$ ${\displaystyle n\to \infty }$ ${\displaystyle X_{1},\ldots ,X_{n}}$

límite superior

• Se tiene , y por lo tanto , se utiliza un camino ingenuo que visita monótonamente los puntos dentro de cada uno de los sectores de ancho del cuadrado. ${\displaystyle L^{*}\leq 2{\sqrt {n}}+2}$ ${\displaystyle \beta \leq 2}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle 1/{\sqrt {n}}}$
• Pocos ^[44] demostraron , por tanto , mejorado posteriormente por Karloff (1987): . ${\displaystyle L_{n}^{*}\leq {\sqrt {2n}}+1.75}$ ${\displaystyle \beta \leq {\sqrt {2}}}$ ${\displaystyle \beta \leq 0.984{\sqrt {2}}}$
• Fietcher ^[45] mostró un límite superior de . ${\displaystyle \beta \leq 0.73\dots }$

Límite inferior

• Al observar que es mayor que la distancia entre el punto más cercano y el más cercano , se obtiene (después de un breve cálculo) ${\displaystyle \mathbb {E} [L_{n}^{*}]}$ ${\displaystyle n}$ ${\displaystyle X_{0}}$ ${\displaystyle X_{i}\neq X_{0}}$

${\displaystyle \mathbb {E} [L_{n}^{*}]\geq {\tfrac {1}{2}}{\sqrt {n}}.}$

• Se obtiene un mejor límite inferior observando que es mayor que multiplicado por la suma de las distancias entre el punto más cercano y el segundo más cercano , lo que da ^[8] ${\displaystyle \mathbb {E} [L_{n}^{*}]}$ ${\displaystyle n/2}$ ${\displaystyle X_{0}}$ ${\displaystyle X_{i},X_{j}\neq X_{0}}$

${\displaystyle \mathbb {E} [L_{n}^{*}]\geq {\bigl (}{\tfrac {1}{4}}+{\tfrac {3}{8}}{\bigr )}{\sqrt {n}}={\tfrac {5}{8}}{\sqrt {n}},}$

• El mejor actualmente ^{[ ¿cuándo? ]} el límite inferior es ^[46]

${\displaystyle \mathbb {E} [L_{n}^{*}]\geq {\bigl (}{\tfrac {5}{8}}+{\tfrac {19}{5184}}{\bigr )}{\sqrt {n}},}$

• Held y Karp dieron un algoritmo de tiempo polinómico que proporciona límites numéricos inferiores para , y por tanto para , que parecen ser buenos hasta más o menos el 1%. ^{[47] [48]} En particular, David S. Johnson obtuvo un límite inferior mediante un experimento informático: ^[49] ${\displaystyle L_{n}^{*}}$ ${\displaystyle \beta (\simeq L_{n}^{*}/{\sqrt {n}})}$

${\displaystyle L_{n}^{*}\gtrsim 0.7080{\sqrt {n}}+0.522,}$

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]

${\displaystyle L_{n}^{*}\gtrsim 0.7078{\sqrt {n}}+0.551}$.

Complejidad computacional

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).

Complejidad de la aproximación

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  [de] , logra una relación de rendimiento de . ^[58] El límite de inaccesibilidad más conocido es 75/74. ^[59] ${\displaystyle 22+\varepsilon }$

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] ${\displaystyle (33+\varepsilon )/25}$

Actuación humana y animal.

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.

Computación natural

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]

Puntos de referencia

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 .

Cultura popular

• Travelling Salesman , del director Timothy Lanzone, es la historia de cuatro matemáticos contratados por el gobierno de Estados Unidos para resolver el problema más difícil de alcanzar en la historia de la informática: P vs. NP . ^[77]
• El matemático Bob Bosche utiliza soluciones al problema en un subgénero llamado arte TSP. ^[78]

Ver también

• Problema de los viajeros canadienses
• Algoritmo exacto
• Problema de inspección de ruta (también conocido como "problema del cartero chino")
• Establecer problema de TSP
• Siete puentes de Königsberg
• El problema del viajante de Steiner
• Desafío del metro
• Desafío del tubo
• Problema de ruta de vehículos
• Exploración de gráficos
• Problema mixto del cartero chino
• Enrutamiento de arco
• Problema de ruta del quitanieves
• matriz monge

Notas

1. Consulte el problema de la gira mundial de TSP que ya se ha resuelto con un margen de error del 0,05% de la solución óptima. [1]
2. "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 qué debe hacer para obtener comisiones y estar seguro de un feliz éxito en su negocio (por un viejo comisario viajero )
3. Se puede encontrar una discusión sobre los primeros trabajos de Hamilton y Kirkman en Graph Theory, 1736-1936 de Biggs, Lloyd y Wilson (Clarendon Press, 1986).
4. Citado y traducción al inglés en Schrijver (2005). Original alemán: "Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden . Este problema es natural debido a las diferentes reglas, pero no es necesario que las reglas se ajusten a las reglas. m diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."
5. Lawler, EL (1985). El problema del viajante: un recorrido guiado por la optimización combinatoria (Repr. con correcciones. Ed.). John Wiley e hijos. ISBN 978-0-471-90413-7.
6. Robinson, Julia (5 de diciembre de 1949). Sobre el juego hamiltoniano (un problema del viajante) (PDF) (Reporte técnico). Santa Mónica, CA: Corporación RAND. RM-303 . Consultado el 2 de mayo de 2020 a través del Centro de información técnica de defensa.
7. En Schrijver (2005) se puede encontrar un tratamiento detallado de la conexión entre Menger y Whitney, así como el crecimiento en el estudio de TSP.
8. Beardwood, Halton y Hammersley (1959).
9. van Bevern, René; Slugina, Viktoriia A. (2020). "Una nota histórica sobre el algoritmo de aproximación 3/2 para el problema métrico del viajante". Historia Matemática . 53 : 118-127. arXiv : 2004.02437 . doi :10.1016/j.hm.2020.04.003. S2CID  214803097.
10. Klarreich, Erica (30 de enero de 2013). "Los informáticos encuentran nuevos atajos para el infame problema del viajante". CABLEADO . Consultado el 14 de junio de 2015 .
11. Klarreich, Erica (8 de octubre de 2020). "Los informáticos baten el récord de vendedores ambulantes". Revista Quanta . Consultado el 13 de octubre de 2020 .
12. Karlin, Anna R .; Klein, Nathan; Gharan, Shayan Oveis (2021), "Un algoritmo de aproximación (ligeramente) mejorado para TSP métrico", en Khuller, Samir ; Williams, Virginia Vassilevska (eds.), STOC '21: 53.º Simposio anual ACM SIGACT sobre teoría de la informática, evento virtual, Italia, 21-25 de junio de 2021 , págs. 32-45, arXiv : 2007.01409 , doi :10.1145/3406325.3451009 , ISBN 978-1-4503-8053-9, S2CID  220347561
13. Rego, César; Gamboa, Dorabela; Glover, Fred; Osterman, Colin (2011), "Heurística del problema del vendedor ambulante: métodos líderes, implementaciones y últimos avances", European Journal of Operational Research , 211 (3): 427–441, doi :10.1016/j.ejor.2010.09.010, MR  2774420, S2CID  2856898.
14. "¿Cómo se arreglan las rutas de los autobuses escolares? Llame al MIT en el Wall Street Journal" (PDF) .
15. Behzad, Arash; Modarres, Mohammad (2002), "Nueva transformación eficiente del problema del viajante generalizado en el problema del viajante", Actas de la 15ª Conferencia Internacional de Ingeniería de Sistemas (Las Vegas)
16. Papadimitriou, CH; Steiglitz, K. (1998), Optimización combinatoria: algoritmos y complejidad , Mineola, Nueva York: Dover, págs.308-309.
17. Tucker, AW (1960), "Sobre gráficos dirigidos y programas enteros", Proyecto de investigación matemática de IBM (Universidad de Princeton)
18. Dantzig, George B. (1963), Extensiones y programación lineal , Princeton, Nueva Jersey: PrincetonUP, págs. 545–7, ISBN 0-691-08000-3 , sexta edición, 1974. 
19. Velednitsky, Mark (2017). "Breve prueba combinatoria de que el politopo DFJ está contenido en el politopo MTZ para el problema del viajante asimétrico". Cartas de investigación operativa . 45 (4): 323–324. arXiv : 1805.06997 . doi :10.1016/j.orl.2017.04.010. S2CID  6941484.
20. Bektaş, Tolga; Gouveia, Luis (2014). "¿Réquiem por las limitaciones de eliminación del subgiro Miller-Tucker-Zemlin?". Revista europea de investigación operativa . 236 (3): 820–832. doi :10.1016/j.ejor.2013.07.038.
21. CE Miller, AW Tucker y RA Zemlin. 1960. Formulación de programación entera de problemas del viajante de comercio. J. ACM 7, 4 (octubre de 1960), 326–329. DOI: https://doi.org/10.1145/321043.321046
22. Dantzig, G.; Fulkerson, R.; Johnson, S. (noviembre de 1954). "Solución de un problema de viajante de comercio a gran escala". Revista de la Sociedad de Investigación de Operaciones de América . 2 (4): 393–410. doi :10.1287/opre.2.4.393.
23. Bellman (1960), Bellman (1962), Held y Karp (1962)
24. Woeginger (2003).
25. Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs (2019). "Aceleraciones cuánticas para algoritmos de programación dinámica de tiempo exponencial". Actas del trigésimo simposio anual ACM-SIAM sobre algoritmos discretos . págs. 1783-1793. doi :10.1137/1.9781611975482.107. ISBN 978-1-61197-548-2. S2CID  49743824.
26. Padberg y Rinaldi (1991).
27. Problema del vendedor ambulante: sucursal y destino en YouTube . Cómo cortar ramas infructuosas usando filas y columnas reducidas como en el algoritmo matricial húngaro
28. Applegate, David; Bixby, Robert; Chvátal, Vašek; Cocinero, William; Helsgaun, Keld (junio de 2004). "Gira óptima por Suecia" . Consultado el 11 de noviembre de 2020 .
29. Johnson, DS ; McGeoch, LA (1997). "El problema del viajante: un estudio de caso sobre optimización local" (PDF) . En Aarts, EHL; Lenstra, JK (eds.). Búsqueda Local en Optimización Combinatoria . Londres: John Wiley and Sons Ltd. págs. 215–310.
30. Gutina, Gregorio; Sí, Anders; Zverovich, Alexey (15 de marzo de 2002). "El viajante de comercio no debe ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP". Matemática Aplicada Discreta . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .>
31. Zverovich, Alexei; Zhang, Weixiong; Sí, Anders; McGeoch, Lyle A.; Gutin, Gregorio; Johnson, David S. (2007), "Análisis experimental de heurística para el ATSP", El problema del viajante y sus variaciones , Optimización combinatoria, Springer, Boston, MA, págs. 445–487, CiteSeerX 10.1.1.24.2386 , doi :10.1007/0-306-48213-4_10, ISBN  978-0-387-44459-8
32. Rosenkrantz, DJ; Stearns, RE; Lewis, PM (14 a 16 de octubre de 1974). Algoritmos aproximados para el problema del viajante de comercio . 15º Simposio Anual sobre Conmutación y Teoría de Autómatas (swat 1974). doi :10.1109/SWAT.1974.4.
33. Rayo, SS; Bandyopadhyay, S.; Pal, SK (2007). "Operadores genéticos para la optimización combinatoria en TSP y ordenamiento de genes de microarrays". Inteligencia Aplicada . 26 (3): 183–195. CiteSeerX 10.1.1.151.132 . doi :10.1007/s10489-006-0018-y. S2CID  8130854. 
34. Kahng, AB; Reda, S. (2004). "Combina dos veces y cose: una nueva heurística de construcción de giras de TSP". Cartas de investigación operativa . 32 (6): 499–509. doi :10.1016/j.orl.2004.04.001.
35. Alatartsev, Sergey; Agustín, Marco; Ortmeier, Frank (2 de junio de 2013). "Heurística de inserción restrictiva para el problema del viajante de comercio con los vecindarios" (PDF) . Actas de la Conferencia Internacional sobre Planificación y Programación Automatizada . 23 : 2–10. doi : 10.1609/icaps.v23i1.13539. ISSN  2334-0843. S2CID  18691261.
36. Dorigo, Marco; Gambardella, Luca María (1997). "Colonias de hormigas para el problema del viajante". Biosistemas . 43 (2): 73–81. Código Bib : 1997BiSys..43...73D. CiteSeerX 10.1.1.54.7734 . doi :10.1016/S0303-2647(97)01708-5. PMID  9231906. S2CID  8243011. 
37. Quintas, LV; Supnick, Fred (1965). "Sobre algunas propiedades de los circuitos hamiltonianos más cortos". El Mensual Matemático Estadounidense . 72 (9): 977–980. doi :10.2307/2313333. JSTOR  2313333. SEÑOR  0188872.
38. Papadimitriou (1977).
39. Allender y col. (2007).
40. Larson y Odoni (1981).
41. Arora (1998).
42. Jonker, Roy; Volgenant, tonelada (1983). "Transformar los problemas asimétricos en simétricos del viajante de comercio". Cartas de investigación operativa . 2 (161–163): 1983. doi :10.1016/0167-6377(83)90048-2.
43. Arlotto, Alessandro; Steele, J. Michael (2016), "Teorema de Beardwood-Halton-Hammersley para secuencias ergódicas estacionarias: un contraejemplo", The Annals of Applied Probability , 26 (4): 2141–2168, arXiv : 1307.0221 , doi : 10.1214/15- AAP1142, S2CID  8904077
44. Pocos, L. (1955). "El camino más corto y el camino más corto a través de n puntos". Matemática . 2 (2): 141-144. doi :10.1112/s0025579300000784.
45. Fiechter, C.-N. (1994). "Un algoritmo de búsqueda tabú paralelo para problemas de grandes viajantes". Desct. Matemáticas Aplicadas . 51 (3): 243–267. doi : 10.1016/0166-218X(92)00033-I .
46. Steinerberger (2015).
47. Retenido, M.; Karp, RM (1970). "El problema del viajante y los árboles de luz mínima". La investigación de operaciones . 18 (6): 1138-1162. doi :10.1287/opre.18.6.1138.
48. Goemans, Michel X .; Bertsimas, Dimitris J. (1991). "Análisis probabilístico del límite inferior de Held y Karp para el problema del viajante euclidiano". Matemáticas de la Investigación de Operaciones . 16 (1): 72–89. doi :10.1287/moor.16.1.72.
49. "error". acerca de.att.com .
50. Christine L. Valenzuela y Antonia J. Jones Archivado el 25 de octubre de 2007 en Wayback Machine.
51. Orponen, P.; Mannila, H. (1987). Sobre la aproximación preservando las reducciones: problemas completos y medidas sólidas' (Informe). Departamento de Ciencias de la Computación, Universidad de Helsinki. Informe Técnico C-1987–28.
52. Papadimitriou y Yannakakis (1993).
53. Cristofides (1976).
54. Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [Sobre algunos paseos extremos en gráficos] (PDF) , Upravlyaemye Sistemy (en ruso), 17 : 76–79
55. Berman y Karpinski (2006).
56. Kaplan y col. (2004).
57. Svensson, Ola; Tarnawski, Jakub; Végh, László A. (2018). "Un algoritmo de aproximación de factor constante para el problema del viajante asimétrico". Actas del 50º Simposio Anual ACM SIGACT sobre Teoría de la Computación . Stoc 2018. Los Ángeles, CA, EE. UU.: ACM Press. págs. 204-213. doi :10.1145/3188745.3188824. ISBN 978-1-4503-5559-9. S2CID  12391033.
58. Traub, Vera ; Vygen, Jens (8 de junio de 2020). "Un algoritmo de aproximación mejorado para ATSP". Actas del 52º Simposio Anual ACM SIGACT sobre Teoría de la Computación . Stoc 2020. Chicago, IL: ACM. págs. 1-13. arXiv : 1912.00670 . doi :10.1145/3357713.3384233. ISBN 978-1-4503-6979-4. S2CID  208527125.
59. Karpinski, Lampis y Schmied (2015).
60. Kosaraju, Park y Stein (1994).
61. Serdyukov (1984).
62. Hassin y Rubinstein (2000).
63. Macgregor, JN; Ormerod, T. (junio de 1996), "Actuación humana en el problema del viajante", Perception & Psychophysics , 58 (4): 527–539, doi : 10.3758/BF03213088 , PMID  8934685.
64. Seco, Mateo; Lee, Michael D.; Vickers, Douglas; Hughes, Peter (2006). "Desempeño humano en problemas de vendedores ambulantes presentados visualmente con números variables de nodos". La revista de resolución de problemas . 1 (1). CiteSeerX 10.1.1.360.9763 . doi :10.7771/1932-6246.1004. ISSN  1932-6246. 
65. Rooij, Iris Van; Stege, Ulrike; Schactman, Alissa (1 de marzo de 2003). "Cruces convexos de casco y recorrido en el problema del viajante de comercio euclidiano: implicaciones para los estudios del desempeño humano". Memoria y cognición . 31 (2): 215–220. CiteSeerX 10.1.1.12.6117 . doi :10.3758/bf03194380. ISSN  0090-502X. PMID  12749463. S2CID  18989303. 
66. MacGregor, James N.; Chu, Yun (2011). "Desempeño humano en el viajante de comercio y problemas relacionados: una revisión". La revista de resolución de problemas . 3 (2). doi : 10.7771/1932-6246.1090 . ISSN  1932-6246.
67. MacGregor, James N.; Crónica, Edward P.; Ormerod, Thomas C. (1 de marzo de 2004). "¿Casco convexo o evitación de cruces? Heurística de solución en el problema del viajante de comercio". Memoria y cognición . 32 (2): 260–270. doi : 10.3758/bf03196857 . ISSN  0090-502X. PMID  15190718.
68. Vickers, Douglas; Mayo, Teresa; Heitmann, Megan; Lee, Michael D; Hughes, Peter (2004). "Inteligencia y diferencias individuales en el rendimiento en tres tipos de problemas de optimización presentados visualmente". Personalidad y diferencias individuales . 36 (5): 1059-1071. doi :10.1016/s0191-8869(03)00200-9.
69. Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva (12 de junio de 2017). "Reconocer violaciones heurísticas de evitación de cruce al resolver el problema del vendedor ambulante euclidiano". Investigación Psicológica . 82 (5): 997–1009. doi :10.1007/s00426-017-0881-7. ISSN  0340-0727. PMID  28608230. S2CID  3959429.
70. Kyritsis, Markos; Blathras, George; Gulliver, Stephen; Varela, Vasiliki-Alexia (11 de enero de 2017). "El sentido de dirección y la escrupulosidad como predictores del desempeño en el problema del viajante euclidiano". Heliyón . 3 (11): e00461. Código Bib : 2017Heliy...300461K. doi : 10.1016/j.heliyon.2017.e00461 . PMC 5727545 . PMID  29264418. 
71. Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva; Din, Shahab Ud (diciembre de 2018). "Comportamiento humano en el problema del viajante euclidiano: modelado computacional de heurísticas y efectos figurativos". Investigación de sistemas cognitivos . 52 : 387–399. doi :10.1016/j.cogsys.2018.07.027. S2CID  53761995.
72. MacGregor, James N.; Chu, Yun (2011), "Desempeño humano en el viajante de comercio y problemas relacionados: una revisión", Journal of Problem Solving , 3 (2), doi : 10.7771/1932-6246.1090.
73. Journal of Problem Solving 1(1), 2006, consultado el 6 de junio de 2014.
74. Gibson, Brett; Wilkinson, Mateo; Kelly, Debbie (1 de mayo de 2012). "Deja que la paloma conduzca el autobús: las palomas pueden planificar rutas futuras en una habitación". Cognición animal . 15 (3): 379–391. doi :10.1007/s10071-011-0463-9. ISSN  1435-9456. PMID  21965161. S2CID  14994429.
75. Jones, Jeff; Adamatzky, Andrew (2014), "Cálculo del problema del viajante mediante una masa que se encoge" (PDF) , Computación natural : 2, 13, arXiv : 1303.4969 , Bibcode : 2013arXiv1303.4969J
76. "TSPLIB". comopt.ifi.uni-heidelberg.de . Consultado el 10 de octubre de 2020 .
77. Geere, Duncan (26 de abril de 2012). "'La película El viajante considera las repercusiones si P es igual a NP ". Reino Unido cableado . Consultado el 26 de abril de 2012 .
78. Cuando la Mona Lisa es NP-Hard Por Evelyn Lamb, Scientific American, 31 de abril de 2015

Referencias

• Applegate, DL; Bixby, RM; Chvátal, V.; Cook, WJ (2006), El problema del viajante , Princeton University Press, ISBN 978-0-691-12993-8.
• Allender, Eric; Bürgisser, Peter; Kjeldgaard-Pedersen, Johan; Mitersen, Peter Bro (2007), "Sobre la complejidad del análisis numérico" (PDF) , SIAM J. Comput. , 38 (5): 1987–2006, CiteSeerX  10.1.1.167.5495 , doi :10.1137/070697926.
• Arora, Sanjeev (1998), "Esquemas de aproximación de tiempo polinómico para el viajante de comercio euclidiano y otros problemas geométricos" (PDF) , Journal of the ACM , 45 (5): 753–782, doi :10.1145/290179.290180, MR  1668147, S2CID  3023351.
• Beardwood, J.; Halton, JH; Hammersley, JM (octubre de 1959), "El camino más corto a través de muchos puntos", Actas de la Sociedad Filosófica de Cambridge , 55 (4): 299–327, Bibcode :1959PCPS...55..299B, doi :10.1017/s0305004100034095, ISSN  0305-0041, S2CID  122062088.
• Bellman, R. (1960), "Procesos combinatorios y programación dinámica", en Bellman, R.; Hall, M. Jr. (eds.), Análisis combinatorio, Actas de simposios en matemáticas aplicadas 10 , Sociedad Matemática Estadounidense, págs..
• Bellman, R. (1962), "Tratamiento de programación dinámica del problema del viajante", Revista de la Asociación de Maquinaria de Computación , 9 : 61–63, doi : 10.1145/321105.321111 , S2CID  15649582.
• Berman, Piotr; Karpinski, Marek (2006), "Algoritmo de aproximación 8/7 para (1,2) -TSP", Proc. 17º Simposio ACM-SIAM sobre algoritmos discretos (SODA '06), págs. 641–648, CiteSeerX  10.1.1.430.2224 , doi :10.1145/1109557.1109627, ISBN 978-0-89871-605-4, S2CID  9054176, ECCC  TR05-069.
• Christofides, N. (1976), Análisis del peor de los casos de una nueva heurística para el problema del viajante , Informe técnico 388, Escuela de Graduados en Administración Industrial, Universidad Carnegie-Mellon, Pittsburgh.
• Hassin, R.; Rubinstein, S. (2000), "Mejores aproximaciones para TSP máximo", Cartas de procesamiento de información , 75 (4): 181–186, CiteSeerX  10.1.1.35.7209 , doi :10.1016/S0020-0190(00)00097-1.
• Celebrado, M.; Karp, RM (1962), "Un enfoque de programación dinámica para problemas de secuenciación", Revista de la Sociedad de Matemáticas Industriales y Aplicadas , 10 (1): 196–210, doi :10.1137/0110015.
• Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M. (2004), "Algoritmos de aproximación para TSP asimétrico mediante la descomposición de multigrafos regulares dirigidos", en Proc. 44º Simposio IEEE. sobre Fundamentos de la Computación. Ciencias , págs. 56–65.
• Karpinski, M.; Lampis, M.; Schmied, R. (2015), "Nuevos límites de inaproximabilidad para TSP", Journal of Computer and System Sciences , 81 (8): 1665–1677, arXiv : 1303.6437 , doi :10.1016/j.jcss.2015.06.003
• Kosaraju, SR; Parque, JK; Stein, C. (1994), "Viajes largos y supercuerdas cortas".", Proc. 35º Simposio Anual del IEEE sobre los fundamentos de la ciencia informática , IEEE Computer Society, págs. 166-177.
• Larson, Richard C.; Odoni, Amedeo R. (1981), "6.4.7: Aplicaciones de modelos de red § Problemas de enrutamiento §§ TSP euclidiano", Investigación de operaciones urbanas , Prentice-Hall, ISBN 978-0-13-939447-8, OCLC  6331426.
• Padberg, M.; Rinaldi, G. (1991), "Un algoritmo de rama y corte para la resolución de problemas simétricos de vendedores ambulantes a gran escala", SIAM Review , 33 : 60–100, doi :10.1137/1033004, S2CID  18516138.
• Papadimitriou, Christos H. (1977), "El problema del viajante euclidiano es NP-completo", Ciencias de la Computación Teórica , 4 (3): 237–244, doi : 10.1016/0304-3975(77)90012-3 , SEÑOR  0455550.
• Papadimitriou, Christos H.; Yannakakis, Mihalis (1993), "El problema del viajante con las distancias uno y dos", Matemáticas de la investigación de operaciones , 18 : 1–11, doi :10.1287/moor.18.1.1.
• Schrijver, Alejandro (2005). "Sobre la historia de la optimización combinatoria (hasta 1960)". En K. Aardal ; GL Nemhauser ; R. Weismantel (eds.). Manual de optimización discreta (PDF) . Ámsterdam: Elsevier. págs. 1–68.
• Serdyukov, AI (1984), "Un algoritmo con una estimación del máximo para el problema del viajante"", Sistema Upravlyaemye , 25 : 80–86.
• Steinerberger, Stefan (2015), "Nuevos límites para la constante del viajante", Avances en probabilidad aplicada , 47 (1): 27–36, arXiv : 1311.6338 , Bibcode : 2013arXiv1311.6338S, doi : 10.1239/aap/1427814579, S2CID  119293287.
• Woeginger, GJ (2003), "Algoritmos exactos para problemas NP-difíciles: una encuesta", Optimización combinatoria - ¡Eureka, te encoges! Apuntes de conferencias sobre informática, vol. 2570 , Springer, págs. 185-207.

Otras lecturas

• Adleman, Leonard (1994), "Computación molecular de soluciones a problemas combinatorios" (PDF) , Science , 266 (5187): 1021–4, Bibcode :1994Sci...266.1021A, CiteSeerX  10.1.1.54.2565 , doi :10.1126 /science.7973651, PMID  7973651, archivado desde el original (PDF) el 6 de febrero de 2005
• Babin, Gilbert; Deneault, Stéphanie; Laportey, Gilbert (2005), "Improvements to the Or-opt Heuristic for the Symmetric Travelling Salesman Problem", The Journal of the Operational Research Society , Cahiers du GERAD, G-2005-02 (3), Montreal: Grupo de Investigación en Análisis de decisiones: 402–407, CiteSeerX  10.1.1.89.9953 , JSTOR  4622707
• Cocinero, William (2012). En busca del viajante: matemáticas en los límites de la computación . Prensa de la Universidad de Princeton. ISBN 978-0-691-15270-7.
• Cocinero, William ; Espinoza, Daniel; Goycoolea, Marcos (2007), "Computación con desigualdades de paridad dominó para el TSP", Revista INFORMA de Computación , 19 (3): 356–365, doi :10.1287/ijoc.1060.0204
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (31 de julio de 2009). "35.2: El problema del viajante". Introducción a los algoritmos (2ª ed.). Prensa del MIT. págs. 1027-1033. ISBN 978-0-262-03384-8.
• Dantzig, GB ; Fulkerson, R .; Johnson, SM (1954), "Solución del problema de un viajante de comercio a gran escala", Investigación de operaciones , 2 (4): 393–410, doi :10.1287/opre.2.4.393, JSTOR  166695, S2CID  44960960
• Garey, Michael R.; Johnson, David S. (1979). "A2.3: ND22-24". Computadoras e intratabilidad: una guía para la teoría de la completitud NP. WH Freeman. págs. 211-212. ISBN 978-0-7167-1044-8.
• Goldberg, DE (1989), "Algoritmos genéticos en búsqueda, optimización y aprendizaje automático", Lectura: Addison-Wesley , Nueva York: Addison-Wesley, Bibcode : 1989gaso.book.....G, ISBN 978-0-201-15767-3
• Gutín, G.; Yeo, A.; Zverovich, A. (15 de marzo de 2002). "El viajante de comercio no debe ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP". Matemática Aplicada Discreta . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 . ISSN  0166-218X.
• Gutín, G.; Punnen, AP (18 de mayo de 2007). El problema del viajante y sus variaciones. Springer Estados Unidos. ISBN 978-0-387-44459-8.
• Johnson, DS ; McGeoch, LA (1997), "El problema del viajante: un estudio de caso sobre optimización local", en Aarts, EHL; Lenstra, JK (eds.), Búsqueda local en optimización combinatoria (PDF) , John Wiley and Sons Ltd., págs.
• Lawler, EL; Shmoys, DB; Kan, AHG Rinnooy; Lenstra, JK (1985). El problema del viajante. John Wiley e hijos, incorporados. ISBN 978-0-471-90413-7.
• MacGregor, JN; Ormerod, T. (1996), "Actuación humana en el problema del viajante", Perception & Psychophysics , 58 (4): 527–539, doi : 10.3758/BF03213088 , PMID  8934685, S2CID  38355042
• Medvédev, Andrei; Lee, Michael; Butavicio, Marco; Vickers, Douglas (1 de febrero de 2001). "Desempeño humano en problemas del viajante presentados visualmente". Investigación Psicológica . 65 (1): 34–45. doi :10.1007/s004260000031. ISSN  1430-2772. PMID  11505612. S2CID  8986203.
• Mitchell, JSB (1999), "Las subdivisiones de guillotina se aproximan a subdivisiones poligonales: un esquema simple de aproximación en tiempo polinómico para TSP geométrico, k -MST y problemas relacionados", SIAM Journal on Computing , 28 (4): 1298–1309, doi : 10.1137/S0097539796309764
• Rao, S.; Smith, W. (1998). "Aproximación de gráficos geométricos mediante 'llaves inglesas' y 'banianos'". STOC '98: Actas del trigésimo simposio anual de ACM sobre teoría de la informática . págs. 540–550. CiteSeerX  10.1.1.51.8676 .
• Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, Felipe M. II (1977). "Un análisis de varias heurísticas para el problema del viajante". Revista SIAM de Computación . sesenta y cinco). SIAM (Sociedad de Matemáticas Industriales y Aplicadas): 563–581. doi :10.1137/0206041. S2CID  14764079.
• Walshaw, Chris (2000), Un enfoque multinivel para el problema del viajante , CMS Press
• Walshaw, Chris (2001), Un algoritmo multinivel de Lin-Kernighan-Helsgaun para el problema del viajante, CMS Press

enlaces externos

• Problema del vendedor ambulante en Wayback Machine (archivado el 17 de diciembre de 2013) en la Universidad de Waterloo
• TSPLIB, Ejemplos de instancias para el TSP en la Universidad de Heidelberg
• El problema del viajante por Jon McLoone en el proyecto de demostraciones Wolfram
• Herramienta de visualización TSP