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-23`

*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:

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:

and __12__-__43__-65

come from __12__-56-__43__`12-43`

sequential move, that is from 2-opt move. The other two moves: asymmetric `12-65-`

and symmetric __34__`12-56-`

come from disconnecting __34__`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.

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.