Lin - Kernighan algorithm for the Travelling Salesman Problem and an application to the Travelling Thief Problem

The Lin-Kernighan algorithm is one of the best performing heuristics for the Travelling Salesman Problem (TSP). In this thesis the literature on the TSP is discussed and a thorough explanation of the Lin-Kernighan algorithm and all state-of-the-art extensions are given. We implement the original algorithm by Lin and Kernighan (1973) and perform an experimental analysis on various TSPlib instances to test the algorithm’s performace. We find runtimes to grow with rate approximately equal to n2:6 and the performance worse than reported in the literature. Additionally, we look at a relatively new benchmark problem: the Travelling Thief Problem (TTP). The TTP tries to capture the interdependency between subproblems present in many real-life problems in a benchmark problem by combining the TSP with the Knapsack Problem. An overview of the current solvers is given and a new construction algorithm, the Lin-Kernighan Modified Distance (LKMD) algorithm, is proposed. While most current state-of-the-art construction algorithms first pick a tour and then try to find a packing plan, the LKMD does the opposite: it first constructs a packing plan, which is afterwards used to find a good tour. The algorithm is tested on the 30 eil51 TTP instances. While overall solution quality of the algorithm is good, the running times are 60 times larger than the other construction algorithms. Still, the algorithm may serve as inspiration for further attempts to find heuristics that exploit the interdependency between the two subproblems.