This report presents an effective implementation of the Lin-Kernighan heuristic for solving the symmetric traveling salesman problem (TSP). The algorithm has been shown to find optimal solutions for all tested problem instances, including a 7397-city problem, the largest nontrivial problem solved to optimality. It also improves solutions for large-scale problems with unknown optima, such as an 85900-city problem. The Lin-Kernighan heuristic is a powerful method for finding optimal or near-optimal solutions for the symmetric TSP. It is more effective than the original algorithm, which has a time complexity of approximately $ n^{2.2} $. The new algorithm uses larger and more complex search steps, along with sensitivity analysis to guide the search. It is able to find optimal solutions for large problems in reasonable time, such as finding the optimal solution for a 100-city problem in less than a second and for a 1000-city problem in less than a minute. The algorithm is based on the concept of $ \lambda $-optimality, where a tour is $ \lambda $-optimal if no shorter tour can be found by replacing $ \lambda $ links. The algorithm dynamically adjusts $ \lambda $ during execution, aiming to find the optimal solution. It uses a set of rules to restrict and direct the search, including sequential exchange criteria, feasibility criteria, positive gain criteria, and disjunctivity criteria. The algorithm has been refined to improve efficiency and effectiveness. One key refinement is the use of $ \alpha $-nearness, a measure based on sensitivity analysis using minimum spanning trees. This measure helps identify edges that are likely to be part of an optimal tour. The $ \alpha $-measure is used to construct a candidate set of edges, which significantly improves the algorithm's ability to find optimal solutions. The algorithm also includes a subgradient optimization method to determine a penalty vector that maximizes a lower bound on the length of an optimal tour. This transformation of the cost matrix improves the $ \alpha $-measure, leading to better performance in finding optimal solutions. Overall, the implementation of the Lin-Kernighan heuristic is highly effective, capable of finding optimal solutions for large-scale problems in reasonable time. It has been shown to outperform the original algorithm in terms of both efficiency and solution quality.This report presents an effective implementation of the Lin-Kernighan heuristic for solving the symmetric traveling salesman problem (TSP). The algorithm has been shown to find optimal solutions for all tested problem instances, including a 7397-city problem, the largest nontrivial problem solved to optimality. It also improves solutions for large-scale problems with unknown optima, such as an 85900-city problem. The Lin-Kernighan heuristic is a powerful method for finding optimal or near-optimal solutions for the symmetric TSP. It is more effective than the original algorithm, which has a time complexity of approximately $ n^{2.2} $. The new algorithm uses larger and more complex search steps, along with sensitivity analysis to guide the search. It is able to find optimal solutions for large problems in reasonable time, such as finding the optimal solution for a 100-city problem in less than a second and for a 1000-city problem in less than a minute. The algorithm is based on the concept of $ \lambda $-optimality, where a tour is $ \lambda $-optimal if no shorter tour can be found by replacing $ \lambda $ links. The algorithm dynamically adjusts $ \lambda $ during execution, aiming to find the optimal solution. It uses a set of rules to restrict and direct the search, including sequential exchange criteria, feasibility criteria, positive gain criteria, and disjunctivity criteria. The algorithm has been refined to improve efficiency and effectiveness. One key refinement is the use of $ \alpha $-nearness, a measure based on sensitivity analysis using minimum spanning trees. This measure helps identify edges that are likely to be part of an optimal tour. The $ \alpha $-measure is used to construct a candidate set of edges, which significantly improves the algorithm's ability to find optimal solutions. The algorithm also includes a subgradient optimization method to determine a penalty vector that maximizes a lower bound on the length of an optimal tour. This transformation of the cost matrix improves the $ \alpha $-measure, leading to better performance in finding optimal solutions. Overall, the implementation of the Lin-Kernighan heuristic is highly effective, capable of finding optimal solutions for large-scale problems in reasonable time. It has been shown to outperform the original algorithm in terms of both efficiency and solution quality.