Lin-Kernighan and a Modified Heuristic for Solving the 2-Cycle Cover Problem

In this thesis the focus lies on the Lin-Kernighan heuristic algorithm for the symmetric Traveling Salesman Problem (Lin & Kernighan, 1973). This heuristic dates from 1973 but is still considered a top-notch heuristic. It has an iterative approach and starts with a feasible solution. It finds better solutions by sequentially exchanging edges. When no more improvements can be found a solution is obtained which is better than the previous. In this study the algorithm is implemented in its most basic form. The heuristic performs well on small instances and finds the optimal solution on the smallest instances we tested on. As in the original implementation, effectiveness decreases with problem size. In this thesis, also a new heuristic is proposed for the 2-CCP. In this problem the goal is to find two disjoint tours of minimum total length. The proposed algorithm starts with a feasible TSP solution and transforms it into a 2-CCP also by a sequential exchange of edges. This algorithm is shown to perform well on small instances as well. The heuristic performs well under the condition that the starting tour is a good solution for the TSP. We conclude that the modified algorithm is an effective method for transforming TSP solutions into 2-CCP solutions.