Ver el código de «Problema del viajante»

El '''problema del vendedor viajero''' ('''problema del vendedor ambulante''', '''problema del agente viajero''' o '''problema del viajante''', '''''PCP''''', '''''TSP''''' por sus siglas en inglés, Travelling Salesman Problem) responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema [[NP-hard|NP-Hard]] dentro en la [[optimización combinatoria]], muy importante en [[investigación operativa]] y en [[ciencias de la computación]].

El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, se conoce gran cantidad de [[Heurística|heurísticas]] y métodos exactos, así que es posible resolver planteamientos concretos del problema desde cien hasta miles de ciudades.

El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la [[Planeamiento|planificación]], la [[logística]] y la fabricación de [[circuitos electrónicos]]. Un poco modificado, aparece como subproblema en muchos campos como la [[secuencia de ADN|secuenciación de ADN]]. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem).

En la [[teoría de la complejidad computacional]], la versión de decisión del TSP (donde, dada una longitud “L”, el objetivo es decidir si el grafo tiene un camino menor o igual que L) pertenece a la clase de los problemas [[NP-completo|NP-completos]]. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma [[EXPTIME|exponencial]] con respecto al número de ciudades.

== Historia ==

El origen de los problemas del viajante no está claro. Una guía para viajantes de 1832 menciona el problema e incluye ejemplos de viajes a través de Alemania y Suiza, pero no contiene un tratamiento matemático del mismo.<ref>"Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (El viajante — cómo debe ser y lo que debería hacer para obtener comisiones y asegurar el feliz éxito en sus negocios — por una antigua ruta comercial)</ref>

[[Archivo:William Rowan Hamilton painting.jpg|miniatura|William Rowan Hamilton]]

El problema del viajante fue definido en los años 1800s por el matemático irlandés [[William Rowan Hamilton | W. R. Hamilton]] y por el matemático británico [[Thomas Kirkman]]. El [[Juego Icosian]] de Hamilton fue un puzle recreativo basado en encontrar un [[Problema del ciclo hamiltoniano | ciclo de Hamilton]].<ref>Una discusión del temprano trabajo de Hamilton y Kirkman puede ser encontrado en  Graph Theory 1736-1936</ref>  Todo parece indicar que la forma general del TSP fue estudiada, por primera vez por matemáticos en Viena y Harvard, durante los años 1930s. Destacándose [[Karl Menger]], quien definió los problemas, considerando el obvio algoritmo de fuerza bruta, y observando la no optimalidad de la heurística de vecinos más cercanos:
{{Quotation|
Denotamos por “Problema del Mensajero” (dado que en la práctica esta pregunta puede resolverse por cada cartero, aunque puede ser resuelta por varios viajeros) la pregunta es encontrar, para un conjunto finito de puntos de los cuales se conocen las distancias entre cada par, el camino más corto entre estos puntos. Por supuesto, el problema es resuelto por un conjunto finito de intentos. La regla que se debe seguir es que desde el punto inicial se va al punto más cercano a este, de ahí a su más cercano y así sucesivamente, en general este algoritmo no retorna la ruta más corta.<ref>Citado y traducido al Inglés en {{harvtxt|Schrijver|2005}}. Original en Alemán: "Wir bezeichnen als ''Botenproblem'' (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. 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. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."</ref>}}
[[Hassler Whitney]] de la [[Princeton University | Universidad de Princeton]]  introdujo el nombre “travelling salesman problem” poco después.<ref>Un tratamiento detallado de la conexión entre Menger y Whitney así como también el crecimiento en el estudio de TSP puede ser encontrado en [[Alexander Schrijver]]'s 2005 artículo "On the history of combinatorial optimization (till 1960). Handbook of Discrete Optimization (K. Aardal, [[George Nemhauser|G.L. Nemhauser]], R. Weismantel, eds.), Elsevier, Amsterdam, 2005, pp. 1–68.[http://homepages.cwi.nl/~lex/files/histco.ps PS],[http://homepages.cwi.nl/~lex/files/histco.pdf PDF]</ref>

Durante los años 1950 a 1960, el problema fue incrementando su popularidad entre el círculo de científicos de Europa y Estados Unidos. Una notable contribución fue la de [[George Dantzig]], [[Delbert Ray Fulkerson]]  y [[Selmer M. Johnson]] de la [[RAND | Corporación RAND]] en [[Santa Mónica (California) | Santa Mónica]], quienes expresaron el problema como [[Programación lineal | Programación Lineal en Enteros]] y desarrollaron para solucionarlo el método de [[Ramificación y poda | Planos Cortantes]]. Con este nuevo método, resolvieron una instancia con 49 ciudades, óptimamente, mediante la construcción de un recorrido y probando que no había un recorrido que pudiera ser más corto. En las siguientes décadas, el problema fue estudiado por muchos investigadores, [[Matemático | matemáticos]], [[Informático teórico  | científicos de la computación]], [[Química | químicos]], [[Físico | físicos]], etc.

[[Richard Karp | Richard M. Karp]] mostró en 1972 que el [[Problema del ciclo hamiltoniano | Problema del Ciclo de Hamilton]] era un problema [[NP-completo]], lo cual implica que el TSP sea un problema [[NP-hard | NP-duro]]. Esto tiene su explicación matemática por la evidente dificultad computacional para encontrar recorridos óptimos.

Gran progreso tuvo a finales de los 70 y principios de los 80, donde Grötschel, Padberg, Rinaldi y otros, manejaron soluciones exactas para instancias con 2392 ciudades, usando Planos Cortantes y [[Ramificación y poda | Ramificación y Acotación]].

En los 90s, Applegate, Bixby, [[Václav Chvátal | Chvátal]], y Cook desarrollaron el programa Concorde, el cual es usado en muchos de los registros de soluciones recientes. Gerhard Reinelt publicó el TSPLIB en 1991, una colección de instancias de pruebas de dificultad variable, la cual es usada por muchos grupos investigativos para comparar resultados. En 2006, Cook y otros, obtuvieron un recorrido óptimo para 85,900 ciudades dado por un problema de diseño de microchip, actualmente TSPLIB es la instancia más larga resuelta. Para otras muchas instancias con millones de ciudades, la solución puede ser encontrada garantizando que la solución contiene un 2-3% del recorrido óptimo.<ref name="rggo">{{Obra citada |título=Traveling salesman problem heuristics: leading methods, implementations and latest advances |apellidos=Rego |nombre=César |pub-periódica=European Journal of Operational Research |número=3 |volumen=211 |páginas=427–441 |apellidos2=Gamboa |nombre2=Dorabela |apellidos3=Glover |nombre3=Fred |apellidos4=Osterman |nombre4=Colin |DOI=10.1016/j.ejor.2010.09.010 |year=2011 |mr=2774420}}.</ref>

== Descripción ==

=== Caso práctico ===
En el problema se presentan N! rutas posibles, aunque se puede simplificar ya que dada una ruta nos da igual el punto de partida y esto reduce el número de rutas a examinar en un factor N quedando (N-1)!. Como no importa la dirección en que se desplace el viajante, el número de rutas a examinar se reduce nuevamente en un factor 2. Por lo tanto, hay que considerar (N-1)!/2 rutas posibles.

En la práctica, para un problema del viajante con 5 ciudades hay (5-1)!/2=12 rutas diferentes y no necesitamos un ordenador para encontrar la mejor ruta, pero apenas aumentamos el número de ciudades las posibilidades crece factorialmente:
* Para 10 ciudades hay (10-1)!/2=181.440 rutas diferentes
* Para 30 ciudades hay más de 4·10^30 rutas posibles. Un ordenador que calcule un millón de rutas por segundo necesitaría 10^17 años para resolverlo. Dicho de otra forma, si se hubiera comenzado a calcular al comienzo de la creación del universo (hace unos 13.400 millones de años) todavía no se habría terminado.

Puede comprobarse que por cada ciudad nueva que incorporemos, el número de rutas se multiplica por el factor N y crece factorialmente. Por ello el problema pertenece a la clase de problemas NP-completos.

=== Como un problema de grafos ===

[[Archivo:Weighted K4.svg|miniatura|TSP simétrico con 4 ciudades ]]
El TSP puede ser modelado como un [[Grafo | grafo ponderado no dirigido]], de manera que las ciudades sean los [[Vértice (teoría de grafos) | vértices]] del grafo, los caminos son las [[Arista (teoría de grafos) | aristas]] y las distancias de los caminos son los pesos de las aristas. Esto es un problema de minimización que comienza y termina en un vértice específico y se visita el resto de los vértices exactamente una vez. Con frecuencia, el modelo es un [[grafo completo]] (cada par de vértices es conectado por una arista). Si no existe camino entre un par de ciudades, se añade arbitrariamente una arista larga para completar el grafo sin afectar el recorrido óptimo.

=== Asimétrico y simétrico ===

En el ‘’’TSP simétrico’’’, la distancia entre un par de ciudades es la misma en cada dirección opuesta, formando un [[Grafo | grafo no dirigido]]. Este problema reduce a la mitad el número de soluciones posibles. En el ‘’’TSP asimétrico’’’, pueden no existir caminos en ambas direcciones o las distancias pueden ser diferentes, formando un [[grafo dirigido]]. Los [[Accidente de tráfico | accidentes de tráfico]], las [[ Sentido de circulación | calles de un solo sentido]] y las tarifas aéreas para ciudades con diferentes costos de partida y arribo, son ejemplos de cómo esta simetría puede ser quebrada.

=== Problemas relacionados ===

<!-- This belongs to somewhere else-->

* Una formulación equivalente en términos de [[Teoría de grafos]] es: dado una [[Grafo completo | grafo ponderado completo]] (donde los vértices representan las ciudades, las aristas representan los caminos y los pesos son el costo o las distancias de estos caminos), encontrar un [[Problema_del_ciclo_hamiltoniano| ciclo Hamiltoniano]] con menor peso.

* Las restricciones de retorno a la ciudad de comienzo no cambia la [[Teoria de la complejidad computacional | complejidad computacional]] del problema, vea [[ Problema del camino Hamiltoniano]].

* Otro problema relacionado es el Problema del viajante con cuello de botella (bottleneck TSP): Encontrar un ciclo de Hamilton en un grafo ponderado con el mínimo peso de las aristas más pesadas. El problema es de una considerable importancia en la práctica, en las áreas del transporte y la logística. Un ejemplo clásico es en la fabricación de circuitos impresos: planificando una ruta de la máquina perforadora para perforar los huecos en un PCB. Otras son, las aplicaciones de perforado o maquinado en la robótica: las “ciudades” son los huecos de diferentes tamaños a perforar y el “costo de viaje” incluye el tiempo para reequipar el robot (problema del secuenciado del trabajo de una máquina simple).<ref>{{Obra citada |título=New Efficient Transformation of the Generalized Traveling Salesman Problem into Traveling Salesman Problem |apellidos=Behzad |nombre=Arash |pub-periódica=Proceedings of the 15th International Conference of Systems Engineering (Las Vegas) |apellidos2=Modarres |nombre2=Mohammad |year=2002}}</ref>

* La generalización del TSP trata con “estados” que tienen (una o más) “ciudades” y el viajante tiene que visitar exactamente una ciudad de cada “estado”. También se conoce como el Problema del Político Viajero. Como una aplicación se considera, el perforado en la fabricación de semiconductores, vea e.g., {{US patent|7054798}}. Sorprendentemente,  Behzad y Modarres demostraron que el problema generalizado del viajante puede ser transformado en el problema del viajante estándar con el mismo número de ciudades, pero modificando la [[Matriz de distancias]]

* El problema de ordenamiento secuencial trata con el problema de visitar un conjunto de ciudades donde se tiene en cuenta las relaciones de precedencias entre las ciudades.

* El problema del viajante comprador trata con un comprador que está cargado con un conjunto de productos. Él puede comprar estos productos en varias ciudades, pero tienen diferentes precios y no todas las ciudades ofrecen los mismos productos. El objetivo es encontrar una ruta entre un subconjunto de ciudades, los cuales minimicen el costo total (costo de viaje + costo de la compra) y habilite la compra de todos los productos requeridos.

== Formulación de la programación lineal en enteros ==

El TSP puede ser formulado por la  [[Programación lineal | programación lineal en enteros]].<ref>{{Obra citada |título=Combinatorial optimization: algorithms and complexity |apellidos=Papadimitriou |nombre=C.H. |lugar=Mineola, NY |editorial=Dover |lugar-publicación=Mineola, NY |apellidos2=Steiglitz, K. |year=1998}}, pp.308-309.</ref><ref>Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)</ref><ref>Dantzig, George B. (1963), ''Linear Programming and Extensions'', Princeton, NJ: PrincetonUP, pp. 545–7, ISBN 0-691-08000-3, sixth printing, 1974.</ref> Sea <math>x_{ij}</math> igual 1, si existe el camino de ir de la ''i'' a la ciudad ''j'', y 0 en otro caso, para el conjunto de ciudades 0,..., ''n''. Sean <math>u_i</math> para ''i'' = 1,..., ''n'' variables artificiales y sea <math>c_{ij}</math> la distancia desde la ciudad ''i'' a la ciudad ''j''. Entonces el modelo de programación lineal en enteros puede ser escrito como:
: <math>
\begin{align}
\min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} & \\
0\le & x_{ij} \le 1  & i,j=0, \dots n  \\
& x_{ij} \text{ integer} & i,j=0, \dots n \\
& \sum_{i=0,i\ne j}^n x_{ij} = 1 &   j=0,\ldots,n \\
& \sum_{j=0,j\ne i}^n x_{ij} = 1 & i=0,\ldots,n \\
u_i-u_j & +nx_{ij} \le n-1 & 1 \le i \ne j \le n.
\end{align}  
</math>
El primer conjunto de igualdades asegura que cada ciudad 0,..., ''n'' de salida llegue exactamente a una ciudad, y el segundo conjunto de igualdades aseguran que desde cada ciudad 1,..., ''n'' se salga exactamente hacia una ciudad (ambas restricciones también implican que exista exactamente una salida desde la ciudad 0.) La última restricción obliga a que un solo camino cubra todas las ciudades y no dos o más caminos disjuntos cubran conjuntamente todas las ciudades. Para probar esto se muestra en (1) que toda solución factible contiene solamente una secuencia cerrada de ciudades, y en (2) que para cada uno de los recorridos que cubren todas las ciudades, hay valores para todas las variables   <math>u_i</math> que satisfacen las restricciones.

Para probar que cada solución factible contiene solamente una secuencia cerrada de ciudades, es suficiente mostrar que cada sub-ruta en una solución factible pasa a través de la ciudad 0 (note que las igualdades aseguran que solamente puede haber un recorrido de ese tipo). Por tanto, si sumamos todas las desigualdades correspondiente a <math>x_{ij}=1</math> para cada sub-ruta de k pasos que no pasan a través de la ciudad 0, obtenemos <math>nk \leq (n-1)k,</math> lo cual es una contradicción.

Ahora, mostramos que para cada recorrido que cubre todas las ciudades, hay valores de las variables <math>u_i</math> que satisfacen las restricciones.

[[Sin pérdida de generalidad]], se define el recorrido con origen y fin en la ciudad 0. Escoger <math>u_{i}=t</math> si la ciudad ''i'' es visitada en el paso ''t'' (''i'', ''t'' = 1, 2,..., n). Entonces <math>u_i-u_j\le n-1</math> dado <math>u_i</math> no puede ser mayor que ''n'' y <math>u_j</math> no puede ser menor que 1; por lo tanto las restricciones se satisfacen siempre que  <math>x_{ij}=0.</math> Para <math>x_{ij}=1,</math><math>  u_{i} - u_{j} + nx_{ij} = (t) - (t+1) + n = n-1,</math> se satisfacen las restricciones.

== Calculando una solución ==

Las líneas tradicionales para atacar un problema NP-duro son las siguientes:
* Formular algoritmos para encontrar soluciones exactas (estos trabajan más rápidos en problemas con dimensiones pequeñas).
* Formular [[Heurística | algoritmos heurísticos]] o “subóptimos” (por ejemplo: algoritmos que den aparentemente o probablemente buenas soluciones, pero no devuelven el óptimo).
* Encontrar los casos especiales para el problema (“subproblemas”) para los cuales heurísticas mejores o algoritmos exactos son posibles.

=== Complejidad Computacional ===
El problema es [[NP-completo | NP-duro]], y la versión del [[Problema de decisión]] (“dado el costo y un número x, decidir si hay una ruta de viaje más barata que x”) es [[NP-completo]]. El problema del viajante con cuello de botella es también NP-duro. El problema sigue siendo NP-duro aún para los casos donde las ciudades están en el plano con [[Distancia euclidiana | distancias Euclidianas]], al igual que en otros casos restrictivos. Eliminando la condición de visitar cada ciudad exactamente una vez no se elimina la condición de problema NP-duro, ya que se ve fácilmente que en el caso planal hay un recorrido óptimo que visita cada ciudad una sola vez (de otra manera, por [[Desigualdad triangular | desigualdades triangulares]], un atajo que se salta una visita repetida no incrementa la longitud del camino).

==== Complejidad de una aproximación ====
En el caso general, encontrar el camino más corto del viajante es NP-completo. Si la medida de distancia es una métrica y es simétrica, el problema se convierte en APX-completo<ref>{{harvtxt|Papadimitriou|1983}}</ref> y el [[Algoritmo de Christofides]] lo aproximan a 1.5.<ref>{{harvtxt|Christofides|1976}}</ref>

Si las distancias son restringidas a 1 y 2 (pero aun es una métrica) la proporción aproximada es de 8/7.<ref>{{harvtxt|Berman|Karpinski|2006}}</ref> En el caso de que sea asimétrico, es conocido solamente un rendimiento logarítmico, el mejor algoritmo actual logra una proporción de 0.814 log ''n'';<ref>{{harvtxt|Kaplan|2004}}</ref> esta es una pregunta abierta, si existe un factor constante de aproximación.

El correspondiente problema de aproximación, de encontrar el recorrido más largo del viajante es aproximable a 63/38.<ref>{{harvtxt|Kosaraju|1994}}</ref> Si la función de distancia es simétrica, el camino más largo puede aproximarse a 4/3 por una algoritmo determinista<ref>{{harvtxt|Serdyukov|1984}}</ref> y a <math>(33+\epsilon)/25</math> por un algoritmo aleatorio.<ref>{{harvtxt|Hassin|2000}}</ref>

=== Algoritmos Exactos ===
La solución más directa puede ser, intentar todas las [[Permutación | permutaciones]] (combinaciones ordenadas) y ver cuál de estas es la menor (usando una [[Búsqueda de fuerza bruta]]). El tiempo de ejecución es un factor polinómico de orden  <math>O(n!)</math>, el [[Factorial]] del número de ciudades, esta solución es impracticable para dado solamente 20 ciudades. Una de las mejores aplicaciones de la [[Programación dinámica]] es el algoritmo Held–Karp que resuelve el problema en <math>O(n^2 2^n)</math>.<ref>{{harvtxt|Bellman|1960}},{{harvtxt|Bellman|1962}},{{harvtxt|Held|Karp|1962}}</ref>
[[Archivo:Bruteforce.gif|derecha| Solución de un TSP con 7 ciudades usando algoritmo fuerza bruta. Nota: Número de permutaciones: (7-1)!/2 = 360]]

La mejora de estos límites de tiempos es difícil. Por ejemplo, no ha sido determinado si existe un algoritmo para el TSP que corra en un tiempo de orden <math>O(1.9999^n)</math><ref>{{harvtxt|Woeginger|2003}}</ref>

Otras aproximaciones incluyen:
* Varios algoritmos de [[Ramificación y poda | ramificación y acotación]], los cuales pueden ser usados para procesar TSP que contienen entre 40 y 60 ciudades.

[[Archivo:Branchbound.gif|derecha| Solución de un TSP con 7 ciudades usando un simple algoritmo de ramificación y acotación. Nota: El número de permutaciones es mucho menor que el de la búsqueda Fuerza Bruta]]

* Algoritmos de mejoras progresivas (iterativas) los cuales utilizan técnicas de [[Programación lineal]]. Trabajan bien para más de 200 ciudades.

* Implementaciones de [[Ramificación y poda | ramificación y acotación]] y un problema específico de generación de cortes ([[Ramificación y poda]]); este es el método elegido para resolver grandes instancias. Esta aproximación retiene el récord vigente, resolviendo una instancia con 85,900 ciudades, vea {{harvtxt|Applegate|Bixby|Chvátal|Cook|2006}}.

Una solución exacta para 15,112 pueblos alemanes desde TSPLIB fue encontrada en 2001 usando el método de planos cortantes propuesto por [[George Dantzig]], [[Delbert Ray Fulkerson | Ray Fulkerson]], y [[Selmer M. Johnson]] en 1954, basados en la programación lineal. Los cálculos fueron realizados por una red de 110 procesadores ubicados en la [[Universidad  Rice]] y en la [[Princeton University | Universidad de Princeton]] (vea el enlace externo Princeton). El tiempo total de cálculo fue equivalente a 22.6&nbsp; años en un [[Alpha 21064 | Procesador alpha]] de 500&nbsp;MHz. En mayo de 2004, el problema del viajante de visitar todos los 24,978 poblados en Suecia fue resuelto: un recorrido de tamaño aproximado de 72,500 kilómetros fue encontrado y se probó que no existía un camino menor.<ref>Work by David Applegate, AT&T Labs – Research, Robert Bixby, [[ILOG]] and Rice University, Vašek Chvátal, Concordia University, William Cook, University of Waterloo, and Keld Helsgaun, Roskilde University is discussed on their project web page hosted by the University of Waterloo and last updated in June 2004, here [http://www.math.uwaterloo.ca/tsp/sweden/]</ref>

En marzo de 2005, el problema del viajante de visitar todos los 33,810 puntos en una tabla de circuitos fue resuelto usando ''[[Concorde TSP Solver]]'': un recorrido de 66,048,945 unidades fue encontrado y se probó que no existía un recorrido menor. El cálculo tomo aproximadamente 15.7 años - CPU  (Cook et al. 2006). En abril de 2006, una instancia con 85,900 puntos fue resuelta usando ´´Concorde TSP Solver´´, tomando  136 años- CPU, vea {{harvtxt|Applegate|Bixby|Chvátal|Cook|2006}}.

=== Algoritmos Heurísticos y aproximados ===
Varios [[Heurística (informática) | algoritmos heurísticos]] y aproximados que retornan rápidamente buenas soluciones han sido creados. Métodos modernos pueden encontrar soluciones para problema extremadamente largos (millones de ciudades) en un tiempo razonable.<ref name="rggo" />

Varias categorías de heurísticas son reconocidas:

==== Heurísticas Constructivas ====
[[Archivo:Nearestneighbor.gif|393px|miniatura|derecha|Algoritmo del vecino más próximo para un TSP con 7 ciudades. La solución cambia cuando el punto de inicio es cambiado]]
El [[Algoritmo del vecino más próximo]] (NN por sus siglas en inglés) o también llamado algoritmo voraz (greedy) permite al viajante elegir la ciudad no visitada más cercana como próximo movimiento. Este algoritmo retorna rápidamente una ruta corta. Para N ciudades aleatoriamente distribuidas en un plano, el algoritmo en promedio, retorna un camino de un 25% más largo que el menor camino posible.<ref>Johnson, D.S. and McGeoch, L.A.. "The traveling salesman problem: A case study in local optimization",  Local search in combinatorial optimization, 1997, 215-310</ref> Sin embargo, existen muchos casos donde la distribución de las ciudades dada hace que el algoritmo NN devuelva el peor camino (Gutin, Yeo, and Zverovich, 2002). Esto es verdad lo mismo para TSP simétricos que asimétricos (Gutin and Yeo, 2007). Rosenkrantz et al. [1977] mostró que el algoritmo NN tiene un factor de aproximación de orden <math>\Theta(\log |V|)</math> para instancias que satisfacen la desigualdad triangular. Una variación del algoritmo NN, llamada operador de Fragmento más cercano (NF por sus siglas en inglés) la cual conecta un grupo (fragmento) de ciudades no visitadas más cercanas, puede encontrar la ruta más corta con iteraciones sucesivas.<ref>S. S. Ray, S. Bandyopadhyay and S. K. Pal, "Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering," Applied Intelligence, 2007, 26(3). pp. 183-195.</ref> El operador NF puede ser aplicado también, en la obtención de soluciones iniciales para el algoritmo NN para además ser mejorado en un modelo elitista, donde solamente son aceptadas las mejores soluciones.

Las construcciones basadas en un [[Árbol recubridor mínimo | árbol de expansión mínima]] (minimum [[spanning tree]]) tienen una proporción de aproximación de 2. El [[Algoritmo de Christofides]] logra una proporción de 1.5.

Match Twice and Stitch (MTS) (Kahng, Reda 2004<ref>A. B. Kahng and S. Reda, "Match Twice and Stitch: A New TSP Tour Construction Heuristic," Operations Research Letters, 2004, 32(6). pp. 499–509. http://dx.doi.org/10.1016/j.orl.2004.04.001</ref>), es otra heurística constructiva, que realiza dos comparaciones secuenciales [[Apareamiento (teoría de grafos) | (matchings)]], donde el segundo macheo es ejecutado después de eliminar todas las aristas del primer macheo, retornando un conjunto de ciclos. Los ciclos son unidos para producir el camino final.

==== Mejora Iterativa ====
;Intercambio par a par: El intercambio par a par o técnica ''2-opt'' involucra en cada iteración la eliminación de dos aristas y el reemplazo de estas con dos aristas diferentes que reconecten los fragmentos creados por la eliminación de las aristas produciendo un camino nuevo más corto. Esto es un caso especial del método k-opt. Note que, la etiqueta Lin–Kernighan es un nombre erróneo para el 2-opt muchas veces utilizado. Lin–Kernighan es realmente el método más general de k-opt.
; Heurística ''k''-opt o heurística Lin-Kernighan: Toma un recorrido dado y elimina k aristas mutuamente disjuntas. Reconecta los fragmentos conformando el recorrido, sin dejar ningún subcamino disjunto (es decir, no conectar los dos extremos de un mismo fragmento). Esto, en efecto, simplifica las consideraciones del TSP convirtiéndolo en un problema más simple. Cada extremo de un fragmento tiene 2''k''&nbsp;&minus;&nbsp;2 posibilidades de ser conectado: del total de 2''k'' extremos de fragmentos disponibles, los dos extremos del fragmento que se está considerando son descartados. Tal restricción de 2''k''- ciudades puede ser resulta con un método de fuerza bruta para encontrar el menor costo de reconectar los fragmentos originales. La técnica ''k''-opt es un caso especial del ''V''-opt o técnica Variable-opt. El método más popular del ''k''-opt es 3-opt, y fue introducido por Shen Lin de Laboratorios Bell en 1965. Este es un caso especial de 3-opt donde las aristas son no disjuntas (dos de las aristas son adyacentes a la otra). En la práctica, es a menudo posible alcanzar mejoras sustanciales sobre el 2-opt sin el costo combinatorio del 3-opt general, restringiendo el 3-changes a este subconjunto especial en el cual dos de las aristas eliminadas son adyacentes. Este es llamado el dos y medio – opt (two-and-a-half-opt), típicamente cae a mitad entre el 2-opt y el 3-opt en términos de calidad del recorrido encontrado y el tiempo para encontrarlo.
; Heurística ''V''-opt: El método variable-opt está relacionado y es una generalización del método ''k''-opt. Mientras el método ''k''-opt elimina un número fijo k de aristas del recorrido original, el método variable-opt no fija el tamaño del conjunto de aristas eliminadas. En cambio, este método aumenta el conjunto a medida que el proceso de búsqueda continúa. El mejor método conocido en esta familia es el método  Lin-Kernighan. Shen Lin y [[Brian Kernighan]] publicaron por primera vez este método en 1972, y fue la heurística más confiable para resolver el problema del viajante por aproximadamente dos décadas. Otros avances de los métodos  variable-opt fueron desarrollados en Laboratorios Bell a finales de los 80 por David Johnson y su equipo de investigación. Estos métodos (a veces llamados Lin-Kernighan-Johnson) basados en el método Lin-Kernighan añaden ideas de la [[Búsqueda tabú]] y la [[Computación evolutiva]]. La técnica básica Lin-Kernighan da resultados que garantizan al menos el 3-opt. Los métodos Lin-Kernighan-Johnson calculan un camino de Lin-Kernighan y entonces perturban el camino por lo que ha sido descrito como una mutación que elimina las últimas cuatro aristas y reconecta el camino de una forma diferente y luego se aplica v-opt al nuevo camino. La mutación es a menudo suficiente para mover el camino desde el mínimo local identificado por Lin-Kernighan. Los métodos V-opt son considerados como la heurística más ponderosa para el problema y es capaz de enfrentar casos especiales, como el Problema del Ciclo de Hamilton y otros TSP no métricos para las cuales otras heurísticas fallan. Por muchos años Lin-Kernighan-Johnson ha identificado soluciones óptimas para todos los TSP donde una solución óptima era conocida y ha identificado la mejor solución para otros TSP sobre los cuales el método ha sido aplicado.

==== Mejoras Aleatorias ====
Los algoritmos optimizados de [[Cadena de Márkov | cadenas de Márkov]] que usan heurísticas de búsquedas locales como sub-algoritmos pueden encontrar una ruta extremadamente cerca de la ruta óptima para instancias de 700 a 800 ciudades.
EL TSP es la base para muchas heurísticas diseñadas para la optimización combinatoria como: los [[Algoritmo genético | algoritmos genéticos]], el [[Algoritmo de recocido simulado | recocido simulado]], la [[Búsqueda tabú]], la [[Algoritmo de la colonia de hormigas | optimización por colonias de hormigas]], la [[Inteligencia de enjambre]], entre otras.

===== Optimización por Colonia de Hormigas =====
{{AP|Algoritmo de la colonia de hormigas}}
El investigador de [[Inteligencia artificial]],  Marco Dorigo describió en 1997 un método que genera heurísticamente “buenas soluciones” para el TSP usando una simulación de una colonia de hormigas llamada ACS (Ant Colony System).<ref>Marco Dorigo. Ant Colonies for the Traveling Salesman Problem. IRIDIA, Université Libre de Bruxelles. IEEE Transactions on Evolutionary Computation, 1(1):53–66. 1997. http://citeseer.ist.psu.edu/86357.html</ref> El cual modela el comportamiento observado en las hormigas reales de encontrar caminos cortos entre las fuentes de comida y su nido, emergió como un comportamiento la preferencia de cada hormiga de seguir el sendero de [[feromonas]] depositado por las otras hormigas.

ACS envía un gran número de hormigas (agentes virtuales) para explorar las posibles rutas en el mapa. Cada hormiga elige probabilísticamente la próxima ciudad a visitar basada en una heurística, combinando la distancia a la ciudad y la cantidad de feromonas depositadas en la arista hacia la ciudad. La hormiga exploradora, deposita feromonas en cada arista que ella cruce, hasta que complete todo el camino. En este punto la hormiga que completó el camino más corto deposita feromonas virtuales a lo largo de toda la ruta recorrida (actualización del camino global). La cantidad de feromonas depositadas es inversamente proporcional a la longitud del camino: el camino más corto, tiene más cantidad de feromonas.

[[Archivo:Aco TSP.svg|600px|centrado]]
[[Archivo:AntColony.gif|centrado| Algoritmo de optimización por Colonia de Hormigas para el TSP con 7 ciudades: Las líneas rojas y gruesas en el mapa de feromonas indican presencia de más feromonas]]

=== Casos Especiales ===

==== TSP métrico ====
En el “TSP métrico”, también conocido como ''delta-TSP'' o Δ-TSP, las distancias entre las ciudades satisfacen la [[Desigualdad triangular]].

Una restricción muy natural para el TSP es que las distancias entre las ciudades formen una [[Métrica]] que satisfagan las desigualdades triangulares; que significa que la conexión desde ''A'' hasta ''B'' no sea mayor que la ruta de “A” a “B” pasando por ''C'':
:<math>d_{AB} \le d_{AC} + d_{CB}</math>.

Las aristas se expanden y construyen una [[Métrica]] para el conjunto de vértices. Cuando las ciudades son vistas como puntos en el plano aparecen varias funciones de distancia y muchas instancias del TSP satisfacen los requerimientos de las mismas.

Los siguientes son ejemplos de TSP métricos para varias definiciones de las funciones de distancias:

* En el TSP Euclidiano la distancia entre dos ciudades es la [[Distancia euclidiana]] entre los puntos correspondientes.

* En el TSP rectilíneo la distancia entre dos ciudades es la suma de las diferencias de las coordenadas “x” e “y” respectivamente. Esta métrica es generalmente llamada [[Geometría del taxista | Distancia de Manhattan]].

* En la métrica máxima, la distancia entre dos puntos es el máximo de los valores absolutos de las diferencias de las coordenadas “x” e “y”.

Las dos últimas métricas aparecen, por ejemplo, enrutando una máquina que perfora un conjunto dado de huecos en [[Circuito impreso | circuitos impresos]] (PCB por sus siglas en inglés). La métrica Manhattan corresponde a la máquina que ajusta a una máquina que ajusta en primer lugar, la primera coordenada y luego la otra, así el tiempo de movimiento al nuevo punto es la suma de ambos movimientos. La métrica máxima corresponde a una máquina que ajusta ambas coordenadas simultáneamente, así el tiempo de moverse al nuevo punto es más despacio que los otros dos movimientos.
En esta definición, el TSP no permite visitar ciudades dos veces, pero muchas aplicaciones no necesitan esta restricción. En tales casos, una instancia simétrica, no métrica puede ser reducida a una instancia con métrica. Este remplaza el grafo original con un grafo completo en el cual las distancias entre ciudades <math>d_{AB}</math> es reemplazada por el [[Problema del camino más corto | camino más corto]] entre <math>A</math> y <math>B</math> en el grafo original.

La expansión del árbol de expansión mínima de la red <math>G</math> is a natural es un límite inferior natural para expandir la ruta óptima, porque eliminando cualquier arista de la ruta óptima, devuelve un Camino de Hamilton, el cual es un árbol de expansión en <math>G</math>. En el TSP con desigualdades triangulares es posible probar en términos de límites superiores del árbol de expansión mínima y diseñar un algoritmo que haga una verificación de los límites superiores en la expansión de la ruta. El primer ejemplo publicado (y el más simple) es el siguiente:
# Construir un [[Árbol recubridor mínimo | árbol de expansión mínima]] <math>T</math> para <math>G</math>.
# Duplicar todas las aristas de <math>T</math>. De manera que, dondequiera que haya una arista de ''u'' a ''v'', adicionar una segunda arista de ''v'' a ''u''. Devolviendo un [[Ciclo euleriano | Grafo Euleriano]]<math>H</math>.
# Encontrar un [[Ciclo euleriano | Circuito Euleriano]] <math>C</math> en <math>H</math>. Claramente, esta expansión es dos veces la expansión del árbol.

# Convertir el circuito euleriano <math>C</math> de <math>H</math> en un ciclo hamiltoniano de <math>G</math> de la siguiente manera: caminar a lo largo de <math>C</math>, y cada vez que caiga en un vértice ya visitado, salte de él y trate de ir al próximo (a lo largo de <math>C</math>).

Es fácil probar que el último paso funciona. Además, gracias a la desigualdad triangular, cada salto del paso 4 es en efecto un camino corto, por ejemplo, la longitud del ciclo no se incrementa. Por lo cual, para un recorrido del TSP este no es más largo que el doble del recorrido óptimo.

El [[Algoritmo de Christofides]] sigue un diseño similar pero combina el árbol de expansión mínima con una solución de otro problema, mínimo pero del macheo perfecto. Esto retorna un camino del TSP que es a lo sumo 1.5 veces el óptimo. El algoritmo de Christofides fue una de los primeros [[Algoritmo de aproximación | algoritmos de aproximación]], y fue en parte responsable por la imagen que se le dio a los algoritmos de aproximación como un acercamiento práctico a los problemas intratables. Como un hecho importante se tiene que, el término "algorithm" no fue comúnmente extendido a algoritmos de aproximación hasta más adelante el algoritmo Christofides fue inicialmente referido como la Heurística Christofides.

==== TSP Euclidiano ====

El  '''TSP Euclidiano''', o '''TSP planal''', es el TSP que utiliza la [[Distancia euclidiana]].

El TSP euclidiano es en particular un caso del TSP métrico, dado que las distancias en un plano cumplen la desigualdad triangular.

Como el TSP general, el TSP Euclidiano es NP-duro. El problema con métrica discretizada (distancia redondeada por exceso a un entero), es NP-completo. Sin embargo, con respecto a esto es más fácil que el TSP métrico general. Por ejemplo, el árbol de expansión mínima del grafo asociado con una instancia del TSP Euclidiano es un árbol de expansión mínima euclidiano, y puede calcularse en un tiempo de O(''n'' log ''n'') para ''n'' Sin embargo, con respecto a esto es más fácil que el TSP métrico general. Por ejemplo, el árbol de expansión mínima del grafo asociado con una instancia del TSP Euclidiano es un árbol de expansión mínima euclidiano, y puede calcularse en un tiempo de 2- aproximación simple para el TSP con desigualad triangular anterior, operar 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 polinomial que encuentra un camino de longitud a lo sumo (1 + 1/''c''), el óptimo para instancia geométricas del TSP se da en tiempo <math>O\left(n (\log n)^{(O(c \sqrt{d}))^{d-1}}\right)</math>; este es llamado un esquema de aproximación a tiempo polinomial (PTAS por sus siglas en inglés). [[Sanjeev Arora]] y Joseph S. B. Mitchell se adjudicaron el [[Premio Gödel]]  en 2010 por el descubrimiento de un PTAS para el TSP Euclidiano.
En la práctica, heurísticas con pocas garantías continúan siendo usadas.

==== TSP Asimétrico ====
En la mayoría de los casos, la distancia entre dos nodos en red del TSP es la misma en ambas direcciones. El caso donde la distancia de ''A'' a ''B'' no es igual que la distancia de ''B'' a ''A'' es llamado asimétrico. Una aplicación práctica de un TSP asimétrico es la optimización de rutas usando un enrutamiento calle-nivel (el cual es asimétrico por calles de un solo nivel, carreteras deslizantes, caminos de motos, etc.).

===== Resolver por conversión al TSP simétrico =====
Resolver un grafo del TSP asimétrico puede ser algo complicado. La siguiente es una matriz de 3×3 que contiene todos los caminos ponderados entre los nodos ''A'', ''B'' y ''C''. Una opción es cambiar una matriz asimétrica de tamaño ''N'' por una [[matriz simétrica]] de tamaño 2''N''.<ref>Roy Jonker and Ton Volgenant. "Transforming asymmetric into symmetric traveling salesman problems". ''[[Operations Research Letters]]'' '''2''':161–163, 1983. {{doi|10.1016/0167-6377(83)90048-2}}</ref>

:{| class="wikitable"
|- style="text-align:center;"
|+ Camino ponderado asimétrico

! !! ''A'' !! ''B'' !! ''C''
|- style="text-align:center;"

! ''A''
| || 1 || 2
|- style="text-align:center;"

! ''B''
| 6 || || 3
|- style="text-align:center;"

! ''C''
| 5 || 4 ||
|}

Doblar el tamaño, cada nodo en el grafo es duplicado, creando un segundo ''nodo fantasma''. Usando los nodos duplicados con pesos muy bajos, como −∞, proporciona rutas baratas con enlaces hacia atrás, al nodo real y permiten continuar la evaluación simétrica. La matriz original de 3×3 mostrada anteriormente es visible en la parte inferior izquierda y el inverso de la original en la parte superior derecha. Ambas copias de la matriz tienen sus diagonales reemplazadas por el menor costo de los caminos saltados, representados por −∞.

:{| class="wikitable"
|- style="text-align:center;" class="wikitable"
|+ Camino ponderado simétrico

! !! ''A'' !! ''B'' !! ''C'' !! ''A&prime;'' !! ''B&prime;'' !! ''C&prime;''
|- style="text-align:center;"

! ''A''
| || || || −∞ || 6 || 5
|- style="text-align:center;"

! ''B''
| || || || 1 || −∞ || 4
|- style="text-align:center;"

! ''C''
| || || || 2 || 3 || −∞
|- style="text-align:center;"

! ''A&prime;''
| −∞ || 1 || 2 || || ||
|- style="text-align:center;"

! ''B&prime;''
| 6 || −∞ || 3 || || ||
|- style="text-align:center;"

! ''C&prime;''
| 5 || 4 || −∞ || || ||
|}

La matriz original de 3×3 produce dos ciclos hamiltonianos (un camino que visita todos los nodos una vez), particularmente ''A''-''B''-''C''-''A'' [costo 9] y ''A''-''C''-''B''-''A'' [costo 12]. Evaluando la versión simétrica de 6×6, el mismo problema ahora produce más caminos, incluyendo ''A''-''A&prime;''-''B''-''B&prime;''-''C''-''C&prime;''-''A'', ''A''-''B&prime;''-''C''-''A&prime;''-''A'', ''A''-''A&prime;''-''B''-''C&prime;''-''A'' [todos los costos 9 – ∞].

Un tema importante sobre cada nueva secuencia se forma alternando los nodos (''A'', ''B'', ''C'') y sus simétricos (''A&prime;'',''B&prime;'',''C&prime;'') y el enlace para ¨saltar¨ entre cualquier par relacionado (''A''-''A&prime;'') es efectivamente libre. Una versión para el algoritmo puede usar cualquier peso para el camino ''A''-''A&prime;'', mientras que el peso sea menor que todos los otros pesos presentes en el grafo. Como el peso del camino ''A''-''A&prime;'' es libre, el valor cero puede ser usado para representar su costo, si cero no está siendo usado para otro propósito (como el de designar caminos inválidos). En los dos ejemplos anteriores, no existen caminos entre los nodos, estos son mostrados con el espacio en blanco.

=== Evaluación Comparativa ===

Para evaluar los algoritmos del TSP, [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ '''TSPLIB'''] es una librería de instancias de ejemplos del TSP y de problemas relacionados, véase la referencia externa TSPLIB. Muchos de estas instancias son listas de ciudades actuales y diseños de [[Circuito impreso | circiutos impresos]] actuales.

== Rendimiento humano en el TSP ==
El RSP, en particular la variante [[Distancia euclidiana | Euclidiana]] del problema, atrae la atención de los investigadores en [[Psicología cognitiva]]. Estos observan que los humanos son capaces de producir rápidamente buenas soluciones. El primer ejemplar del [http://docs.lib.purdue.edu/jps/ Journal of Problem Solving] es dedicado al tema del rendimiento de los humanos en el TSP.

== Longitud del camino en el TSP para conjuntos de puntos aleatorios en un cuadrado ==
Suponiendo N puntos aleatoriamente distribuidos en un cuadrado de 1×1 con ''N''>>1. Considerar muchos de estos cuadrados. Suponer que conocemos el promedio del camino más corto (por ejemplo, en la solución del TSP) de cada cuadrado.

=== Límites Inferiores ===
<math>\frac{1}{2} \sqrt{N}</math> Es un límite inferior obtenido por asumir ''i''un punto en la secuencia e ''i'' tiene como próximo vecino el último en el camino.

<math>\left({\frac{1}{4} + \frac{3}{8}}\right) \sqrt{N}</math> Es un mejor límite inferior obtenido asumiendo que el último de ''i''<nowiki>'</nowiki>s es el próximo de ''i''<nowiki>'</nowiki>s, y el antiguo ''i''<nowiki>'</nowiki>s es el que le sigue al próximo ''i''<nowiki>'</nowiki>s.

<math>\sqrt{\frac{N}{2}}</math> Es un aún mejor límite inferior obtenido dividiendo el camino en dos partes como ''antes_de_i'' y ''después_de_i'' cada parte contiene ''N''/2 puntos, y luego eliminamos ''antes_de_i'' formando un conjunto de puntos relajado.

* David S. Johnson<ref>[https://web.archive.org/web/20071025205408/http://www.research.att.com/~dsj/papers/HKsoda.pdf David S. Johnson]</ref> obtuvo un límite inferior por el cálculo del siguiente experimento:
<math>0.7080\sqrt{N}+0.522</math>, donde 0.522 proviene de los puntos del límite del cuadrado que contiene menos vecinos.

* Christine L. Valenzuela and Antonia J. Jones<ref>[http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf Christine L. Valenzuela and Antonia J. Jones] {{Wayback|url=http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf |date=20071025205411 }}</ref> obtuvieron otro límite inferior con el siguiente experimento
<math>0.7078\sqrt{N}+0.551</math>

== TSP de Analyst ==

Este es un problema análogo en la teoría de las medidas geométricas la cual presenta la siguiente interrogante: ¿Bajo qué condiciones puede un subconjunto ''E'' del espacio Euclidiano contener en una curva rectificable (esto es, cuando una curva con longitud finita visita todos los puntos en “E”)? Este problema es conocido como TSP de analyst (analyst's travelling salesman problem) o TSP geométrico.

== Software libres para resolver el TSP ==
{| class="wikitable"
|-
!Nombre<br>
!Licencia
!Lenguaje API
!Breve información
|-
|[http://www.math.uwaterloo.ca/tsp/concorde.html Concorde]|| Libre (académico)||solamente ejecutable|| Require instalar un solucionador lineal para el subproblemas MILP.
|-
|[https://web.archive.org/web/20131206185300/http://www.andrew.cmu.edu/user/neils/tsp/ DynOpt]||?||C|| Una solución aproximada de la implementación en ANSI C de un algoritmo basado en la programación dinámica desarrollado por Balas y Simonetti.
|-
|[http://www.akira.ruc.dk/~keld/research/LKH/ LKH] ||solamente investigativa|| C || Una efectiva implementación de la heurística Lin-Kernighan para TSP Euclidianos.
|-
|[[OpenOpt]] ||[[BSD]]|| Python || Soluciones exactas y aproximadas, STSP / ATSP, pueden manejar multigrafos, restricciones, problemas multiobjetivos.
|-
|[http://tsp.r-forge.r-project.org/ R TSP package]||[[GPL]]||[[R (programming language)|R]]|| Infraestructura y soluciones para STSP / ATSP, interface de Concorde
|-
|[http://tspsg.info/ TSP Solver and Generator] ||[[GPL]]|| C++ || Algoritmo de ramificación y acotación
|-
|[https://web.archive.org/web/20131217224715/http://www.rz.uni-karlsruhe.de/~lh71/ TSPGA]||?||C|| Solución aproximada del STSP usando el paquete "pgapack"
|}

== Cultura popular ==

* ''Travelling Salesman'', película del 2012 dirigida por Timothy Lanzone, es una historia de cuatro matemáticos contratados por el gobierno estadounidense para resolver el más difícil problema en la historia de la ciencia de la computación: [[Clases de complejidad P y NP|P versus NP]].<ref>{{Cita web |url=http://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman |título='Travelling Salesman' movie considers the repercussions if P equals NP |fechaacceso=26 de abril de 2012 |apellido=Geere |nombre=Duncan |editorial=Wired |fechaarchivo=14 de mayo de 2016 |urlarchivo=https://web.archive.org/web/20160514041511/http://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman |deadurl=yes }}</ref>

== Véase también ==

* [[Problema del cartero chino]]
* [[Problema de los puentes de Königsberg]]
* [[Problema de transporte]]
* [[Movilidad de último kilómetro]]

== Referencias ==
{{Listaref|2}}

== Notas ==
* {{Obra citada |título=The Traveling Salesman Problem |apellidos=Applegate |nombre=D. L. |apellidos2=Bixby |nombre2=R. M. |apellidos3=Chvátal |nombre3=V. |apellidos4=Cook |nombre4=W. J. |enlaceautor4=William J. Cook |ISBN=0-691-12993-2 |year=2006}}.
* {{Obra citada |título=Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems |apellidos=Arora |nombre=Sanjeev |enlaceautor=Sanjeev Arora |pub-periódica=[[Journal of the ACM]] |número=5 |volumen=45 |páginas=753–782 |DOI=10.1145/290179.290180 |year=1998 |mr=1668147}}.
* {{Obra citada |título=Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10, |apellidos=Bellman |nombre=R. |editorial=American Mathematical Society |capítulo=Combinatorial Processes and Dynamic Programming |páginas=217–249 |editor=Bellman, R., Hall, M., Jr. (eds.) |year=1960}}.
* {{Obra citada |título=Dynamic Programming Treatment of the Travelling Salesman Problem |apellidos=Bellman |nombre=R. |pub-periódica=J. Assoc. Comput. Mach. |volumen=9 |páginas=61–63 |DOI=10.1145/321105.321111 |year=1962}}.
* {{Obra citada |título=Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA '06) |apellidos=Berman |nombre=Piotr |capítulo=8/7-approximation algorithm for (1,2)-TSP |páginas=641–648 |apellidos2=Karpinski |nombre2=Marek |enlaceautor2=Marek Karpinski |ISBN=0898716055 |DOI=10.1145/1109557.1109627 |year=2006}}.
* {{Obra citada |título=Worst-case analysis of a new heuristic for the travelling salesman problem |apellidos=Christofides |nombre=N. |editorial=Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh |serie=Technical Report 388 |year=1976}}.
* {{Obra citada |título=Better approximations for max TSP |apellidos=Hassin |nombre=R. |pub-periódica=Information Processing Letters |número=4 |volumen=75 |páginas=181–186 |apellidos2=Rubinstein |nombre2=S. |DOI=10.1016/S0020-0190(00)00097-1 |year=2000}}.
* {{Obra citada |título=A Dynamic Programming Approach to Sequencing Problems |apellidos=Held |nombre=M. |enlaceautor=Michael Held |pub-periódica=Journal of the Society for Industrial and Applied Mathematics |número=1 |volumen=10 |páginas=196–210 |apellidos2=Karp |nombre2=R. M. |enlaceautor2=Richard Karp |DOI=10.1137/0110015 |year=1962}}.
* {{Obra citada |título=In Proc. 44th IEEE Symp. on Foundations of Comput. Sci |apellidos=Kaplan |nombre=H. |capítulo=Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs |páginas=56–65 |apellidos2=Lewenstein |nombre2=L. |apellidos3=Shafrir |nombre3=N. |apellidos4=Sviridenko |nombre4=M. |year=2004}}.
* {{Obra citada |título=Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci |apellidos=Kosaraju |nombre=S. R. |editorial=IEEE Computer Society |capítulo=Long tours and short superstrings' |páginas=166–177 |apellidos2=Park |nombre2=J. K. |apellidos3=Stein |nombre3=C. |year=1994}}.
* {{Obra citada |título=On approximation preserving reductions: Complete problems and robust measures' |apellidos=Orponen |nombre=P. |pub-periódica=Technical Report C-1987–28, Department of Computer Science, University of Helsinki |apellidos2=Mannila |nombre2=H. |enlaceautor2=Heikki Mannila |year=1987}}.
* {{Obra citada |título=The Euclidean traveling salesman problem is NP-complete |apellidos=Papadimitriou |nombre=Christos H. |enlaceautor=Christos Papadimitriou |pub-periódica=Theoretical Computer Science |número=3 |volumen=4 |páginas=237–244 |DOI=10.1016/0304-3975(77)90012-3 |year=1977 |mr=0455550}}.
* {{Obra citada |título=The traveling salesman problem with distances one and two |apellidos=Papadimitriou |nombre=C. H. |pub-periódica=Math. Oper. Res. |volumen=18 |páginas=1–11 |apellidos2=Yannakakis |nombre2=M. |DOI=10.1287/moor.18.1.1 |year=1993}}.
* {{Obra citada |título=An algorithm with an estimate for the traveling salesman problem of the maximum' |apellidos=Serdyukov |nombre=A. I. |pub-periódica=Upravlyaemye Sistemy |volumen=25 |páginas=80–86 |year=1984}}.
* {{Obra citada |título=Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570 |apellidos=Woeginger |nombre=G.J. |editorial=Springer |capítulo=Exact Algorithms for NP-Hard Problems: A Survey |páginas=185–207 |year=2003}}.

== Bibliografía ==
* {{Obra citada |título=Molecular Computation of Solutions To Combinatorial Problems |apellidos=Adleman |nombre=Leonard |enlaceautor=Leonard Adleman |url=http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf |fechaacceso=17 de diciembre de 2013 |pub-periódica=Science |número=5187 |volumen=266 |páginas=1021–4 |PMID=7973651 |bibcode=1994Sci...266.1021A |DOI=10.1126/science.7973651 |year=1994 |archiveurl=https://web.archive.org/web/20050206144827/http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf |archivedate=6 de febrero de 2005}}
* {{Obra citada |título=Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems |apellidos=Arora |nombre=S. |enlaceautor=Sanjeev Arora |url=http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arora-tsp.pdf |pub-periódica=Journal of the ACM |número=5 |volumen=45 |páginas=753–782 |DOI=10.1145/290179.290180 |year=1998}}.
* {{Obra citada |título=Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem |apellidos=Babin |nombre=Gilbert |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.9953 |lugar=Montreal |editorial=Group for Research in Decision Analysis |lugar-publicación=Montreal |serie=Cahiers du GERAD |volumen=G-2005-02 |apellidos2=Deneault |nombre2=Stéphanie |apellidos3=Laportey |nombre3=Gilbert |year=2005}}.
* {{Obra citada |título=In Pursuit of the Travelling Salesman: Mathematics at the Limits of Computation |apellidos=Cook |nombre=William |enlaceautor=William J. Cook |editorial=[[Princeton University Press]] |ISBN=978-0-691-15270-7 |year=2011}}.
* {{Obra citada |título=Computing with domino-parity inequalities for the TSP |apellidos=Cook |nombre=William |enlaceautor=William J. Cook |pub-periódica=INFORMS Journal on Computing |número=3 |volumen=19 |páginas=356–365 |apellidos2=Espinoza |nombre2=Daniel |apellidos3=Goycoolea |nombre3=Marcos |DOI=10.1287/ijoc.1060.0204 |year=2007}}.
* {{Obra citada |título=[[Introduction to Algorithms]] |apellidos=Cormen |nombre=T. H. |enlaceautor=Thomas H. Cormen |edición=2nd |editorial=[[MIT Press]] and McGraw-Hill |capítulo=35.2: The traveling-salesman problem |páginas=1027–1033 |apellidos2=Leiserson |nombre2=C. E. |apellidos3=Rivest |nombre3=R. L. |apellidos4=Stein |nombre4=C. |enlaceautor2=Charles E. Leiserson |enlaceautor3=Ronald L. Rivest |enlaceautor4=Clifford Stein |ISBN=0-262-03293-7 |year=2001}}.
* {{Obra citada |título=Solution of a large-scale traveling salesman problem |apellidos=Dantzig |nombre=G. B. |enlaceautor=George Dantzig |pub-periódica=Operations Research |número=4 |volumen=2 |páginas=393–410 |apellidos2=Fulkerson |nombre2=R. |apellidos3=Johnson |nombre3=S. M. |enlaceautor2=D. R. Fulkerson |enlaceautor3=Selmer M. Johnson |DOI=10.1287/opre.2.4.393 |year=1954 |jstor=166695}}.
* {{Obra citada |título=Computers and Intractability: A Guide to the Theory of NP-Completeness |apellidos=Garey |nombre=M. R. |enlaceautor=Michael R. Garey |url=https://archive.org/details/computersintract0000gare/page/211 |editorial=W.H. Freeman |capítulo=A2.3: ND22–24 |páginas=[https://archive.org/details/computersintract0000gare/page/211 211–212] |apellidos2=Johnson |nombre2=D. S. |enlaceautor2=David S. Johnson |ISBN=0-7167-1045-5 |year=1979}}.
* {{Obra citada |título=Genetic Algorithms in Search, Optimization & Machine Learning |apellidos=Goldberg |nombre=D. E. |lugar=New York |editorial=Addison-Wesley |lugar-publicación=New York |pub-periódica=Reading: Addison-Wesley |ISBN=0-201-15767-5 |bibcode=1989gaso.book.....G |year=1989}}.
* {{Obra citada |título=Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP |apellidos=Gutin |nombre=G. |pub-periódica=Discrete Applied Mathematics |número=1–3 |volumen=117 |páginas=81–86 |apellidos2=Yeo |nombre2=A. |apellidos3=Zverovich |nombre3=A. |DOI=10.1016/S0166-218X(01)00195-0 |year=2002}}.
* {{Obra citada |título=The Traveling Salesman Problem and Its Variations |apellidos=Gutin |nombre=G. |editorial=Springer |apellidos2=Punnen |nombre2=A. P. |ISBN=0-387-44459-9 |year=2006}}.
* {{Obra citada |título=Local Search in Combinatorial Optimisation |apellidos=Johnson |nombre=D. S. |enlaceautor=David S. Johnson |editorial=John Wiley and Sons Ltd |capítulo=The Traveling Salesman Problem: A Case Study in Local Optimization |páginas=215–310 |apellidos2=McGeoch |nombre2=L. A. |editor=Aarts |nombre-editor=E. H. L. |enlace-editor2=Jan Karel Lenstra |year=1997 |editor2-first=J. K. |editor2-last=Lenstra}}.
* {{Obra citada |título=The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization |apellidos=Lawler |nombre=E. L. |enlaceautor=Eugene Lawler |url=https://archive.org/details/travelingsalesma00lawl |editorial=John Wiley & Sons |apellidos2=Lenstra |nombre2=J. K. |apellidos3=Rinnooy Kan |nombre3=A. H. G. |apellidos4=Shmoys |nombre4=D. B. |enlaceautor2=Jan Karel Lenstra |ISBN=0-471-90413-9 |year=1985}}.
* {{Obra citada |título=Human performance on the traveling salesman problem |apellidos=MacGregor |nombre=J. N. |url=http://www.psych.lancs.ac.uk/people/uploads/TomOrmerod20030716T112601.pdf |fechaacceso=17 de diciembre de 2013 |pub-periódica=Perception & Psychophysics |número=4 |volumen=58 |páginas=527–539 |apellidos2=Ormerod |nombre2=T. |DOI=10.3758/BF03213088 |urlarchivo=https://web.archive.org/web/20091229053516/http://www.psych.lancs.ac.uk/people/uploads/TomOrmerod20030716T112601.pdf |fechaarchivo=29 de diciembre de 2009 |year=1996}}.
* {{Obra citada |título=Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, ''k''-MST, and related problems |apellidos=Mitchell |nombre=J. S. B. |enlaceautor=Joseph S. B. Mitchell |url=http://citeseer.ist.psu.edu/622594.html |pub-periódica=SIAM Journal on Computing |número=4 |volumen=28 |páginas=1298–1309 |DOI=10.1137/S0097539796309764 |year=1999}}.
* {{Obra citada |título=[[Symposium on Theory of Computing|Proc. 30th Annual ACM Symposium on Theory of Computing]] |apellidos=Rao |nombre=S. |capítulo=Approximating geometrical graphs via 'spanners' and 'banyans' |páginas=540–550 |apellidos2=Smith |nombre2=W. |year=1998}}.
* {{Obra citada |título=An Analysis of Several Heuristics for the Traveling Salesman Problem |apellidos=Rosenkrantz |nombre=Daniel J. |pub-periódica=SIAM Journal on Computing |número=5 |volumen=6 |páginas=563–581 |apellidos2=Stearns |nombre2=Richard E. |apellidos3=Lewis |nombre3=Philip M., II |DOI=10.1137/0206041 |year=1977}}.
* {{Obra citada |título=Human performance on visually presented traveling salesman problems |apellidos=Vickers |nombre=D. |pub-periódica=Psychological Research |número=1 |volumen=65 |páginas=34–45 |apellidos2=Butavicius |nombre2=M. |apellidos3=Lee |nombre3=M. |apellidos4=Medvedev |nombre4=A. |PMID=11505612 |DOI=10.1007/s004260000031 |year=2001}}.
* {{Obra citada |título=A Multilevel Approach to the Travelling Salesman Problem |apellidos=Walshaw |nombre=Chris |editorial=CMS Press |year=2000}}.
* {{Obra citada |título=A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem |apellidos=Walshaw |nombre=Chris |editorial=CMS Press |year=2001}}.

== Enlaces externos ==
{{Commons category|Traveling salesman problem}}
* [http://www.gestiondeoperaciones.net/programacion-entera/solucion-del-problema-del-vendedor-viajero/ Solución al Problema del Vendedor Viajero]
=== En inglés ===
* [http://www.math.uwaterloo.ca/tsp/index.html Traveling Salesman Problem] en la [[Universidad de Waterloo]]
* [http://theory.cs.uni-bonn.de/info5/tsp/ Approximation Taxonomy of Metric TSP] en la [[Universidad de Bonn]]
* [https://web.archive.org/web/20170325123309/http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ TSPLIB] en la [[Universidad de Heidelberg]]
* ''[http://demonstrations.wolfram.com/TravelingSalesmanProblem/ Traveling Salesman Problem]'' by Jon McLoone at the Wolfram Demonstrations Project
* [http://www.adaptivebox.net/CILib/code/tspcodes_link.html Source code library for the travelling salesman problem]
* [http://tsp.r-forge.r-project.org/ TSP solvers in R] for symmetric and asymmetric TSPs. Implements various insertion, nearest neighbor and 2-opt heuristics and an interface to Concorde and Chained Lin-Kernighan heuristics.
* {{IMDb título|1801123}}
* "[http://www.ibm.com/developerworks/cloud/library/cl-optimizepythoncloud1/index.html Traveling Salesman in Python and Linear Optimization, IBM Developerworks with Source Code]" by Noah Gift

{{Control de autoridades}}
{{DEFAULTSORT:Travelling Salesman Problem}}
[[Categoría:Algoritmos de grafos]]
[[Categoría:Investigación operativa]]
[[Categoría:Problemas computacionales de teoría de grafos]]
[[Categoría:Problemas NP-completos]]
[[Categoría:Ciclos de Hamilton]]
[[Categoría:Combinatoria]]
[[Categoría:Problemas de matemática recreativa]]
[[Categoría:Optimización combinatoria]]
[[Categoría:Problema del viajante| ]]
[[Categoría:Problemas NP-difíciles]]