# 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