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

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
GO BACK
Error Image
The account details entered are not currently associated with an Irish Times subscription. Please subscribe to sign in to comment.
Comment Sign In

Forgot password?
The Irish Times Logo
Thank you
You should receive instructions for resetting your password. When you have reset your password, you can Sign In.
The Irish Times Logo
Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.
Screen Name Selection

Hello

Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
Forgot Password
Please enter your email address so we can send you a link to reset your password.

Sign In

Your Comments
We reserve the right to remove any content at any time from this Community, including without limitation if it violates the Community Standards. We ask that you report content that you in good faith believe violates the above rules by clicking the Flag link next to the offending comment or by filling out this form. New comments are only accepted for 3 days from the date of publication.