TECHNOLOGY

Pigeon, curve, and travel vendor problems

Moe Williams’ Children’s books Do not let the pigeon drive the bus!, The main character – a pigeon, obvs – uses every technique in the book (literally) to convince the reader that a regular driver should be allowed to drive the bus if he leaves suddenly. Williams ’book had an unintended scientific consequence in 2012, when the fully-respected journal Human Cognition published a completely respected paper by fully-respected researchers Brett Gibson, Matthew Wilkinson and Debbie Kelly. They experimentally showed that pigeons could find solutions, close to favorable, in the simplest case of a famous mathematical curiosity: the travel salesman problem. Their title was ‘Let the Pigeons Drive the Bus: Pigeons Can Plan Their Future in a House.’

Let no one claim that there is a lack of humor among scientists. Or that doesn’t help promote that beautiful title.

The problem of traveling salesmen is not just curiosity. This is a very important example of a problem of huge practical significance, called combinatorial optimization. Mathematicians have a habit of asking deep and meaningful questions on seemingly trivial matters.

The notable trivial matter that inspired this article originated in a helpful book – you guessed it – for traveling salespeople. Door to door sellers. Like any intelligent business person, the German travel salesman of 1832 (and in those days it was always a man) kept a premium for using his time efficiently and reducing costs. Fortunately, there was help in the form of a manual: the traveling salesman he should be and what he should do, to get orders and be sure of the happy success of his business – an old travel salesman.

This veteran peripatetic vendor has indicated that:

The business now brings the traveling salesman here, then there, and no travel route can be accurately indicated which is appropriate in all cases happening; But sometimes, by a proper choice and arrangement of the tour, so much time can be gained, that we do not think we can avoid giving some rules in this regard … touching the same place twice.

The manual does not offer any math to solve this problem, but it does contain five examples of so-called optimal travel.

The Traveling Salesman Problem, or TSP, as it was known – later changed to the Traveling Salesperson Problem to avoid sexism, which is conveniently the same abbreviation – is an established example of the mathematical field now known as Combinatorial Optimization. Which means ‘finding the best option in a range of possibilities that’s too big to do one check at a time.’

Interestingly, the name TSP does not appear to have been explicitly used in any publications on this problem until 1984, although it has long been used in informal discussions among mathematicians.

In the age of the internet, companies rarely sell their products by sending someone from town to town with a sample-filled suitcase. They put everything on the web. This change in the usual (unreasonable) culture did not make TSP obsolete. With the rapid growth of online shopping, the demand for efficient ways of setting routes and schedules is becoming more important for everything from parcels to supermarket orders to pizzas.

Mathematical portability is also effective. TSP applications are not limited to travel within the city or on city streets. At one time, prominent astronomers had their own telescopes, or shared them with a few colleagues. Telescopes could easily point to new celestial bodies, so it was easy to improve. Not so when the telescopes used by astronomers are huge, destructively expensive, and accessible online. It takes time to point the telescope at a fresh object, and when the telescope is being moved, it cannot be used for observation. Inspect targets in the wrong order and a lot of time is wasted moving the telescope too far, and then back again somewhere near where it started.

In DNA sequencing, the fragmented sequences of the DNA base must be properly assembled and customized in order not to waste computer time. Other applications range from efficient routing of aircraft to design and manufacture of computer microchips and printed circuit boards. Approximate solutions of TSPs have been used to find effective routes for wheel-on-wheel and to optimize blood supply to the hospital. A version of the TSP has even been shown in ‘Star Wars’, more precisely President Ronald Reagan’s speculative strategic defense initiative, where a powerful laser orbiting the Earth was targeted in a series of incoming nuclear missiles.

Meryl Flood, the pioneer of Operations Research in 1956, argued that TSP could be difficult. In 1979, Michael Gary and David Johnson proved that he was right: there is no effective algorithm to solve the ‘worst case’ problem. But the worst situations are often very imaginative, and not like the examples in the real world. So mathematicians in operations research were prepared to see how many cities they could manage for real-world problems.