Problema del vendedor ambulante

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

NP-hard problema en optimización combinatoria

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

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

El problema del comprador ambulante y el problema de generación de rutas para vehículos son generalizaciones de TSP.

En la teoría de la complejidad computacional, la versión de decisión del TSP (donde dada una longitud L, la tarea es decidir si el gráfico tiene un recorrido de como mucho L i>) pertenece a la clase de problemas NP-completos. Por lo tanto, es posible que el tiempo de ejecución del 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 intensamente 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 pueden resolverse completamente e incluso problemas con millones de ciudades pueden aproximarse dentro de una pequeña fracción del 1%.

El TSP tiene varias aplicaciones incluso en su formulación más pura, como la planificación, la logística y la fabricación de microchips. Ligeramente modificado, aparece como un subproblema en muchas áreas, como la secuenciación del ADN. En estas aplicaciones, el concepto ciudad representa, por ejemplo, clientes, puntos de soldadura o fragmentos de ADN, y el concepto distancia representa tiempos o costos de viaje, o una medida de similitud entre fragmentos de ADN. El TSP también aparece en astronomía, ya que los astrónomos que observan muchas fuentes 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 de comercio no están claros. Un manual para vendedores ambulantes de 1832 menciona el problema e incluye recorridos de ejemplo por Alemania y Suiza, pero no contiene un tratamiento matemático.

William Rowan Hamilton

El TSP fue formulado matemáticamente en el siglo XIX por el matemático irlandés William Rowan Hamilton y por el matemático británico Thomas Kirkman. El juego icosiano de Hamilton era un rompecabezas recreativo basado en encontrar un ciclo hamiltoniano. 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, especialmente por Karl Menger, quien define el problema, considera el algoritmo de fuerza bruta obvio y observa la falta de optimización de la más cercana. heurística del vecino:

Denotamos problema de mensajeros (ya que en la práctica esta pregunta debe ser resuelta por cada cartero, de todos modos también por muchos viajeros) la tarea de encontrar, para finitamente muchos puntos cuyas distancias pares son conocidas, la ruta más corta que conecta los puntos. Por supuesto, este problema es solucionable por muchas pruebas finitas. No se conocen las reglas que empujarían el número de juicios por debajo del número de permutaciones de los puntos dados. La regla que primero debe ir desde el punto de partida hasta el punto más cercano, luego al punto más cercano a esto, etc., en general no produce la ruta más corta.

Se consideró matemáticamente por primera vez en la década de 1930 por Merrill M. Flood, que buscaba resolver un problema de enrutamiento de autobuses escolares. 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 RAND Corporation de 1949 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 RAND Corporation 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 de manera óptima mediante la construcción de un recorrido y demostrando que ningún otro recorrido podría ser más corto. Dantzig, Fulkerson y Johnson, sin embargo, especularon que, dada una solución casi óptima, podemos encontrar la optimización o probar la optimización agregando una pequeña cantidad de desigualdades adicionales (cortes). Usaron esta idea para resolver su problema inicial de 49 ciudades usando un modelo de cuerdas. Descubrieron que solo necesitaban 26 cortes para llegar a una solución para su problema de 49 ciudades. Si bien este documento no proporcionó un enfoque algorítmico para los problemas de TSP, las ideas contenidas en él fueron indispensables para crear posteriormente métodos de solución exactos para el TSP, aunque llevaría 15 años 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 ramificación y acotación quizás por primera vez.

En 1959, Jillian Beardwood, J.H. 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 lugares 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 probablemente esté 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 usarían luego con enfoques de ramificación y límite. 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, de forma independiente, hicieron un gran avance en esta dirección: el algoritmo de Christofides-Serdyukov produce una solución que, en el peor de los casos, es como mucho 1,5 veces más larga que la solución óptima. Como el algoritmo era simple y rápido, muchos esperaban que daría paso a un método de solución casi óptimo. Sin embargo, esta esperanza de mejora no se materializó de inmediato, y Christofides-Serdyukov siguió siendo el método con el 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 "gráfico".; TSP. En 2020, esta pequeña mejora se extendió al TSP (métrico) completo.

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

Se lograron grandes avances a fines de la década de 1970 y 1980, cuando Grötschel, Padberg, Rinaldi y otros lograron resolver instancias de forma exacta con hasta 2392 ciudades, utilizando planos de corte y bifurcación y límite.

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 instancias de referencia de diversa dificultad, que ha sido utilizada por muchos grupos de investigación para comparar resultados. En 2006, Cook y otros calcularon un recorrido óptimo a través de una instancia de 85 900 ciudades dada por un problema de diseño de microchip, actualmente la instancia TSPLIB más grande resuelta. Para muchos otros casos con millones de ciudades, se pueden encontrar soluciones que garantizan estar dentro del 2-3 % de un recorrido óptimo.

Descripción

Como un problema gráfico

TSP simétrico con cuatro ciudades

TSP se puede modelar como un gráfico ponderado no dirigido, de modo que las ciudades sean los vértices del gráfico, las rutas sean los bordes del gráfico y la distancia de una ruta sea el borde. peso. Es un problema de minimización que comienza y termina en un vértice específico después de haber visitado cada vértice exactamente una vez. A menudo, el modelo es un gráfico completo (es decir, cada par de vértices está conectado por una arista). Si no existe un camino entre dos ciudades, agregar un borde lo suficientemente largo completará el gráfico sin afectar el recorrido óptimo.

Asimétrica y simétrica

En el TSP simétrico, la distancia entre dos ciudades es la misma en cada dirección opuesta, formando un gráfico no dirigido. Esta simetría reduce a la mitad el número de soluciones posibles. En el TSP asimétrico, los caminos 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 podría romperse esta simetría.

Problemas relacionados

Una formulación equivalente en términos de teoría del gráfico es: Dado un gráfico ponderado completo (donde los vértices representarían las ciudades, los bordes representarían las carreteras, y los pesos serían el costo o la distancia de ese camino), encontrar un ciclo Hamiltoniano con el menor peso.
El requisito de volver a la ciudad inicial no cambia la complejidad computacional del problema, véase el problema de la ruta Hamiltoniana.
Otro problema relacionado es el problema del vendedor de viajes de cuello de botella (bottleneck TSP): Encuentra un ciclo Hamiltoniano en un gráfico ponderado 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, aparte de las zonas de transporte y logística evidentes. Un ejemplo clásico es en la fabricación de circuito impreso: programación de una ruta de la máquina de perforación para perforar agujeros en un PCB. En aplicaciones de mecanizado o perforación robóticas, las "ciudades" son partes en la máquina o agujeros (de diferentes tamaños) para perforar, y el "costo de viaje" incluye tiempo para retocar el robot (problema de secuenciación de trabajo de máquina única).
El problema generalizado de los vendedores ambulantes, también conocido como el "problema político itinerante", trata de "estados" que tienen (uno o más) "ciudades" y el vendedor tiene que visitar exactamente una "ciudad" de cada "estado". Una aplicación se encuentra en el orden de una solución al problema del corte de stock para minimizar los cambios del cuchillo. Otro está preocupado por la perforación en la fabricación de semiconductores, véase, por ejemplo, U.S. Patent 7,054,798. El mediodía y Bean demostraron que el problema generalizado del vendedor puede transformarse en un TSP estándar con el mismo número de ciudades, pero una matriz de distancia modificada.
El problema de orden secuencial se refiere al problema de visitar un conjunto de ciudades donde existen relaciones de precedencia entre las ciudades.
Una pregunta de entrevista común en Google es cómo tratar los datos entre los nodos de procesamiento de datos; las rutas varían a tiempo para transferir los datos, pero los nodos también difieren por su poder de cálculo y almacenamiento, agravando el problema de dónde enviar datos.
El problema del comprador itinerante se ocupa de un comprador encargado de comprar un conjunto de productos. Puede comprar 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 las ciudades que minimiza el costo total (costo de viaje + costo de compra) y permite la compra de todos los productos requeridos.

Formulaciones de programación lineal entera

El TSP se puede formular como un programa lineal entero. Se conocen varias formulaciones. Dos formulaciones notables son la formulación Miller-Tucker-Zemlin (MTZ) y la formulación Dantzig-Fulkerson-Johnson (DFJ). La formulación DFJ es más fuerte, aunque la formulación MTZ sigue siendo útil en ciertos entornos.

Común para ambas formulaciones es que una etiqueta las ciudades con los números $1,ldotsn$ y tomas $0}" xmlns="http://www.w3.org/1998/Math/MathML">cij■0{displaystyle c_{ij}0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d2d754e494ca2548ccbf2dc5613444c9d28d6039" style="vertical-align: -1.005ex; width:6.745ex; height:2.843ex;"/>$ ser la distancia de la ciudad $i$ a la ciudad $j$ . Las principales variables en las formulaciones son:

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

Es porque estas son variables 0/1 que las formulaciones se convierten en programas enteros; todas las demás restricciones son puramente lineales. En particular, el objetivo del programa es

minimizar la longitud del tour

{displaystyle sum _{i=1}^{n}sum _{jneq i,j=1}^{n}c_{ij}x_{ij}}

Sin más limitaciones, ${displaystyle {x_{ij}}_{i,j}}$ sin embargo, variando efectivamente sobre todos los subconjuntos del conjunto de bordes, que está muy lejos de los conjuntos de bordes en un recorrido, y permite un mínimo trivial donde todo ${displaystyle x_{ij}=0}$ . Por lo tanto, ambas formulaciones también tienen las limitaciones que hay en cada vértice es exactamente un borde entrante y un borde saliente, que puede ser expresado como el $2n$ ecuaciones lineales

{displaystyle sum _{i=1,ineq j}^{n}x_{ij}=1}

para

{displaystyle j=1,ldotsn}

{displaystyle sum _{j=1,jneq i}^{n}x_{ij}=1}

para

{displaystyle i=1,ldotsn}

Estos aseguran que el conjunto de aristas elegido localmente se parece al de un recorrido, pero aún permiten soluciones que violan el requisito global de que hay un recorrido que visita todos los vértices, ya que los aristas elegidos podrían componer varios recorridos cada uno visitando solo un subconjunto de los vértices; Podría decirse que es este requisito global lo que hace que TSP sea un problema difícil. Las formulaciones MTZ y DFJ difieren en cómo expresan este requisito final como restricciones lineales.

Fórmula Miller-Tucker-Zemlin

Además de la $x_{{ij}}$ variables como arriba, hay para cada ${displaystyle i=2,ldotsn}$ a dummy variable $u_{i}$ que hace un seguimiento del orden en el que se visitan las ciudades, contando desde la ciudad $1$ ; la interpretación es que $<math alttext="{displaystyle u_{i}ui.uj{displaystyle ¿Qué?<img alt="{displaystyle u_{i}$ implica ciudad $i$ se visita antes de la ciudad $j$ . Para un recorrido dado (como codificado en valores del $x_{{ij}}$ variables), se puede encontrar valores satisfactorios para las variables $u_{i}$ variables haciendo $u_{i}$ igual al número de bordes a lo largo de esa gira, cuando va de la ciudad $1$ a la ciudad $i$ .

Porque la programación lineal favorece las desigualdades no restrictivas ( $ge$ ) sobre estricto ( $}" xmlns="http://www.w3.org/1998/Math/MathML">■{displaystyle } " aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1b27b77ab4e3293ea9ce65cef60fea655c398423" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;"/>$ ), nos gustaría imponer restricciones al efecto de que

{displaystyle u_{j}geq u_{i}+1}

{displaystyle x_{ij}=1}

Merely requiring ${displaystyle u_{j}geq u_{i}+x_{ij}}$ lo haría. no lograrlo, porque esto también requiere ${displaystyle u_{j}geq u_{i}}$ cuando ${displaystyle x_{ij}=0}$ , que no es correcto. En lugar de MTZ utilizar el ${displaystyle (n-1)(n-2)}$ limitaciones lineales

{displaystyle u_{j}+(n-2)geq u_{i}+(n-1)x_{ij}}

para todos

{displaystyle i,jin {2,dotscn}}

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

El camino $u_{i}$ variables entonces imponen que una sola visita a todas las ciudades es que aumentan por (al menos) $1$ para cada paso a lo largo de un recorrido, con una disminución sólo permitido donde el recorrido pasa por la ciudad $1$ . Esa restricción sería violada por cada tour que no pasa por la ciudad $1$ , por lo que la única manera de satisfacerlo es que la ciudad que pasa $1$ también pasa por todas las otras ciudades.

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

{displaystyle {begin{aligned}min sum _{i=1}^{n}sum _{jneq i,j=1}^{n}c_{ij}x_{ij}&colon &&\x_{ij}in {}&{0,1}&&i,j=1,ldotsn;\u_{i}in {}&mathbf {Z} &&i=2,ldotsn;\sum _{i=1,ineq j}^{n}x_{ij}={}&1&&j=1,ldotsn;\sum _{j=1,jneq i}^{n}x_{ij}={}&1&&i=1,ldotsn;\u_{i}-u_{j}+(n-1)x_{ij}leq {}&n-2&&2leq ineq jleq n;\1leq u_{i}leq {}&n-1&&2leq ileq n.end{aligned}}}

El primer conjunto de igualdades requiere que cada ciudad sea llegada de exactamente una ciudad, y el segundo conjunto de igualdades requiere que de cada ciudad hay una salida a exactamente otra ciudad. Las últimas restricciones imponen que sólo hay un solo recorrido por todas las ciudades, y no dos o más viajes desvinculados que sólo cubren colectivamente todas las ciudades. Para probar esto, se muestra a continuación (1) que cada solución factible contiene sólo una secuencia cerrada de ciudades, y (2) que para cada tour que cubre todas las ciudades, hay valores para las variables muñecos $u_{i}$ que satisfacen las limitaciones.

Para probar que cada solución factible contiene sólo una secuencia cerrada de ciudades, basta demostrar que cada subtorno en una solución factible pasa por la ciudad 1 (sintiendo que las igualdades aseguran que sólo puede haber una de tales giras). Porque si sumamos todas las desigualdades correspondientes a $x_{ij}=1$ para cualquier subtorno k pasos que no pasan por la ciudad 1, obtenemos:

{displaystyle (n-1)kleq (n-2)k,}

lo cual es una contradicción.

Ahora debe demostrarse que para cada tour que cubre todas las ciudades, hay valores para las variables muñecas $u_{i}$ que satisfacen las limitaciones.

Sin pérdida de generalidad, definir el tour como originario (y final) en la ciudad 1. Elija $u_{i}=t$ si la ciudad $i$ se visita en el paso ${displaystyle t(i,t=2,3,ldotsn)}$ . Entonces...

{displaystyle u_{i}-u_{j}leq n-2,}

desde entonces $u_{i}$ no puede ser mayor que $n$ y $u_{j}$ no puede ser menos de 2; por lo tanto, las limitaciones están satisfechas cada vez que $x_{ij}=0.$ Para $x_{ij}=1$ , tenemos:

{displaystyle u_{i}-u_{j}+(n-1)x_{ij}=(t)-(t+1)+n-1=n-2,}

satisfaciendo la restricción.

Formulación de Dantzig-Fulkerson-Johnson

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

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

Toma. $0}" xmlns="http://www.w3.org/1998/Math/MathML">cij■0{displaystyle c_{ij}0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d2d754e494ca2548ccbf2dc5613444c9d28d6039" style="vertical-align: -1.005ex; width:6.745ex; height:2.843ex;"/>$ ser la distancia de la ciudad i a la ciudad j. Luego TSP se puede escribir como el siguiente problema de programación lineal entero:

{displaystyle {begin{aligned}min &sum _{i=1}^{n}sum _{jneq i,j=1}^{n}c_{ij}x_{ij}colon &&\&sum _{i=1,ineq j}^{n}x_{ij}=1&&j=1,ldotsn;\&sum _{j=1,jneq i}^{n}x_{ij}=1&&i=1,ldotsn;\&sum _{iin Q}{sum _{jneq i,jin Q}{x_{ij}}}leq |Q|-1&&forall Qsubsetneq {1,ldotsn},|Q|geq 2\end{aligned}}}

La última restricción de la formulación DFJ, llamada restricción de eliminación del subtour, garantiza que ningún subconjunto Q adecuado pueda formar un subtour, por lo que la solución devuelta es un tour único y no la unión de recorridos más pequeños. Excursiones. Debido a que esto conduce a un número exponencial de posibles restricciones, en la práctica se resuelve con la generación de filas.

Calcular una solución

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

Desarrollando algoritmos exactos, que funcionan razonablemente rápido sólo para pequeños tamaños de problemas.
Devising "suboptimal" o algoritmos heurísticos, es decir, algoritmos que ofrecen soluciones aproximadas en un tiempo razonable.
Encontrar casos especiales para el problema ("subproblemas") para los cuales es posible una heurística mejor o exacta.

Algoritmos exactos

La solución más directa sería probar todas las permutaciones (combinaciones ordenadas) y ver cuál es más barata (usando búsqueda de fuerza bruta). El tiempo de ejecución para este enfoque se encuentra dentro de un factor polinomio $O(n!)$ , el factorial del número de ciudades, por lo que esta solución se vuelve poco práctica incluso para sólo 20 ciudades.

Una de las primeras aplicaciones de la programación dinámica es el algoritmo Held-Karp que resuelve el problema a tiempo $O(n^{2}2^{n})$ . Este límite también ha sido alcanzado por Exclusión-Inclusión en un intento previo al enfoque dinámico de programación.

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

Mejorar estos plazos parece ser difícil. Por ejemplo, no se ha determinado si un algoritmo clásico exacto para TSP que funciona en el tiempo $O(1.9999^{n})$ existe. El algoritmo actual quantum exacto para TSP debido a Ambainis et al. se ejecuta en el tiempo ${displaystyle O(1.728^{n})}$ .

Otros enfoques incluyen:

Diversos algoritmos ram-and-bound, que se pueden utilizar para procesar TSP que contienen 40–60 ciudades.

Solución de un TSP con 7 ciudades usando un simple Rama y algoritmo atado. 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 la programación lineal. Funciona bien para hasta 200 ciudades.
Implementaciones de la generación de cortes de ramas y límites y problemas específicos (branch-and-cut); este es el método de elección para resolver casos grandes. Este enfoque tiene el registro 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 la programación lineal. Los cálculos se realizaron en una red de 110 procesadores ubicados en la Universidad de 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, se resolvió el problema del viajante de visitar los 33.810 puntos de una placa de circuito 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 años de CPU (Cook et al. 2006). En abril de 2006, se resolvió una instancia con 85 900 puntos utilizando Concorde TSP Solver, lo que ocupó más de 136 años de CPU, consulte Applegate et al. (2006).

Algoritmos heurísticos y de aproximación

Se han ideado varias heurísticas y algoritmos de aproximación que rápidamente arrojan buenas soluciones. Estos incluyen el algoritmo de fragmentos múltiples. Los métodos modernos pueden encontrar soluciones para problemas extremadamente grandes (millones de ciudades) dentro de un tiempo razonable que, con una alta probabilidad, se encuentran a solo un 2 o 3 % de distancia de la solución óptima.

Se reconocen varias categorías de heurísticas.

Heurísticas constructivas

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

El algoritmo vecino más cercano (NN) (un algoritmo codicioso) permite al vendedor elegir la ciudad invisible más cercana como su próximo movimiento. Este algoritmo produce rápidamente una ruta corta eficaz. Para las ciudades N distribuidas aleatoriamente en un plano, el algoritmo en promedio produce un camino 25% más largo que el camino más corto posible. Sin embargo, existen muchas distribuciones de ciudades especialmente arregladas que hacen que el algoritmo NN dé la peor ruta. Esto es cierto tanto para los TSP asimétricos como simétricos. Rosenkrantz et al. mostró que el algoritmo NN tiene el factor de aproximación $Theta (log |V|)$ para casos que satisfagan la desigualdad del triángulo. Una variación del algoritmo NN, llamado fragmento más cercano (NF) operador, que conecta un grupo (fragmento) de ciudades no visibles más cercanas, puede encontrar rutas más cortas con itinerarios sucesivos. El operador de NF también se puede aplicar en una solución inicial obtenida por algoritmo NN para mejorar aún más un modelo elitista, donde sólo 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 coincidencias secuenciales, donde la segunda coincidencia se ejecuta después de eliminar todos los bordes de la primera coincidencia, para generar un conjunto de ciclos. Luego, los ciclos se unen para producir el recorrido final.

El Algoritmo de Christofides y Serdyukov

Crear una coincidencia

Usando un atajo heurístico en el gráfico creado por la coincidencia anterior

El algoritmo de Christofides y Serdyukov sigue un esquema similar, pero combina el árbol de expansión mínima con una solución de otro problema, la coincidencia perfecta de peso mínimo. Esto da un recorrido TSP que es como máximo 1,5 veces el óptimo. Fue uno de los primeros algoritmos de aproximación y fue en parte responsable de llamar la atención sobre los algoritmos de aproximación como un enfoque práctico para problemas intratables. De hecho, el término "algoritmo" no se extendió comúnmente a los algoritmos de aproximación hasta más tarde; el algoritmo de Christofides se denominó inicialmente como la heurística de Christofides.

Este algoritmo mira las cosas de manera diferente mediante el uso de un resultado de la teoría del gráfico que ayuda a mejorar en el límite inferior de la TSP que se originó de duplicar el costo del árbol mínimo de azotes. Dado un gráfico eulerio podemos encontrar un tour eulerio $O(n)$ tiempo. Así que si teníamos un gráfico Eulerian con ciudades de un TSP como vértices, entonces podemos ver fácilmente que podríamos utilizar tal método para encontrar un tour Eulerian para encontrar una solución TSP. Por desigualdad triangular sabemos que la gira TSP ya no puede ser más que la gira Euleria y como tal tenemos un límite inferior para la TSP. Este método se describe a continuación.

Encontrar un árbol mínimo para el problema
Crear duplicados para cada borde para crear un gráfico eulerio
Encuentra un recorrido por Eulerian para este gráfico
Convertir en TSP: si una ciudad es visitada dos veces, crear un atajo de la ciudad antes de esto en el tour a uno después de esto.

Para mejorar el límite inferior se necesita una mejor manera de crear un gráfico eulerio. Por desigualdad triangular, el mejor gráfico Eulerian debe tener el mismo costo que el mejor tour de vendedores ambulantes, por lo que encontrar gráficos Eulerian óptimos es al menos tan duro como TSP. Una forma de hacer esto es por peso mínimo que coincide con algoritmos de $O(n^{3})$ .

Convertir 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 ser pares. Entonces, se debe agregar una coincidencia para los vértices de grado impar que aumenta el orden de cada vértice de grado impar en uno. Esto nos deja con un gráfico donde cada vértice es de orden par, por lo que es euleriano. La adaptación del método anterior da el algoritmo de Christofides y Serdyukov.

Encontrar un árbol mínimo para el problema
Cree una coincidencia para el problema con el conjunto de ciudades de orden extraño.
Encuentra un recorrido por Eulerian para este gráfico
Convertir a TSP usando atajos.

Intercambio por parejas

Un ejemplo de una iteración de 2 puntos

La técnica de intercambio por pares o 2-opt consiste en eliminar iterativamente 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. De manera similar, la técnica de 3 opciones elimina 3 bordes y los vuelve a conectar para formar un recorrido más corto. Estos son casos especiales del método k-opt. La etiqueta Lin–Kernighan es un nombre inapropiado que se escucha a menudo para 2-opt. Lin-Kernighan es en realidad el método k-opt más general.

Para las instancias euclidianas, las heurísticas de 2 puntos dan soluciones medias que son alrededor del 5% mejores que el algoritmo de Christofides. Si empezamos con una solución inicial hecha con un algoritmo codicioso, el número promedio de movimientos disminuye mucho de nuevo y es $O(n)$ . Para el azar comienza sin embargo, el número promedio de movimientos es ${displaystyle O(nlog(n))}$ . Sin embargo, mientras que para esto es un pequeño aumento de tamaño, el número inicial de movimientos para pequeños problemas es 10 veces más grande para un comienzo aleatorio en comparación con uno hecho de una heurística avaricia. Esto se debe a que tales heurísticas de 2 puntos explotan partes 'bad' de una solución como cruces. Estos tipos de heurística se utilizan a menudo dentro del problema de enrutamiento del vehículo heurísticas para reoptimizar las soluciones de ruta.

Heurística K-opt, o heurística 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:

Dado un tour, eliminar k se descomponen mutuamente.
Reensambla los fragmentos restantes en un recorrido, sin dejar subtours descomunados (es decir, no conectes los puntos finales de un fragmento juntos). Esto en efecto simplifica el TSP que se está considerando en un problema mucho más simple.
Cada punto final de fragmento se puede conectar a $2 k - 2$ otras posibilidades: de 2k total fragment endpoints available, the two endpoints of the fragment under consideration are disallowed. Tal limitación 2k- la ciudad TSP se puede resolver con métodos de fuerza bruta para encontrar la recombinación de menor costo de los fragmentos originales.

El más popular de los métodos k-opt es 3-opt, tal como lo introdujo Shen Lin de Bell Labs en 1965. Un caso especial de 3-opt es donde los bordes no están disjuntos (dos de los bordes son adyacentes entre sí). En la práctica, a menudo es posible lograr una mejora sustancial sobre 2-opt sin el costo combinatorio del 3-opt general restringiendo los 3-cambios a este subconjunto especial donde dos de los bordes eliminados son adyacentes. Esta llamada opción de dos opciones y media generalmente se encuentra aproximadamente a mitad de camino entre la opción de dos opciones y la opción de tres opciones, tanto en términos de la calidad de los recorridos logrados como del tiempo requerido para lograr esos recorridos.

Heurística V-opt

(feminine)

El método variable-opt está relacionado y es una generalización del método k-opt. 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 para 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. 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 y agregan ideas de la búsqueda tabú y la computación evolutiva. La técnica básica de Lin-Kernighan brinda resultados garantizados de al menos 3 opciones. Los métodos Lin-Kernighan-Johnson calculan un recorrido Lin-Kernighan y luego perturban el recorrido mediante lo que se ha descrito como una mutación que elimina al menos cuatro bordes y vuelve a conectar el recorrido de una manera diferente, luego V-optar por el nuevo tour. La mutación suele ser suficiente para mover el recorrido desde el mínimo local identificado por Lin-Kernighan. Los métodos V-opt se consideran ampliamente las heurísticas más poderosas para el problema y pueden abordar casos especiales, como el problema del ciclo de Hamilton y otros TSP no métricos en los que fallan otras heurísticas. Durante muchos años, Lin-Kernighan-Johnson había identificado soluciones óptimas para todos los TSP en los que se conocía una solución óptima y había identificado las soluciones más conocidas para todos los demás TSP en los que se había probado el método.

Mejora aleatoria

Los algoritmos de cadena de Markov optimizados que utilizan subalgoritmos heurísticos de búsqueda local pueden encontrar una ruta extremadamente cercana a la ruta óptima para 700 u 800 ciudades.

TSP es una piedra de toque para muchas heurísticas generales diseñadas para la optimización combinatoria, como algoritmos genéticos, recocido simulado, búsqueda tabú, optimización de colonias de hormigas, dinámica de formación de ríos (ver inteligencia de enjambre) y el método de entropía cruzada.

Heurística de inserción restrictiva

Comience con un sub-recorrido como el casco convexo, inserte otros vértices.

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" al TSP usando 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 de manera probabilística la siguiente ciudad para visitar en función de una heurística que combina la distancia a la ciudad y la cantidad de feromona virtual depositada en el borde de la ciudad. Las hormigas exploran depositando 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 la colonia de hormigas para un TSP con 7 ciudades: Líneas rojas y gruesas en el mapa de feromonas indican presencia de más feromonas

Casos especiales

Métrico

En el TSP métrico, también conocido como delta-TSP o Δ-TSP, las distancias entre ciudades satisfacen la desigualdad triangular.

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

d_{AB}leq d_{AC}+d_{CB}

Los tramos de borde luego crean una métrica en el conjunto de vértices. Cuando las ciudades se ven como puntos en el plano, muchas funciones de distancia natural son métricas y muchas instancias naturales de TSP satisfacen esta restricción.

Los siguientes son algunos ejemplos de TSP de métricas para varias métricas.

En el TSP Euclidean (ver abajo) la distancia entre dos ciudades es la distancia Euclidea entre los puntos correspondientes.
En el TSP rectilineal la distancia entre dos ciudades es la suma de los valores absolutos de las diferencias de sus x- y Sí.- coordinación. Esta métrica se llama a menudo la distancia de Manhattan o la métrica de bloqueo urbano.
En la métrica máxima, la distancia entre dos puntos es el máximo de los valores absolutos de las diferencias de sus x- y Sí.- coordinación.

Las dos últimas métricas aparecen, por ejemplo, en el enrutamiento de una máquina que taladra un conjunto determinado de orificios 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 pasar a un nuevo punto es el más lento de los dos movimientos.

En su definición, el TSP no permite que las ciudades sean visitadas dos veces, pero muchas aplicaciones no necesitan esta limitación. En tales casos, una instancia simétrica no métrica puede reducirse a una métrica. Esto reemplaza el gráfico original con un gráfico completo en el que la distancia interurbana $d_{AB}$ es reemplazado por la longitud más corta del camino entre A y B en el gráfico original.

Euclidiana

(feminine)

Para los puntos en el plano euclidiano, la solución óptima al problema del vendedor ambulante forma un polígono simple a través de todos los puntos, una poligonalización de los puntos. Cualquier solución no óptima con cruces puede convertirse en una solución más corta sin cruces mediante optimizaciones locales. La distancia euclidiana obedece a la desigualdad del triángulo, por lo que la TSP euclidiana forma un caso especial de la TSP métrica. Sin embargo, incluso cuando los puntos de entrada tienen coordenadas enteras, sus distancias generalmente toman la forma de raíces cuadradas, y la longitud de un recorrido es una suma de radicales, lo que dificulta realizar el cálculo simbólico necesario para realizar comparaciones exactas de las longitudes de diferentes recorridos.

Al igual que el TSP general, el TSP euclidiano exacto es NP-difícil, pero el problema con las sumas de radicales es un obstáculo para probar que su versión de decisión está en NP y, por lo tanto, NP-completo. Una versión discretizada del problema con distancias redondeadas a números enteros es NP-completo. Con coordenadas racionales y la métrica euclidiana real, se sabe que el TSP euclidiano está 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. A pesar de estas complicaciones, el TSP euclidiano es mucho más fácil que el caso métrico general para la aproximación. Por ejemplo, el árbol de expansión mínimo del grafo asociado con una instancia del TSP euclidiano es un árbol de expansión mínimo euclidiano y, por lo tanto, se puede calcular en O esperado (n log n) tiempo para n puntos (considerablemente menos que el número de aristas). Esto permite que el algoritmo simple de 2 aproximaciones para TSP con la desigualdad triangular anterior funcione más rápidamente.

En general, para cualquier c > 0, donde d es el número de dimensiones en el espacio euclidiano, hay 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

Oleft(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 S. B. 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étrica

En la mayoría de los casos, la distancia entre dos nodos en la red TSP es la misma en ambas direcciones. El caso en que la distancia de A a B no es igual a la distancia de B a A se denomina asimétrico TSP. Una aplicación práctica de un TSP asimétrico es la optimización de rutas mediante el enrutamiento a nivel de calle (que se hace asimétrico mediante calles de sentido único, vías de acceso, autopistas, etc.).

Conversión a simétrica

(feminine)

Resolver un gráfico TSP asimétrico puede ser algo complejo. La siguiente es una matriz de 3×3 que contiene todos los pesos de ruta posibles entre los nodos A, B y C. Una opción es convertir una matriz asimétrica de tamaño N en una matriz simétrica de tamaño 2N.

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 del gráfico se duplica, creando un segundo nodo fantasma, vinculado al nodo original con un "fantasma" borde de peso muy bajo (posiblemente negativo), aquí denotado −w. (Alternativamente, los bordes fantasma tienen peso 0, y el peso w se agrega a todos los demás bordes). La matriz original de 3 × 3 que se muestra arriba es visible en la parte inferior izquierda y la transposición del original en la parte superior derecha. Se han reemplazado las diagonales de ambas copias de la matriz por 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 fantasma.

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 "fantasmas" que unen los nodos fantasmas a los nodos originales correspondientes debe ser lo suficientemente bajo para asegurar que todos los bordes fantasma deben pertenecer a cualquier solución TSP simétrica óptima en el nuevo gráfico (w=0 no siempre es lo suficientemente bajo). Como consecuencia, en el recorrido simétrico óptimo, cada nodo original aparece junto a su nodo fantasma (por ejemplo, un camino posible es ${displaystyle mathrm {Ato A'to Cto C'to Bto B'to A} }$ ) y al fusionar los nodos originales y fantasma de nuevo obtenemos una solución (optimal) del problema asimétrico original (en nuestro ejemplo, ${displaystyle mathrm {Ato Cto Bto A} }$ ).

Problema de la analista

(feminine)

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

Longitud de ruta para conjuntos aleatorios de puntos en un cuadrado

Suppose $X_{1},ldotsX_{n}$ son $n$ variables aleatorias independientes con distribución uniforme en la plaza $[0,1]^{2}$ , y dejar $L_{n}^{ast }$ ser la longitud más corta del camino (es decir, solución TSP) para este conjunto de puntos, de acuerdo con la distancia Euclideana habitual. Se sabe que, casi seguro,

{frac {L_{n}^{*}}{sqrt {n}}}rightarrow beta qquad {text{when }}nto infty

Donde $beta$ es una constante positiva que no se conoce explícitamente. Desde $L_{n}^{*}leq 2{sqrt {n}}+2$ (ver abajo), se deriva del teorema de convergencia atado que $beta =lim _{nto infty }mathbb {E} [L_{n}^{*}]/{sqrt {n}}$ , por lo tanto los límites inferiores y superiores en $beta$ seguimiento de los límites en $mathbb {E} [L_{n}^{*}]$ .

El límite casi seguro ${displaystyle {frac {L_{n}^{*}}{sqrt {n}}}rightarrow beta }$ como $nto infty$ tal vez no exista si los emplazamientos independientes $X_{1},ldotsX_{n}$ son reemplazados por observaciones de un proceso ergodic estacionario con marginales uniformes.

Límite superior

Uno tiene $L^{*}leq 2{sqrt {n}}+2$ , y por consiguiente $beta leq 2$ , utilizando un camino ingenuo que visita monotonicamente los puntos dentro de cada uno de ${sqrt {n}}$ rebanadas de ancho $1/{sqrt {n}}$ en la plaza.
Pocos probadas $L_{n}^{*}leq {sqrt {2n}}+1.75$ , por lo tanto $beta leq {sqrt {2}}$ , más tarde mejorada por Karloff (1987): $beta leq 0.984{sqrt {2}}$ .
Fietcher mostró un límite superior de ${displaystyle beta leq 0.73dots }$ .

Límite inferior

Al observar que $mathbb {E} [L_{n}^{*}]$ es mayor que $n$ tiempos la distancia entre $X_{0}$ y el punto más cercano $X_{i}neq X_{0}$ , se obtiene (después de una breve computación)

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

Se obtiene un límite más bajo observando que $mathbb {E} [L_{n}^{*}]$ es mayor que ${tfrac {1}{2}}n$ tiempos la suma de las distancias entre $X_{0}$ y los puntos más cercanos y segundo más cercanos $X_{i},X_{j}neq X_{0}$ , que da

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

El límite más bajo actual es

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

Held y Karp dieron un algoritmo de tiempo polinomio que proporciona límites inferiores numéricos para $L_{n}^{*}$ , y así $beta (simeq L_{n}^{*}/{sqrt {n}})$ que parece ser bueno hasta más o menos 1%. En particular, David S. Johnson obtuvo un menor límite por experimento de computadora:

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

donde 0.522 proviene de los puntos cercanos al límite cuadrado que tienen menos vecinos, y Christine L. Valenzuela y Antonia J. Jones obtuvieron el siguiente límite inferior numérico:

L_{n}^{*}gtrsim 0.7078{sqrt {n}}+0.551

Complejidad computacional

Se ha demostrado que el problema es NP-difícil (más precisamente, es completo para la clase de complejidad FP^NP; ver problema de función), y la versión del problema de decisión ("dada los costos y un número x, deciden si hay una ruta de ida y vuelta más barata que x") es NP-completo. El problema del viajante de comercio de cuello de botella 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 otros casos restrictivos. Eliminando la condición de visitar cada ciudad "solo una vez" no elimina la dureza NP, ya que en el caso planar hay un recorrido óptimo que visita cada ciudad una sola vez (de lo contrario, por la desigualdad del triángulo, un atajo que salta una visita repetida no aumentaría la duración del recorrido).

Complejidad de aproximación

En el caso general, encontrar el recorrido más corto del viajante de comercio 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.

Si las distancias se restringen a 1 y 2 (pero todavía son métricas) la relación de aproximación se convierte en 8/7. En el caso asimétrico con desigualdad triángulo, hasta hace poco sólo se conocían las garantías de rendimiento logarítmico. En 2018, la aproximación de factores constantes fue desarrollada por Svensson, Tarnawski y Végh. El mejor algoritmo actual, por Traub y Vygen, logra una relación de rendimiento ${displaystyle 22+varepsilon }$ . El límite de inaplicabilidad más conocido es 75/74.

El problema de maximización correspondiente de encontrar el más larga Tour de vendedor de viaje es aproximable en 63/38. Si la función de distancia es simétrica, el recorrido más largo puede ser aproximado dentro de 4/3 por un algoritmo determinista y dentro ${tfrac {1}{25}}(33+varepsilon)$ por un algoritmo aleatorizado.

Rendimiento humano y animal

El TSP, en particular la variante euclidiana del problema, ha atraído la atención de los investigadores en psicología cognitiva. Se ha observado que los humanos son capaces de producir soluciones casi óptimas rápidamente, de forma casi lineal, con un rendimiento que va desde un 1 % menos eficiente, para gráficos con 10-20 nodos, hasta 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 cruce. Sin embargo, evidencia adicional sugiere que el desempeño humano es bastante variado y que 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 llevado 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" llamado así por el libro infantil Don't Let the Pigeon Drive the Bus!, examinó la cognición espacial en palomas al estudiar sus patrones de vuelo entre múltiples comederos en un laboratorio en relación con el viaje problema del vendedor En el primer experimento, las palomas se colocaron en la esquina de una sala de laboratorio y se les permitió volar a los comederos cercanos que contenían guisantes. Los investigadores descubrieron 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 ineficiente si las palomas necesitaran visitar cada comedero. Los resultados del segundo experimento indican que las palomas, si bien siguen favoreciendo las soluciones basadas en la proximidad, "pueden planificar varios pasos adelante a lo largo de la ruta cuando las diferencias en los costos de viaje entre las rutas eficientes y menos eficientes basadas en la proximidad se hacen mayores". 34; 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.

Cálculo natural

Cuando se le presenta una configuración espacial de fuentes de alimento, el ameboide Physarum polycephalum adapta su morfología para crear un camino eficiente entre las fuentes de alimento que también puede verse como una solución aproximada al TSP.

Puntos de referencia

Para la evaluación comparativa de los algoritmos TSP, TSPLIB es una biblioteca de instancias de muestra del TSP y se mantienen 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, por el director Timothy Lanzone, es la historia de cuatro matemáticos contratados por el gobierno de Estados Unidos para resolver el problema más difícil en la historia de la ciencia informática: P vs. NP. Las soluciones al problema son utilizadas por el matemático Bob Bosche en un subgenre llamado arte TSP.

Contenido relacionado

Más resultados...