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).
History:
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