Pigeons, curves and a problem with the traveling salesman

In Mo Willems children `s book Don’t let the pigeon ride the bus!, the protagonist – a pigeon, obvs – uses every trick in the book (literally) to convince the reader that he should be allowed to drive a bus when the ordinary human driver suddenly has to leave. Williams’ book had unintended scientific implications in 2012 when the highly respected journal Human Cognition published a highly respected report by fully respected researchers Brett Gibson, Matthew Wilkinson, and Debbie Kelly. They showed experimentally that pigeons can find solutions close to the optimal, simple cases of the famous mathematical curiosity: The problem of the traveling salesman. Their title was “Let the pigeon ride the bus: pigeons can plan future routes in a room.”

Let no one claim that scientists lack a sense of humor. Or that cute headlines don’t help generate publicity.

The problem with the traveling salesman is not just curiosity. This is a very important example of a class of problems of great practical importance called combinatorial optimization. Mathematicians have a habit of asking deep and meaningful questions in terms of obvious curious facts.

The piece of significant curiosity that inspires this article originates from a useful book for – you guessed it – traveling traders. Door to door sellers. Like any sensible businessman, the German merchant traveler of 1832 (and in those days was always a man) set a bonus for using his time efficiently and reducing costs. Fortunately, the help was at hand in the form of a guide: The travel salesman – what he should be and what he should do to receive orders and be sure of happy success in his business – from an old salesman.

This adult seller of peripatetics stated that:

The business leads the traveling salesman now here, then there, and travel routes that are appropriate for all cases cannot be properly identified; but sometimes, by proper choice and arrangement of the tour, so much time can be gained that we do not think that we can avoid giving some rules on this issue … The main point is always to visit as much as possible places without having to tap the same place twice.

The guide does not offer math to solve this problem, but contains examples of five supposedly optimal laps.

The problem of the traveling salesman or TSP, as it became known – later changed to the Problem of the traveling salesman to avoid sexism, which conveniently has the same abbreviation – is a fundamental example of the mathematical field known today as combinatorial optimization. Which means “finding the best option among a number of options that are too large to be tested one by one.”

Curiously, the name TSP did not appear to be used explicitly in any publication devoted to this problem until 1984, although it was often used much earlier in informal discussions among mathematicians.

In the age of the Internet, companies rarely sell their goods by sending someone from city to city with a suitcase full of samples. They put everything on the net. As usual (unjustified efficiency), this change in culture did not make TSP obsolete. As online shopping grows exponentially, the search for effective ways to determine routes and schedules is becoming increasingly important for everything from parcels to supermarket orders to pizza.

The portability of mathematics also comes into play. TSP applications are not limited to traveling between cities or on city streets. Famous astronomers once had their own telescopes or shared them with several colleagues. The telescopes could easily be reoriented to point to new celestial bodies, so it was easy to improvise. This is no longer the case when the telescopes used by astronomers are huge, terribly expensive and available online. Aiming the telescope at a fresh object takes time, and while the telescope is moving, it cannot be used for observations. Visit the targets in the wrong order and waste a lot of time moving the telescope a long way, then back again to somewhere close to where it started.

When DNA sequencing, the fragmentary sequences of DNA bases must be properly linked and the order in which this is done must be optimized to avoid wasting computer time. Other applications range from efficient targeting of aircraft to the design and manufacture of computer microchips and printed circuit boards. Approximate TSP solutions have been used to find effective cycling feeding routes and to optimize blood supply to hospitals. A version of the TSP even appeared in Star Wars, specifically in President Ronald Reagan’s hypothetical strategic defense initiative, where a powerful laser orbiting the Earth would be aimed at a series of incoming nuclear missiles.

In 1956, Merrill Flood, a pioneer in operational research, argued that TSP was likely to be difficult. In 1979, Michael Garey and David Johnson proved him right: there is no effective algorithm for solving the problem in the “worst cases”. But the worst-case scenarios often turn out to be very fictional and atypical of real-world examples. So the mathematicians in operational research set out to see how many cities could deal with real problems.