next up previous
Next: 2. Construction Heuristics Up: TSP Algorithms in Action Previous: TSP Algorithms in Action


1. Introduction

A salesman has to visit N cities with given distances dij between cities i and j, returning finally to his city of origin. Each city is to be visited only once, and the route is to be made as short as possible. A popular special case is the Euclidean TSP, where the cities are given by their positions (xi,yi) in the plane and the distance matrix is given by the Euclidean distance,

d_{ij} = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}.

The Travelling Salesman Problem (TSP) is the most prominent problem in combinatorial optimization [1]. It has attracted - and still attracts - researchers from various fields.

Any known algorithm that claims to find the true optimum tour has a running time that grows exponentially with the number N of cities. Since TSP is NP-complete this will hold for any future algorithm - at least with high probability. Therefore efforts have concentrated on the development of heuristic algorithms, that do not aim to find the shortest tour but a tour that is reasonable short. Such approximate algorithms incorporate ideas that range from simple to highly sophisticated, and some of them give results that come very close to the optimum solution [2].

This is an introduction to some these approximate TSP algorithms. It contains animated, graphical implementations that allows you watch the algorithms in action and to play around with them. To use the animations, you should read the section ``Notes on the Java-Applets'' 1.1 first.

The author appreciates any comments. Enjoy.

1.1 Notes on the Java-Applets

The Java-Applets are animated demonstrations of TSP algorithms. These buttons and checkboxes are common to all applets:

The applets have been tested to run within Netscape Navigator 4.5 under the Linux and Solaris Operating Systems, but according to the Java philosophy they should run within any browser that supports Java. In practice, you need Netscape 4.06 or higher since the applets use JDK 1.1 which is not supported by earlier releases. If you encounter any error you should check whether your browser supports JDK 1.1. Note that sometimes you have to enable Java in your browser. For the Netscape Navigator the corresponding checkbox can be found under preferences/advanced.

1.2 Related WWW Resources

Please notify the author if you know additional resources.

next up previous
Next: 2. Construction Heuristics Up: TSP Algorithms in Action Previous: TSP Algorithms in Action
Stephan Mertens