A Mo Willems’ children’s book Don’t let the pigeon drive the bus!, the main character — a pigeon, obviously — uses all the tricks in the book (literally) to convince the reader that he should be allowed to drive a bus when the normal human driver has to leave suddenly. Willems ’book had an unintended scientific consequence in 2012, when the fully respectable journal Human Cognition published a completely respectable article by respectable researchers Brett Gibson, Matthew Wilkinson, and Debbie Kelly. They showed experimentally that pigeons can find almost optimal solutions to simple cases of a famous mathematical curiosity: the problem of the traveling salesman. Its title was “Let the Pigeon Drive the Bus: Pigeons Can Plan Future Routes in a Room.”
Let no one claim that scientists have no sense of humor. Or that beautiful headlines don’t help generate advertising.
The problem of the street vendor is not just a curiosity. It is a very important example of a class of problems of enormous practical importance, called combinatorial optimization. Mathematicians have a habit of asking deep and meaningful questions in terms of apparent trivialities.
The significant trivia that inspires this article had its origins in a useful book for traveling sellers (you guessed it). Door to door sellers. Like any sensible businessman, the German traveling salesman of 1832 (and in those days he was always a man) charged a premium for using his time efficiently and reducing costs. Fortunately, there was help in hand, in the form of a manual: A traveling salesman — how he should be and what he should do, to get orders and be sure of a happy success in his business — of an old traveling salesman .
This elderly peripatetic salesman noted that:
The business causes the traveling salesman to go here, then there, and proper travel routes cannot be properly indicated for all cases; but sometimes, with the right choice and arrangement of the tour, you can save so much time, that we don’t think we can avoid giving some rules about it too … The main point is always to visit as many places as possible, without having to touch the same place twice.
The manual did not propose any mathematics to solve this problem, but it contained examples of five supposedly optimal paths.
The Traveling Salesman Problem, or TSP, as it was known – later changed to Traveling Salesperson Problem to avoid sexism, which conveniently has the same acronym – is a prime example for the mathematical area now known as combinatorial optimization. Which means “finding the best option among a range of possibilities that is too large to check one by one.”
Interestingly, the name TSP does not appear to have been used explicitly in any publication on this problem until 1984, although it was a common use long before in informal discussions among mathematicians.
In the Internet age, companies rarely sell their products by sending someone from town to town with a suitcase full of samples. They put it all on the web. As usual (unreasonable effectiveness), this change in culture has not made the TSP obsolete. As online shopping grows exponentially, the demand for efficient ways to determine routes and schedules is increasingly important for everything from parcels to grocery orders to pizza.
The portability of math also comes into play. TSP applications are not limited to traveling between cities or on city streets. Once upon a time, prominent astronomers had their own telescopes or shared them with a few colleagues. Telescopes could be easily redirected to aim at new celestial bodies, so it was easy to improvise. It is no longer, when the telescopes used by astronomers are huge, they are ruinously expensive and accessed online. Pointing the telescope at a new object takes time, and while the telescope is moving, it cannot be used to make observations. Visit the lenses in the wrong order and waste a lot of time moving the telescope a long way and return it back to somewhere nearby where it started.
In DNA sequencing, the fragmentary DNA base sequences must be joined correctly and the order in which this is done must be optimized to avoid wasting computer time. Other applications range from efficient aircraft routing to the design and manufacture of computer microchips and printed circuit boards. Approximate TSP solutions have been used to find efficient food routes on wheels and to optimize blood delivery to hospitals. A version of the TSP even appeared in ‘Star Wars’, more aptly President Ronald Reagan’s hypothetical Strategic Defense Initiative, where a powerful laser orbiting the Earth would have been aimed at a series of incoming nuclear missiles.
In 1956, pioneering operational research Merrill Flood argued that TSP is likely to be difficult. In 1979, Michael Garey and David Johnson proved him right: there is no efficient algorithm to solve the problem in the “worst cases.” But the worst cases are usually very artificial and are not typical of real world examples. Thus, mathematicians in operations research set out to see how many cities they could handle for real-world problems.