Traveling salesman problem heuristics: Leading methods, implementations and latest advances

Traveling salesman problem heuristics: Leading methods, implementations and latest advances

0.00 Avg rating0 Votes
Article ID: iaor20112740
Volume: 211
Issue: 3
Start Page Number: 427
End Page Number: 441
Publication Date: Jun 2011
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: heuristics
Abstract:

Heuristics for the traveling salesman problem (TSP) have made remarkable advances in recent years. We survey the leading methods and the special components responsible for their successful implementations, together with an experimental analysis of computational tests on a challenging and diverse set of symmetric and asymmetric TSP benchmark problems. The foremost algorithms are represented by two families, deriving from the Lin–Kernighan (LK) method and the stem‐and‐cycle (S&C) method. We show how these families can be conveniently viewed within a common ejection chain framework which sheds light on their similarities and differences, and gives clues about the nature of potential enhancements to today’s best methods that may provide additional gains in solving large and difficult TSPs.

Reviews

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