1. Introduction

A salesman has to visit N cities with given distances d_ij 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 (x_i,y_i) 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:

• new: Press this button to generate a new random instance of an Euclidean TSP.
• reset: Press this button to remove all edges, tours and partial tours from the display. The TSP instance is preserved. This button can be used to restart the algorithm.
• step: Perform a single step of the algorithm.
• run: Automatic execution of the algorithm. The single steps of the algorithm are triggered in constant time intervals. The interval can be set in the speed checkboxes. While the algorithm is running, the run button changes into a stop button that allows you to pause the execution.
• solve: Press this button to see the true optimum tour. Note that the calculation of the true optimum may take some time, depending on the instance and on the platform the applet is running on. While the solver is running, the solve button turns into a cancel button that allows you to abort the calculation.
• nodes: Select the number of nodes (cities) with these checkboxes.
• speed: Select the speed of animation with these checkboxes (see run button above)

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

• http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html TSPBIB Home Page: This page intends to be a comprehensive listing of papers, source code, preprints, technical reports, etc, available on the Internet about the TSP and some associated problems. Maintained by Pablo Moscato.
• http://www-c.mcs.anl.gov/home/otc/Guide/faq/linear-programming-faq.html#Q6.10 What software is there for the TSP?
• http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html TSPLIB is a library of sample instances for the TSP (and related problems) from various sources and of various types.
• http://www.wiwi.uni-frankfurt.de/~stockhei/touropt.html A Java applet that demonstrates some heuristics on the TSP

Please notify the author if you know additional resources.