Santa’s TSP Algorithm

This week’s That’s Maths column ( TM011 ) discusses the challenge faced by Santa Claus: he has about a billion homes to visit in one night, so he needs to be smart in picking his route. The challenge he faces is called the Travelling Salesman Problem, or TSP. Santa-and-Sleigh

Although he won’t reveal his secret, Santa has worked out a brilliant algorithm. So he should arrive at your house in good time. I hope you and your family get whatever you wish, and have a Happy Christmas.

The TSP

The basic idea of the Travelling Salesman Problem is to find the shortest route a salesman can choose to visit a number of cities and return to his starting point. For a small number of cities, it is simple to calculate all the possible routes and pick the shortest: this is the “brute-force” solution of the TSP.

We might say that the problem is solved; but there is a huge difficulty: for n cities, the number of routes grows like n!  Using Stirling’s approximation,

\displaystyle{n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n}

we see that n! grows at a rate faster than exponential. Thus, 10! = 3,628,800 and 20! is more than two million million million. The brute force approach is useless. We have to find a smarter way to solve the problem.

The TSP is a combinatorial optimization problem. It is easy to state but difficult to solve effectively. The mathematical structure underlying the TSP is called a graph: each city is a vertex, and edges are drawn connecting every two vertices.

Minimum distance route through all major towns in USA.

Minimum distance route through all major towns in USA.

A round-trip of all the cities is called a Hamiltonian cycle, after William Rowan Hamilton, the outstanding Irish mathematician who, in 1857, considered a problem of this type when designing a puzzle called the Icosian Game. The object of the game is to find a closed route along the edges of a dodecahedron, or regular 12-faced polyhedron, such that every vertex is visited a single time.

A Hamiltonian cycle on a dodecahedron. Left: 2D projection. Right: 3D image.

A Hamiltonian cycle on a dodecahedron. Left: 2D projection. Right: 3D image.

Various heuristic solutions of the TSP have been devised; for example, the nearest neighbour algorithm, where we pick the closest city not yet chosen. But none of these is optimal in all cases. Cross-overs in the route can be removed to shorten it, so that the best route does not intersect itself but is a simple curve, like a greatly distorted circle with an inside and outside.

An excellent book, In Pursuit of the Traveling Salesman, by William J. Cook, has recently been published by Princeton University Press.

Applications

Why should we worry about the TSP? Well, the same problem arises in a large number of practical applications. For example, in the manufacture of computer circuit boards, thousands of holes must be drilled. This has to be done in an efficient way. The holes are the “cities” and the total travel time of the drill head is to be minimised.

The Concorde TSP Solver is a program for solving the Travelling Salesman Problem. It is freely available for academic use. Concorde has been used to obtain optimal solutions for a wide range of practical problems: computing DNA sequences for genetic engineering; allocating routes to a fleet of aircraft; designing optic fibre cable networks; scheduling material stocks in warehouses; and many others.

The TSP is a prototype of the “P versus NP Problem”, one of the trickiest problems in mathematics. The record number of “cities” for which an optimal solution has been found is 85,900. But Santa’s challenge is vast by comparison, so he must have found a truly excellent algorithm for solving the TSP.


Last 50 Posts

Categories