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