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

This question reminds me of a question I asked a couple of months ago https://or.stackexchange.com/questions/6729/traveling-salesman-problem-determine-k-exchange-feasibility — fontanf, Apr 19 '22 at 21:53

score 5 · Answer 1 · answered Apr 24 '22 at 14:01

5

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.

answered Apr 24 '22 at 14:01

Keld Helsgaun

51
1

Great! I think this answers my question – fontanf Apr 24 '22 at 17:04

score 4 · Accepted Answer · answered Apr 19 '22 at 19:47

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.$

Thanks! I get the impression that the best approach is to apply swaps $x_i, y_i$ as they come, rather than only maintaining $X, Y$, to make it easier to check which side of the tour some $t_{2i}$ belongs to. — llilibbou, Apr 20 '22 at 14:53
Let's say that you number the nodes in initial tour from 1 to $n$, and let $x_h$ be the number assigned to node $t_h$. When you are looking at deleting arc $t_i \rightarrow t_j,$ compute new numbers $y_h = x_h - x_i (\textrm{mod } n),$ which results in $y_i = 0,$ $y_j = 1$ and $y_k > 1.$ Now you just have to pick the neighbor $t_\ell$ of $t_k$ for which $y_\ell \le y_k.$ That should make shopping for swaps pretty easy. Once you execute a swap, though, you have to renumber the tour (reset the $x_h$ values). — prubin, Apr 20 '22 at 15:42

Lin-Kernighan TSP edge choice

2 Answers2