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.

Sequential moves: connecting and disconnecting

The simplest sequential move consist of two steps, that is of two link exchanges. Obvious example of such move is 2-opt move. We can describe it using tour order notation:

2-opt move = 12-43

The following question arises: does any combination of numbers 1,2,3,4 describe some sequential move? Let us take for example: 13-24. This cannot be a sequential move, because by definition first pair of cities in sequential move must be a pair of tour neighbors. The same for second and every other pair. This means that each pair of numbers in the record must contain two consecutive numbers, in one or the other order.

Therefore there are only four combinations of numbers 1,2,3,4 that actually describe sequential moves:

		First pair
		12	21
Second pair	34	12-34	21-34
	43	12-43	21-43

The corresponding diagrams are as follows:

Forward
Move 12-34	Move 12-43
Backward
Move 21-34	Move 21-43

As we can see, moves starting with 21- are "backward moves" and their schemes are simply mirror images of their "forward" counterparts. Therefore we will no longer consider features of "backward" moves and we will focus on "forward" moves, that is moves which notation begins with 12-.

So there are only two sequential moves consisting of two steps, that is of two link exchanges: 12-34 and 12-43.

Move 12-43 is 2-opt move; we already know it and it does not require further comments.

Move 12-34 is a sequential move, despite the fact that it disconnects tour into two disjoint cycles. It may seem not useful and tempting to change the definition of a sequential move, but moves of this kind, although not producing valid tours, can be a part of connecting sequential move.

Let us take pure 3-opt moves. As we have already seen, there are exactly three pure 3-opt moves:

Pure 3-opt moves as sequential moves

Asymmetric
Move 12-43-65	Move 12-56-43	Move 12-65-34
Symmetric
Move 12-56-34

If we look closer to these diagrams we can notice that only two pure 3-opt moves: 12-43-65 and 12-56-43 come from 12-43 sequential move, that is from 2-opt move. The other two moves: asymmetric 12-65-34 and symmetric 12-56-34 come from disconnecting 12-34 sequential move. That is why we do not narrow the definition of a sequential move and actually consider disconnecting sequential moves — to have a consistent method of extending 2-exchange moves into full set of 3-moves, 3-moves to 4-moves and so on.

Origins of pure 3-opt moves from shorter sequential moves

12-34	12-65-34
	12-56-34
12-43	12-56-43
	12-43-65

We can notice that above table does not contain all possibilities of inserting a pair (5,6) or (6,5) into sequences 12-34 and 12-43. Moves 12-34-56, 12-34-65, 12-65-43 and 12-43-56 are missing, because they do not describe valid (connecting) 3-opt moves. Let us take a look at the last of them:

12-43-56

This is a disconnecting sequential move and we would not consider it when we want to narrow our searching to valid 2-opt and 3-opt moves. On the other way it leads to four valid sequential 4-opt moves (12-87-43-56, 12-78-43-56, 12-43-78-56, 12-43-87-56), so if we would like to consider all valid sequential 4-opt moves, then we should not omit it while building a sequential move step by step.

Sequential moves and tour order

Let us take a look at diagrams of two 3-opt sequential moves:

Move A	Move B

In both cases, A and B, the same set of cities is used to make a move: {c1, c2, c3, c4, c5, c6}, or: the same set of positions in tour. However, schemes for each of these two moves are different, and therefore the results would be different.

How can we distinguish between move of type A and of type B then?

We can use simple and unambiguous notation: by indicating the tour order of cities involved, starting from c1.

Let us take move A: we start from c1 and move along the tour clockwise. The next city from the set is c2 (second city engaged in move), then we encounter c4 (that is: fourth city of move), c3 (third city of move), c6 (sixth city of move) and c5 (fifth city of move). The tour order of cities in this sequential move is: c1, c2, c4, c3, c6, c5, so the move can be described as 12-43-65.

Move A = 12-43-65	Move B = 12-56-43

In move B the tour order of cities is: c1, c2, c5, c6, c4, c3, so this move can be described as 12-56-43.

This notation is simple, unambiguous and natural. Thanks to it we no longer need to use some arbitrary numbers as labels for each type of 3-opt move, not saying anything about scheme of given move. Moreover, this notation can be used to identify a scheme of any other sequential move, for example sequential 4-opt moves, 5-opts and so on.

Three examples of 4-opt sequential moves

Move 12-87-43-65	Move 12-78-56-43	Move 12-43-65-87

Sequential moves

2-opt as a sequential move

Let us consider 2-opt move described in the following way:

1. Step 0:
   1. Start from certain city c1 on tour.

1. Step 1:
   1. Remove link between c1 and one of its tour neighbors, c2.
   2. Add link between c2 and some other city c3.

1. Step 2:
   1. Remove link between c3 and its tour neighbor c4.
   2. Add link between c4 and the first city c1, to close the tour.

Note that steps 1 and 2 have the same scheme: remove a link between a city and its tour neighbor and then add link between this neighbor and some other city. Each step exchanges two links.

Example of 3-opt sequential move

We can extend 2-opt move to 3-opt move using the same scheme. Step 1 would be the same as in 2-opt move, so we show the procedure from step 2. Note that the only difference is in part B of this step:

1. Step 2:
   1. Remove link between c3 and its tour neighbor c4.
   2. Add link between c4 and the some other city c5.

1. Step 3:
   1. Remove link between c5 and its tour neighbor c6.
   2. Add link between c6 and the first city c1, to close the tour.

Example of 4-opt sequential move

1. Step 3:
   1. Remove link between c5 and its tour neighbor c6.
   2. Add link between c6 and the some other city c7.

1. Step 4:
   1. Remove link between c7 and its tour neighbor c8.
   2. Add link between c8 and the first city c1, to close the tour.

General scheme of a sequential move

As we can see the general scheme of sequential move is as follows:

1. Step 1
   1. Remove link between c1 and its tour neighbor c2.
   2. Add link between c2 and some c3.
2. Step 2
   1. Remove link between c3 and its tour neighbor c4.
   2. Add link between c4 and some c5.
3. ...
4. Last step can close the tour this way:
1. Remove link between c_2k1 and its tour neighbor c_2k.
2. Add link between c_2k and the first city c1, to close the tour.

The result of all steps is:

remove: (c1,c2) (c3,c4) (c5,c6) ... (c_2k1, c_2k)
add:    (c2,c3) (c4,c5) (c6,c7) ... (c_2k, c1)