Lin-Kernighan TSP edge choice

Question

Step 4a of the original paper describing the Lin-Kernighan TSP algorithm states that the choice of edge $x_i = (t_{2i}, t_{2i+1})$ to be deleted is uniquely determined by the choice of edge $y_{i-1} = (t_{2i-1}, t_{2i})$ previously added. Helsgaun elaborates on this by saying:

"... only one of these makes it possible to ‘close’ the tour (by the addition of $y_i$). The other choice results in two disconnected subtours"

Can somebody explain why this is the case, and how to tell which choice of $x_i / t_{2i}$ given some $y_{2i-1}$ is correct?

I have an idea (that I'm not sure is correct) of a way to test if a tour contains disconnected subtours*, but doing so would force you to build a tour $T'$ from $T, X, Y$ at every step of a k-opt move, which is inefficient.

---

*if tour is a list of cities containing a disconnected subtour then some city must be visited twice, so you could do something like len(set(tour)) == len(tour) in python

Answer 1

It might help to refer to Figure 3(a) in the Lin-Kernigan paper. Assume that you started out with the tour oriented so that the nodes were visited in the order $$t_1 \rightarrow t_2 \rightarrow \dots \rightarrow t_4 \rightarrow t_3 \rightarrow \hat{t} \dots -\rightarrow t_1,$$where $\hat{t}$ is the unlabeled endpoint of the $y_2$ edge opposite $t_4.$ You choice of $y_1$ put the focus on node $t_3,$ forcing you to choose for deletion one of the two edges ($(t_3, t_4)$ or $(t_3, \hat{t})$) incident to $t_3$ and present in the original tour. The key is that $t_4$ occurs between $t_2$ and $t_3$ in the original tour, and $\hat{t}$ does not. You are going to add the edge $y_1 = (t_2,t_4)$ to the tour. If you leave $(t_3,t_4)$ in the tour while adding $y_1$, you end up with a subtour $$t_2\rightarrow \dots \rightarrow t_4 \rightarrow t_3 \rightarrow t_2$$ (the last arc courtesy of $y_1$).

More generally, if you delete an arc $t_i \rightarrow t_j$ and add an arc $t_j \rightarrow t_k$, then the arc incident at $t_k$ that you delete is the one whose other endpoint was between $t_j$ and $t_k$ before the changes when the tour is oriented $t_i \rightarrow t_j \rightarrow \dots \rightarrow t_k \rightarrow \dots \rightarrow t_i.$

Answer 2

In Section 5.3 of

K. Helsgaun, General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation, 1(2-3):119-163 (2009).

it is demonstrated how the feasibility of a k-opt move can be determined in O(k log k) time.