University of Twente Student Theses


Experimental Analysis of the Lin-Kernighan heuristic

Idzenga, A.N. (2023) Experimental Analysis of the Lin-Kernighan heuristic.

[img] PDF
Abstract:The Traveling Salesman Problem is a combinatorial optimization problem with many applications. In the problem, the goal is to find a Hamiltonian tour of min- imum cost in a graph. As finding the global optimum is difficult, many heuristics have been developed. These heuristics find tours of low, but not necessarily optimal, cost in reasonable time. The Lin-Kernighan heuristic is one of the best heuristics for the Traveling Salesman Problem. Theoretical analysis for this heuristic seems to be difficult, as we show in this paper. Therefore we investigate the heuristic experimen- tally. We find that the average number of iterations with respect to the input size is linear. The effect of four different settings of the heuristic are investigated. Two of the settings influence the slope of the linear relationship. The other two settings do not significantly influence the average number of iterations.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page