Problema del vendedor ambulante - Travelling salesman problem

El problema del vendedor ambulante (también llamado problema del vendedor ambulante o 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 al ciudad de origen? " Es un problema NP-difícil en la optimización combinatoria , importante en la informática teórica y la investigación de operaciones .

El problema del comprador viajero y el problema de la ruta del vehículo son generalizaciones de TSP.

En la teoría de la complejidad computacional , la versión de decisión del TSP (donde se le da una longitud L , la tarea es decidir si el gráfico tiene un recorrido de 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 , por lo que algunas instancias con decenas de miles de ciudades se pueden resolver por completo e incluso los problemas con millones de ciudades se pueden aproximar en una pequeña fracción del 1%.

El TSP tiene varias aplicaciones incluso en su formulación más pura, como planificación , logística y fabricación de microchips . Ligeramente modificado, aparece como un subproblema en muchas áreas, como la secuenciación del 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 los tiempos de viaje o el costo, 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 querrán 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 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.

El problema del viajante de comercio fue formulado matemáticamente en el siglo XIX por el matemático irlandés WR 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 . 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 algoritmo obvio de fuerza bruta y observa la no optimización de los valores más cercanos. vecino heurístico:

Denotamos por problema de mensajero (ya que en la práctica esta cuestión debe ser resuelta por cada cartero, de todos modos 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 conecta los puntos. Por supuesto, este problema se puede resolver mediante un número finito de ensayos. Se desconocen las reglas que empujarían el número de intentos por debajo del número de permutaciones de los puntos dados. La regla de que se debe ir primero 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.

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 autobús escolar. 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 usó la frase "problema del viajante de comercio" fue el informe de 1949 de la RAND Corporation de Julia Robinson , "Sobre el juego hamiltoniano (un problema del viajante de comercio)".

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 en Santa Mónica ofreciera premios por los pasos para resolver el problema. 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 seminal sobre el tema en el que con estos nuevos métodos resolvieron una instancia con 49 ciudades a la optimización mediante la construcción de un recorrido y demostrando que ningún otro recorrido podía ser más corto. Sin embargo, Dantzig, Fulkerson y Johnson especularon que, dada una solución casi óptima, podríamos encontrar la optimización o demostrar la optimización agregando una pequeña cantidad de desigualdades (cortes) adicionales. Usaron esta idea para resolver su problema inicial de 49 ciudades usando un modelo de cuerdas. Descubrieron que solo necesitaban 26 recortes para llegar a una solución para el problema de 49 ciudades. Si bien este documento no proporcionó un enfoque algorítmico a 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. Además de los métodos de plano de corte, Dantzig, Fulkerson y Johnson utilizaron algoritmos de bifurcación y ligadura quizás por primera vez.

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. 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 vendedor que comienza en una casa u oficina y visita un número fijo de ubicaciones antes de regresar al inicio.

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 está probablemente 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 entonces con enfoques de bifurcación y cota. Un método para hacer esto fue 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.

En 1976, Christofides y Serdyukov, independientemente entre sí, hicieron un gran avance en esta dirección: el algoritmo de Christofides-Serdyukov arroja 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 mejora esperada 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". En 2020, esta pequeña mejora se extendió al TSP completo (métrico).

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

Se logró un gran progreso a fines de la década de 1970 y 1980, cuando Grötschel, Padberg, Rinaldi y otros lograron resolver exactamente instancias con hasta 2.392 ciudades, utilizando planos de corte y bifurcaciones y límites .

En la década de 1990, Applegate , Bixby , Chvátal y Cook desarrollaron el programa Concorde que se ha utilizado en muchas soluciones de grabación recientes. Gerhard Reinelt publicó el TSPLIB en 1991, una colección de casos de referencia de diversa dificultad, que ha sido utilizado 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 están garantizadas dentro del 2-3% de un recorrido óptimo.

Descripción

Como un problema de gráfico

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 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 un borde). Si no existe una ruta 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 posibles soluciones. En el TSP asimétrico , las rutas pueden no existir en ambas direcciones o las distancias pueden ser diferentes, formando un gráfico dirigido . Las colisiones de tráfico , las calles de un solo sentido y las tarifas aéreas para ciudades con diferentes tarifas de salida y llegada son ejemplos de cómo esta simetría podría romperse.

Problemas relacionados

• Una formulación equivalente en términos de teoría de grafos es: Dada una gráfica ponderada completa (donde los vértices representarían las ciudades, los bordes representarían las carreteras y las ponderaciones serían el costo o la distancia de esa carretera), encuentre un ciclo hamiltoniano con el menor peso.
• El requisito de regresar a la ciudad de partida no cambia la complejidad computacional del problema, vea el problema de la trayectoria hamiltoniana .
• Otro problema relacionado es el problema del viajante de cuello de botella (TSP de cuello de botella): encuentre un ciclo hamiltoniano en una gráfica ponderada con el peso mínimo del borde más pesado . Por ejemplo, evitando calles estrechas con grandes autobuses. El problema es de considerable importancia práctica, además de evidentes áreas de transporte y logística. Un ejemplo clásico es en circuito impreso de fabricación: programación de una ruta de la perforación de la máquina para perforar agujeros en una PCB. En aplicaciones de taladrado o mecanizado robótico, las "ciudades" son piezas para mecanizar o agujeros (de diferentes tamaños) para taladrar, y el "costo de viaje" incluye el tiempo para reequipar el robot (problema de secuenciación de trabajos de una sola máquina).
• El problema generalizado del viajante de comercio , también conocido como el "problema del político viajero", trata con "estados" que tienen (una o más) "ciudades" y el vendedor tiene que visitar exactamente una "ciudad" de cada "estado". Se encuentra una aplicación al pedir una solución al problema del material de corte con el fin de minimizar los cambios de cuchilla. Otro se refiere a la perforación en la fabricación de semiconductores , véase, por ejemplo, la patente de EE.UU. 7.054.798 . Noon y Bean demostraron que el problema generalizado del viajante de comercio puede transformarse en un problema estándar del viajante de comercio con el mismo número de ciudades, pero con una matriz de distancia modificada .
• El problema del ordenamiento secuencial se ocupa del problema de visitar un conjunto de ciudades donde existen relaciones de precedencia entre las ciudades.
• Una pregunta común en las entrevistas de Google es cómo enrutar los datos entre los nodos de procesamiento de datos; Las rutas varían según el tiempo para transferir los datos, pero los nodos también se diferencian por su capacidad de procesamiento 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 comprar 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 de enteros . 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.

Formulación de Miller – Tucker – Zemlin

Rotula las ciudades con los números y define: ${\ Displaystyle 1, \ ldots, n}$

${\ displaystyle x_ {ij} = {\ begin {cases} 1 & {\ text {la ruta va de la ciudad}} i {\ text {a la ciudad}} j \\ 0 & {\ text {de lo contrario}} \ end {cases }}}$

Para , sea ​​una variable ficticia y, finalmente, tome la distancia de una ciudad a otra . Entonces TSP se puede escribir como el siguiente problema de programación lineal de enteros: ${\ Displaystyle i = 1, \ ldots, n}$${\ Displaystyle u_ {i}}$${\ Displaystyle c_ {ij}> 0}$${\ Displaystyle i}$${\ Displaystyle j}$

${\ Displaystyle {\ begin {alineado} \ min & \ sum _ {i = 1} ^ {n} \ sum _ {j \ neq i, j = 1} ^ {n} c_ {ij} x_ {ij} \ dos puntos && \\ & x_ {ij} \ in \ {0,1 \} && i, j = 1, \ ldots, n; \\ & u_ {i} \ in \ mathbf {Z} && i = 2, \ 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} + nx_ {ij} \ leq n-1 && 2 \ leq i \ neq j \ leq n; \ \ & 1 \ leq u_ {i} \ leq n-1 && 2 \ leq i \ leq n. \ End {alineado}}}$

El primer conjunto de igualdad requiere que se llegue a cada ciudad desde exactamente otra ciudad, y el segundo conjunto de igualdad requiere que de cada ciudad haya una salida a exactamente otra ciudad. Las últimas limitaciones imponen que hay un solo recorrido que cubre todas las ciudades, y no dos o más recorridos inconexos que solo cubren colectivamente todas las ciudades. Para probar esto, se muestra a continuación (1) que cada solución factible contiene solo una secuencia cerrada de ciudades, y (2) que para cada recorrido que cubre todas las ciudades, hay valores para las variables ficticias que satisfacen las restricciones. (Las variables ficticias indican el orden del recorrido, lo que implica que la ciudad se visita antes que la ciudad . Esto se puede lograr aumentando cada vez que se visita). ${\ Displaystyle u_ {i}}$${\ Displaystyle u_ {i} <u_ {j}}$${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle u_ {i}}$

Para demostrar que cada solución factible contiene solo una secuencia cerrada de ciudades, basta con mostrar que cada subtour en una solución factible pasa por la ciudad 1 (teniendo en cuenta que las igualdades aseguran que solo pueda haber un recorrido de este tipo). Pues si sumamos todas las desigualdades correspondientes a para cualquier subtour de k pasos que no pasen por la ciudad 1, obtenemos: ${\ Displaystyle x_ {ij} = 1}$

${\ Displaystyle nk \ leq (n-1) k,}$

lo cual es una contradicción.

Ahora debe demostrarse que para cada recorrido que cubre todas las ciudades, existen valores para las variables ficticias que satisfacen las restricciones. ${\ Displaystyle u_ {i}}$

Sin pérdida de generalidad, defina el recorrido como que se origina (y termina) en la ciudad 1. Elija si se visita la ciudad en el paso . Luego ${\ Displaystyle u_ {i} = t}$${\ Displaystyle i}$${\ Displaystyle t (i, t = 1,2, \ ldots, n)}$

${\ Displaystyle u_ {i} -u_ {j} \ leq n-1,}$

desde puede ser mayor que y puede ser inferior a 1; por lo tanto, las restricciones se satisfacen siempre que Para , tenemos: ${\ Displaystyle u_ {i}}$${\ Displaystyle n}$${\ Displaystyle u_ {j}}$${\ Displaystyle x_ {ij} = 0.}$${\ Displaystyle x_ {ij} = 1}$

${\ Displaystyle u_ {i} -u_ {j} + nx_ {ij} = (t) - (t + 1) + n = n-1,}$

satisfaciendo la restricción.

Formulación de Dantzig-Fulkerson-Johnson

Etiquete las ciudades con los números 1,…, ny defina:

${\ displaystyle x_ {ij} = {\ begin {cases} 1 & {\ text {la ruta va de la ciudad}} i {\ text {a la ciudad}} j \\ 0 & {\ text {de lo contrario}} \ 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 de enteros: ${\ Displaystyle c_ {ij}> 0}$

${\ Displaystyle {\ begin {alineado} \ min & \ sum _ {i = 1} ^ {n} \ sum _ {j \ neq i, j = 1} ^ {n} c_ {ij} x_ {ij} \ dos puntos && \\ & \ 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 {alineado}}}$

La última restricción de la formulación DFJ asegura que ningún subconjunto Q adecuado pueda formar un sub-recorrido, por lo que la solución devuelta es un recorrido único 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 una generación de columnas retrasada .

Calculando una solución

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

• Diseñar algoritmos exactos , que funcionen razonablemente rápido solo para problemas de tamaño pequeño.
• Diseñar 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 que son posibles heurísticas mejores o 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 la búsqueda por 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 a tiempo . Este límite también ha sido alcanzado por Exclusión-Inclusión en un intento que precede al enfoque de programación dinámica. ${\ Displaystyle O (n ^ {2} 2 ^ {n})}$

Mejorar estos plazos parece difícil. Por ejemplo, no se ha determinado si existe un algoritmo exacto para TSP que se ejecute a tiempo . ${\ Displaystyle O (1.9999 ^ {n})}$

Otros enfoques incluyen:

• Varios algoritmos de ramificación y enlace , que se pueden utilizar para procesar TSP que contienen entre 40 y 60 ciudades.

• Algoritmos de mejora progresiva que utilizan técnicas que recuerdan a la programación lineal . Funciona bien para hasta 200 ciudades.
• Implementaciones de generación de cortes de bifurcación y límite y de problemas específicos ( bifurcación y corte ); este es el método de elección para resolver grandes instancias. Este enfoque tiene el récord actual, resolviendo una instancia con 85,900 ciudades, ver Applegate et al. (2006) .

En 2001 se encontró una solución exacta para 15,112 ciudades alemanas de TSPLIB utilizando el método de 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 y se demostró que no existe un recorrido más corto. En marzo de 2005, el problema del viajante de comercio de visitar los 33,810 puntos en una placa de circuito se resolvió utilizando Concorde TSP Solver : se encontró un recorrido de 66,048,945 unidades de longitud y se comprobó que no existe un recorrido más corto. El cálculo tomó aproximadamente 15,7 CPU-años (Cook et al. 2006). En abril de 2006, se resolvió una instancia con 85,900 puntos usando Concorde TSP Solver , que tomó más de 136 años de CPU, ver Applegate et al. (2006) .

Algoritmos heurísticos y de aproximación

Se han ideado varios algoritmos heurísticos y de aproximación , que rápidamente producen buenas soluciones. Estos incluyen 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.

Se reconocen varias categorías de heurísticas.

Heurística constructiva

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 en promedio produce una ruta un 25% más larga que la ruta más corta posible. Sin embargo, existen muchas distribuciones de ciudades especialmente organizadas que hacen que el algoritmo NN proporcione la peor ruta. Esto es cierto para los TSP asimétricos y simétricos. Rosenkrantz y col. mostró que el algoritmo NN tiene el factor de aproximación para las instancias que satisfacen la desigualdad del triángulo. Una variación del algoritmo NN, llamado 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. 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 los puntos como vértices; se puede calcular de manera eficiente mediante 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 cosen para producir el recorrido final.

El algoritmo de Christofides y Serdyukov

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, la coincidencia perfecta 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 algoritmos de aproximación hasta más tarde; el algoritmo de Christofides se denominó inicialmente heurística de Christofides.

Este algoritmo mira las cosas de manera diferente utilizando 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. Entonces, si tuviéramos un gráfico euleriano con ciudades de un TSP como vértices, entonces podemos ver fácilmente que podríamos usar un método de este tipo para encontrar un recorrido euleriano para encontrar una solución TSP. Por desigualdad triangular sabemos que el recorrido TSP no puede ser más largo que el recorrido euleriano y, como tal, tenemos un límite inferior para el TSP. Dicho método 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 en el recorrido a la siguiente.

Para mejorar el límite inferior, se necesita una mejor forma de crear un gráfico euleriano. Por desigualdad triangular, la mejor gráfica euleriana debe tener el mismo costo que la gira del mejor vendedor ambulante, por lo tanto, encontrar gráficas eulerianas óptimas es al menos tan difícil como TSP. Una forma de hacer esto es haciendo coincidir el peso mínimo usando algoritmos de . ${\ Displaystyle O (n ^ {3})}$

La conversión de un gráfico en un gráfico euleriano comienza con el árbol de expansión mínimo. Entonces todos los vértices de orden impar deben hacerse pares. Por lo tanto, se debe agregar una coincidencia para los vértices de grados impares, lo que aumenta el orden de cada vértice de grados impares en uno. Esto nos deja con un gráfico en el que cada vértice es de orden par, por lo que es euleriano. La adaptación del método anterior proporciona el algoritmo de Christofides y Serdyukov.

1. Encuentre un árbol de expansión mínimo para el problema
2. Cree una correspondencia 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

El intercambio por pares o la técnica de 2 opciones implica eliminar de forma iterativa dos bordes y reemplazarlos con dos bordes diferentes que vuelven a conectar los fragmentos creados por la eliminación de bordes en un recorrido nuevo y más corto. Del mismo modo, el 3-opt técnica elimina 3 bordes y 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 las instancias euclidianas, la heurística de 2 opciones proporciona en promedio soluciones que son aproximadamente un 5% mejores que el algoritmo de Christofides. Si comenzamos con una solución inicial hecha con un algoritmo codicioso , el número promedio de movimientos disminuye considerablemente nuevamente y es . Sin embargo, para inicios aleatorios, el número promedio de movimientos es . Sin embargo, aunque en orden esto es un pequeño aumento de tamaño, el número inicial de movimientos para problemas pequeños es 10 veces mayor para un comienzo aleatorio en comparación con uno hecho a partir de una heurística codiciosa. Esto se debe a que estas heurísticas de 2 opciones aprovechan las partes "malas" de una solución, como los cruces. Estos tipos de heurística se utilizan a menudo dentro de la heurística de problemas de enrutamiento de vehículos para volver a optimizar las soluciones de ruta. ${\ 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, elimine k bordes mutuamente disjuntos.
2. Vuelva a ensamblar los fragmentos restantes en un recorrido, sin dejar subtítulos inconexos (es decir, no conecte los puntos finales de un fragmento entre sí). En efecto, esto simplifica el TSP que se está considerando en un problema mucho más simple.
3. Cada punto final de fragmento se puede conectar a 2 k  - 2 otras posibilidades: de los 2 k puntos finales de fragmentos totales disponibles, los dos puntos finales del fragmento en consideració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.

Los métodos k -opt más populares son 3-opt, como los introdujo Shen Lin de Bell Labs en 1965. Un caso especial de 3-opt es donde 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 del 3-opt general al restringir los 3-cambios a este subconjunto especial donde dos de los bordes eliminados son adyacentes. Esta llamada opción de dos y media generalmente se ubica aproximadamente a medio camino entre 2 opciones y 3 opciones, tanto en términos de la calidad de los recorridos logrados como del tiempo requerido para lograr esos recorridos.

V -opt heurístico

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 los problemas de los vendedores ambulantes durante casi dos décadas. David Johnson y su equipo de investigación desarrollaron métodos de opción variable más avanzados en Bell Labs a fines de la década de 1980. 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 de Lin-Kernighan da resultados que están garantizados en al menos 3 opciones. Los métodos Lin-Kernighan-Johnson calculan un recorrido Lin-Kernighan y luego perturban el recorrido por lo que se ha descrito como una mutación que elimina al menos cuatro bordes y vuelve a conectar el recorrido de una manera diferente, luego V -optando el nuevo recorrido. La mutación es a menudo suficiente para mover el recorrido del 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 fallan otras heurísticas. Durante muchos años, Lin – Kernighan – Johnson había identificado soluciones óptimas para todos los TSP donde 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 enjambres ) y el método de entropía cruzada .

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 utilizando una simulación de una colonia de hormigas llamada ACS ( sistema de colonias de hormigas ). 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 para 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 han 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.

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 del triángulo .

Una restricción muy natural del TSP es requerir 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 a través del intermedio C :

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

Los tramos de los bordes luego 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.

A continuación, se muestran algunos ejemplos de TSP métricas 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 rectilínea TSP la distancia entre dos ciudades es la suma de los valores absolutos de las diferencias de su x - y y coordenadas x. Esta métrica a menudo se denomina distancia de Manhattan o métrica de cuadra de la 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, 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 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 ruta más corta entre A y B en el gráfico original. ${\ Displaystyle d_ {AB}}$

Euclidiana

Cuando los números de entrada pueden ser números reales arbitrarios, el TSP euclidiano es un caso particular de TSP métrico, ya que las distancias en un plano obedecen a la desigualdad del triángulo. Cuando los números de entrada deben ser enteros, comparar longitudes de recorridos implica comparar sumas de raíces cuadradas.

Como el TSP general, Euclidean TSP es NP-hard en cualquier caso. Con coordenadas racionales y métrica discretizada (distancias redondeadas a un número entero), el problema es NP-completo. Con coordenadas racionales y la métrica euclidiana real, se sabe que el TSP euclidiano se encuentra en la Jerarquía de conteo, una subclase de PSPACE. Con coordenadas reales arbitrarias, Euclidean TSP no puede estar en tales clases, ya que hay innumerables entradas posibles. Sin embargo, Euclidean TSP es probablemente la versión más fácil de aproximar. 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 , por lo que se puede calcular en el tiempo O ( n log n ) esperado 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 arriba opere 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 de tiempo polinomial (PTAS). 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 hacen asimétricas por calles de un solo sentido, vías de acceso, autopistas, etc.).

Conversión a simétrico

Resolver un gráfico TSP asimétrico puede resultar algo complejo. La siguiente es una matriz de 3 x 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 .

Pesos de trayectoria asimétrica

	A	B	C
A		1	2
B	6		3
C	5	4

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 . (Alternativamente, 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. 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 los nodos originales y ningún borde vincula directamente los nodos fantasmas.

Pesos de trayectoria simétrica

	A	B	C	A'	B'	C'
A				- w	6	5
B				1	- w	4
C				2	3	- w
A'	- w	1	2
B'	6	- w	3
C'	5	4	- w

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 pertenezcan 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 los nodos original y fantasma nuevamente obtenemos una solución (óptima) del problema asimétrico original (en nuestro ejemplo, ). ${\ Displaystyle \ mathrm {A \ a A '\ a C \ a C' \ a B \ a B '\ a A}}$${\ Displaystyle \ mathrm {A \ a C \ a B \ a A}}$

Problema del analista

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

Longitud de la ruta 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 de camino más corta (es decir, la solución TSP) para este conjunto de puntos, de acuerdo con la distancia euclidiana habitual . Se sabe 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), se sigue del teorema de la convergencia acotada que , por lo tanto, los límites superior e inferior en 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 de que no puede existir si las ubicaciones independientes son reemplazadas con las observaciones de un proceso ergódico estacionario con marginales uniformes. ${\ Displaystyle {\ frac {L_ {n} ^ {*}} {\ sqrt {n}}} \ rightarrow \ beta}$${\ Displaystyle n \ to \ infty}$${\ Displaystyle X_ {1}, \ ldots, X_ {n}}$

Límite superior

• Uno tiene , y por lo tanto , usando un camino ingenuo que visita monótonamente los puntos dentro de cada uno de los cortes de ancho en el cuadrado.${\ Displaystyle L ^ {*} \ leq 2 {\ sqrt {n}} + 2}$${\ Displaystyle \ beta \ leq 2}$${\ Displaystyle {\ sqrt {n}}}$${\ Displaystyle 1 / {\ sqrt {n}}}$
• Pocos demostró , por lo tanto , más tarde mejorado por Karloff (1987): .${\ Displaystyle L_ {n} ^ {*} \ leq {\ sqrt {2n}} + 1.75}$${\ Displaystyle \ beta \ leq {\ sqrt {2}}}$${\ Displaystyle \ beta \ leq 0.984 {\ sqrt {2}}}$
• Algún estudio informó un límite superior .${\ Displaystyle \ beta \ leq 0.73 \ dots}$

Límite inferior

• Al observar que es mayor que multiplicado por la distancia entre y el punto 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}}.}$

• Un mejor límite inferior se obtiene al observar que es mayor que la suma de las distancias entre los puntos más cercano y el segundo más cercano , lo que da${\ Displaystyle \ mathbb {E} [L_ {n} ^ {*}]}$${\ Displaystyle {\ tfrac {1} {2}} n}$${\ Displaystyle X_ {0}}$${\ Displaystyle X_ {i}, X_ {j} \ neq X_ {0}}$

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

• El mejor límite inferior actualmente es

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

• Held y Karp proporcionaron un algoritmo de tiempo polinomial que proporciona límites inferiores numéricos para y, por lo tanto, para los que parecen ser buenos hasta más o menos el 1%. En particular, David S. Johnson obtuvo un límite inferior mediante un experimento informático:${\ 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:

${\ 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 ; consulte el problema de función ), y la versión del problema de decisión ("dados los costos y un número x , decida si hay una ronda -la ruta de viaje más barata que x ") es NP-completa . El problema del cuello de botella del viajante de negocios también es NP-difícil. El problema sigue siendo NP-difícil incluso para el caso en que las ciudades están en el plano con distancias euclidianas , así como en una serie de otros casos restrictivos. Eliminar la condición de visitar cada ciudad "solo una vez" no elimina la dureza NP, ya que en el caso plano hay un recorrido óptimo que visita cada ciudad solo 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 aproximación

En el caso general, encontrar un recorrido más corto para vendedores ambulantes es NPO -completo. Si la medida de la distancia es métrica (y por lo tanto simétrica), el problema se vuelve APX -completo y el algoritmo de Christofides y Serdyukov lo aproxima dentro de 1.5. Una preimpresión de 2020 mejora este límite . El límite de inaproximación más conocido es 123/122. ${\ displaystyle 1.5-10 ^ {- 36}}$

Si las distancias están restringidas a 1 y 2 (pero siguen siendo métricas), la relación de aproximación se convierte en 8/7. En el caso asimétrico con desigualdad triangular , hasta hace poco solo se conocían garantías de desempeño logarítmico. En 2018, Svensson, Tarnawski y Végh desarrollaron una aproximación de factores constantes. El mejor algoritmo actual, de Traub y Vygen, logra una relación de rendimiento de . El límite de inaproximación más conocido es 75/74. ${\ Displaystyle 22+ \ varepsilon}$

El correspondiente problema de maximización de encontrar el recorrido de vendedor ambulante más largo es aproximado dentro de 63/38. Si la función de distancia es simétrica, el recorrido más largo se puede aproximar dentro de 4/3 mediante un algoritmo determinista y dentro de un algoritmo aleatorio. ${\ displaystyle {\ tfrac {1} {25}} (33+ \ varepsilon)}$

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 pueden producir soluciones casi óptimas rápidamente, de una manera casi lineal, con un rendimiento que varía entre un 1% menos eficiente para gráficos con 10-20 nodos y un 11% menos eficiente para gráficos con 120 nodos. 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 heurística de evitación de cruces. 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. Sin embargo, los resultados sugieren que el rendimiento de la computadora en el TSP puede mejorarse al comprender y emular los métodos utilizados por los humanos para estos problemas, y también han conducido a nuevos conocimientos sobre los mecanismos del pensamiento humano. El primer número del Journal of Problem Solving se dedicó al tema del desempeño humano en TSP, y una revisión de 2011 enumeró docenas de artículos sobre el tema.

Un estudio de 2011 sobre cognición animal titulado "Deja que la paloma conduzca el autobús", que lleva el nombre del libro para niños ¡No dejes que la paloma conduzca el autobús! , examinó la cognición espacial en palomas mediante el estudio de 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 encontraron que las palomas usaban en gran medida la proximidad para determinar qué comedero seleccionarí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 ineficaz 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 a lo largo de la ruta cuando las diferencias en los costos de viaje entre las rutas eficientes y las menos eficientes basadas en la proximidad sean mayores". Estos resultados son consistentes con otros experimentos realizados con no primates, que han demostrado que algunos no primates pudieron 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 alimentos, el ameboide Physarum polycephalum adapta su morfología para crear una ruta eficiente entre las fuentes de alimentos que también puede verse como una solución aproximada a la TSP.

Benchmarks

Para la evaluación comparativa de los algoritmos de TSP, TSPLIB es una biblioteca de ejemplos de TSP y se mantienen los 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 los Estados Unidos para resolver el problema más difícil de alcanzar en la historia de la informática: P vs. NP .

Ver también

• Problema del viajero canadiense
• 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
• Problema del viajante Steiner
• Desafío del metro
• Desafío del tubo
• Problema de ruta del vehículo
• Exploración de gráficos

Notas

Referencias

Otras lecturas

enlaces externos

• Problema del vendedor ambulante en la Wayback Machine (archivado el 17 de diciembre de 2013) en la Universidad de Waterloo
• TSPLIB en la Universidad de Heidelberg
• Problema del vendedor ambulante por Jon McLoone en el Proyecto de demostraciones Wolfram
• Herramienta de visualización de TSP