JAVA Traveling Salesperson Problem (TSP) info

This JAVA applet implements a solution for the symetric traveling sales person problem (TSP). In this problem a salesperson has to visit all of N cities, returning to the starting point, while using the shortest posible route.
first attempt: (not available now)
The algorithm does an exhaustive best first search, but uses several heuristics to prevent the search of nodes that never lead to a solution. One of these is a look ahead feature that (under)estimates the length of the route throug the remaining cities.
second attempt:
This was nice, but to improve the algorithm I had to improve the upper bound. So the current version evolved, It uses a fast approximation method to compute a reasonable tour even for a large number of cities (up to 30.000). The methods used are 2opt (removing 2 edges, and connecting the opposite nodes), partial 3opt (the same for 3 edges) and "double bridging 4opt" (a 2opt move that forms 2 seprate tours, reconnected by another 2opt). Although the 4opt seems quite cpu intensive, it yields greater improvements. It appears that the algorithm with the 4opt is both faster and better than without. Try the checkbox "opt4" to see the difference.
The performance is very good (318 points in 0.04 sec on P300).
third attempt:
Simulated annealing added a further improvement. This makes a few dirtortions is the best solution found, and reoptimizes on this. If an improvement is found, it replaces the last one found. This is repeated until a fixed number of failures is found (selectable from the "iterations" listbox). This gives a great improvement on the result, for the LK318 problem we get an average of 0.05% over the optimal solution in 40 seconds per try (for iterations set to 100).

My interest in combinatorial problems started in 1971, when in a COBOL class some of us implemented the Knights problem for a 5*6 field. This ran in 2 minutes on an IBM 360-40 computer.
In 1976 to 1985 I used this as a standard app when learning other languages (IBM 360 assembler, C and PROLOG).
In 1983 we toook part in a sailing tournament where we had to find an optimal route selecting from a given set of nodes in order to finish within a timelimit of 16 hours. With the Knights problem program as basis I implemented this in IBM 370 assembler. In 1985 this program ran on a HP 8086 laptop PC emulating 370 instructions so we could take it on board. The program was modified in order to be interactively used, allowing us to take variations in wind direction and speed, which was impossible with the offline version. Due to the very limited posibility for test runs the program never worked perfect, but it had some nice optimisations (heuristics), while it had to make real time decisions. In 1989 the program was converted to C.
In 1992 I did my last sailing match, and development stopped (I had liked to implement a direct coupling to the GPS positioning system, allowing for continuous decision making, and even changing current decisions when circumstances change (wind shift)).
In 1990 the sailing C program was stripped down to a Symetric Traveling Salerperson Program.
The next project was a PROLOG program to select the best team of athletes, where a limited number of athletes had to perform a fixed number of tasks, and each of them was allowed to 0,1 or 2 tasks. Each athlete has different abilities for each task, and some tasks cannot be combined (e.g. 800m and Long jump occur at the same time, as do Short put and 100m).
Then this year JAVA came, and the TSP program was a good choice to use as a template. Conversion to a procedural JAVA program could be done in one evening, the graphical interface was added and confrontated me with a lot of ugly things. It was nice to see what was going wrong, crossing lines, forgotten points and more.
The first version was strugling with 7 points. The procedural version was converted to a somewhat more OO approach, and the DEMO sets were added in order to test with a predefined set of points (including some samples of the TSPLIB). Lots of new heuristics were added, and some programming tricks made the program even faster.

External references

for more information: Email Onno Waalewijn