A note on single alternating cycle neighborhoods for the travelling salesman problem

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 & Kerninghan's gain criterion is applied.