New TSP construction heuristics and their relationships to the 2-Opt
Correction heuristics for the traveling salesman problem (TSP), with the 2-Opt applied as a postprocess, are studied with respect to their tour lengths and computation times. This study analyzes the "2-Opt dependency," which indicates how the performance of the 2-Opt depends on the initial tours built by the construction heuristics. In accordance with the analysis, we devise a new construction heuristic, the recursive-selection with long-edge preference (RSL) method, which runs faster than the multiple-fragment method and produces a comparable tour when they are combined with the 2-Opt.
construction heuristic traveling salesman problem 2-opt dependency edge-exchange heuristic