Introduction

The Travelling Salesman Problem (TSP) is a deceptively simple combinatorial problem. It can be stated very simply:

A salesman spends his time visiting n cities (or nodes) cyclically. In one tour he visits each city just once, and finishes up where he started. In what order should he visit them to minimise the distance travelled?

If there are only 2 cities then the problem is trivial, since only one tour is possible. For the symmetric case a 3 city TSP is also trivial. If all links are present then there are (n-1)! different tours for an n city asymmetric TSP. To see why this is so, pick any city as the first - then there are n-1 choices for the second city visited, n-2 choices for the third, and so on. For the symmetric case there are half as many distinct solutions - (n-1)!/2 for an n city TSP. In either case the number of solutions becomes extremely large for large n, so that an exhaustive search is impractible.

The problem has some direct importance, since quite a lot of practical applications can be put in this form. It also has a theoretical importance in complexity theory, since the TSP is one of the class of "NP Complete" combinatorial problems. NP Complete problems have intractable in the sense that no one has found any really efficient way of solving them for large n. They are also known to be more or less equivalent to each other; if you knew how to solve one kind of NP Complete problem you could solve the lot.

The holy grail is to find a solution algorithm that gives an optimal solution in a time that has a polynomial variation with the size n of the problem. If you could find a method whose solution time varies like a quadratic expression, for example, then doubling n multiplies the solution time by 4 for large n. The best that people have been able to do, however, is to solve it in a time that varies exponentially with n. Such algorithms run out of puff at a certain level of n, more or less independently of computing power. If computation varies as 2^n, say, then a thousand-fold increase in computing power will only allow you to add another 10 nodes. So an algorithm that peters out at 50 cites now will probably never get you to 100 nodes, whatever happens to hardware technology.

Alternatively there are algorithms that seem to come up with a good solution quite quickly, but you cannot say just how far it is from being optimal.

Getting the feel of it

The first algorithm looks for a true optimum tour by doing a truncated search of the entire solution space - known as the Branch and Bound technique. It reaches an initial tour very quickly, and then continues to search, finding better tours and/or establishing that no shorter tour exists. As each tour is found it is drawn on the screen, and details are entered in a file called tsp.log. This algorithm is quite fast up to about 25 nodes, but becomes painfully slow beyond 40.

The good news is that you can truncate the search at any time by hitting any key. You can also set a % bound margin; setting this to 10 means that you wind up with a tour whose length is within 10% of the shortest - but you get there rather more quickly than if you insist on a true optimum (margin=0). If you like you can set the margin at 100, so it gives up immediately after finding the solution.

The second algorithm  starts from a random tour and seeks to improve it using an algorithm base on dynamic programming. When no further improvement is obtainable the tour is displayed and details are logged. The process is repeated using 5 different random starting points. You will see that the algorithm is fast for problems with up to 100 nodes (the limit of the program). It often finds the true optimum tour and, when it doesn't, gets within a couple of percent of the shortest length. Because the first algorithm runs out of puff above 40 nodes, however, it is hard to say how well it sustains its performance for really large problems.

It is interesting, however, to see how very different near-optimal tours can be - especially for really large problems with around 100 nodes. To improve on a good solution you really do have to make a lot of changes. No wonder this problem is so intractible!

To download the program press here

This will give you a self extracting archive which expands into tsp.exe and egavga.bhi (a graphics device driver needed by tsp.exe). This program is copyright by me, but you are free to use it for fun.

To run this program type, at the DOS prompt,
tsp n p m r

• n is number of nodes (10-100, default 10)
• p is number of problems to generate and solve (default 1)
• m is search accuracy (default 2) - will find tour whose length is within m% of the shortest - set to 0 for true optimum, 100 to give up after the first tour is found
• r is "r" or "R" to cause initial randomisation - so every run gives a different sequence of problems; otherwise the random number generator always starts from a common "seed" and and so generates the same sequence of problems every time. This helps when you are comparing algorithm variants.

Please Email me if you have any comments

Other TSP sources: See the TSPBIB Home Page for a comprehensive set of TSP links.

© Copyright Robert Dakin 1996-2002
Last updated 6 September 2002