Modified Lin-Kernighan-Helsgaun Based on Binary α

The Lin-Kernighan-Helsgaun algorithm is one of the most effective heuristics for the traveling salesman problem, and its performance largely depends on the candidate edge sets built from 1-tree based$\bold symbol{\alpha}$values. However, computing these$\alpha$values requires repeated 1 -tree construction and updates, which becomes a major preprocessing bottleneck on medium- and large-scale instances and complicates integration with other metaheuristics. This paper proposes a lightweight candidate-set construction method that replaces the classical 1tree$\alpha$computation with Minimum Spanning Tree (MST)guided binary$\alpha$strategy. A minimum spanning tree is first built as a global structural backbone, and multiple MST-guided initial tours are generated to identify frequently used edges. Each edge is then assigned a binary label indicating whether it appears in at least one initial tour, and candidate edges are selected by sorting incident edges using the binary label and edge cost. Experiments on TSPLIB instances show that the proposed method achieves solution quality comparable to classical The Lin-Kernighan-Helsgaun while reducing preprocessing time on many medium and large-scale instances, although the total runtime can occasionally be dominated by the downstream local search, demonstrating an effective trade-off between efficiency and performance for large-scale settings and hybrid frameworks.