TSP Solver

2011-08-01

The travelling salesman problem (TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

Iteratively solving the Travelling Salesman problem with k-opt operations

1

Fast operations such as 2-Opt are less computationally expensive, but due to
granularity, more likely to become stuck in local extrema. The higher level
operations such as 3- or 4-Opt are less likely to be trapped in the extrema.

Parallelization, if permitted in the solution, also reduces the runtime cost.

Sept. 17, 2010  Original implementation
Apr.   4, 2011	Removed dependency on raphael.js; refactored everything.
                Created a more detailed README.

--------------------------------------------------------------------------------
Object		Description

Loc			Location - predefines some aspect of the distance of the tour.
			Contains a distance function specific to this geometry: Euclidean.

Tour		Essentially a sequence of Locations. The tour distance is a
			function of its Location visit sequence.
			Can also replace the current sequence if a new sequence has an
			improved tour distance.

--------------------------------------------------------------------------------
Heuristic	Description

CLUSTER     Group locations into clusters (neighborhoods) and optimize the graph
            within the clusters in parallel.

2-FLIP      Reverses a subsequence of the tour.
3-MOVE      Moves a subsequence within a sequence.
3-SPLIT     Splits a sequence into 2 sequences each carried out in parallel.
4-SWAP      Swap 2 subsequences from different Tours.

--------------------------------------------------------------------------------
2-Opt: FLIP operation

    Reverse a selected portion of the original Tour. For example:

       Head
     _/_                                  Interior
    |   |      Body                     - B - C - D - E -
         _____/_____
        |           |     Tail            Exterior
                         /              A -  ..  F -
                        |
        i           j          2-OPT      Interior reversed
    A - B - C - D - E - F      ---->    A - E - D - C - B - F

                                          Exterior reversed
                                        F - B - C - D - E - A

    Reversing the order of either interior or exterior completes the 2-opt.
	Though the direction of the sequence is different in between these cases,
	the geometry of the Tour remains the same; "unknotting" any crossed paths.

--------------------------------------------------------------------------------
3-Opt: MOVE operation

	Move a subsequence to a new position within the same Tour; treating the
    segment as a single location in the larger sequence.

    i       Starting index of the segment
    l       Segment length
    shift   Where to shift to the new position

    Cut the segment from the old sequence, and build the new sequence by
    adding anything before the start index, the segment and then appending any
    remaining Locations in the old sequence that weren't in the segment.

                  Length 3
                  Segment         3-OPT MOVE           Shift   New position
             ____/__              SHIFT BY 1          /   ____/__
            |       |               ----->           |   |       |
    A - B - C - D - E - F - G                A - B - F - C - D - E - G
                        1
                        |
                       /
                  Shift


                  Length 3
                  Segment         3-OPT MOVE             Shift     New position
             ____/___             SHIFT BY 2          __/_    ____/___
            |       |               ----->           |   |   |       |
    A - B - C - D - E - F - G                A - B - F - G - C - D - E
                        1   2
                        |___|
                         /
                    Shift

--------------------------------------------------------------------------------
3-Opt: SPLIT operation

    Split a subsequence of a Tour off into another Tour (can be empty).
    Much like the MOVE operation, we extract a subsequnce of a specified length
    from the first Tour and put it somewhere in the destination Tour.
    The resulting Tours should begin at the same location if not roundtrip.

    i       Starting index of segment
    l       Segment length
    j       Insertion index in destination Tour


              Length 3
              Segment         3-OPT SPLIT      Original Tour
         ____/__              INTO NEW TOUR    A - E - F - G
        |       |               ----->
    A - B - C - D - E - F - G                     New Tour
                        1                      A - B - C - D
                        |
                       /                     Total DISTANCE of Tours should
                  Shift                      follow the triangle inequality.

--------------------------------------------------------------------------------
4-Opt: SWAP operation ...
 

Source code

See code on GitHub