This report describes an implementation of the Lin-Kernighan heuristic, a highly effective method for generating optimal or near-optimal solutions to the symmetric traveling salesman problem (TSP). The implementation has been shown to be highly effective, finding optimal solutions for all solved problem instances, including a 7397-city problem, the largest nontrivial problem instance solved to optimality today. The algorithm also improved the best known solutions for several large-scale problems with unknown optima, such as an 85900-city problem. The Lin-Kernighan heuristic is a local optimization algorithm that repeatedly performs exchanges to reduce the length of the current tour. The original algorithm, implemented by Lin and Kernighan in 1971, had an average running time of \( n^2 \) and could find optimal solutions for most problems with fewer than 100 cities. However, the implementation was complex and not straightforward to optimize. The new modified version of the algorithm differs from the original in several key aspects. It uses larger and more complex search steps, including sequential 5-opt moves, and employs sensitivity analysis to direct and restrict the search. The new algorithm also includes heuristic rules to limit and direct the search, such as restricting the candidate set to the α-nearest neighbors of each node, where α is a measure of nearness based on minimum spanning trees. These changes significantly improve the efficiency and effectiveness of the algorithm, allowing it to find optimal solutions for large-scale problems in reasonable running times. The report is organized into sections covering the traveling salesman problem, the original Lin-Kernighan algorithm, the modified algorithm, and its implementation. Computational experiments demonstrate the effectiveness of the new algorithm, showing that it can find optimal solutions for typical 100-city problems in less than a second and for 1000-city problems in less than a minute on a 300 MHz G3 Power Macintosh.This report describes an implementation of the Lin-Kernighan heuristic, a highly effective method for generating optimal or near-optimal solutions to the symmetric traveling salesman problem (TSP). The implementation has been shown to be highly effective, finding optimal solutions for all solved problem instances, including a 7397-city problem, the largest nontrivial problem instance solved to optimality today. The algorithm also improved the best known solutions for several large-scale problems with unknown optima, such as an 85900-city problem. The Lin-Kernighan heuristic is a local optimization algorithm that repeatedly performs exchanges to reduce the length of the current tour. The original algorithm, implemented by Lin and Kernighan in 1971, had an average running time of \( n^2 \) and could find optimal solutions for most problems with fewer than 100 cities. However, the implementation was complex and not straightforward to optimize. The new modified version of the algorithm differs from the original in several key aspects. It uses larger and more complex search steps, including sequential 5-opt moves, and employs sensitivity analysis to direct and restrict the search. The new algorithm also includes heuristic rules to limit and direct the search, such as restricting the candidate set to the α-nearest neighbors of each node, where α is a measure of nearness based on minimum spanning trees. These changes significantly improve the efficiency and effectiveness of the algorithm, allowing it to find optimal solutions for large-scale problems in reasonable running times. The report is organized into sections covering the traveling salesman problem, the original Lin-Kernighan algorithm, the modified algorithm, and its implementation. Computational experiments demonstrate the effectiveness of the new algorithm, showing that it can find optimal solutions for typical 100-city problems in less than a second and for 1000-city problems in less than a minute on a 300 MHz G3 Power Macintosh.