Sometimes double bridge move is used to perturb a tour. When local optimization method finds no more improving moves, it finishes its work and tour cannot be further improved by this method. But we can slightly perturb resulting tour to obtan a new, very similar, but not fully optimized tour and then try to optimize it in hope to find better result.
When double bridge (or some other non-sequential move) is to be used as a mean to perturb a tour, it does not matter whether it is improving move or not. It is sufficient to use any valid double bridge to obtain perturbed tour. So we can just take any set of cities that can form such move.
Since c2 is always the tour successor of c1, d2 is the successor of d1 and so on, the move is determinated by four cities. Then to make double bridge we can use a set of any four cities. The following proc generates four random city numbers, then sorts these cities by their ascending positions on tour and uses as parameters to make a double bridge move.
proc Double_Bridge_Perturbation() =
var
randCity: City_Number
citiesDblBridge: array[0..3, City_Number]
forbidden: bool
i: int
c1, c2, c3, c4: City_Number
d1, d2, d3, d4: City_Number
randomize()
i = 0
while i <= 3:
randCity = random(N) # returns number from 0 to N-1 inclusive
forbidden = false
for j in 0 .. i-1:
# check if city is already taken
if randCity == citiesDblBridge[j]:
forbidden = true
continue
# check if city is a tour neighbor of already taken
if t_succ(randCity) == citiesDblBridge[j] or
t_pred(randCity) == citiesDblBridge[j]:
forbidden = true
continue
if not forbidden:
citiesDblBridge[i] = randCity
i = i + 1
# sort by ascending position
sort(citiesDblBridge) do (x,y: City_Number) -> int:
result = cmp(position[x], position[y])
c1 = citiesDblBridge[0]
d1 = citiesDblBridge[1]
c3 = citiesDblBridge[2]
d3 = citiesDblBridge[3]
c2 = t_succ(c1)
c4 = t_succ(c3)
d2 = t_succ(d1)
d4 = t_succ(d3)
# make the move:
Make_4opt_NS_Move(c1, c2, c3, c4, d1, d2, d3, d4, TO_ADBC)
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:
Proc Exchange_Links() used here takes city numbers, not city positions in tour, as arguments. Confusing these two different ways leads to wrong results.
