Computer Science – Data Structures and Algorithms
Scientific paper
2010-03-27
European Journal of Operational Research 208(3), pages 221-232, 2011
Computer Science
Data Structures and Algorithms
25 pages
Scientific paper
10.1016/j.ejor.2010.08.011
The Lin-Kernighan heuristic is known to be one of the most successful heuristics for the Traveling Salesman Problem (TSP). It has also proven its efficiency in application to some other problems. In this paper we discuss possible adaptations of TSP heuristics for the Generalized Traveling Salesman Problem (GTSP) and focus on the case of the Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the Lin-Kernighan algorithm for the GTSP reproduces the success of the original heuristic. Different variations of our adaptation outperform all other heuristics in a wide range of trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search.
Gutin Gregory
Karapetyan Daniel
No associations
LandOfFree
Lin-Kernighan Heuristic Adaptations 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 Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-127529