Solving the Travelling Salesman Problem

Felix Andrews, 2003

A project for Case Studies in Advanced Computation, a course at the Australian National University.

Compututational power was provided by the APAC National Facility.

1. introduction

The Travelling Salesman Problem (TSP) is the optimisation of a tour through a set of cities so that it is as short as possible. More generally, the problem is to find the shortest path going through each one of a set of points once and only once, and returning to the starting point. Even more generally, it is the combinatorial minimisation of some cost function. The TSP has applications in surprising places; see the Solving TSPs site at Princeton University.

In this study I evaluated some algorithms for solving the TSP.

2. methods and code

• finding the exact solution

• code structure

• uniform random sampling

• simulated annealing

• an evolutionary algorithm

• parallelisation

3. Western Sahara: 29 cities

• uniform random sampling

• simulated annealing

• evolutionary algorithm
  

4. Canada: 4663 cities

• simulated annealing

• evolutionary algorithm

• parallelisation
  

5. conclusions

The best method of those tried depends on the problem size. For the small problem a simple evolutionary approach with a small population and rank selection was extremely efficient. However, it didn't scale well to the larger problem. Simulated Annealing performed fairly well on that problem. It was also quite efficient and certainly usable for the smaller one, so overall is probably the better method. It is a bit grand to call it Simulated Annealing since there was very little benefit found from using a temperature above zero. The algorithm is then simply to adopt beneficial perturbations.

A sizable advantage was found from using greedy initial tours, especially with the evolutionary algorithm. It may be speculated that a genetic algorithm could take more advantage of this, by recombining segments of several locally optimal tours. Unfortunately there was not enough time to try a real genetic algorithm here.

The benefit attained from running a parallel simulated annealing was marginal. Genetic methods are probably better suited to parallelisation.

The effect of 'temperature' in Boltzmann selection depends on the problem scale. It would probably be a lot easier to use a non-parameterised selection method. This could be as simple as the weighted probability of Fogel (1988), or sophisticated as in the Enhanced Genetic Algorithm approach of Yang & Stacey (2001).