# 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)