New travelling salesman problem construction heuristics and their relationships to the 2-Opt

New travelling salesman problem construction heuristics and their relationships to the 2-Opt

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.