A note on single alternating cycle neighborhoods for the TSP
This paper investigates two different local search approaches for the TSP. Both approaches are based on the general concept of single-alternating cycle neighborhoods. The first approach, stems from the famous heuristic suggested by Lin and Kernighan and the second is based on the notion of stem-and-cycles developed by Glover in the early nineties. We show that the corresponding neighborhoods are not identical and that only a subset of moves can be found when Lin & Kernighan's gain criterion is applied.
tsp local search edge-exchange neighborhoods lin-kernighan ejection chains