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.