Article ID: | iaor20002458 |
Country: | Netherlands |
Volume: | 5 |
Issue: | 1 |
Start Page Number: | 71 |
End Page Number: | 88 |
Publication Date: | Mar 1999 |
Journal: | Journal of Heuristics |
Authors: | Okano H., Misono S., Iwano K. |
Correction heuristics for the traveling salesman problem, 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 method, which runs faster than the multiple-fragment method and produces a comparable tour when they are combined with the 2-Opt.