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: | Glover Fred, Rego Csar, Gamboa Dorabela, Osterman Colin |
Keywords: | heuristics |
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