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
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 ...