How Santa deals with the challenge of the Travelling Salesman Problem

THAT'S MATHS:In the course of a single night, Santa Claus has a billion homes to visit. To ensure that every child gets a gift, he needs to pick a smart route. How does he do it? His challenge is called the Travelling Salesman Problem, or TSP.

Suppose a salesman based in Dublin must visit Waterford, Cork and Derry, and wants the shortest route. He can pick any city to begin, then either of the remaining two, and finally the last one before returning home. So, he has 3 x 2 x 1 = 6 choices. But some routes are much longer than others. Clearly, he will not go first to Cork, then to Derry and then to Waterford.

The salesman can calculate the distance of all six possible routes and choose the shortest. This is the “brute-force” solution of the TSP. But what if there are 10 cities instead of three? Then there are 10 x 9 x 8 x . . . x 3 x 2 x 1 possible routes. The product of the first 10 numbers, called 10 factorial and written 10!, comes to 3,628,800, far too many to check by hand. And for 20 cities it is 20 factorial, which 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 optimisation” problem. It is easy to state but difficult to solve effectively. The mathematical structure underlying the problem is called a graph: each city is a vertex, and edges are drawn connecting every two vertices. A round-trip of all the cities is called a Hamiltonian cycle, after William Rowan Hamilton, the outstanding Irish mathematician. Hamilton solved a problem of this type when designing a puzzle called the Icosian Game.

The goal of the TSP is to minimise the total length of the round trip. Various “heuristic solutions” 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 can be removed so that the best route does not intersect itself but is a simple curve, like a greatly distorted circle with an inside and an outside.

Why should we worry about the TSP? Well, the same problem arises in a large number of practical applications. These include the manufacture of computer circuit boards, calculating DNA sequences in genetic engineering, allocating routes to a fleet of aircraft, designing fibre-optic-cable networks and scheduling material stocks in warehouses.

The TSP is a prototype for the “P versus NP Problem”, one of the trickiest unsolved 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.

* Peter Lynch is professor of meteorology at University College Dublin. He blogs at thatsmaths.com