Problema del viajante de comercio

Problema NP-hard en optimización combinatoria

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

El problema del viajante , también conocido como el problema del vendedor ambulante ( 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-hard en optimización combinatoria , importante en informática teórica e investigación de operaciones .

El problema del comprador viajero , el problema de enrutamiento del vehículo y el problema de la estrella en anillo ^[1] son ​​tres 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 grafo 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 del TSP aumente de manera superpolinómica (pero no más que exponencial ) con el número de ciudades.

El problema se formuló por primera vez en 1930 y es uno de los problemas de optimización que se han estudiado más intensamente. 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 se pueden resolver por completo, e incluso los problemas con millones de ciudades se pueden aproximar con una pequeña fracción del 1%. ^[2]

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 de ADN . En estas aplicaciones, el concepto de ciudad representa, por ejemplo, clientes, puntos de soldadura o fragmentos de ADN, y el concepto de distancia representa tiempos de viaje o costos, 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 empleado en 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 de comercio no están claros. Un manual para viajantes de comercio de 1832 menciona el problema e incluye ejemplos de viajes por Alemania y Suiza , pero no contiene ningún tratamiento matemático. ^[3]

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 . ^[4] 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 optimalidad de la heurística del vecino más cercano:

Llamamos problema del mensajero (ya que en la práctica esta cuestión debería ser resuelta por cada cartero, y en todo caso también por muchos viajeros) a la tarea de encontrar, para un número finito de puntos cuyas distancias por pares son conocidas, la ruta más corta que los une. Por supuesto, este problema se puede resolver mediante un número finito de ensayos. No se conocen reglas que hagan que el número de ensayos sea inferior al número de permutaciones de los puntos dados. La regla según la cual primero hay que ir desde el punto de partida al punto más cercano, luego al punto más cercano a éste, etc., en general no da la ruta más corta. ^[5]

Merrill M. Flood lo consideró matemáticamente por primera vez en la década de 1930 cuando buscaba resolver un problema de rutas de autobuses escolares. ^[6] 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" fue el informe de la Corporación RAND de 1949 de Julia Robinson , "Sobre el juego hamiltoniano (un problema del viajante de comercio)". ^{[7] [8]}

En los años 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 en Santa Mónica ofreciera premios por los pasos para resolver el problema. ^[6] George Dantzig , Delbert Ray Fulkerson y Selmer M. Johnson de la Corporación RAND 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 seminal sobre el tema en el que, con estos nuevos métodos, resolvieron un caso con 49 ciudades hasta la optimalidad construyendo un recorrido y demostrando que ningún otro recorrido podría ser más corto. Sin embargo, Dantzig, Fulkerson y Johnson especularon que, dada una solución casi óptima, uno podría ser capaz de encontrar la optimalidad o probar la optimalidad agregando un pequeño número de desigualdades adicionales (cortes). Utilizaron esta idea para resolver su problema inicial de 49 ciudades utilizando un modelo de cuerdas. Descubrieron que sólo necesitaban 26 cortes para llegar a una solución para su problema de 49 ciudades. Si bien este artículo no proporcionó un enfoque algorítmico para los problemas de TSP, las ideas que se encontraban en él fueron indispensables para crear posteriormente métodos de solución exacta para el TSP, aunque se necesitarían 15 años para encontrar un enfoque algorítmico para crear estos cortes. ^[6] Además de los métodos de plano de corte, Dantzig, Fulkerson y Johnson utilizaron algoritmos de ramificación y acotación quizás por primera vez. ^[6]

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 Cambridge Philosophical Society . ^[9] El teorema de Beardwood-Halton-Hammersley proporciona una solución práctica al problema del viajante de comercio. Los autores derivaron una fórmula asintótica para determinar la longitud de la ruta más corta para un viajante de comercio 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 las matemáticas , la informática , la química , la física y otras ciencias. Sin embargo, en la década de 1960 se creó un nuevo enfoque que, en lugar de buscar soluciones óptimas, produciría una solución cuya longitud está 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 grafo 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. ^[6]

En 1976, Christofides y Serdyukov (de forma independiente) hicieron un gran avance en esta dirección: ^[10] 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 óptima. Sin embargo, esta esperanza de mejora no se materializó de inmediato, y Christofides-Serdyukov siguió siendo el método con el mejor escenario en 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". ^[11] En 2020, esta pequeña mejora se extendió al TSP completo (métrico). ^{[12] [13]}

Richard M. Karp demostró en 1972 que el problema del ciclo hamiltoniano era NP-completo , lo que implica la NP-dureza del TSP. Esto proporcionó una explicación matemática para la aparente dificultad computacional de encontrar recorridos óptimos.

Se lograron grandes avances a finales de la década de 1970 y en 1980, cuando Grötschel, Padberg, Rinaldi y otros lograron resolver con exactitud instancias con hasta 2.392 ciudades, utilizando planos de corte y ramificación y acotación .

En la década de 1990, Applegate , Bixby , Chvátal y Cook desarrollaron el programa Concorde que se ha utilizado en muchas soluciones de registros recientes. Gerhard Reinelt publicó el TSPLIB en 1991, una colección de instancias de referencia de diversa 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 muchas otras instancias con millones de ciudades, se pueden encontrar soluciones que están garantizadas en un 2-3% de un recorrido óptimo. ^[14]

Descripción

Como un problema gráfico

TSP simétrico con cuatro ciudades

El 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 las aristas del gráfico y la distancia de una ruta es el peso de la arista. Es un problema de minimización que comienza y termina en un vértice especificado después de haber visitado cada uno de los otros vértices 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 una ruta entre dos ciudades, entonces agregar una arista lo suficientemente larga 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 grafo no dirigido . Esta simetría reduce a la mitad el número de posibles soluciones. En el TSP asimétrico , es posible que no existan caminos en ambas direcciones o que las distancias sean diferentes, formando un grafo dirigido . La congestión del tráfico, las calles de un solo sentido 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 grafo completo ponderado (donde los vértices representarían las ciudades, las aristas 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 trayectoria hamiltoniana , que solo pregunta si existe una trayectoria (o ciclo) hamiltoniana en un grafo no ponderado no completo.
• El requisito de regresar a la ciudad de partida no cambia la complejidad computacional del problema; véase el problema de la trayectoria hamiltoniana .
• Otro problema relacionado es el problema del viajante de comercio con cuello de botella : encontrar un ciclo hamiltoniano en un grafo ponderado con el peso mínimo de la arista más pesada . Un ejemplo del mundo real es evitar calles estrechas con grandes autobuses. ^[15] El problema es de considerable importancia práctica, aparte de las evidentes áreas de transporte y logística. Un ejemplo clásico es la fabricación de circuitos impresos : la programación de una ruta de la máquina perforadora para perforar agujeros en una PCB. En las aplicaciones de mecanizado o perforación robóticas, las "ciudades" son piezas para mecanizar o agujeros (de diferentes tamaños) para perforar, y el "costo de viaje" incluye el tiempo para reequipar el robot (problema de secuenciación de trabajos de una sola máquina). ^[16]
• El problema generalizado del viajante de comercio , también conocido como el "problema del político viajero", trata de "estados" que tienen (una o más) "ciudades", y el viajante de comercio debe visitar exactamente una ciudad de cada estado. Una aplicación se encuentra al ordenar una solución al problema del material de corte para minimizar los cambios de cuchillas. Otra se relaciona con 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 una matriz de distancia modificada .
• El problema del ordenamiento secuencial aborda el problema de visitar un conjunto de ciudades, donde existen relaciones de precedencia entre ellas.
• Una pregunta común en las entrevistas en Google es cómo enrutar los datos entre los nodos de procesamiento de datos; las rutas varían según el tiempo necesario para transferir los datos, pero los nodos también difieren en su poder de cómputo y almacenamiento, lo que agrava el problema de dónde enviar los datos.
• El problema del comprador viajero se plantea cuando un comprador debe 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 coste total (costo del viaje + coste de la 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 . ^{[17] [18] [19]} 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. ^{[20] [21]}

Ambas formulaciones tienen en común que se etiquetan las ciudades con números y se toma como el costo (distancia) de ciudad a ciudad . Las variables principales 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 longitud del recorrido.

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

Sin más restricciones, la voluntad efectivamente abarcará 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 las restricciones 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.}$

Estos garantizan que el conjunto de aristas elegido se parezca localmente al de un recorrido, pero aún así permiten soluciones que violan el requisito global de que exista un recorrido que visite todos los vértices, ya que las aristas elegidas podrían formar varios recorridos, cada uno de los cuales visitaría solo un subconjunto de los vértices; se podría decir que es este requisito global lo que hace que TSP sea un problema difícil. Las formulaciones 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, hay para cada una una variable ficticia que lleva un registro del orden en el que se visitan las ciudades, contando desde la ciudad ; la interpretación es que implica que se visita la ciudad antes que la ciudad. Para un recorrido determinado (codificado en valores de las variables), uno puede encontrar valores satisfactorios para las variables haciendo que sea igual al número de aristas a lo largo de ese recorrido, al ir de ciudad en ciudad ^[22] ${\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 también exige cuándo, lo cual no es correcto. En su lugar, 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 luego imponen que un solo tour visite todas las ciudades es que aumentan al menos en cada paso a lo largo del tour, con una disminución permitida solo cuando el tour pasa por la ciudad.  Esa restricción sería violada por cada tour que no pase por la ciudad,  por lo que la única forma de satisfacerla es que el tour 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 entonces 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 exige que se llegue a cada ciudad desde exactamente otra ciudad, y el segundo conjunto de igualdades exige que desde cada ciudad haya una salida hacia exactamente otra ciudad. La última restricción exige 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 entre la ciudad i y la ciudad j . Entonces, TSP puede escribirse 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 subrecorridos , garantiza que ningún subconjunto propio Q pueda formar un subrecorrido, por lo que la solución devuelta es un único 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 la generación de filas . ^[23]

Calcular una solución

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

• Idear 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 sean posibles heurísticas mejores o más exactas.

Algoritmos exactos

La solución más directa sería probar todas las permutaciones (combinaciones ordenadas) y ver cuál es la más barata (utilizando una 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 se vuelve impráctica incluso para solo 20 ciudades. ${\displaystyle O(n!)}$

Una de las primeras aplicaciones de la programación dinámica es el algoritmo Held-Karp , que resuelve el problema en el tiempo . ^[24] Este límite también se alcanzó mediante Exclusión-Inclusión en un intento anterior al enfoque de programación dinámica. ${\displaystyle O(n^{2}2^{n})}$

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

Mejorar estos límites temporales parece ser difícil. Por ejemplo, no se ha determinado si existe un algoritmo exacto clásico para TSP que se ejecute en el tiempo . ^{[25] El mejor} algoritmo exacto cuántico actual para TSP, creado por Ambainis et al., se ejecuta en el tiempo . ^[26] ${\displaystyle O(1.9999^{n})}$ ${\displaystyle O(1.728^{n})}$

Otros enfoques incluyen:

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

Solución de un TSP con 7 ciudades utilizando un algoritmo de Branch and bound simple. Nota: El número de permutaciones es mucho menor que 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 específicos de problemas y de ramificación y acotación ( branching-and-cut ^[27] ); ^[28] este es el método de elección para resolver instancias grandes. Este enfoque tiene el récord actual, al resolver una instancia con 85.900 ciudades, consulte 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 solo procesador Alpha de 500 MHz . En mayo de 2004, se resolvió el problema del viajante de comercio de visitar las 24.978 ciudades de Suecia: se encontró un recorrido de aproximadamente 72.500 kilómetros de longitud y se demostró que no existe un recorrido más corto. ^[29] En marzo de 2005, se resolvió el problema del viajante de comercio que debía visitar los 33.810 puntos de una placa de circuitos utilizando el solucionador Concorde TSP : 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 el solucionador Concorde TSP , que tomó más de 136 años-CPU; véase Applegate et al. (2006).

Algoritmos heurísticos y de aproximación

Se han ideado diversos algoritmos heurísticos y de aproximación que rápidamente producen buenas soluciones, entre ellos el algoritmo de fragmentos múltiples . 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 solo un 2-3% de la solución óptima. ^[14]

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 modifica 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 una ruta 25% más larga que la ruta más corta posible; ^[30] sin embargo, existen muchas distribuciones de ciudades especialmente organizadas que hacen que el algoritmo NN proporcione la peor ruta. ^[31] Esto es cierto tanto para TSP asimétricos como simétricos. ^[32] Rosenkrantz et al. ^[33] demostraron que el algoritmo NN tiene el factor de aproximación para instancias que satisfacen la desigualdad triangular. 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. ^[34] El operador NF también se puede aplicar en una solución inicial obtenida por el algoritmo NN para una mejora adicional 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 como vértices los puntos; se puede calcular eficientemente con programación dinámica .

Otra heurística constructiva , Match Twice and Stitch (MTS), realiza dos emparejamientos secuenciales , donde el segundo emparejamiento se ejecuta después de eliminar todos los bordes del primer emparejamiento, para producir un conjunto de ciclos. Luego, los ciclos se unen para producir el recorrido final. ^[35]

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ínima con una solución de otro problema, el emparejamiento perfecto de peso mínimo . Esto da un recorrido TSP que es como máximo 1,5 veces el óptimo. Fue uno de los primeros algoritmos de aproximación y 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 inicialmente se denominó heurística de Christofides. ^[10]

Este algoritmo ve las cosas de manera diferente al usar 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 grafo euleriano , podemos encontrar un recorrido euleriano en ⁠ ⁠ ${\displaystyle O(n)}$ tiempo, ^[6] así que si tuviéramos un grafo euleriano con ciudades de un TSP como vértices, entonces podemos ver fácilmente que podríamos usar dicho método para encontrar un recorrido euleriano para encontrar una solución TSP. Por la desigualdad triangular , sabemos que el recorrido del TSP no puede ser más largo que el recorrido euleriano, y por lo tanto tenemos un límite inferior para el TSP. Tal método se describe a continuación.

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

Para mejorar el límite inferior, se necesita una mejor manera de crear un gráfico euleriano. Por la desigualdad triangular, el mejor gráfico euleriano debe tener el mismo costo que el mejor viaje del viajante de comercio; por lo tanto, encontrar gráficos eulerianos óptimos es al menos tan difícil como TSP. Una forma de hacer esto es mediante la correspondencia de peso mínimo utilizando algoritmos con una complejidad de . ^[6] ${\displaystyle O(n^{3})}$

Para convertir un grafo en un grafo euleriano, se comienza con el árbol de expansión mínimo; todos los vértices de orden impar deben hacerse pares, por lo que se debe agregar una correspondencia para los vértices de grado impar, lo que aumenta el orden de cada vértice de grado impar en 1. ^[6] Esto nos deja con un grafo donde cada vértice es de orden par, que es, por lo tanto, euleriano. Adaptando el método anterior obtenemos el algoritmo de Christofides y Serdyukov:

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

Intercambio por pares

Un ejemplo de una iteración de 2 opciones

La técnica de intercambio por pares o 2-opt implica la eliminación iterativa de dos aristas y su reemplazo por dos aristas diferentes que reconectan los fragmentos creados por la eliminación de aristas en un recorrido nuevo y más corto. De manera similar, la técnica 3-opt elimina 3 aristas y las reconecta 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 2-opt dan en promedio soluciones que son aproximadamente un 5% mejores que las producidas por el algoritmo de Christofides. Si comenzamos con una solución inicial hecha con un algoritmo voraz , entonces el número promedio de movimientos disminuye considerablemente nuevamente y es ⁠ ⁠ ${\displaystyle O(n)}$ ; sin embargo, para inicios aleatorios, el número promedio de movimientos es ⁠ ⁠ ${\displaystyle O(n\log(n))}$ . Si bien este es un pequeño aumento en 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 hecho a partir de una heurística voraz. Esto se debe a que tales heurísticas 2-opt 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 enrutamiento de vehículos para volver a optimizar las soluciones de ruta. ^[30]

a-heurística opt, 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, elimine k aristas mutuamente disjuntas.
2. Reensamblar los fragmentos restantes en un recorrido, sin dejar subrecorridos disjuntos (es decir, no conectar los puntos finales de un fragmento). Esto, en efecto, simplifica el TSP en cuestión y lo convierte en un problema mucho más simple.
3. Cada extremo de fragmento puede conectarse a 2 k  − 2 posibilidades más: de los 2 k extremos de fragmentos disponibles, los dos extremos del fragmento en cuestión no están permitidos. Este TSP de 2 k ciudades restringido puede resolverse con métodos de fuerza bruta para encontrar la recombinación de menor costo de los fragmentos originales.

El método k -opt más popular es el 3-opt, introducido por Shen Lin de Bell Labs en 1965. Un caso especial de 3-opt es aquel en el que las aristas no están disjuntas (dos de las aristas son adyacentes entre sí). En la práctica, a menudo es posible lograr una mejora sustancial con respecto al método 2-opt sin el costo combinatorio del método 3-opt general, restringiendo los 3 cambios a este subconjunto especial en el que dos de las aristas eliminadas son adyacentes. Este método, denominado dos y medio-opt, suele estar aproximadamente a medio camino entre el método 2-opt y el método 3-opt, tanto en términos de la calidad de los recorridos logrados como del tiempo necesario para lograrlos.

V-opt heurística

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 aristas del recorrido original, los métodos variable-opt no fijan el tamaño del conjunto de aristas que se eliminarán. 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. A fines de la década de 1980, David Johnson y su equipo de investigación desarrollaron métodos variable-opt más avanzados en Bell Labs. Estos métodos (a veces llamados Lin-Kernighan-Johnson) se basan en el método Lin-Kernighan, agregando ideas de la búsqueda tabú y la computación evolutiva . La técnica básica Lin-Kernighan brinda resultados que se garantiza que son al menos 3-opt. Los métodos Lin–Kernighan–Johnson calculan un recorrido 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, para luego aplicar la opción V al nuevo recorrido. La mutación suele ser suficiente para mover el recorrido desde el mínimo local identificado por Lin–Kernighan. Los métodos V -opt se consideran ampliamente 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 más 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 700 a 800 ciudades.

TSP es una piedra de toque para muchas heurísticas generales diseñadas para la optimización combinatoria, como algoritmos genéticos , recocido simulado , búsqueda tabú , optimización de colonias de hormigas , 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 subrecorrido como la envoltura convexa y luego inserta otros vértices. ^[36]

Optimización de colonias de hormigas

El investigador de inteligencia artificial Marco Dorigo describió en 1993 un método de generación heurística de "buenas soluciones" al TSP utilizando una simulación de una colonia de hormigas llamada ACS ( ant colony system ). ^[37] Modela el comportamiento observado en hormigas reales para encontrar caminos cortos entre las fuentes de alimento y su nido, un comportamiento emergente resultante de la preferencia de cada hormiga de seguir feromonas de rastro depositadas por otras hormigas.

ACS envía una gran cantidad de agentes hormigas virtuales para explorar muchas rutas posibles en el mapa. Cada hormiga elige de manera probabilística la siguiente ciudad que visitará en función de 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 feromona en cada borde que cruzan, hasta que todas han completado un recorrido. En este punto, la hormiga que completó el recorrido más corto deposita feromona virtual a lo largo de su ruta de recorrido completa ( 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 deposita.

1) Una hormiga elige un camino entre todos los posibles y deja en él un rastro de feromonas. 2) Todas las hormigas recorren caminos diferentes, dejando un rastro de feromonas proporcional a la calidad de la solución. 3) Cada borde del mejor camino está más reforzado que los demás. 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 el sistema métrico TSP , también conocido como delta-TSP o Δ-TSP, las distancias entre ciudades satisfacen la desigualdad triangular .

Una restricción muy natural del TSP es exigir que las distancias entre ciudades formen una métrica para satisfacer la desigualdad triangular ; es decir, la conexión directa de A a B nunca es más lejana que la ruta a través del punto intermedio C :

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

Los bordes construyen entonces una métrica en el conjunto de vértices. Cuando las ciudades se consideran puntos en el plano, muchas funciones de distancia naturales son métricas, y muchas instancias naturales de TSP satisfacen esta restricción.

Los siguientes son algunos ejemplos de TSP métricos para diversas 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 x e y . Esta métrica se suele denominar distancia de Manhattan o métrica de manzanas de ciudad.
• 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 x e y .

Las dos últimas métricas aparecen, por ejemplo, en el enrutamiento de una máquina que perfora un conjunto determinado de agujeros en una placa de circuito impreso . La métrica Manhattan corresponde a una máquina que ajusta primero una coordenada, y luego la otra, por lo que el tiempo para moverse 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 moverse a un nuevo punto es el más lento de los dos movimientos.

En su definición, el TSP no permite que las ciudades se visiten 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 de la ruta más corta entre A y B en el gráfico original. ${\displaystyle d_{AB}}$

Euclidiano

Para los puntos en el plano euclidiano , la solución óptima al problema del viajante forma un polígono simple a través de todos los puntos, una poligonalización de los puntos. ^[38] 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 triangular, 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 la realización del 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-hard, 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, es NP-completa. Una versión discretizada del problema con distancias redondeadas a números enteros es NP-completa. ^[39] Con coordenadas racionales y la métrica euclidiana real, se sabe que el TSP euclidiano está en la Jerarquía de conteo, ^[40] una subclase de PSPACE. Con coordenadas reales arbitrarias, el TSP euclidiano no puede estar en tales clases, ya que hay una cantidad incontable de posibles entradas. A pesar de estas complicaciones, el TSP euclidiano es mucho más fácil que el caso de la métrica general para la aproximación. ^[41] 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 un tiempo esperado de 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 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, hay un algoritmo de tiempo polinomial que encuentra un recorrido de longitud como máximo (1 + 1/ c ) veces la óptima para instancias geométricas de TSP en

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

tiempo; esto se llama esquema de aproximación de tiempo polinomial (PTAS). ^[42] Sanjeev Arora y Joseph SB Mitchell fueron galardonados con 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 mediante el uso de rutas a nivel de calle (que se vuelven asimétricas mediante calles de un solo sentido, ramales, autopistas, etc.).

Conversión a simétrico

Resolver un gráfico TSP asimétrico puede ser algo complejo. La siguiente es una matriz 3×3 que contiene todos los posibles pesos de ruta 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. ^[43 ]

Para duplicar el tamaño, se duplica cada uno de los nodos del gráfico, lo que crea un segundo nodo fantasma , vinculado al nodo original con un borde "fantasma" de peso muy bajo (posiblemente negativo), aquí denotado como − w . (Alternativamente, los bordes fantasma tienen un peso de 0 y se agrega el peso w a todos los demás bordes). La matriz 3×3 original que se muestra arriba es visible en la parte inferior izquierda y la transposición del original en la parte superior derecha. Ambas copias de la matriz han tenido sus diagonales reemplazadas por las rutas de salto de bajo costo, representadas por − w . En el nuevo gráfico, ningún borde vincula directamente a los nodos originales y ningún borde vincula directamente a los nodos fantasma.

El peso − w de los bordes "fantasma" que unen los nodos fantasma con 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 originales 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} }$

Problema del analista

Existe un problema análogo en la teoría de la medida geométrica que plantea la siguiente pregunta: ¿en qué condiciones puede un subconjunto E del espacio euclidiano estar contenido en una curva rectificable (es decir, cuándo existe una curva con longitud finita que visita cada punto de E )? Este problema se conoce como el problema del viajante de comercio del analista .

Longitud de la trayectoria para conjuntos aleatorios de puntos en un cuadrado

Supóngase 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 ^[9] 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. Puesto que (ver más abajo), se deduce del teorema de convergencia acotada que , por lo tanto, los límites inferior y superior de se derivan de los límites de . ${\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. ^[44] ${\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 , utilizando un camino ingenuo que visita monótonamente los puntos dentro de cada una de las rebanadas de ancho del cuadrado. ${\displaystyle L^{*}\leq 2{\sqrt {n}}+2}$ ${\displaystyle \beta \leq 2}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle 1/{\sqrt {n}}}$
• Pocos ^[45] demostraron , por lo tanto , posteriormente mejorado por Karloff (1987): . ${\displaystyle L_{n}^{*}\leq {\sqrt {2n}}+1.75}$ ${\displaystyle \beta \leq {\sqrt {2}}}$ ${\displaystyle \beta \leq 0.984{\sqrt {2}}}$
• Fietcher ^[46] sugirió empíricamente un límite superior de . ${\displaystyle \beta \leq 0.73\dots }$

Límite inferior

• Al observar que es mayor que veces la distancia entre y el punto más cercano , se obtiene (después de un cálculo breve) ${\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 límite inferior mejor al observar que es mayor que veces la suma de las distancias entre los puntos más cercano y segundo más cercano , lo que da ^[9] ${\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 límite inferior actualmente mejor ^{[ ¿cuándo? ] es [47]}

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

• Held y Karp dieron un algoritmo de tiempo polinomial que proporciona límites inferiores numéricos para , y por lo tanto para , que parecen ser buenos hasta más o menos el 1%. ^{[48] [49]} En particular, David S. Johnson obtuvo un límite inferior mediante un experimento informático: ^[50] ${\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 cuadrado que tienen menos vecinos, y Christine L. Valenzuela y Antonia J. Jones obtuvieron el siguiente otro límite inferior numérico: ^[51]

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

Complejidad computacional

Se ha demostrado que el problema es NP-duro (más precisamente, es 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 , decidir si hay una ruta de ida y vuelta más barata que x ") es NP-completo . El problema del viajante de comercio con cuello de botella también es NP-duro. El problema sigue siendo NP-duro incluso para el caso en que las ciudades están en el plano con distancias euclidianas , así como en varios otros casos restrictivos. Eliminar la condición de visitar cada ciudad "solo una vez" no elimina la NP-duro, ya que en el caso planar hay un recorrido óptimo que visita cada ciudad solo una vez (de lo contrario, por la desigualdad triangular , un atajo que saltea una visita repetida no aumentaría la duración del recorrido).

Complejidad de aproximación

En el caso general, encontrar el recorrido más corto de un viajante de comercio es NPO -completo. ^[52] Si la medida de distancia es una métrica (y por lo tanto simétrica), el problema se vuelve APX -completo, ^[53] y el algoritmo de Christofides y Serdyukov lo aproxima dentro de 1,5. ^{[54] [55] [10]}

Si las distancias se limitan a 1 y 2 (pero siguen siendo una métrica), entonces la relación de aproximación se convierte en 8/7. ^[56] En el caso asimétrico con desigualdad triangular , en 2018, Svensson, Tarnawski y Végh desarrollaron una aproximación de factor constante. ^[57] Un algoritmo de Vera Traub y Jens Vygen  [de] logra una relación de rendimiento de . ^[58] El límite de inaproximabilidad más conocido es 75/74. ^[59] ${\displaystyle 22+\varepsilon }$

El problema de maximización correspondiente de encontrar el recorrido más largo del viajante de comercio es aproximable dentro de 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 de 4/3 mediante un algoritmo aleatorio. ^[62] ${\displaystyle (33+\varepsilon )/25}$

Rendimiento humano 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 una manera casi lineal, con un rendimiento que varía desde un 1% menos eficiente, para grafos con 10-20 nodos, hasta un 11% menos eficiente para grafos 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 utilizan una o más heurísticas, siendo las dos teorías más populares posiblemente la hipótesis de la envoltura convexa y la heurística de evitación de cruces. ^{[65] [66] [67]} Sin embargo, evidencia adicional sugiere que el rendimiento humano es bastante variado, y las diferencias individuales, así como la geometría del grafo, parecen afectar el rendimiento en la tarea. ^{[68] [69] [70]} Sin embargo, los resultados sugieren que el rendimiento de la computadora en el TSP se puede mejorar al comprender y emular los métodos utilizados por los humanos para estos problemas, ^[71] y también han llevado a nuevos conocimientos sobre los mecanismos del pensamiento humano. ^[72] El primer número del Journal of Problem Solving se dedicó al tema del rendimiento humano en el 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", llamado así por el libro infantil ¡No dejes que la paloma conduzca el autobús!, examinó 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 de comercio. 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 usaban en gran medida la proximidad para determinar qué comedero elegirían a continuación. En el segundo experimento, los comederos se organizaron de tal manera que volar al comedero más cercano en cada oportunidad sería en gran medida ineficiente si las palomas necesitaran 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 por adelantado 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 eran 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, lo 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 ejemplos de 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 esquivo en la historia de la informática: P vs. NP . ^[77]
• El matemático Robert A. Bosch utiliza soluciones al problema en un subgénero llamado arte TSP. ^[78]

Véase también

• Problema del viajero canadiense
• Algoritmo exacto
• Problema de inspección de ruta (también conocido como "problema del cartero chino")
• Problema de configuración de TSP
• Los siete puentes de Königsberg
• El problema del viajante de comercio de Steiner
• Desafío del metro
• Desafío del tubo
• Problema de ruta del vehículo
• Exploración de gráficos
• Problema mixto del cartero chino
• Enrutamiento de arco
• Problema de ruta de la máquina quitanieves
• Matriz de Monge

Notas

1. Labbé, Martine; Laporte, Gilbert; Martín, Inmaculada Rodríguez; González, Juan José Salazar (mayo de 2004). "El problema de la estrella anillo: análisis poliédrico y algoritmo exacto". Redes . 43 (3): 177–189. doi :10.1002/net.10114. ISSN  0028-3045.
2. Véase el problema de la gira mundial del TSP, que ya se ha resuelto con un margen de error del 0,05 % de la solución óptima. [1]
3. "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 )
4. Se puede encontrar un análisis de los primeros trabajos de Hamilton y Kirkman en Graph Theory, 1736–1936 , de Biggs, Lloyd y Wilson (Clarendon Press, 1986).
5. 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."
6. Lawler, EL (1985). El problema del viajante: una visita guiada a la optimización combinatoria (Repr. con correcciones, ed.). John Wiley & sons. ISBN 978-0-471-90413-7.
7. Robinson, Julia (5 de diciembre de 1949). On the Hamiltonian game (a travelling salesman problem) (PDF) (Informe técnico). Santa Monica, CA: The RAND Corporation. RM-303 . Consultado el 2 de mayo de 2020 – a través del Centro de Información Técnica de Defensa.
8. Un tratamiento detallado de la conexión entre Menger y Whitney, así como del crecimiento en el estudio de TSP, se puede encontrar en Schrijver (2005).
9. Beardwood, Halton y Hammersley (1959).
10. van Bevern, René; Slugina, Viktoriia A. (2020). "Una nota histórica sobre el algoritmo de aproximación 3/2 para el problema del viajante métrico". Historia Mathematica . 53 : 118–127. arXiv : 2004.02437 . doi :10.1016/j.hm.2020.04.003. S2CID  214803097.
11. Klarreich, Erica (30 de enero de 2013). "Los científicos informáticos encuentran nuevos atajos para el infame problema del viajante de comercio". WIRED . Consultado el 14 de junio de 2015 .
12. Klarreich, Erica (8 de octubre de 2020). «Los informáticos rompen el récord de ventas de los vendedores ambulantes». Revista Quanta . Consultado el 13 de octubre de 2020 .
13. 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 computación, evento virtual, Italia, del 21 al 25 de junio de 2021 , págs. 32–45, arXiv : 2007.01409 , doi :10.1145/3406325.3451009, ISBN 978-1-4503-8053-9, Número de identificación del sujeto  220347561
14. Rego, César; Gamboa, Dorabela; Glover, Fred; Osterman, Colin (2011), "Heurísticas del problema del viajante: 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.
15. "¿Cómo se arreglan las rutas de los autobuses escolares? Llama al MIT en el Wall Street Journal" (PDF) .
16. Behzad, Arash; Modarres, Mohammad (2002), "Nueva transformación eficiente del problema generalizado del viajante de comercio en el problema del viajante de comercio", Actas de la 15.ª Conferencia Internacional de Ingeniería de Sistemas (Las Vegas)
17. Papadimitriou, CH; Steiglitz, K. (1998), Optimización combinatoria: algoritmos y complejidad , Mineola, NY: Dover, págs.308-309.
18. Tucker, AW (1960), "Sobre gráficos dirigidos y programas enteros", Proyecto de investigación matemática de IBM (Universidad de Princeton)
19. Dantzig, George B. (1963), Programación lineal y extensiones , Princeton, NJ: PrincetonUP, págs. 545–7, ISBN 0-691-08000-3 , sexta impresión, 1974. 
20. Velednitsky, Mark (2017). "Prueba combinatoria breve de que el politopo DFJ está contenido en el politopo MTZ para el problema asimétrico del viajante de comercio". Operations Research Letters . 45 (4): 323–324. arXiv : 1805.06997 . doi :10.1016/j.orl.2017.04.010. S2CID  6941484.
21. Bektaş, Tolga; Gouveia, Luis (2014). "¿Réquiem por las restricciones de eliminación de subtours de Miller–Tucker–Zemlin?". Revista Europea de Investigación Operativa . 236 (3): 820–832. doi :10.1016/j.ejor.2013.07.038.
22. CE Miller, AW Tucker y RA Zemlin. 1960. Formulación de problemas de viajante mediante programación entera. J. ACM 7, 4 (octubre de 1960), 326–329. DOI: https://doi.org/10.1145/321043.321046
23. 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 Estados Unidos . 2 (4): 393–410. doi :10.1287/opre.2.4.393.
24. Bellman (1960), Bellman (1962), Held y Karp (1962)
25. Woeginger (2003).
26. 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. Número de identificación del sujeto  49743824.
27. Padberg y Rinaldi (1991).
28. Problema del viajante: rama y límite en YouTube . Cómo cortar ramas infructuosas usando filas y columnas reducidas como en el algoritmo matricial húngaro
29. 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 .
30. Johnson, DS ; McGeoch, LA (1997). "El problema del viajante: un estudio de caso en optimización local" (PDF) . En Aarts, EHL; Lenstra, JK (eds.). Búsqueda local en optimización combinatoria . Londres: John Wiley and Sons Ltd. pp. 215–310.
31. Gutina, Gregory; Yeob, Anders; Zverovich, Alexey (15 de marzo de 2002). "El viajante de comercio no debería ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP". Matemáticas Aplicadas Discretas . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .>
32. Zverovitch, Alexei; Zhang, Weixiong; Yeo, Anders; McGeoch, Lyle A.; Gutin, Gregory; Johnson, David S. (2007), "Análisis experimental de heurísticas 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
33. Rosenkrantz, DJ; Stearns, RE; Lewis, PM (14–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.
34. Ray, SS; Bandyopadhyay, S.; Pal, SK (2007). "Operadores genéticos para optimización combinatoria en ordenamiento de genes de microarrays y TSP". Inteligencia Aplicada . 26 (3): 183–195. CiteSeerX 10.1.1.151.132 . doi :10.1007/s10489-006-0018-y. S2CID  8130854. 
35. Kahng, AB; Reda, S. (2004). "Match Twice and Stitch: Una nueva heurística de construcción de recorridos TSP". Operations Research Letters . 32 (6): 499–509. doi :10.1016/j.orl.2004.04.001.
36. Alatartsev, Sergey; Augustine, Marcus; Ortmeier, Frank (2 de junio de 2013). "Heurística de inserción restrictiva para el problema del viajante con vecindarios" (PDF) . Actas de la Conferencia internacional sobre planificación y programación automatizadas . 23 : 2–10. doi :10.1609/icaps.v23i1.13539. ISSN  2334-0843. S2CID  18691261.
37. Dorigo, Marco; Gambardella, Luca Maria (1997). "Colonias de hormigas para el problema del viajante de comercio". Biosystems . 43 (2): 73–81. Bibcode :1997BiSys..43...73D. CiteSeerX 10.1.1.54.7734 . doi :10.1016/S0303-2647(97)01708-5. PMID  9231906. S2CID  8243011. 
38. Quintas, LV; Supnick, Fred (1965). "Sobre algunas propiedades de los circuitos hamiltonianos más cortos". The American Mathematical Monthly . 72 (9): 977–980. doi :10.2307/2313333. JSTOR  2313333. MR  0188872.
39. Papadimitriou (1977).
40. Allender y otros (2007).
41. Larson y Odoni (1981).
42. Arora (1998).
43. Jonker, Roy; Volgenant, Ton (1983). "Transformación de problemas asimétricos en simétricos del viajante de comercio". Operations Research Letters . 2 (161–163): 1983. doi :10.1016/0167-6377(83)90048-2.
44. 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
45. Few, L. (1955). "El camino más corto y la carretera más corta a través de n puntos". Mathematika . 2 (2): 141–144. doi :10.1112/s0025579300000784.
46. Fiechter, C.-N. (1994). "Un algoritmo de búsqueda tabú paralelo para grandes problemas de viajante de comercio". Disc. Matemáticas Aplicadas . 51 (3): 243–267. doi : 10.1016/0166-218X(92)00033-I .
47. Steinerberger (2015).
48. Held, M.; Karp, RM (1970). "El problema del viajante y los árboles de expansión mínima". Investigación de operaciones . 18 (6): 1138–1162. doi :10.1287/opre.18.6.1138.
49. Goemans, Michel X. ; Bertsimas, Dimitris J. (1991). "Análisis probabilístico del límite inferior de Held y Karp para el problema euclidiano del viajante de comercio". Matemáticas de la investigación de operaciones . 16 (1): 72–89. doi :10.1287/moor.16.1.72.
50. "error". about.att.com .
51. Christine L. Valenzuela y Antonia J. Jones Archivado el 25 de octubre de 2007 en Wayback Machine.
52. Orponen, P.; Mannila, H. (1987). 'Sobre reducciones que preservan la aproximación: problemas completos y medidas robustas' (Informe). Departamento de Ciencias de la Computación, Universidad de Helsinki. Informe técnico C-1987–28.
53. Papadimitriou y Yannakakis (1993).
54. Cristófides (1976).
55. Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [Sobre algunos paseos extremos en gráficos] (PDF) , Upravlyaemye Sistemy (en ruso), 17 : 76–79
56. Berman y Karpinski (2006).
57. Svensson, Ola; Tarnawski, Jakub; Végh, László A. (2018). "Un algoritmo de aproximación de factor constante para el problema asimétrico del viajante de comercio". 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.S2CID12391033  .​
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. pp. 1–13. arXiv : 1912.00670 . doi :10.1145/3357713.3384233. ISBN 978-1-4503-6979-4.S2CID208527125  .​
59. Karpinski, Lampis y Schmied (2015).
60. Kosaraju, Park y Stein (1994).
61. Serdiukov (1984).
62. Hassin y Rubinstein (2000).
63. Macgregor, JN; Ormerod, T. (junio de 1996), "Rendimiento humano en el problema del viajante de comercio", Perception & Psychophysics , 58 (4): 527–539, doi : 10.3758/BF03213088 , PMID  8934685.
64. Dry, Matthew; Lee, Michael D.; Vickers, Douglas; Hughes, Peter (2006). "Rendimiento humano en problemas de vendedores ambulantes presentados visualmente con diferentes números de nodos". The Journal of Problem Solving . 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 de casco convexo y de recorrido en el problema euclidiano del viajante de comercio: implicaciones para los estudios de 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). "Rendimiento humano en el viajante de comercio y problemas relacionados: una revisión". The Journal of Problem Solving . 3 (2). doi : 10.7771/1932-6246.1090 . ISSN  1932-6246.
67. MacGregor, James N.; Chronicle, Edward P.; Ormerod, Thomas C. (1 de marzo de 2004). "¿Casco convexo o evitación de cruces? Heurísticas 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, Therese; 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). "Reconocimiento de violaciones de la heurística de evitación de cruces al resolver el problema euclidiano del viajante de comercio". Psychological Research . 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). "Sentido de orientación y escrupulosidad como predictores del desempeño en el problema euclidiano del viajante de comercio". Heliyon . 3 (11): e00461. Bibcode :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 euclidiano del viajante de comercio: modelado computacional de heurísticas y efectos figurales". 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), "Rendimiento 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, Matthew; 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". Animal Cognition . 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 burbuja que se encoge" (PDF) , Natural Computing : 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 'Travelling Salesman' considera las repercusiones si P es igual a NP". Wired UK . 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 de comercio , 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 temporal polinómica para problemas geométricos y del viajante euclidiano" (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 sobre matemáticas aplicadas 10 , American Mathematical Society, págs. 217–249.
• Bellman, R. (1962), "Tratamiento de programación dinámica del problema del viajante", Journal of the Association for Computing Machinery , 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 caso de una nueva heurística para el problema del viajante de comercio , Informe técnico 388, Escuela de Graduados de Administración Industrial, Universidad Carnegie-Mellon, Pittsburgh.
• Hassin, R.; Rubinstein, S. (2000), "Mejores aproximaciones para el TSP máximo", Information Processing Letters , 75 (4): 181–186, CiteSeerX  10.1.1.35.7209 , doi :10.1016/S0020-0190(00)00097-1.
• Held, M.; Karp, RM (1962), "Un enfoque de programación dinámica para problemas de secuenciación", Journal of the Society for Industrial and Applied Mathematics , 10 (1): 196–210, doi :10.1137/0110015.
• Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M. (2004), "Algoritmos de aproximación para TSP asimétricos mediante la descomposición de multigrafos regulares dirigidos", en Proc. 44th IEEE Symp. on Foundations of Comput. Sci , 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; Park, JK; Stein, C. (1994), "Giras largas y supercuerdas cortas"", Actas del 35.° Simposio anual IEEE sobre fundamentos de la 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", Urban Operations Research , Prentice-Hall, ISBN 978-0-13-939447-8, OCLC  6331426.
• Padberg, M.; Rinaldi, G. (1991), "Un algoritmo de ramificación y corte para la resolución de problemas de viajante de comercio simétricos 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", Theoretical Computer Science , 4 (3): 237–244, doi : 10.1016/0304-3975(77)90012-3 , MR  0455550.
• Papadimitriou, Christos H.; Yannakakis, Mihalis (1993), "El problema del viajante de comercio con distancias uno y dos", Matemáticas de la investigación de operaciones , 18 : 1–11, doi :10.1287/moor.18.1.1.
• Schrijver, Alexander (2005). "Sobre la historia de la optimización combinatoria (hasta 1960)". En K. Aardal ; GL Nemhauser ; R. Weismantel (eds.). Handbook of Discrete Optimization (PDF) . Ámsterdam: Elsevier. págs. 1–68.
• Serdyukov, AI (1984), "Un algoritmo con una estimación para el problema del viajante de comercio del máximo"", Sistema Upravlyaemye , 25 : 80–86.
• Steinerberger, Stefan (2015), "Nuevos límites para la constante del viajante de comercio", Advances in Applied Probability , 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 clase sobre informática, vol. 2570 , Springer, págs. 185-207.

Lectura adicional

• Adleman, Leonard (1994), "Molecular Computation of Solutions To Combinatorial Problems" (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), "Mejoras en la heurística Or-opt para el problema del viajante simétrico", The Journal of the Operational Research Society , Cahiers du GERAD, G-2005-02 (3), Montreal: Group for Research in Decision Analysis: 402–407, CiteSeerX  10.1.1.89.9953 , JSTOR  4622707
• Cook, William (2012). En busca del viajante de comercio: las matemáticas en los límites de la computación . Princeton University Press. ISBN 978-0-691-15270-7.
• Cook, William ; Espinoza, Daniel; Goycoolea, Marcos (2007), "Computación con desigualdades de paridad dominó para el TSP", INFORMS Journal on Computing , 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 de comercio". Introducción a los algoritmos (2.ª ed.). MIT Press. págs. 1027–1033. ISBN 978-0-262-03384-8.
• Dantzig, GB ; Fulkerson, R. ; Johnson, SM (1954), "Solución de un problema de 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", Reading: Addison-Wesley , Nueva York: Addison-Wesley, Bibcode :1989gaso.book.....G, ISBN 978-0-201-15767-3
• Gutin, G.; Yeo, A.; Zverovich, A. (15 de marzo de 2002). "El viajante de comercio no debería ser codicioso: análisis de dominación de heurísticas de tipo codicioso para el TSP". Matemáticas Aplicadas Discretas . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 . ISSN  0166-218X.
• Gutin, G.; Punnen, AP (18 de mayo de 2007). El problema del viajante de comercio y sus variaciones. Springer US. ISBN 978-0-387-44459-8.
• Johnson, DS ; McGeoch, LA (1997), "El problema del viajante: un estudio de caso en optimización local", en Aarts, EHL; Lenstra, JK (eds.), Búsqueda local en optimización combinatoria (PDF) , John Wiley and Sons Ltd., págs. 215–310
• Lawler, EL; Shmoys, DB; Kan, AHG Rinnooy; Lenstra, JK (1985). El problema del viajante de comercio. John Wiley & Sons, Incorporated. ISBN 978-0-471-90413-7.
• MacGregor, JN; Ormerod, T. (1996), "Rendimiento humano en el problema del viajante de comercio", Perception & Psychophysics , 58 (4): 527–539, doi : 10.3758/BF03213088 , PMID  8934685, S2CID  38355042
• Medvedev, Andrei; Lee, Michael; Butavicius, Marcus; Vickers, Douglas (1 de febrero de 2001). "Rendimiento humano en problemas de 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 las subdivisiones poligonales: un esquema simple de aproximación en tiempo polinomial 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 'banyans'"". STOC '98: Actas del trigésimo simposio anual de la ACM sobre teoría de la computación . págs. 540–550. CiteSeerX  10.1.1.51.8676 .
• Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, Philip M. II (1977). "Análisis de varias heurísticas para el problema del viajante de comercio". Revista SIAM de informática . 6 (5). 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 de comercio , CMS Press
• Walshaw, Chris (2001), Un algoritmo Lin-Kernighan-Helsgaun multinivel para el problema del viajante de comercio, CMS Press

Enlaces externos

• Problema del viajante de comercio 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 de Jon McLoone en el proyecto de demostraciones Wolfram
• Herramienta de visualización TSP