¿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.


William Rowan Hamilton
El TSP fue formulado matemáticamente en el siglo XIX por el matemático irlandés William Rowan Hamilton y por el matemático británico Thomas Kirkman. El juego icosiano de Hamilton era un rompecabezas recreativo basado en encontrar un ciclo hamiltoniano La forma general del TSP parece haber sido estudiada por primera vez por matemáticos durante la década de 1930 en Viena y en Harvard, 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.

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 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)".

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. 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. 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.

En 1959, Jillian Beardwood, J.H. Halton y John Hammersley publicaron un artículo titulado "El camino más corto a través de muchos puntos" en la revista de la Sociedad Filosófica de Cambridge. El teorema 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.

En 1976, Christofides y Serdyukov, independientemente el uno del otro, hicieron un gran avance en este sentido: 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". En 2020, esta diminuta mejora se extendió al TSP completo (métrico).

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.
* 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.