El problema del viajante

El problema del viajante (TSP) puede modelarse como un grafo ponderado no dirigido , donde las ciudades son los vértices , los caminos son las aristas y la distancia de un camino es el peso de la arista. Se trata de un problema de minimización que comienza y termina en un vértice específico después de haber visitado cada uno de los demás vértices exactamente una vez. A menudo, el modelo es un grafo completo (es decir, cada par de vértices está conectado por una arista). Si no existe un camino entre dos ciudades, añadir una arista suficientemente larga completará el grafo sin afectar el recorrido óptimo.

En el problema del viajante simétrico (TSP simétrico) , la distancia entre dos ciudades es la misma en ambas direcciones opuestas, formando un grafo no dirigido . Esta simetría reduce a la mitad el número de soluciones posibles. En el problema del viajante asimétrico (TSP asimétrico) , puede que no existan caminos en ambas direcciones o que las distancias sean diferentes, formando un grafo dirigido . La congestión del tráfico, las calles de sentido único y las tarifas aéreas para ciudades con diferentes precios de salida y llegada son consideraciones del mundo real que podrían dar lugar a un problema del viajante en forma asimétrica.

• Una formulación equivalente en términos de teoría de grafos es: dado un grafo completo ponderado (donde los vértices representan las ciudades, las aristas las carreteras y los pesos el costo o la distancia de cada carretera), encontrar un ciclo hamiltoniano con el menor peso. Esto es más general que el problema del camino hamiltoniano , que solo pregunta si existe un camino (o ciclo) hamiltoniano en un grafo no completo y sin ponderar.
• El requisito de regresar a la ciudad de partida no cambia la complejidad computacional del problema; véase el problema del camino hamiltoniano .
• Otro problema relacionado es el problema del viajante de comercio con cuello de botella : encontrar un ciclo hamiltoniano en un grafo ponderado con el peso mínimo de la arista más pesada . Un ejemplo del mundo real es evitar calles estrechas con autobuses grandes. ^{[ 15 ]} El problema tiene una importancia práctica considerable, aparte de las evidentes áreas de transporte y logística. Un ejemplo clásico es en la fabricación de circuitos impresos : la programación de una ruta de la máquina perforadora para taladrar agujeros en una PCB. En las aplicaciones de mecanizado o perforación robótica, las "ciudades" son piezas a mecanizar o agujeros (de diferentes tamaños) a taladrar, y el "costo del viaje" incluye el tiempo para reequipar el robot (problema de secuenciación de trabajos de una sola máquina). ^{[ 16 ]}
• El problema generalizado del viajante , también conocido como el "problema del político viajero", trata sobre "estados" que tienen (una o más) "ciudades", y el vendedor debe visitar exactamente una ciudad de cada estado. Una aplicación se encuentra en la ordenación de una solución al problema de corte de materiales para minimizar los cambios de cuchillas. Otra se relaciona con la perforación en la fabricación de semiconductores ; véase, por ejemplo, la patente estadounidense 7,054,798 . Noon y Bean demostraron que el problema generalizado del viajante puede transformarse en un problema estándar del viajante con el mismo número de ciudades, pero con una matriz de distancias modificada .
• El problema del ordenamiento secuencial aborda el problema de visitar un conjunto de ciudades, donde existen relaciones de precedencia entre ellas.
• Una pregunta común en las entrevistas de trabajo en Google es cómo enrutar los datos entre los nodos de procesamiento de datos; las rutas varían en cuanto al tiempo de transferencia de datos, pero los nodos también difieren en su capacidad de procesamiento y almacenamiento, lo que complica aún más el problema de dónde enviar los datos.
• El problema del comprador viajero plantea la cuestión de un comprador que debe adquirir un conjunto de productos. Puede adquirirlos en varias ciudades, pero a precios diferentes, y no todas las ciudades ofrecen los mismos productos. El objetivo es encontrar una ruta entre un subconjunto de ciudades que minimice el coste total (coste de viaje + coste de compra) y le permita adquirir todos los productos necesarios.

Además de la${\displaystyle x_{ij}}$variables como arriba, hay para cada${\displaystyle i=1,\ldots ,n}$una variable ficticia${\displaystyle u_{i}}$que registra el orden en que se visitan las ciudades, contando desde la ciudad${\displaystyle 1}$; la interpretación es que${\displaystyle u_{i}<u_{j}}$implica ciudad${\displaystyle i}$es visitada antes de la ciudad${\displaystyle j.}$Para un recorrido determinado (como se codifica en valores de la${\displaystyle x_{ij}}$variables), se pueden encontrar valores satisfactorios para la${\displaystyle u_{i}}$variables haciendo${\displaystyle u_{i}}$igual al número de aristas a lo largo de ese recorrido, cuando se va de ciudad a ciudad${\displaystyle 1}$a la ciudad${\displaystyle i.}$^{[ 22 ]}

Debido a que la programación lineal favorece las desigualdades no estrictas (${\displaystyle \geq }$) sobre estricto (${\displaystyle >}$), nos gustaría imponer restricciones en el sentido de que

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

Simplemente requiere${\displaystyle u_{j}\geq u_{i}+x_{ij}}$no lograría eso, porque esto también requiere${\displaystyle u_{j}\geq u_{i}}$cuando${\displaystyle x_{ij}=0,}$lo cual no es correcto. En su lugar, MTZ utiliza el${\displaystyle n(n-1)}$restricciones lineales

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

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

La forma en que el${\displaystyle u_{i}}$Las variables imponen que un solo recorrido visite todas las ciudades, es decir, que aumenten al menos${\displaystyle 1}$por cada paso a lo largo de un recorrido, con una disminución permitida solo donde el recorrido pasa por la ciudad ${\displaystyle 1.}$Esa restricción sería violada por cualquier recorrido que no pase por la ciudad. ${\displaystyle 1,}$por lo que la única manera de satisfacerlo es que el tour pase por la ciudad ${\displaystyle 1}$También pasa por todas las demás ciudades.

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

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

El primer conjunto de igualdades exige que a cada ciudad se llegue desde exactamente otra ciudad, y el segundo conjunto de igualdades exige que desde cada ciudad haya una salida hacia exactamente otra ciudad. La última restricción garantiza que solo exista un único recorrido que abarque todas las ciudades, y no dos o más recorridos inconexos que, en conjunto, solo las abarquen todas.

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

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

Llevar${\displaystyle c_{ij}>0}$sea ​​la distancia de la ciudad i a la ciudad j . Entonces, el problema del viajante se puede escribir como el siguiente problema de programación lineal entera:

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

La última restricción de la formulación DFJ —denominada restricción de eliminación de subtours— garantiza que ningún subconjunto propio Q pueda formar un subtour, por lo que la solución devuelta es un único tour y no la unión de tours más pequeños. Intuitivamente, para cada subconjunto propio Q de las ciudades, la restricción exige que haya menos aristas que ciudades en Q: si hubiera tantas aristas en Q como ciudades en Q, eso representaría un subtour de las ciudades de Q. Dado que esto conlleva un número exponencial de posibles restricciones, en la práctica se resuelve mediante la generación de filas . ^{[ 23 ]}

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

Una de las primeras aplicaciones de la programación dinámica es el algoritmo de Held-Karp , que resuelve el problema en tiempo${\displaystyle O(n^{2}2^{n})}$. ^{[ 24 ]}

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

Otros enfoques incluyen:

• Diversos algoritmos de ramificación y acotación que pueden utilizarse para procesar problemas del viajante que contienen miles de ciudades.

• Algoritmos de mejora progresiva, que utilizan técnicas similares a la programación lineal . Esto funciona bien para hasta 200 ciudades.
• Implementaciones de ramificación y acotación y generación de cortes específicos del problema ( ramificación y corte ^{[ 27 ]} ); ^{[ 28 ]} este es el método de elección para resolver instancias grandes. Este enfoque tiene el récord actual, resolviendo una instancia con 85.900 ciudades, véase Applegate et al. (2006) .

En 2001 se encontró una solución exacta para 15.112 ciudades alemanas de TSPLIB utilizando el método del plano de corte propuesto por George Dantzig , Ray Fulkerson y Selmer M. Johnson en 1954, basado en programación lineal . Los cálculos se realizaron en una red de 110 procesadores ubicados en la Universidad Rice y la Universidad de Princeton . El tiempo total de cálculo fue equivalente a 22,6  años en un solo procesador Alpha de  500 MHz . En mayo de 2004, se resolvió el problema del viajante de comercio que consiste en 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. ^{[ 29 ]} En marzo de 2005, el problema del viajante de comercio de visitar los 33.810 puntos de una placa de circuito impreso se resolvió utilizando Concorde TSP Solver : se encontró un recorrido de 66.048.945 unidades y se demostró que no existe un recorrido más corto. El cálculo tardó 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 , que tardó más de 136 años de CPU; véase Applegate et al. (2006) .

Se han ideado diversas heurísticas y algoritmos de aproximación que proporcionan rápidamente buenas soluciones. Entre ellos se incluye el algoritmo multifragmento . Los métodos modernos pueden encontrar soluciones para problemas extremadamente grandes (millones de ciudades) en un tiempo razonable, con una alta probabilidad de que se encuentren a tan solo un 2-3% de la solución óptima. ^{[ 14 ]}

Se reconocen varias categorías de heurísticas.

Heurísticas constructivas

El algoritmo del vecino más cercano (NN) (un algoritmo voraz ) permite al vendedor elegir la ciudad no visitada más cercana como su siguiente movimiento. Este algoritmo produce rápidamente una ruta efectiva corta. Para N ciudades distribuidas aleatoriamente en un plano, el algoritmo produce en promedio una ruta un 25 % más larga que la ruta más corta posible; ^{[ 30 ]} sin embargo, existen muchas distribuciones de ciudades especialmente dispuestas que hacen que el algoritmo NN dé la peor ruta. ^{[ 31 ]} Esto es cierto tanto para TSP asimétricos como simétricos. ^{[ 32 ]} Rosenkrantz et al. ^{[ 33 ]} demostraron que el algoritmo NN tiene el factor de aproximación${\displaystyle \Theta (\log |V|)}$para instancias que satisfacen la desigualdad triangular. Una variación del algoritmo NN, denominada operador de fragmento más cercano (NF), que conecta un grupo (fragmento) de ciudades no visitadas más cercanas, puede encontrar rutas más cortas con iteraciones sucesivas. ^{[ 34 ]} El operador NF también puede aplicarse a una solución inicial obtenida por el algoritmo NN para una mayor mejora 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 a esos puntos como vértices; se puede calcular de manera eficiente con programación dinámica .

Otra heurística constructiva , Match Twice and Stitch (MTS), realiza dos emparejamientos secuenciales , donde el segundo se ejecuta después de eliminar todas las aristas del primero, para generar un conjunto de ciclos. Luego, los ciclos se unen para producir el recorrido final. ^{[ 35 ]}

El algoritmo de Christofides y Serdyukov

El algoritmo de Christofides y Serdyukov sigue un esquema similar, pero combina el árbol de expansión mínima con la solución de otro problema: el emparejamiento perfecto de peso mínimo . Esto proporciona un recorrido para el problema del viajante que es, como máximo, 1,5 veces más eficiente que el óptimo. Fue uno de los primeros algoritmos de aproximación y contribuyó en parte a que se prestara atención a los algoritmos de aproximación como un enfoque práctico para problemas intratables . De hecho, el término «algoritmo» no se extendió comúnmente a los algoritmos de aproximación hasta más tarde; el algoritmo de Christofides se denominó inicialmente heurística de Christofides. ^{[ 10 ]}

Este algoritmo examina las cosas de manera diferente al utilizar un resultado de la teoría de grafos que ayuda a mejorar el límite inferior del TSP que se originó al duplicar el costo del árbol de expansión mínimo. Dado un grafo euleriano , podemos encontrar un recorrido euleriano en${\displaystyle O(n)}$tiempo , ^{[ 6 ]} así que si tuviéramos un grafo euleriano con ciudades de un TSP como vértices, entonces podemos ver fácilmente que podríamos usar tal método para encontrar un recorrido euleriano para encontrar una solución TSP. Por la desigualdad triangular , sabemos que el recorrido TSP no puede ser más largo que el recorrido euleriano, y por lo tanto tenemos una cota inferior para el TSP. Dicho método se describe a continuación.

1. Encuentra un árbol de expansión mínima para el problema.
2. Crea duplicados para cada arista para crear un grafo euleriano.
3. Encuentra un recorrido euleriano para este grafo.
4. Conversión a TSP: si una ciudad se visita dos veces, entonces crea un atajo desde la ciudad anterior en el recorrido a la siguiente.

Para mejorar el límite inferior, se necesita una mejor manera de crear un grafo euleriano. Según la desigualdad triangular, el mejor grafo euleriano debe tener el mismo coste que el mejor recorrido del viajante; por lo tanto, encontrar grafos eulerianos óptimos es al menos tan difícil como el problema del viajante. Una forma de hacerlo es mediante la coincidencia de peso mínimo utilizando algoritmos con una complejidad de${\displaystyle O(n^{3})}$. ^{[ 6 ]}

La transformación de un grafo en un grafo euleriano comienza con el árbol de expansión mínima; todos los vértices de orden impar deben convertirse en pares, por lo que se debe agregar un emparejamiento para los vértices de grado impar, lo que incrementa el orden de cada vértice de grado impar en 1. ^{[ 6 ]} Esto nos deja con un grafo donde cada vértice es de orden par, que por lo tanto es euleriano. Adaptando el método anterior se obtiene el algoritmo de Christofides y Serdyukov:

1. Encuentra un árbol de expansión mínima para el problema.
2. Crea una correspondencia para el problema con el conjunto de ciudades en orden impar.
3. Encuentra un recorrido euleriano para este grafo.
4. Conviértelo a TSP usando atajos.

Intercambio por pares

La técnica de intercambio por pares o 2-opt consiste en eliminar iterativamente dos aristas y reemplazarlas por otras dos que reconectan los fragmentos resultantes para formar un recorrido nuevo y más corto. De forma similar, la técnica 3-opt elimina tres aristas y las reconecta para formar un recorrido más corto. Estos son casos particulares del método k -opt. El término Lin-Kernighan se usa erróneamente para referirse a 2-opt; en realidad, Lin-Kernighan es el método k -opt, que es más general.

Para instancias euclidianas, las heurísticas 2-opt dan en promedio soluciones que son aproximadamente un 5% mejores que las producidas por el algoritmo de Christofides. Si comenzamos con una solución inicial hecha con un algoritmo voraz , entonces el número promedio de movimientos disminuye mucho de nuevo y es ⁠${\displaystyle O(n)}$⁠ ; sin embargo, para inicios aleatorios, el número promedio de movimientos es ⁠${\displaystyle O(n\log(n))}$Aunque se trata de un pequeño aumento de tamaño, el número inicial de movimientos para problemas pequeños es 10 veces mayor con un inicio aleatorio en comparación con uno basado en una heurística voraz. Esto se debe a que dichas heurísticas 2-opt explotan las partes "malas" de una solución, como los cruces. Este tipo de heurísticas se utilizan a menudo en problemas de enrutamiento de vehículos para reoptimizar las soluciones de ruta. ^{[ 30 ]}

optimización de colonias de hormigas

En 1993, el investigador de inteligencia artificial Marco Dorigo describió 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 colonia de hormigas ). ^{[ 37 ]} Este método 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 por seguir las feromonas de rastro depositadas por otras hormigas.

ACS envía un gran número de agentes hormiga virtuales para explorar múltiples rutas posibles en el mapa. Cada hormiga elige probabilísticamente la siguiente ciudad a visitar basándose en una heurística que combina la distancia a la ciudad y la cantidad de feromona virtual depositada en el borde que la conecta con ella. Las hormigas exploran, depositando feromona en cada borde que cruzan, hasta que todas completan un recorrido. En ese momento, la hormiga que completó el recorrido más corto deposita feromona virtual a lo largo de su ruta completa ( actualización global del rastro ). La cantidad de feromona depositada es inversamente proporcional a la duración del recorrido: cuanto más corto sea el recorrido, mayor será la cantidad depositada.

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 que satisfaga la desigualdad triangular ; es decir, la conexión directa de A a B nunca está más lejos que la ruta a través de la ciudad intermedia C :

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

Los bordes, a su vez, construyen una métrica sobre el conjunto de vértices. Cuando las ciudades se consideran puntos en el plano, muchas funciones de distancia naturales son métricas, por lo que muchos casos reales del problema del viajante satisfacen esta restricción.

A continuación se muestran algunos ejemplos de problemas del viajante métricos para diversas métricas.

• En el problema del viajante euclidiano (véase más abajo), la distancia entre dos ciudades es la distancia euclidiana entre los puntos correspondientes.
• En el problema del viajante rectilíneo, la distancia entre dos ciudades es la suma de los valores absolutos de las diferencias entre sus coordenadas x e y . Esta métrica se conoce comúnmente como distancia de Manhattan o métrica de manzana.
• En la métrica máxima , la distancia entre dos puntos es el máximo de los valores absolutos de las diferencias de sus coordenadas x e y .

Las dos últimas métricas aparecen, por ejemplo, en el enrutamiento de una máquina que perfora 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, de modo 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, de modo 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 visitar dos veces una misma ciudad, pero muchas aplicaciones no necesitan esta restricción. En tales casos, una instancia simétrica no métrica puede reducirse a una métrica. Esto reemplaza el grafo original con un grafo completo en el que la distancia entre ciudades${\displaystyle d_{AB}}$se reemplaza por la longitud del camino más corto entre A y B en el gráfico original.

Para puntos en el plano euclidiano , la solución óptima del problema del viajante forma un polígono simple que pasa por todos los puntos, una poligonalización de los puntos. ^{[ 38 ]} 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 la desigualdad triangular, por lo que el TSP euclidiano forma un caso especial del TSP métrico. Sin embargo, incluso cuando los puntos de entrada tienen coordenadas enteras, sus distancias generalmente toman la forma de raíces cuadradas , y la longitud de un recorrido es una suma de radicales , lo que hace que sea difícil 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 demostrar que su versión de decisión está en NP y, por lo tanto, es NP-completa. Una versión discretizada del problema con distancias redondeadas a enteros es NP-completa. ^{[ 39 ]} Con coordenadas racionales y la métrica euclidiana real, se sabe que el TSP euclidiano está en la Jerarquía de Conteo, ^{[ 40 ]} una subclase de PSPACE . Con coordenadas reales arbitrarias, el TSP euclidiano no puede estar en tales clases, ya que hay una cantidad incontable de entradas posibles. A pesar de estas complicaciones, el TSP euclidiano es mucho más fácil que el caso de la métrica general para la aproximación. ^{[ 41 ]} Por ejemplo, el árbol de expansión mínima del grafo asociado a una instancia del TSP euclidiano es un árbol de expansión mínima euclidiana , y por lo tanto se puede calcular en un tiempo esperado de O ( n log n ) para n puntos (considerablemente menor que el número de aristas). Esto permite que el algoritmo simple de aproximación 2 para el TSP con desigualdad triangular anterior funcione más rápidamente.

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

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

tiempo; esto se denomina esquema de aproximación en tiempo polinomial (PTAS). ^{[ 42 ]} 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 sencillas con garantías más débiles.

En la mayoría de los casos, la distancia entre dos nodos en la red del problema del viajante (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 del TSP asimétrico es la optimización de rutas mediante el enrutamiento a nivel de calle (que se vuelve asimétrico debido a calles de sentido único, vías de acceso, autopistas, etc.).

El problema de la grúa apiladora puede considerarse un caso especial del problema del viajante asimétrico (TSP). En este problema, la entrada consiste en pares ordenados de puntos en un espacio métrico, que deben visitarse consecutivamente en orden durante el recorrido. Estos pares de puntos pueden verse como los nodos de un TSP asimétrico, donde las distancias asimétricas reflejan el costo combinado de viajar desde el primer punto de un par hasta el segundo, y luego desde el segundo punto de un par hasta el primer punto del siguiente par.

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

Suponer${\displaystyle X_{1},\ldots ,X_{n}}$son${\displaystyle n}$variables aleatorias independientes con distribución uniforme en el cuadrado${\displaystyle [0,1]^{2}}$y dejar${\displaystyle L_{n}^{\ast }}$sea ​​la longitud del camino más corto (es decir, la solución del TSP) para este conjunto de puntos, según la distancia euclidiana usual . Se sabe ^{[ 9 ]} que, casi con seguridad,

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

dónde${\displaystyle \beta }$es una constante positiva que no se conoce explícitamente. Dado que${\displaystyle L_{n}^{*}\leq 2{\sqrt {n}}+2}$(véase más abajo), se deduce del teorema de convergencia acotada que${\displaystyle \beta =\lim _{n\to \infty }\mathbb {E} [L_{n}^{*}]/{\sqrt {n}}}$, por lo tanto, límites inferiores y superiores en${\displaystyle \beta }$seguir desde los límites en${\displaystyle \mathbb {E} [L_{n}^{*}]}$.

El límite casi seguro${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta }$como${\displaystyle n\to \infty }$Es posible que no existan si las ubicaciones independientes${\displaystyle X_{1},\ldots ,X_{n}}$se reemplazan con observaciones de un proceso ergódico estacionario con marginales uniformes. ^{[ 44 ]}

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

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

El problema de maximización correspondiente de encontrar el recorrido más largo del viajante de comercio es aproximable dentro de 63/38. ^{[ 61 ]} Si la función de distancia es simétrica, entonces el recorrido más largo puede aproximarse dentro de 4/3 mediante un algoritmo determinista ^{[ 62 ]} y dentro de${\displaystyle (33+\varepsilon )/25}$mediante un algoritmo aleatorio . ^{[ 63 ]}