Exact Traveling Salesman Problem (TSP)
Exact implementation for the Traveling Salesman Problem
Also solves Asymmetric TSP's - see demo's
The following actions are performed to compute the shortest path:
- make an initial path by greedy or nearest neighbour assignments
- improve this by Opt4, Opt2 and Opt3 moves
- improve this again by Simulated Annealing
- then start an exhaustive search, with the upperbound found in the previous step
- here we backtrack if the lowerbound found by computing the Minimum Spanning Tree for the unassigned cities exceeds the upperbound
- improve the lowerbound by Lagrangean Relaxation
- for 2d problems I also try to exclude crossings in the path using opt2 (still thinking about opt3/4)
- I also try to find points close to but not in the path yet, that can be proven to belong in the path
usage:
While computing the optimal solution intermediate results are shown at 5 second intervals:
The black line shows current path, red line shows MST, green is best found yet
Interrupt by pressing the Break button
The knights 5*6 and 8*8 are not true TSP problems, but the Knights problem for a
5*6 and a 8*8 chessboard. The Knight has to make a closed tour, touching each square exact once
It is modified to a TSP
problem by setting valid knight moves to a distance of 0, and invalid moves to 1.
I included this because it was the first problem I solved in this field.
(1971, using COBOL on a IBM 360-40, runningtime 150 seconds...)
See also: Traveling Salesman Problem heuristic version,
up to 20000 cities with many TSPLIB examples
Email:
Onno Waalewijn
more information
links to related sites
my other applets (Quadratic assignment, Laser cutting)