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

Double Bridge as a mean of perturbation

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)