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)