Sequential moves: improving and promising

Improving move condition

A move is improving when it is valid and it improves a tour. Any k-opt move that improves a tour must fulfill the condition:

Sum of lengths of links removed from tour must be greater than sum of links added to tour.

In other words:

delLength - addLength > 0

Let us take a sequential move. Then g1 defined by:

g1 = distance(c1, c2) - distance(c2, c3)

is a partial gain obtained from the first step in sequence. If a sequence consists of more than two steps, then g2 defined by:

g2 = distance(c3, c4) - distance(c4, c5)

is a gain obtained from the second step in sequence. Gain obtained so far, from these two moves, is then equal:

G_2 = g1 + g2

In general:

$$G_k = \sum_{i=1}^{k} g_i$$

g1 = distance(c1, c2) - distance(c2, c3)  # gain from step 1
g2 = distance(c3, c4) - distance(c4, c5)  # gain from step 2
g3 = distance(c5, c6) - distance(c6, c7)  # gain from step 3
...
G_k = g1 + g2 + g3 + ...

The last step of valid sequential k-opt move and then a gain from this step deviate from above pattern. This is because we must connect last city of sequence not with some next one, but with the first one:

# gain from the last, closing-up step
# Note `c1` in second distance
g_k = distance(c_2k1, c_2k) - distance(c_2k, c1)

G_k = g1 + g2 + g3 + ... + g_k

So total gain from a sequential move is sum of gains from each step of this move. Although some of g1, g2, g3... may be negative, when this sum of numbers is positive then the move is an improving move.

Promising move condition

We should note that sequential moves are cyclic: we can start from any step of move and apply them one by one, until we make them all. Lin and Kernighan noticed (1973) that:

If a sequence of numbers has a positive sum, there is a cyclic permutation of these numbers such that every partial sum is positive.

Proof

Let $m$ is the largest index for which $g_1 + ... + g_{m-1}$ is minimum. We start our permutation and partial sums from this index.

Then for each $j$:

1. a) if $j \ge m$:

   1. since

      $$g_1 + ... g_j \gt g_1 + ... g_{m-1}$$

      then

      $$G'_j = g_m + ... + g_j = (g_1 + ... g_j) - (g_1 + ... g_{m-1}) \gt 0$$

2. b) if $j \lt m$:

   1. since

      $$g_1 + ... g_j \ge g_1 + ... + g_{m-1}$$

      then

      $$G'_j = (g_m + ... + g_k) + (g_1 + ... g_j) \ge (g_m + ... g_k) + (g_1 + ... g_{m-1}) \gt 0$$

Lin and Kernighan noticed that:

In particular, then, since we are looking for sequences of gains $g_i$'s that have positive sum, we need only consider sequences of gains whose partial sum is always positive. This gain criterion enables us to reduce enormously the number of sequences we need to examine

Therefore during process of building a sequential move we check partial sum of gains. If this sum remains positive before the last, closing step, then a sequence of exchanges is promising and we can continue, even if it is not valid move now.