# jsyang/TSP-Heuristics

k-opt operators to solve the Traveling Salesman Problem
Switch branches/tags
Nothing to show
Latest commit 0ff23fa May 13, 2011
 Failed to load latest commit information. README Apr 5, 2011 entity.js Apr 19, 2011 gLayer.js Apr 4, 2011 jsyang.tsp Mar 7, 2011 kopt.html May 13, 2011 koptWorkers.html Apr 19, 2011 ops.js Apr 19, 2011 worker.js Apr 19, 2011

```Traveling Salesmen Problem heuristics
jsyang.ca@gmail.com

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.

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

_/_                                  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