¿Cuál es la historia del problema del viajante de comercio a lo largo de los años en una breve lista con viñetas?
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 ejemplos de recorridos por Alemania y Suiza, pero no contiene ningún tratamiento matemático[2].


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[3] La forma general del TSP parece haber sido estudiada por primera vez por matemáticos durante la década de 1930 en Viena y en Harvard, en particular por Karl Menger, que define el problema, considera el algoritmo obvio de fuerza bruta y observa la no optimalidad de la heurística del vecino más próximo:

Denotamos problema del mensajero (ya que en la práctica esta cuestión debería resolverla cada cartero, de todos modos también muchos viajeros) a la tarea de encontrar, para un número finito de puntos cuyas distancias entre pares sean conocidas, la ruta más corta que conecte los puntos. Por supuesto, este problema puede resolverse mediante un número finito de intentos. No se conocen las reglas que harían que el número de pruebas fuera inferior al número de permutaciones de los puntos dados. La regla según la cual primero hay que ir del punto de partida al punto más cercano, luego al punto más cercano a éste, etc., en general no da el camino más corto[4].

Fue considerado matemáticamente por primera vez en la década de 1930 por Merrill M. Flood, que buscaba resolver un problema de rutas de autobuses escolares[5] Hassler Whitney, de la Universidad de Princeton, generó interés por el problema, al que llamó "problema de los 48 estados". La primera publicación en la que se utilizó la expresión "problema del viajante de comercio" fue el informe de 1949 de la Corporación RAND, redactado por Julia Robinson, "Sobre el juego hamiltoniano (un problema del viajante de comercio)"[6][7].

En las décadas de 1950 y 1960, el problema se hizo cada vez más popular en los círculos científicos de Europa y Estados Unidos, después de que la Corporación RAND de Santa Mónica ofreciera premios por los pasos dados en la resolución del problema[5]. Contribuyeron notablemente George Dantzig, Delbert Ray Fulkerson y Selmer M. Johnson, de la Corporación RAND, que 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 fundamental sobre el tema, en el que, con estos nuevos métodos, resolvieron una instancia con 49 ciudades hasta la optimalidad construyendo un recorrido y demostrando que ningún otro recorrido podía ser más corto. Sin embargo, Dantzig, Fulkerson y Johnson especularon con que, dada una solución casi óptima, podríamos encontrar la optimalidad o demostrar la optimalidad añadiendo un pequeño número de desigualdades adicionales (cortes). Utilizaron esta idea para resolver su problema inicial de 49 ciudades utilizando un modelo de cadenas. Descubrieron que sólo necesitaban 26 cortes para llegar a la solución de su problema de 49 ciudades. Aunque este artículo no ofrecía un enfoque algorítmico de los problemas del TSP, las ideas que contenía fueron indispensables para crear posteriormente métodos de solución exacta para el TSP, aunque se tardaría 15 años en encontrar un enfoque algorítmico para crear estos cortes[5]. Además de los métodos de planos de corte, Dantzig, Fulkerson y Johnson utilizaron algoritmos de bifurcación y delimitación quizá por primera vez[5].

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[8]. El teorema 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 parte de una casa u oficina y visita un número fijo de lugares antes de volver al punto de partida.

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 los años 60, sin embargo, se creó un nuevo enfoque que, en lugar de buscar soluciones óptimas, produciría una solución cuya longitud estuviera limitada de forma demostrable por un múltiplo de la longitud óptima, y al hacerlo crearía límites inferiores para el problema; estos límites inferiores se utilizarían después con enfoques de bifurcación y delimitación. Un método para hacerlo consistía en crear un árbol de expansión mínima del grafo y luego duplicar todas sus aristas, 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ínima[5].

En 1976, Christofides y Serdyukov, independientemente el uno del otro, hicieron un gran avance en este sentido:[9] el algoritmo Christofides-Serdyukov da una solución que, en el peor de los casos, es como máximo 1,5 veces más larga que la solución óptima. Como el algoritmo era sencillo y rápido, muchos esperaban que diera paso a un método de solución casi óptima. Sin embargo, esta esperanza de mejora no se materializó inmediatamente, y Christofides-Serdyukov siguió siendo el método con la mejor solución en el peor de los casos hasta 2011, cuando se desarrolló un algoritmo de aproximación (muy) ligeramente mejorado para el subconjunto de TSP "gráficos"[10]. En 2020, esta diminuta mejora se extendió al TSP completo (métrico)[11][12].

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

Se hicieron grandes progresos a finales de los años 70 y en 1980, cuando Grötschel, Padberg, Rinaldi y otros consiguieron resolver exactamente instancias con hasta 2.392 ciudades, utilizando planos de corte y branch and bound.

En la década de 1990, Applegate, Bixby, Chvátal y Cook desarrollaron el programa Concorde, que se ha utilizado en muchas soluciones récord recientes. Gerhard Reinelt publicó en 1991 el TSPLIB, una colección de instancias de referencia de dificultad variable, 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 disposición de microchips, actualmente la mayor instancia TSPLIB resuelta. Para muchas otras instancias con millones de ciudades, se pueden encontrar soluciones que están garantizadas dentro del 2-3% de un recorrido óptimo[13].
* Siglo XIX - Formulada matemáticamente por primera vez por el matemático irlandés William Rowan Hamilton y por el matemático británico Thomas Kirkman.
* Década de 1930 - Estudiada por primera vez por matemáticos en Viena y en Harvard, sobre todo por Karl Menger y Merill M. Flood, que buscaba resolver un problema de rutas de autobuses escolares.
* 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, que proporcionó la primera solución práctica.
* Década de 1960 - se crea un nuevo enfoque, que produce una solución cuya longitud está limitada de forma demostrable por un múltiplo de la longitud óptima.
* 1972 - Richard M. Karp demostró que el problema del ciclo hamiltoniano era NP-completo, lo que implica la NP-dureza del problema del viajante de comercio.
* 1976 - Christofides y Serdyukov inventaron independientemente un nuevo algoritmo que da una solución que, en el peor de los casos, es como máximo 1,5 veces más larga que la solución óptima.
* Década de 1990 - Applegate, Bixby, Chvátal y Cook desarrollaron el programa Concorde, que se ha utilizado en muchas soluciones récord recientes.
* 1991 - Gerhard Reinelt publicó el TSPLIB, una colección de instancias de referencia de dificultad variable, que ha sido utilizada por muchos grupos de investigación para comparar resultados.
* 2006 - Cook y otros calcularon un recorrido óptimo a través de una instancia de 85.900 ciudades dada por un problema de disposición de microchips, actualmente la mayor instancia TSPLIB resuelta.
* 2011 - Se desarrolla un algoritmo de aproximación ligeramente mejorado para el subconjunto del problema del viajante de comercio "gráfico".
* 2020 - Se amplía el algoritmo de aproximación ligeramente mejorado desarrollado para el subconjunto del problema del viajante de comercio "gráfico" para cubrir el problema del viajante de comercio completo.
What is the history of the travelling salesman problem throughout the years in a short bulleted list?
The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, but contains no mathematical treatment.[2]


William Rowan Hamilton
The TSP was mathematically formulated in the 19th century by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman. Hamilton's icosian game was a recreational puzzle based on finding a Hamiltonian cycle.[3] The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger, who defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic:

We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.[4]

It was first considered mathematically in the 1930s by Merrill M. Flood who was looking to solve a school bus routing problem.[5] Hassler Whitney at Princeton University generated interest in the problem, which he called the "48 states problem". The earliest publication using the phrase "travelling salesman problem" was the 1949 RAND Corporation report by Julia Robinson, "On the Hamiltonian game (a traveling salesman problem)."[6][7]

In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the United States after the RAND Corporation in Santa Monica offered prizes for steps in solving the problem.[5] Notable contributions were made by George Dantzig, Delbert Ray Fulkerson and Selmer M. Johnson from the RAND Corporation, who expressed the problem as an integer linear program and developed the cutting plane method for its solution. They wrote what is considered the seminal paper on the subject in which with these new methods they solved an instance with 49 cities to optimality by constructing a tour and proving that no other tour could be shorter. Dantzig, Fulkerson and Johnson, however, speculated that given a near optimal solution we may be able to find optimality or prove optimality by adding a small number of extra inequalities (cuts). They used this idea to solve their initial 49 city problem using a string model. They found they only needed 26 cuts to come to a solution for their 49 city problem. While this paper did not give an algorithmic approach to TSP problems, the ideas that lay within it were indispensable to later creating exact solution methods for the TSP, though it would take 15 years to find an algorithmic approach in creating these cuts.[5] As well as cutting plane methods, Dantzig, Fulkerson and Johnson used branch and bound algorithms perhaps for the first time.[5]

In 1959, Jillian Beardwood, J.H. Halton and John Hammersley published an article entitled "The Shortest Path Through Many Points" in the journal of the Cambridge Philosophical Society.[8] The Beardwood–Halton–Hammersley theorem provides a practical solution to the travelling salesman problem. The authors derived an asymptotic formula to determine the length of the shortest route for a salesman who starts at a home or office and visits a fixed number of locations before returning to the start.

In the following decades, the problem was studied by many researchers from mathematics, computer science, chemistry, physics, and other sciences. In the 1960s, however, a new approach was created, that instead of seeking optimal solutions would produce a solution whose length is provably bounded by a multiple of the optimal length, and in doing so would create lower bounds for the problem; these lower bounds would then be used with branch and bound approaches. One method of doing this was to create a minimum spanning tree of the graph and then double all its edges, which produces the bound that the length of an optimal tour is at most twice the weight of a minimum spanning tree.[5]

In 1976, Christofides and Serdyukov independently of each other made a big advance in this direction:[9] the Christofides-Serdyukov algorithm yields a solution that, in the worst case, is at most 1.5 times longer than the optimal solution. As the algorithm was simple and quick, many hoped it would give way to a near optimal solution method. However, this hope for improvement did not immediately materialize, and Christofides-Serdyukov remained the method with the best worst-case scenario until 2011, when a (very) slightly improved approximation algorithm was developed for the subset of "graphical" TSPs.[10] In 2020 this tiny improvement was extended to the full (metric) TSP.[11][12]

Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours.

Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2,392 cities, using cutting planes and branch and bound.

In the 1990s, Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions. Gerhard Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2006, Cook and others computed an optimal tour through an 85,900-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 2–3% of an optimal tour.[13]
* 19th century - mathematically formulated for first time by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman
* 1930s - First studied by mathematicians in Vienna and at Harvard, most notably by Karl Menger and Merill M. Flood who was looking to solve a school bus routing problem.
* 1959 - Jillian Beardwood, J.H. Halton and John Hammersley published an article entitled "The Shortest Path Through Many Points" in the journal of the Cambridge Philosophical Society, which provided the first practical solution.
* 1960s - new approach is created, which produce a solution whose length is provably bounded by a multiple of the optimal length.
* 1972 - Richard M. Karp showed that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of traveling salesman problem.
* 1976 - Christofides and Serdyukov independently invented new algorithm, which yields a solution that in the worst case is at most 1.5 times longer than the optimal solution.
* 1990s -  Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions.
* 1991 - Gerhard Reinelt published the TSPLIB, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results
* 2006 - Cook and others computed an optimal tour through an 85,900-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance.
* 2011 - Slightly improved approximation algorithm is developed for the subset of "graphical" traveling salesman problem.
* 2020 - The slightly improved approximation algorithm developed for the subset of "graphical" is extended to cover the full traveling salesman problem.