2-opt with DLB and Fixed Radius

Note

This example of code does not contain any new ideas and can be skipped by a reader.

proc One_City_2_Opt_DLBR(tour: var Tour_Array,
                         basePos: Tour_Index,
                         DontLook: var DLB_Array): bool =
  var
    improved: bool
    i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number
    radius: Length

  improved = false
  block two_loops:
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
      else:
        i  = (N + basePos - 1) mod N
        X2 = tour[i]
        X1 = tour[basePos]  # == tour[(i+1) mod N]
      radius = distance(X1, X2)

      for counter_2 in 0 .. N-1:
        j = counter_2
        Y1 = tour[j]
        Y2 = tour[(j+1) mod N]
        if direction == backward:
          swap(Y1, Y2)
        if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
          continue

        if distance(X2, Y2) > radius:
          continue

        if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
          Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
          Make_2_Opt_Move(tour, i, j)
          improved = true
          break two_loops
  result = improved

proc LS_2_Opt_DLBR(tour: var Tour_Array) =
  ## Optimizes the given tour using 2-opt with Don't Look Bits (DLB)
  ## and fixed radius search
  var
    locallyOptimal: bool = false
    improved: bool
    DontLook: DLB_Array
    baseCity: City_Number

  Set_DLB_off(DontLook, tour)

  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      baseCity = tour[basePos]
      if isDLB_on(DontLook, baseCity):
        continue
      improved = One_City_2_Opt_DLBR(tour, basePos, DontLook)
      if not improved:
        Set_DLB_on(DontLook, baseCity)
      else:
        locallyOptimal = false