2010/05/31 by Daniel Karapetyan, Gregory Gutin · 66 citations
Computer Science · Engineering · Mathematics · #2-opt #Advanced Graph Theory Research #Algorithm #Bottleneck traveling salesman problem #Combinatorial optimization #Computer science #Graph Labeling and Dimension Problems #Heuristics #Lin–Kernighan heuristic #Local search (optimization) #Mathematical optimization #Mathematics #Set (abstract data type) #Traveling purchaser problem #Travelling salesman problem #Vehicle Routing Optimization Methods #cs.DS
paper · pdf · doi:10.1016/j.ejor.2012.01.011
published in European Journal of Operational Research 219(2), 234-251 (Elsevier BV) · 29 pages
openalex publication_date 2012/01/13 · arxiv created 2012/02/13 · arxiv updated 2012/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The Generalized Traveling Salesman Problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once. While the GTSP is a very important combinatorial optimization problem and is well studied in many aspects, the local search algorithms used in the literature are mostly basic adaptations of simple TSP heuristics. Hence, a thorough and deep research of the neighborhoods and local search algorithms specific to the GTSP is required. We formalize the procedure of adaptation of a TSP neighborhood for the GTSP and classify all other existing and some new GTSP neighborhoods. For every neighborhood, we provide efficient exploration algorithms that are often significantly faster than the ones known from the literature. Finally, we compare different local search implementations empirically.