LinKernighan heuristic adaptations for the generalized traveling salesman problem
The LinKernighan 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 LinKernighan algorithm. At first, we provide an easy-to-understand description of the original LinKernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the LinKernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the LinKernighan 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 LinKernighan the state-of-the-art GTSP local search.
linkernighan heuristics generalized traveling salesman problem combinatorial optimization