5
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ This question reminds me of a question I asked a couple of months ago or.stackexchange.com/questions/6729/… $\endgroup$
    – fontanf
    Apr 19, 2022 at 21:53
  • $\begingroup$ Interesting. Did you make any progress? $\endgroup$
    – llilibbou
    Apr 20, 2022 at 14:50
  • $\begingroup$ No, but I didn't spend a lot of time on it $\endgroup$
    – fontanf
    Apr 20, 2022 at 15:00

2 Answers 2

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – llilibbou
    Apr 20, 2022 at 14:53
  • 1
    $\begingroup$ 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). $\endgroup$
    – prubin
    Apr 20, 2022 at 15:42
  • $\begingroup$ Thank you, that makes perfect sense $\endgroup$
    – llilibbou
    Apr 21, 2022 at 11:02
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Great! I think this answers my question $\endgroup$
    – fontanf
    Apr 24, 2022 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.