to be in the tour. This “importance” metric for edges is called $\alpha$-nearness and described in [@Cit:LKH; @Cit:TSP_sahai]. The algorithm has found great success on large instances of the TSP, see [@Cit:cook] for more details.

In [@Cit:TSP_sahai], the $\alpha$-nearness metric is replaced with a new Procrustes solution–based metric that prunes/identifies important potential edges to include in the “candidate set list”. This list is then used to generate the $k$-opt moves. The metric is captured in Fig. \[fig:distance\_vs\_procrustes\]. The Procrustes solution tends to capture the longer edges that are important. To increase the inclusion of the short edges, the approach in [@Cit:TSP_sahai] constructs a homotopy between the Procrustes ($P$-nearness) solution and the distance matrix. Using a graph Laplacian approach, the mixture of the two matrices is compared to the $\alpha$-nearness approach on 22 well-known instances of the TSP. $ P $-nearness based LKH converges to lower cost values in $18$ of the instances when compared to $\alpha$-nearness based LKH. Moreover, for $50$ random TSP instances of size $1000$ (cities) it is found that $P$-nearness has lower tour costs after a fixed number of $k$-opt moves in $31$ of the instances, translating into an improvement for $62\%$ of the instances.

![Illustration of 