Computer Science – Data Structures and Algorithms
Scientific paper
2010-05-30
European Journal of Operational Research 219 (2012) 234-251
Computer Science
Data Structures and Algorithms
29 pages
Scientific paper
10.1016/j.ejor.2012.01.011
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.
Gutin Gregory
Karapetyan Daniel
No associations
LandOfFree
Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-161931