Non-sequential 4-opt moves – part 1 of 4

Among all 48 types of 4-opt moves there are exactly five non-sequential pure 4-opt moves. They apparently form two distinct groups:

Moves AbCd and AdCb

AbCd	AdCb

While it may be suprising to count them as pure 4-opt non-sequential moves, in fact they are moves of this kind. They are 4-opt moves, because they remove four links and then add four links. They are both pure 4-opt moves, because none of them is equivalent of any single 2-opt nor 3-opt move. They are not sequential moves, which can be easily seen from the fact that we cannot show any closed polygonal chain of line segments connecting the consecutive cities. So by definition they are pure 4-opt non-sequential moves.

On the other hand, each of these moves consists of just two completely independent 2-opt moves, changing two non-overlaping ranges. Each 2-opt move of the pair can be improving or not improving and accordingly to this we would applied it or not. Therefore during optimization there is no need to treat these 4-opt non-sequential moves as practically distinct 4-opt moves, but rather as two separate 2-opts, then as two moves of type we consider anyway during the process of optimization by using sequential moves.

Moves ADbc, AcdB and ADCB

ADbc	AcdB	ADCB

This group includes non-sequential 4-opt moves, semeed to be specific combinations of two submoves, both being 2-exchanges, where one of them is disjoining (see parallel lines on schemes above) and the other is either disjoining or joining (2-opt, see x-crossed lines).

Including these moves into optimization procedure requires, as usual, resolving two issues: how to find (or generate) such moves and how to actually apply them. Let us start with solution of the latter issue.

The last case, so called "double bridge" move, is most known and instructive. It can be perceived as a kind of combination of two disjoining 2-exchanges. Then the first submove would be always disjoining, and on the other hand we cannot represent two disjoined segments when using array representation of tour (because this single array always contains consecutive city numbers of all cities, as there were links between each pair of consecutive cities). So we would not be able to implement even the first submove of double bridge move.

Second approach to this issue is based on observation that double bridge, which is ADCB, can be obtained from original tour ABCD by shifting two segments or swapping them. This would however require to introduce segment shift (or swap) as second basic transformation, distinct from link exchange we used so far as the only needed basic transformation.

While this may not be obvious, neither segment shifting nor swapping is necessary to obtain the same effect. Let symbol prime (') after a letter or letters in parenthesis means that we reverse this segment(s) and lower letter represent reversed segments:

0.  ABCD
1.  A(BC)'D = AcbD
2.  Ac(bD)' = AcdB
3.  A(cd)'B = ADCB

So double bdridge move is just a specific combination of three segment reversals (then three 2-opts), exactly as any pure 4-opt sequential move:

# 'ADBC' (||=), double bridge
Exchange_Links(d1, d2, d4, d3)
Exchange_Links(c1, c2, c4, c3)
Exchange_Links(d1, d3, d4, d2)

ABCD
AcbD	AcdB	ADCB

Note that segment configuration before last exchange is AcdB, which is one of the remaining pure 4-opt non-sequential cases. So for this case we have:

# 'AcdB' (||X), crossed vertical bridge
Exchange_Links(d1, d2, d4, d3)
Exchange_Links(c1, c2, c4, c3)

The first case (ADbc) from this group can be implemented by analogy:

0.  ABCD
1.  AB(CD)' = ABdc
2.  A(Bd)'c = ADbc

We can make a general proc for making 4-opt non-sequential move:

const
  TO_ADBC   = -1  # 4-opt 'ADBC' (||=), double bridge
  TO_AxcxdB = -2  # 4-opt 'AcdB' (||X), crossed vertical bridge
  TO_ADxbxc = -3  # 4-opt 'ADbc' (X=), crossed horizontal bridge

proc Make_4opt_NS_Move(c1, c2, c3, c4, d1, d2, d3, d4: City_Number;
                       tourOrder: int) =

  case tourOrder

  of TO_ADBC:    # 'ADBC' (||=), double bridge
   # c12-d12-c34-d34
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d1, d3, d4, d2)

  of TO_AxcxdB:  # 'AcdB' (||X), crossed vertical bridge
    # c12-d12-c34-d43
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    
  of TO_ADxbxc:  # 'ADbc' (X=), crossed horizontal bridge
    # c12-d12-c43-d34
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d1, d2, d3, d4)
  
  else:
    echo "Unknown 4-opt non-sequential move: ", tourOrder
    quit 1

Beware

Proc Exchange_Links() used here takes city numbers, not city positions in tour, as arguments. Confusing these two different ways leads to wrong results.