Traveling salesman problem heuristics: Leading methods, implementations and latest advances |
| |
Authors: | César Rego Dorabela Gamboa |
| |
Institution: | a School of Business Administration, University of Mississippi, MS 38677, USA b Escola Superior de Tecnologia e Gestão de Felgueiras, CIICESI, GECAD, Instituto Politécnico do Porto, Apt. 205, 4610-156 Felgueiras, Portugal c University of Colorado, Boulder, CO 80309-0419, USA |
| |
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. |
| |
Keywords: | Traveling salesman problem Heuristics Ejection chains Local search |
本文献已被 ScienceDirect 等数据库收录! |
|