Problema del vendedor ambulante

NP-hard problem in combinatorial optimization

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

El problema del vendedor ambulante (también llamado problema del vendedor ambulante ^[1] 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 a la 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%. ^[2]

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 se puede incrustar dentro de unproblema de control óptimo . ^{[3] [4]} En muchas aplicaciones, se pueden imponer restricciones adicionales, como recursos limitados o ventanas de tiempo.

Historia

Los orígenes del problema de los viajantes 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. ^[5]

William Rowan Hamilton

El problema del viajante 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 . ^[6] 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 la heurística del vecino más cercano:

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. ^[7]

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. ^[8] 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 de comercio" fue el informe de la RAND Corporation de 1949 de Julia Robinson , "Sobre el juego hamiltoniano (un problema del viajero viajero)". ^{[9] [10]}

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. ^[8] 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 plano de corte.método 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.^[8] Además de los métodos del plano de corte, Dantzig, Fulkerson y Johnson utilizaronalgoritmos de bifurcación y ligadura quizás por primera vez. ^[8]

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. ^[11]  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. Sin embargo, en la década de 1960 se creó un nuevo enfoque, que en lugar de buscar soluciones óptimas, se 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 se pueden utilizar con enfoques de bifurcación y enlace. 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. ^[8]

En 1976, Christofides y Serdyukov, independientemente entre sí, hicieron un gran avance en esta dirección: ^[12] 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 tan simple y rápido, muchos esperaban que diera paso a un método de solución casi óptimo. Este sigue siendo el método con el mejor escenario en el peor de los casos. Sin embargo, para un caso especial bastante general del problema, fue superado por un pequeño margen en 2011. ^[13]

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. ^[14]

En 2020, se desarrolló un algoritmo de aproximación ligeramente mejorado. ^{[15] [16]}

Descripción

Como un problema de gráfico

TSP simétrico con cuatro ciudades

TSP se puede modelar como un gráfico ponderado no dirigido , de modo que las ciudades son los vértices del gráfico , las rutas son los bordes del gráfico y la distancia de una ruta es el peso del borde. Es un problema de minimización que comienza y termina en un vértice específico después de haber visitado cada 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. ^[17] 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 : programación de una ruta de perforaciónmáquina para perforar agujeros en una placa de circuito impreso. 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). ^[18]
• El problema generalizado del viajante de comercio , también conocido como "problema del político viajero", trata de "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 se puede transformar 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 que 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 . ^{[19] [20] [21]} 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. ^{[22] [23]}

Formulación de Miller-Tucker-Zemlin

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

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

Para i = 1,…, n , sea ​​una variable ficticia y, finalmente, tome 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 u_{i}}$${\displaystyle c_{ij}>0}$

${\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;\\&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{aligned}}}$

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, existen 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). Porque 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 i en el paso t ( i , t = 1, 2, ..., n). Entonces${\displaystyle u_{i}=t}$

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

desde puede ser no mayor que n y puede no menos de 1 ser; por lo tanto, las restricciones se satisfacen siempre que Para , tenemos:${\displaystyle u_{i}}$${\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{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise}}\end{cases}}}$

Considere la distancia de la ciudad i a la ciudad j . Entonces TSP se puede escribir como el siguiente problema de programación lineal de enteros:${\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}}}\geq 1&&\forall Q\subsetneq \{1,\ldots ,n\},|Q|\geq 2\\\end{aligned}}}$

La última restricción de la formulación DFJ asegura que no haya sub-recorridos entre los vértices no iniciales, 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 . ^[24] 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})}$

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

Mejorar estos plazos parece difícil. Por ejemplo, no se ha determinado si existe un algoritmo exacto para TSP que se ejecute en el tiempo . ^[25]${\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.

Solución de un TSP con 7 ciudades utilizando un simple algoritmo de bifurcación y cota. Nota: el número de permutaciones es mucho menor que la búsqueda de fuerza bruta

• 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 cierre y de problemas específicos ( bifurcación y corte ^[26] ); 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. ^[27] 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 demostró 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. ^[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 cambia el punto de partida

El algoritmo del vecino más cercano (NN) (un algoritmo codicioso ) permite al vendedor elegir la ciudad no visitada más cercana como su próximo movimiento. Este algoritmo produce rápidamente una ruta efectivamente corta. Para N ciudades distribuidas aleatoriamente en un plano, el algoritmo en promedio produce una ruta un 25% más larga que la ruta más corta posible. ^[28] Sin embargo, existen muchas distribuciones de ciudades especialmente organizadas que hacen que el algoritmo NN proporcione la peor ruta. ^[29] Esto es cierto para los PST asimétricos y simétricos. ^[30] Rosenkrantz y col. ^[31] mostró que el algoritmo NN tiene el factor de aproximación${\displaystyle \Theta (\log |V|)}$para los casos 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. ^[32] 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.

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. ^[33]

El algoritmo de Christofides y Serdyukov

Creando una coincidencia

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

El algoritmo de Christofides y Serdyukov sigue un esquema similar pero combina el árbol de expansión mínimo con una solución de otro problema, 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. ^[12]

Este algoritmo mira las cosas de manera diferente utilizando un resultado de la teoría de grafos que ayuda a mejorar el LB 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. ^[8] 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 dicho método 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 LB 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 hacerlo es mediante la comparación de pesos mínimos mediante algoritmos de . ^[8]${\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 grado impar, lo que aumenta el orden de cada vértice de grado impar en uno. ^[8] 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

Un ejemplo de una iteración de 2 opciones

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ísticas se utilizan a menudo dentro de la heurística de problemas de enrutamiento de vehículos para volver a optimizar las soluciones de ruta. ^[28]${\displaystyle O(n)}$${\displaystyle O(n\log(n))}$

k -opt heuristic, 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 posibilidades más: de los 2 k puntos finales de fragmentos totales disponibles, los dos puntos finales del fragmento en consideración no se permiten. 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ás popular de los métodos k -opt son 3-opt, como lo 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í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 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 Kernighanpublicó 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. Los métodos de opción variable más avanzados fueron desarrollados en Bell Labs a fines de la década de 1980 por David Johnson y su equipo de investigación. 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 proporciona 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-optar el nuevo tour. 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

Artículo principal: algoritmos de 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 ). ^[34] 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.

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étrica

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 la duración de los 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. ^[35] Con coordenadas racionales y la métrica euclidiana real, se sabe que el TSP euclidiano se encuentra en la Jerarquía de conteo, ^[36] 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. ^[37] 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 O ( n logn ) tiempo 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),}$

hora; esto se denomina esquema de aproximación de tiempo polinomial (PTAS). ^[38] 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 . ^[39]

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\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 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 ^[11] 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. ^[40]${\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 ^[41] demostrado , 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ó ^[42] un límite superior .${\displaystyle \beta \leq 0.92\dots }$
• Algún estudio informó ^[43] 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}}.}$

• Se obtiene un mejor límite inferior ^[11] 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 ^[42] es

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

• Held y Karp ^[44] 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%. ^[45] En particular, David S. Johnson ^[46] 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 ^[47] 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 varios 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. ^[48] Si la medida de la distancia es métrica (y por tanto simétrica), el problema se vuelve APX -completo ^[49] y el algoritmo de Christofides y Serdyukov lo aproxima dentro de 1,5. ^{[50] [51] [12]} Una preimpresión de 2020 mejora este límite . ^[52] El límite de inapropiabilidad más conocido es 123/122. ^[53]${\displaystyle 1.5-10^{-36}}$

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

El correspondiente problema de maximización de encontrar el recorrido más largo del vendedor ambulante es aproximado dentro de 63/38. ^[58] Si la función de distancia es simétrica, el recorrido más largo puede aproximarse dentro de 4/3 por un algoritmo determinista ^[59] y dentro por un algoritmo aleatorio. ^[60]${\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. ^{[61] [62]} 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 el cruce -Evitación heurística. ^{[63] [64] [65]}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. ^{[66] [67] [68]} No obstante, 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, ^[69] y también han llevado a nuevos conocimientos sobre los mecanismos humanos. pensamiento. ^[70] El primer número del Journal of Problem Solving se dedicó al tema del desempeño humano en TSP, ^[71] y una revisión de 2011 enumeró docenas de artículos sobre el tema. ^[70]

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, "puede 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 ".^[72] 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. ^[73] Se considera que presenta posibilidades interesantes y se ha estudiado en el área de la computación natural .

Puntos de referencia

Para la evaluación comparativa de los algoritmos de TSP, TSPLIB ^[74] 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 . ^[75]

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

1. "Búsqueda de" problema de vendedor ambulante " " . Google Scholar . Consultado el 23 de noviembre de 2019 .
2. Vea el problema de la gira mundial de TSP que ya ha sido resuelto dentro del 0.05% de la solución óptima. [1]
3. Ross, MI; Proulx, RJ; Karpenko, M. (6 de mayo de 2020). "Una teoría de control óptimo para el problema del viajante y sus variantes". arXiv : 2005.03186 [ math.OC ].
4. Ross, MI; Proulx, RJ; Karpenko, M. (julio de 2019). "Planificación, programación y maniobras autónomas de sensores UAV: ​​una técnica de participación de obstáculos" . Conferencia Americana de Control (ACC) 2019 . IEEE: 65–70. doi : 10.23919 / acc.2019.8814474 . ISBN 978-1-5386-7926-5. S2CID  201811463 .
5. "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 de comercio - cómo debe ser y qué debe hacer para obtener comisiones y estar seguro del feliz éxito en su negocio - por un viejo commis-voyageur )
6. Se puede encontrar una discusión sobre los primeros trabajos de Hamilton y Kirkman en Graph Theory, 1736-1936 de Biggs, Lloyd y Wilson (Clarendon Press, 1986).
7. Citado y traducción al inglés en Schrijver (2005) . Alemán original: "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 .Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg ".
8. Lawler, EL (1985). El problema del vendedor ambulante: una visita guiada de optimización combinatoria (Repr. Con correcciones. Ed.). John Wiley e hijos. ISBN 978-0471904137.
9. Robinson, Julia (5 de diciembre de 1949). "Sobre el juego hamiltoniano (un problema de viajante)" . Proyecto Rand . Santa Mónica, CA: The Rand Corporation (RM-303) . Consultado el 2 de mayo de 2020 .
10. Un tratamiento detallado de la conexión entre Menger y Whitney, así como el crecimiento en el estudio de TSP se puede encontrar en Schrijver (2005) .
11. Beardwood, Halton y Hammersley (1959) .
12. 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 . 
13. Klarreich, Erica (30 de enero de 2013). "Los científicos informáticos encuentran nuevos atajos para el infame problema del viajante" . CON CABLE . Consultado el 14 de junio de 2015 .
14. Rego, César; Gamboa, Dorabela; Glover, Fred; Osterman, Colin (2011), "Heurística de problemas de los vendedores ambulantes: 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 .
15. Klarreich, Erica (8 de octubre de 2020). "Los informáticos rompen el récord de vendedor ambulante" . Revista Quanta . Consultado el 13 de octubre de 2020 .
16. Karlin, Anna R .; Klein, Nathan; Gharan, Shayan Oveis (30 de agosto de 2020). "Un algoritmo de aproximación (ligeramente) mejorado para TSP métrico". arXiv : 2007.01409 [ cs.DS ].
17. " ¿Cómo se arreglan las rutas de los autobuses escolares? Llame al MIT en Wall Street Journal" (PDF) .
18. Behzad, Arash; Modarres, Mohammad (2002), "Nueva transformación eficiente del problema del vendedor ambulante generalizado en un problema del vendedor ambulante", Actas de la 15ª Conferencia Internacional de Ingeniería de Sistemas (Las Vegas)
19. Papadimitriou, CH; Steiglitz, K. (1998), Optimización combinatoria: algoritmos y complejidad , Mineola, NY: Dover, págs. 308-309.
20. Tucker, AW (1960), "Sobre programas de números enteros y gráficos dirigidos", Proyecto de investigación matemática de IBM (Universidad de Princeton)
21. Dantzig, George B. (1963), Programación lineal y extensiones , Princeton, Nueva Jersey: PrincetonUP, págs. 545-7, ISBN 0-691-08000-3 , sexta impresión, 1974. 
22. Velednitsky, Mark (2017). "Breve prueba combinatoria de que el politopo DFJ está contenido en el politopo MTZ para el problema del vendedor ambulante asimétrico". Cartas de investigación operativa . 45 (4): 323–324. arXiv : 1805.06997 . doi : 10.1016 / j.orl.2017.04.010 . S2CID 6941484 . 
23. Bektaş, Tolga; Gouveia, Luis (2014). "¿Réquiem por las limitaciones de eliminación de los subtour Miller-Tucker-Zemlin?". Revista europea de investigación operativa . 236 (3): 820–832. doi : 10.1016 / j.ejor.2013.07.038 .
24. Bellman (1960) , Bellman (1962) , Held & Karp (1962)
25. Woeginger (2003) .
26. Padberg y Rinaldi (1991) .
27. Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William; Helsgaun, Keld (junio de 2004). "Gira óptima de Suecia" . Consultado el 11 de noviembre de 2020 .
28. Johnson, DS ; McGeoch, LA (1997). "El problema del vendedor ambulante: un estudio de caso de optimización local" (PDF) . En Aarts, EHL; Lenstra, JK (eds.). Búsqueda local en optimización combinatoria . Londres: John Wiley and Sons Ltd. págs. 215–310.
29. Gutina, Gregory; Yeob, Anders; Zverovich, Alexey (15 de marzo de 2002). "El vendedor ambulante no debe 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 .>
30. Zverovitch, Alexei; Zhang, Weixiong; Yeo, Anders; McGeoch, Lyle A .; Gutin, Gregory; Johnson, David S. (2007), "Análisis experimental de heurística para el ATSP", El problema del viajante y sus variaciones , Optimización combinatoria, Springer, Boston, MA, págs. 445–487, CiteSeerX 10.1.1.24.2386 , doi : 10.1007 / 0-306-48213-4_10 , ISBN  978-0-387-44459-8
31. Rosenkrantz, DJ; Stearns, RE; Lewis, PM (14-16 de octubre de 1974). Algoritmos aproximados para el problema del vendedor ambulante . 15º Simposio Anual sobre Teoría de la Conmutación y Autómatas (swat 1974). doi : 10.1109 / SWAT.1974.4 .
32. Ray, SS; Bandyopadhyay, S .; Pal, SK (2007). "Operadores genéticos para la optimización combinatoria en TSP y ordenamiento de genes de microarrays". Inteligencia aplicada . 26 (3): 183-195. CiteSeerX 10.1.1.151.132 . doi : 10.1007 / s10489-006-0018-y . S2CID 8130854 .  
33. Kahng, AB; Reda, S. (2004). "Match Twice y Stitch: una nueva heurística de construcción de Tour TSP". Cartas de investigación operativa . 32 (6): 499–509. doi : 10.1016 / j.orl.2004.04.001 .
34. Dorigo, Marco; Gambardella, Luca Maria (1997). "Colonias de hormigas para el problema del viajante". Biosistemas . 43 (2): 73–81. CiteSeerX 10.1.1.54.7734 . doi : 10.1016 / S0303-2647 (97) 01708-5 . PMID 9231906 . S2CID 8243011 .   
35. Papadimitriou (1977) .
36. Allender y col. (2007) .
37. Larson y Odoni (1981) .
38. Arora (1998) .
39. Jonker, Roy; Volgenant, Ton (1983). "Transformación asimétrica en problemas de viajante simétrico". Cartas de investigación operativa . 2 (161-163): 1983. doi : 10.1016 / 0167-6377 (83) 90048-2 .
40. 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 
41. Pocos, L. (1955). "El camino más corto y el camino más corto a través de n puntos". Mathematika . 2 (2): 141-144. doi : 10.1112 / s0025579300000784 .
42. Steinerberger (2015) .
43. Fiechter, C.-N. (1994). "Un algoritmo de búsqueda tabú paralelo para grandes problemas de viajantes". Dto. Matemáticas aplicadas . 51 (3): 243-267. doi : 10.1016 / 0166-218X (92) 00033-I .
44. Celebrada, M .; Karp, RM (1970). "El problema del vendedor ambulante y árboles de expansión mínima". Investigación operativa . 18 (6): 1138-1162. doi : 10.1287 / opre.18.6.1138 .
45. Goemans, M .; Bertsimas, D. (1991). "Análisis probabilístico del límite inferior de Held y Karp para el problema del viajante de comercio euclidiano". Matemáticas de la investigación operativa . 16 (1): 72–89. doi : 10.1287 / moor.16.1.72 .
46. "error" . about.att.com .
47. Christine L. Valenzuela y Antonia J. Jones Archivado el 25 de octubre de 2007 en la Wayback Machine.
48. Orponen, P .; Mannila, H. (1987). Sobre aproximación preservando reducciones: problemas completos y medidas robustas '(Informe). Departamento de Ciencias de la Computación, Universidad de Helsinki. Informe técnico C-1987–28.
49. Papadimitriou y Yannakakis (1993) .
50. Christofides (1976) .
51. Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [Sobre algunos paseos extremos en gráficos] (PDF) , Upravlyaemye Sistemy (en ruso), 17 : 76–79
52. Karlin, Anna R .; Klein, Nathan; Gharan, Shayan Oveis (30 de agosto de 2020). "Un algoritmo de aproximación (ligeramente) mejorado para TSP métrico". arXiv : 2007.01409 [ cs ].
53. Karpinski, Lampis y Schmied (2015) .
54. Berman y Karpinski (2006) .
55. Kaplan y col. (2004) .
56. Svensson, Ola; Tarnawski, Jakub; Végh, László A. (2018). "Un algoritmo de aproximación de factor constante para el problema del viajante de comercio asimétrico" . Actas del 50 ° Simposio Anual ACM SIGACT sobre Teoría de la Computación - STOC 2018 . Los Ángeles, CA, EE.UU .: ACM Press: 204–213. doi : 10.1145 / 3188745.3188824 . ISBN 978-1-4503-5559-9. S2CID  12391033 .
57. 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 . Chicago, IL: ACM: 1–13. arXiv : 1912.00670 . doi : 10.1145 / 3357713.3384233 . ISBN 978-1-4503-6979-4. S2CID  208527125 .
58. Kosaraju, Park y Stein (1994) .
59. Serdyukov (1984) .
60. Hassin y Rubinstein (2000) .
61. 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 .
62. Seco, Mateo; Lee, Michael D .; Vickers, Douglas; Hughes, Peter (2006). "Rendimiento humano en problemas de vendedores ambulantes presentados visualmente con diferentes números de nodos". El diario de resolución de problemas . 1 (1). CiteSeerX 10.1.1.360.9763 . doi : 10.7771 / 1932-6246.1004 . ISSN 1932-6246 .  
63. Rooij, Iris Van; Stege, Ulrike; Schactman, Alissa (1 de marzo de 2003). "Cascos convexos y cruces turísticos en el problema del vendedor ambulante euclidiano: 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 .    
64. MacGregor, James N .; Chu, Yun (2011). "Actuación humana en el viajante de comercio y problemas relacionados: una revisión" . El diario de resolución de problemas . 3 (2). doi : 10.7771 / 1932-6246.1090 . ISSN 1932-6246 . 
65. MacGregor, James N .; Crónica, Edward P .; Ormerod, Thomas C. (1 de marzo de 2004). "¿Casco convexo o evitación de cruce? Solución heurística en el problema del viajante de comercio" . Memoria y cognición . 32 (2): 260–270. doi : 10.3758 / bf03196857 . ISSN 0090-502X . PMID 15190718 .  
66. 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 .
67. Kyritsis, Markos; Gulliver, Stephen R .; Feredoes, Eva (12 de junio de 2017). "Reconocimiento de violaciones heurísticas de evitación de cruce al resolver el problema del vendedor ambulante euclidiano". Investigación psicológica . 82 (5): 997–1009. doi : 10.1007 / s00426-017-0881-7 . ISSN 0340-0727 . PMID 28608230 . S2CID 3959429 .   
68. Kyritsis, Markos; Blathras, George; Gulliver, Stephen; Varela, Vasiliki-Alexia (11 de enero de 2017). "Sentido de dirección y conciencia como predictores del desempeño en el problema del viajero viajero euclidiano" . Heliyon . 3 (11): e00461. doi : 10.1016 / j.heliyon.2017.e00461 . PMC 5727545 . PMID 29264418 .  
69. Kyritsis, Markos; Gulliver, Stephen R .; Feredoes, Eva; Din, Shahab Ud (diciembre de 2018). "Comportamiento humano en el problema del vendedor ambulante euclidiano: modelado computacional de efectos heurísticos y figurativos". Investigación de sistemas cognitivos . 52 : 387–399. doi : 10.1016 / j.cogsys.2018.07.027 . S2CID 53761995 . 
70. 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.
71. Journal of Problem Solving 1 (1) , 2006, consultado el 6 de junio de 2014.
72. 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". Cognición animal . 15 (3): 379–391. doi : 10.1007 / s10071-011-0463-9 . ISSN 1435-9456 . PMID 21965161 . S2CID 14994429 .   
73. Jones, Jeff; Adamatzky, Andrew (2014), "Computación del problema del viajante de comercio por una gota que se encoge" (PDF) , Computación natural : 2, 13, arXiv : 1303.4969 , Bibcode : 2013arXiv1303.4969J
74. "TSPLIB" . comopt.ifi.uni-heidelberg.de . Consultado el 10 de octubre de 2020 .
75. Geere, Duncan (26 de abril de 2012). " La película ' Travelling Salesman' considera las repercusiones si P es igual a NP" . Reino Unido cableado . Consultado el 26 de abril de 2012 .

Referencias

• Applegate, DL; Bixby, RM; Chvátal, V .; Cook, WJ (2006), El problema del vendedor ambulante , ISBN 978-0-691-12993-8.
• Allender, Eric; Bürgisser, Peter; Kjeldgaard-Pedersen, Johan; Mitersen, Peter Bro (2007), "Sobre la complejidad del análisis numérico" (PDF) , SIAM J. Comput. , 38 (5): 1987–2006, CiteSeerX  10.1.1.167.5495 , doi : 10.1137 / 070697926.
• Arora, Sanjeev (1998), "Esquemas de aproximación de tiempo polinomial para el viajante de comercio euclidiano y otros problemas geométricos" (PDF) , Journal of the ACM , 45 (5): 753–782, doi : 10.1145 / 290179.290180 , MR  1668147 , S2CID  3023351.
• Beardwood, J .; Halton, JH; Hammersley, JM (octubre de 1959), "The Shortest Path Through Many Points" , Proceedings of the Cambridge Philosophical Society , 55 (4): 299–327, Bibcode : 1959PCPS ... 55..299B , doi : 10.1017 / s0305004100034095 , ISSN  0305-0041.
• Bellman, R. (1960), "Procesos combinatorios y programación dinámica", en Bellman, R .; Hall, M. Jr. (eds.), Análisis combinatorio, Actas de simposios en matemáticas aplicadas 10 , American Mathematical Society, págs. 217–249.
• Bellman, R. (1962), "Tratamiento de programación dinámica del problema del vendedor ambulante", J. Assoc. Computación. Mach. , 9 : 61–63, doi : 10.1145 / 321105.321111 , S2CID  15649582.
• Berman, Piotr; Karpinski, Marek (2006), "Algoritmo de aproximación de 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-0898716054, 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 max TSP", 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), "A Dynamic Programming Approach to Sequencing Problems", Journal of the Society for Industrial and Applied Mathematics , 10 (1): 196-210, doi : 10.1137 / 0110015 , hdl : 10338.dmlcz / 103900.
• Kaplan, H .; Lewenstein, L .; Shafrir, N .; Sviridenko, M. (2004), "Algoritmos de aproximación para TSP asimétrico mediante la descomposición de multigrafos regulares dirigidos", In Proc. 44th IEEE Symp. sobre Fundamentos de la Computación. Sci , págs. 56-65.
• Karpinski, M .; Lampis, M .; Schmied, R. (2015), "New Inapproximability limits for 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), "tours largos y cortos superstrings ' ", Proc. 35th Ann. IEEE Symp. sobre Fundamentos de la Computación. Sci , IEEE Computer Society, págs. 166-177.
• Larson, Richard C .; Odoni, Amedeo R. (1981), "6.4.7: Aplicaciones de modelos de red § Problemas de enrutamiento §§ TSP euclidiano" , Investigación de operaciones urbanas , Prentice-Hall, ISBN 9780139394478, OCLC  6331426.
• Padberg, M .; Rinaldi, G. (1991), "Un algoritmo de ramificación y corte para la resolución de problemas de viajantes ambulantes simétricos a gran escala" , Revisión de SIAM , 33 : 60–100, doi : 10.1137 / 1033004 , S2CID  18516138.
• Papadimitriou, Christos H. (1977), "El problema del viajante de comercio euclidiano es NP-completo", Theoretical Computer Science , 4 (3): 237–244, doi : 10.1016 / 0304-3975 (77) 90012-3 , MR  0455550.
• Papadimitriou, CH; Yannakakis, M. (1993), "El problema del viajante con las distancias uno y dos", Math. Oper. Res. , 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.). Manual de optimización discreta (PDF) . Amsterdam: Elsevier. págs. 1-68.
• Serdyukov, AI (1984), "Un algoritmo con una estimación para el problema del vendedor ambulante del máximo ' ", Upravlyaemye Sistemy , 25 : 80-86.
• Steinerberger, Stefan (2015), "New Bounds for the Travelling Salesman Constant", 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-Hard: una encuesta", Optimización combinatoria - ¡Eureka, usted encoge! Apuntes de conferencias en ciencias de la computación, vol. 2570 , Springer, págs. 185–207.

Lectura adicional

• Adleman, Leonard (1994), "Computación molecular de soluciones a problemas combinatorios" (PDF) , Science , 266 (5187): 1021–4, Bibcode : 1994Sci ... 266.1021A , CiteSeerX  10.1.1.54.2565 , doi : 10.1126 /science.7973651 , PMID  7973651 , archivado desde el original (PDF) el 6 de febrero de 2005
• Babin, Gilbert; Deneault, Stéphanie; Laportey, Gilbert (2005), "Mejoras en la heurística Or-opt para el problema del viajante ambulante simétrico", The Journal of the Operational Research Society , Cahiers du GERAD, Montreal: Grupo de investigación en análisis de decisiones, G-2005-02 ( 3): 402–407, CiteSeerX  10.1.1.89.9953 , JSTOR  4622707
• Cook, William (2012). En busca del vendedor ambulante: Matemáticas en los límites de la computación . Prensa de la Universidad de Princeton. ISBN 9780691152707.
• 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 9780262033848.
• 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". Las computadoras y la intratabilidad: una guía para la teoría de la completitud NP . WH Freeman. págs. 211–212. ISBN 9780716710448.
• Goldberg, DE (1989), "Algoritmos genéticos en búsqueda, optimización y aprendizaje automático", Lectura: Addison-Wesley , Nueva York: Addison-Wesley, Bibcode : 1989gaso.book ..... G , ISBN 978-0-201-15767-3
• Gutin, G .; Yeo, A .; Zverovich, A. (15 de marzo de 2002). "El vendedor ambulante no debe 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 y sus variaciones . Springer EE. UU. ISBN 9780387444598.
• Johnson, DS ; McGeoch, LA (1997), "El problema del vendedor ambulante: un estudio de caso de 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 . John Wiley & Sons, Incorporated. ISBN 9780471904137.
• MacGregor, JN; Ormerod, T. (1996), "Rendimiento humano en el problema del viajante de comercio" (PDF) , Perception & Psychophysics , 58 (4): 527–539, doi : 10.3758 / BF03213088 , PMID  8934685 , S2CID  38355042 , archivado desde el original. (PDF) el 29 de diciembre de 2009
• Medvedev, Andrei; Lee, Michael; Butavicius, Marcus; Vickers, Douglas (1 de febrero de 2001). "Actuación humana en problemas visualmente presentados del Viajero Viajero". 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 de tiempo polinomial para TSP geométricos, 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 ' ", Actas , págs. 540–550, CiteSeerX  10.1.1.51.8676
• Rosenkrantz, Daniel J .; Stearns, Richard E .; Lewis, Philip M., II (1977). "Un análisis de varias heurísticas para el problema del viajante" . Revista SIAM de Computación . SIAM (Sociedad de Matemática Industrial y Aplicada). 6 (5): 563–581. doi : 10.1137 / 0206041 . S2CID  14764079 .
• Ross, MI, Proulx, RJ, Karpenko, M. (2020). Una teoría de control óptima para el problema del viajante y sus variantes . arXiv 2005.03186 .
• Walshaw, Chris (2000), Un enfoque multinivel del problema del vendedor ambulante , CMS Press
• Walshaw, Chris (2001), Un algoritmo de varios niveles Lin-Kernighan-Helsgaun para el problema del vendedor ambulante , CMS Press

Enlaces externos

Wikimedia Commons tiene medios relacionados con el problema del vendedor ambulante .

• 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