University of Twente Student Theses
Experimental Analysis of the Lin-Kernighan heuristic
Idzenga, A.N. (2023) Experimental Analysis of the Lin-Kernighan heuristic.
|
PDF
1MB |
| 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: | https://purl.utwente.nl/essays/96650 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page