Implementation analysis of efficient heuristic algorithms for the traveling salesman problem

Implementation analysis of efficient heuristic algorithms for the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20072094
Country: United Kingdom
Volume: 33
Issue: 4
Start Page Number: 1154
End Page Number: 1172
Publication Date: Apr 2006
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

The state-of-the-art of local search heuristics for the traveling salesman problem (TSP) is chiefly based on algorithms using the classical Lin–Kernighan (LK) procedure and the stem-and-cycle (S&C) ejection chain method. Critical aspects of implementing these algorithms efficiently and effectively rely on taking advantage of special data structures and on maintaining appropriate candidate lists to store and update potentially available moves. We report the outcomes of an extensive series of tests on problems ranging from 1000 to 1,000,000 nodes, showing that by intelligently exploiting elements of data structures and candidate lists routinely included in state-of-the-art TSP solution software, the S&C algorithm clearly outperforms all implementations of the LK procedure. Moreover, these outcomes are achieved without the use of special tuning and implementation tricks that are incorporated into the leading versions of the LK procedure to enhance their computational efficiency.

Reviews

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