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

Double Bridge as an improving 4-opt move, part 2

In previous part we have found such cF1...cF4 that replacing links cF1-cF2 and cF3-cF4 with links cF2-cF3 and cF4-cF1 disjoins tour, but gives gain:

We can expect that segment from cF2 to cF3 contains relatively small number of cities. Therefore we will look for d1 by examining one by one all cities between cF2 and cF3, and then look for d3 among these neighbors of given d1 that are in the other segment, that is between cF4 and cF1. If total gain from set of all eight cities obtained this way is positive, then we have found improving non-sequential move.

But what if segment from cF2 to cF3 contains more cities than the other one?

Then we can simply "rename" cities before using the procedure described above:

So we use:

if (2 * Segment_Size(cF2,cF3)) > N:
  (cF1, cF2, cF3, cF4) = (cF3, cF4, cF1, cF2)

where:

proc Segment_Size(cityStart, cityEnd: City_Number): int =
  ## Returns number of cities in segment given by the two cities.
  ## Note that order of parameters is important to distinguish
  ## between two possible segments
  result = (N + position[cityEnd] + 1 - position[cityStart]) mod N

Rest of the code implements the idea described above:

proc LK_Bridge_A1(c1, c2, c3, c4: City_Number;
                  G0: Length_Gain): bool =
  var
    improved: bool
    cF1, cF2, cF3, cF4: City_Number
    d1, d2: City_Number
    Ga, G1a: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    breadth: int

  improved = false
  # order cities 'forward':
  if (c2 == t_succ(c1)):
    (cF1, cF2, cF3, cF4) = (c1, c2, c3, c4)
  else:
    (cF1, cF2, cF3, cF4) = (c2, c1, c4, c3)
  #end_if
  # we want segment [cF2,cF3] to be the shorter one
  if (2 * Segment_Size(cF2,cF3)) > N:
    (cF1, cF2, cF3, cF4) = (cF3, cF4, cF1, cF2)

  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    d1 = cF2
    d2 = t_succ(d1)
    while d2 != cF3:
      G1a = G0 + distance(d1, d2)
      goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2, Ga: G1a)
      goodSufficesList.add(goodSuffix)
      d1 = d2
      d2 = t_succ(d1)
    #end_loop while d2 != cF3
  #end_block find_promising_moves
    
  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      d1 = goodSuffix.c2iplus1
      d2 = goodSuffix.c2iplus2     
      Ga = goodSuffix.Ga
      improved = LK_Bridge_A2(cF1, cF2, cF3, cF4, d1, d2, Ga)
      if improved:
        break evaluate_promising_moves
  #end_block evaluate_promising_moves

  result = improved

and:

proc LK_Bridge_A2(c1, c2, c3, c4, d1, d2: City_Number;
                  G1a: Length_Gain): bool =
  var
    improved: bool
    d3, d4: City_Number
    d2_pred, d2_succ: City_Number
    d3_pred, d3_succ: City_Number
    G1, G2a, gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    tourOrder: int
    tried_c3: int = 0
    breadth: int

  improved = false
  
  # find d3 as a candidate for end of link (d2,d3) to add
  d2_succ = t_succ(d2)
  d2_pred = t_pred(d2)
  
  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for d3 in neighbors(d2):
      if tried_c3 >= 2*Max_Breadth_1:
        break find_promising_moves
      if (d3 == d2_succ) or (d3 == d2_pred):
        continue
      if inOrder(c2, d3, c3, true):
        # d3 should not be between c2 and c3
        continue
        
      G1 = G1a - distance(d2, d3)
      # choose d4 as one of the two tour neighbors of d3:
      d3_succ = t_succ(d3)
      d3_pred = t_pred(d3)
      for d4 in [d3_succ, d3_pred]:
        if d4 == d2:
          continue
        if (d3 == c1) and (d4 == c2)  or
           (d3 == c2) and (d4 == c1):
          continue
        if (d3 == c3) and (d4 == c4)  or
           (d3 == c4) and (d4 == c3):
          continue

        G2a = G1 + distance(d3, d4)
        if (d4 == t_succ(d3)):
          tourOrder = TO_ADBC    # 'ADBC' (||=)
        else:
          tourOrder = TO_AxcxdB  # 'AcdB' (||X)
        #end_if
        goodSuffix = Suffix(c2iplus1: d3, c2iplus2: d4,
                            tourOrder: tourOrder, Ga: G2a)
        goodSufficesList.add(goodSuffix)
        tried_c3 = tried_c3 + 1
      #end_loop for d4
    #end_loop for d3
  #end_block find_promising_moves
        
  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      d3 = goodSuffix.c2iplus1
      d4 = goodSuffix.c2iplus2     
      G2a = goodSuffix.Ga
      gainFromCloseUp = G2a - distance(d4, d1)
      if gainFromCloseUp > 0: # improving move found
        improved = true
        Make_4opt_NS_Move(c1, c2, c3, c4,
                          d1, d2, d3, d4, tourOrder)
        tourLen = tourLen - gainFromCloseUp
        Set_DLB_off(DontLook, [c1, c2, c3, c4,
                               d1, d2, d3, d4])
        break evaluate_promising_moves 
  #end_block evaluate_promising_moves

  result = improved