The \(\alpha \) -measure.
LKH ([1]} [1]}) proposes an \(\alpha \) -value instead of city distance as the measure for selecting and sorting cities in the candidate set, called the \(\alpha \) -measure, to improve the quality of the candidate set. The \(\alpha \) -value is defined from the structure of 1-tree ([3]} [3]}). A 1-tree for a graph \(G(V, E)\)  (\(V\)  is the set of nodes, \(E\)  is the set of edges) is a spanning tree on the node set \(V\backslash \lbrace v\rbrace \)  combined with two edges from \(E\)  incident to a node \(v\) , which is a special point chosen arbitrarily. Figure REF  shows a 1-tree. A minimum 1-tree is a 1-tree with minimum length, which can be found by determining the minimum spanning tree on \(G\)  and then adding an edge corresponding to the second nearest neighbor of one of the tree leaves. The leaf (i.e., the special point) chosen is the one that has the longest second nearest neighbor distance. Obviously, the length of the minimum 1-tree is the lower bound of the optimal TSP solution. An important observation is that 70-80% of the edges in the optimal solution of TSP are also in the minimum 1-tree ([1]} [1]}). Therefore, the LKH algorithm tries to define an \(\alpha \) -value using the minimum 1-tree to replace the distance used by LK. The equation of calculating the \(\alpha \) -value of an edge \((i,j)\)  is as follows:
\(\alpha (i,j) = L(T^+(i,j))-L(T),\) 
