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)