The Traveling Salesman Problem (TSP) is a prominent challenge in combinatorial optimization. It involves a set of cities and the costs associated with traveling between each pair. The objective of the TSP is to determine the most cost-effective route for visiting all cities and returning to the starting point.

​

The TSP can also be framed as the problem of finding a Hamiltonian cycle of minimum weight in an edge-weighted graph.

​

The Lin-Kernighan algorithm is categorized as a local search algorithm. Such algorithms begin at a specific point in the search space and move to neighboring locations iteratively.

​

This algorithm is defined by a series of exchanges that transform one candidate solution into another. Starting with a feasible TSP tour, the Lin-Kernighan algorithm repeatedly applies exchanges that reduce the length of the current tour until no further improvements can be made. This process can be executed multiple times using initial tours generated randomly.

​

The Lin-Kernighan algorithm (LK) specifically utilizes k-opt moves on tours. A k-opt move modifies a tour by replacing k edges with k different edges, resulting in a shorter tour.