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


    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)