Pigeons, Curves, and the Traveling Salesperson Problem
In Mo Willems’ children’s book Don’t Let the Pigeon Drive the Bus!, the main character—a pigeon, obvs—uses every trick in the book (literally) to convince the reader that it should be allowed to drive a bus when the regular human driver suddenly has to leave. Willems’s book had an unintended scientific consequence in 2012, when the entirely respectable journal Human Cognition published an entirely respectable paper by the entirely respectable researchers Brett Gibson, Matthew Wilkinson, and Debbie Kelly. They showed experimentally that pigeons can find solutions, close to optimal, to simple cases of a famous mathematical curiosity: the Travelling Salesman Problem. Their title was ‘Let the pigeon drive the bus: pigeons can plan future routes in a room.’
Let no one claim that scientists lack a sense of humor. Or that cute titles don’t help to generate publicity.
The Traveling Salesman Problem is not just a curiosity. It’s a very important example of a class of problems of enormous practical significance, called combinatorial optimization. Mathematicians have a habit of posing deep and significant questions in terms of apparent trivia.
The piece of significant trivia that inspires this article had its origins in a helpful book for—you guessed it—traveling salesmen. Door-to-door sellers. Like any sensible business person, the German traveling salesman of 1832 (and in those days it always was a man) placed a premium on using his time efficiently and cutting costs. Fortunately, help was at hand, in the form of a manual: The traveling salesman—how he should be and what he has to do, to obtain orders and to be sure of a happy success in his business—by an old traveling salesman.
This elderly peripatetic vendor pointed out that:
Business brings the traveling salesman now here, then there, and no travel routes can be properly indicated that are suitable for all cases occurring; but sometimes, by an appropriate choice and arrangement of the tour, so much time can be gained, that we do not think we may avoid giving some rules also on this… The main point always consists of visiting as many places as possible, without having to touch the same place twice.
The manual didn’t propose any mathematics to solve this problem, but it did contain examples of five allegedly optimal tours.
The Traveling Salesman Problem, or TSP, as it came to be known—later changed to Traveling Salesperson Problem to avoid sexism, which conveniently has the same acronym—is a founding example for the mathematical area now known as combinatorial optimization. Which means ‘finding the best option among a range of possibilities that’s far too big to check one at a time.’
Curiously, the TSP name seems not to have been used explicitly in any publication concerning this problem until 1984, although it was common usage much earlier in informal discussions among mathematicians.
In the age of the Internet, companies seldom sell their goods by sending someone from town to town with a suitcase full of samples. They put everything on the web. As usual (unreasonable effectiveness) this change of culture hasn’t made the TSP obsolete. As online shopping grows exponentially, the demand for efficient ways to determine routes and schedules is becoming ever more important for everything from parcels to supermarket orders to pizza.
The portability of mathematics also comes into play. Applications of the TSP are not restricted to travel between towns or along city streets. Once upon a time, prominent astronomers had their own telescopes, or shared them with a few colleagues. The telescopes could easily be redirected to point at new heavenly bodies, so it was easy to improvise. Not so any more, when the telescopes used by astronomers are enormous, ruinously expensive, and accessed online. Pointing the telescope at a fresh object takes time, and while the telescope is being moved, it can’t be used for observations. Visit targets in the wrong order and a lot of time is wasted moving the telescope a long way, and then back again to somewhere near where it started.
In DNA sequencing, fragmentary sequences of DNA bases must be joined together correctly, and the order in which this is done has to be optimised to avoid wasting computer time. Other applications range from routing aircraft efficiently to the design and manufacture of computer microchips and printed circuit boards. Approximate solutions of TSPs have been used to find efficient routes for Meals on Wheels and to optimise the delivery of blood to hospitals. A version of the TSP even showed up in ‘Star Wars,’ more properly President Ronald Reagan’s hypothetical Strategic Defense Initiative, where a powerful laser orbiting the Earth would have been targeted at a series of incoming nuclear missiles.
<
p class=”paywall”>In 1956 operations research pioneer Merrill Flood argued that the TSP is likely to be hard. In 1979, Michael Garey and David Johnson proved that he was right: no efficient algorithm exists to solve the problem in ‘worst cases.’ But worst-case scenarios often turn out to be very contrived, and not typical of examples in the real world. So mathematicians in operations research set out to see just how many cities they could handle for real-world problems.
