El viajante de comercio

Los orígenes del problema del viajante de comercio no son claras, el primer índice de éste fue a partir de 1832 en Alemania en un libro titulado: El problema del viajero, cómo debe hacer para obtener éxito en sus negocios, dónde en su último capítulo se vislumbra la esencia del TSP cuando se comenta que con una elección apropiada del tour, se puede ganar mucho tiempo y que el aspecto más importante es cubrir tantas ciudades como sean posibles sin visitar una de ellas dos veces, pero no contenía ningún tratamiento matemático.

El problema fue definido como tal en 1800 por el matemático irlandés WR Hamilton y por el matemático británico Thomas Kirkman. Hamilton Icosian Game. El juego Icosain es un desafío conocido como icosian game, un juego matemático desarrollado en 1857 por William Rowan Hamilton. El objetivo del juego es dar con el recorrido de Hamilton por las aristas de un dodecaedro para visitar una y sólo una vez cada vértice y que el de llegada coincida con el de partida. Este desafío se comercializó como un tablero con agujeros en cada nodo del grafo del dodecaedro y luego, fue distribuido en Europa en diversos formatos. Era un rompecabezas de recreo con base en la búsqueda de un ciclo de Hamilton. La forma general de la TSP parece haber sido estudiado por primera vez por los matemáticos durante la década de 1930 en Viena y la Universidad de Harvard, en particular por Karl Menger, que define el problema, considera el algoritmo de fuerza bruta obvio, y observa la falta de optimización de la cercana vecino heurística: Se trata de un problema NP-duro en la optimización combinatoria, importante en la investigación de operaciones y ciencias de la computación teórica.

Merrill Flood fue el responsable de divulgar el nombre del TSP. Le habló acerca de él a A. W. Tucker en 1937. Tucker le comentó que recordaba haberlo escuchado de boca de Hassler Whitney de la Universidad de Princeton, quién estaba estudiando la teoría de grafos, en especial el problema de los cuatro colores, pero no podía confirmar con certeza esta historia. De ser verídica, asegura que ocurrió en los años 1931-1932 ya que fue entonces cuando se hallaba terminando su tesis con Lefschetz.

John Williams incitó a Flood en 1948 a popularizar el TSP en la corporación RAND en Santa Mónica, motivado por el propósito de crear talentos intelectuales para modelos fuera de la teoría de juegos. No hay dudas de que la reputación y la autoridad de RAND, que rápidamente se convirtió en el centro intelectual de muchas de las investigaciones sobre esta teoría, amplificó la publicidad de Flood. Otra razón de la popularidad del problema fue su íntima conexión con el problema de la asignación y el del transporte.

La aparición del artículo "Soluciones de un problema del viajante de gran tamaño" de Dantzig, Fulkerson y Johnson en el Journal of the Operations Research Society of America fue uno de los principales eventos en la historia de la optimización, ya que esto conllevó al estudio de la combinatoria y los problemas de programación lineal: el problema del transporte y el de asignación.

Dantzig desarrolló el método simplex para resolver problemas de programación lineal.

En 1953, existían códigos de implementación efectivos del método simplex en general y adaptaciones especiales para los casos del problema del transporte y de asignación. En 1954 Dantzig, Fulkerson y Johnson hicieron un método que resolvía el problema del horario de los buques. La solución llegó varios años después de que el modelo se volviera obsoleto, pero logró sobrevivir porque el método podía ser usado para estudiar preguntas básicas de la teoría combinatoria. Ford y Fulkerson escribieron su primer reporte sobre sistemas de flujo en 1956, iniciando de este modo un tópico mayor del cual derivó un resultado de Johnson sobre la secuencia de trabajos. El TSP, sin embargo, no estaba relacionado a simple vista con estos desarrollos pero había esperanza de que lo estuviera.

Los tres matemáticos antes mencionados especulaban que, empezando de un tour óptimo o tal vez cercano al óptimo, era posible probar optimalidad utilizando pocas ecuaciones adicionales (llamadas cortes). El método parecía funcionar en pequeños problemas, por eso, pasaron a trabajar sobre uno de 49 ciudades.

Ellos sugirieron la posibilidad de que fuesen necesarios un gran número de cortes. Dantzig, optimista, le apostó a Fulkerson que el número de cortes necesarios eran a lo sumo 25, en cambio Fulkerson más pesimista opinaba que se necesitaban al menos 26. Las predicciones fueron bastante acertadas: la cantidad correcta resultó ser 26 pero en el papel que se publicó se decía que sólo 25 eran necesarios.

Dantzig, Fulkerson y Johnson no sólo resolvieron un TSP de tamaño considerable sino que también demostraron que la complejidad de la estructura de un problema de optimización combinatoria no era un obstáculo insuperable para resolverlo. Ellos utilizaron por primera vez el concepto de branch y bound, que es un método computacional muy popular, en particular, cuando se requiere que sólo algunas de las variables sean enteras.

Otro método que se ha aplicado en la resolución del TSP fue la programación dinámica pero debido a la enorme cantidad de condiciones que incluye puede resolver instancias de problemas relativamente pequeños.

Richard M. Karp mostró en 1972 que el problema del ciclo de Hamilton era NP-completo, que implica la NP-dureza de TSP. Esto suministra una explicación matemática de la dificultad computacional aparente de encontrar rutas óptimas. Se hizo un gran avance en la década de 1970 y 1980, cuando Grotschel, Padberg, Rinaldi y otros lograron resolver exactamente los casos con un máximo de 2.392 ciudades, con planos de corte y la rama y los consolidados. En la década de 1990, Applegate, Bixby, Chvtal, y Cocine desarrollaron el programa Concorde que se ha utilizado en muchas soluciones de registro recientes.

Gerhard Reinelt publicó el TSPLIB  que contiene la descripción de una biblioteca para el problema del viajante que está destinada a proporcionar a los investigadores un amplio conjunto de problemas de prueba de diversas fuentes y propiedades, en 1991, es decir, una colección de instancias de referencias de diferentes dificultades, que ha sido utilizado por muchos grupos de investigación para la comparación de resultados, como por ejemplo, en 2006, Cook y otros calculan un recorrido óptimo a través de una instancia de 85.900 ciudades dada por un problema de diseño microchip. En muchos otros casos, con millones de ciudades, se pueden encontrar soluciones que están garantizados para estar dentro del 1% de un recorrido óptimo.