En Mo Willems ‘ Libro de niños ¡No dejes que la paloma conduzca el autobús!, el personaje principal, una paloma, obviamente, usa todos los trucos del libro (literalmente) para convencer al lector de que se debe permitir conducir un autobús si el conductor humano normal tiene que irse de repente. El libro de Willems tuvo una consecuencia científica involuntaria en 2012 cuando la respetable revista Human Cognition publicó un artículo respetable de los respetables investigadores Brett Gibson, Matthew Wilkinson y Debbie Kelly. Demostraron experimentalmente que las palomas pueden encontrar soluciones casi óptimas a casos simples de una famosa curiosidad matemática: el problema del viajante. Su título era: “Deja que la paloma conduzca el autobús: las palomas pueden planificar rutas futuras en una habitación”.

Nadie debería decir que los científicos carecen de humor. O que los títulos lindos no ayudan a promoverlo.

El problema del vendedor ambulante no es solo una curiosidad. Este es un ejemplo muy importante de una clase de problemas de enorme importancia práctica denominados optimización combinatoria. Los matemáticos tienen la costumbre de hacer preguntas profundas y significativas sobre aparentemente trivialidades.

El conocimiento importante que inspira este artículo tiene su origen en un libro útil para, lo adivinó, los viajeros de negocios. Vendedor puerta a puerta. Como cualquier hombre de negocios sensato, el viajante de comercio alemán de 1832 (y en aquel entonces siempre fue un hombre) se propuso utilizar su tiempo de manera eficiente y ahorrar dinero. Afortunadamente, la ayuda estaba disponible en forma de manual: El vendedor ambulante – cómo debería ser y qué hacer para recibir pedidos y estar seguro de un feliz éxito comercial – de un viejo vendedor ambulante.

Este vendedor ambulante anciano señaló que:

Los negocios ahora llevan al viajante de comercio aquí, luego allá, y es imposible identificar correctamente los itinerarios que sean adecuados para todos los casos que se presenten; pero a veces se puede ganar tanto tiempo eligiendo y diseñando el recorrido en consecuencia que no creemos que podamos establecer algunas reglas aquí también … tocar el mismo punto dos veces.

El manual no proporcionó ninguna sugerencia matemática para resolver este problema, pero sí incluyó ejemplos de cinco recorridos supuestamente óptimos.

El problema del viajante de comercio, o TSP, como se le conoció más tarde, cambiado al problema del viajante para evitar el sexismo, que convenientemente tiene el mismo acrónimo, es un ejemplo fundamental del campo matemático que ahora se conoce como optimización combinatoria. Esto significa “encontrar la mejor opción entre una serie de posibilidades que son demasiado grandes para examinarlas individualmente”.

Curiosamente, el nombre TSP no parece haber sido utilizado explícitamente en ninguna publicación sobre este problema hasta 1984, aunque se utilizó en discusiones informales entre matemáticos mucho antes.

En la era de Internet, las empresas rara vez venden sus productos enviando a alguien de pueblo en pueblo con una maleta llena de muestras. Pones todo en la red. Como es habitual (eficacia irrazonable), este cambio cultural no ha dejado obsoleto al TSP. A medida que las compras en línea crecen exponencialmente, la demanda de rutas y horarios eficientes se vuelve cada vez más importante, desde paquetes hasta pedidos de supermercados y pizzas.

La portabilidad matemática también juega un papel. Las aplicaciones del TSP no se limitan a viajar entre ciudades o en vías urbanas. Los astrónomos prominentes solían tener sus propios telescopios o los compartían con algunos colegas. Los telescopios se podían redirigir fácilmente para apuntar a nuevos cuerpos celestes, por lo que era fácil de improvisar. Ya no cuando los telescopios utilizados por los astrónomos son enormes, terriblemente caros y accesibles en línea. Se necesita tiempo para alinear el telescopio con un nuevo objeto y, mientras se mueve el telescopio, no se puede utilizar para la observación. Visitar destinos en el orden incorrecto perderá mucho tiempo moviendo el telescopio lejos y luego moviéndolo de regreso a una ubicación cerca del punto de partida.

En la secuenciación de ADN, las secuencias fragmentarias de bases de ADN deben ensamblarse correctamente y el orden debe optimizarse para evitar el tiempo de la computadora. Otros usos van desde el enrutamiento eficiente de aeronaves hasta el diseño y fabricación de microchips de computadora y placas de circuito. Las soluciones de proximidad de los TSP se han utilizado para encontrar formas eficientes de comer sobre ruedas y optimizar el suministro de sangre a los hospitales. Incluso apareció una versión del TSP en “Star Wars”, más específicamente en la hipotética iniciativa de defensa estratégica del presidente Ronald Reagan, en la que un poderoso láser que orbita la tierra habría estado dirigido a una serie de misiles nucleares entrantes.

En 1956, el pionero de la investigación quirúrgica Merrill Flood argumentó que es probable que el TSP sea difícil. En 1979, Michael Garey y David Johnson demostraron que tenía razón: no existe un algoritmo eficaz para resolver el problema del “peor de los casos”. Pero los peores escenarios a menudo resultan ser muy construidos y no típicos de los ejemplos del mundo real. Entonces, los matemáticos en Investigación de Operaciones se propusieron cuántas ciudades podrían abordar para problemas reales.