2-opt with Neighbor Lists and optional DLB and FR

Note

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

proc One_City_2_Opt_NDR(tour: var Tour_Array;
                        basePos: Tour_Index;
                        neighbor: Neighbor_Matrix;
                        position: var City_Position_In_Tour;
                        numberOfNeigbors: int;
                        DontLook: var DLB_Array;
                        useDLB: bool;
                        useFixedRadius: bool): bool =
  var
    improved: bool
    pos_Y2, i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number
    d_X1_X2, d_X1_Y1: 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[(i+1) mod N]  # == tour[basePos]
      d_X1_X2 = distance(X1, X2)

      for neighbor_number in 0 .. numberOfNeigbors-1:
        # after 2-opt move new tour would contain direct link X1-Y1,
        # so we look for city Y1 among cities that are close to city X1
        Y1 = neighbor[X1][neighbor_number]
        if direction == forward:
          j = position[Y1]
          Y2 = tour[(j+1) mod N]
        else:
          j  = (N + position[Y1] - 1) mod N  # pos[Y1] == j+1
          Y2 = tour[j]

        if (X2 == Y1) or (Y2 == X1):
          # 2-opt is for non-adjacent links only
          # by constuction X1 != Y1
          continue
          
        d_X1_Y1 = distance(X1, Y1)
          
        if useFixedRadius:
          if d_X1_Y1 > d_X1_X2:
            break

        # the same as: Gain_From_2_Opt(X1, X2, Y1, Y2) > 0
        if (d_X1_X2 + distance(Y1, Y2)) -
           (d_X1_Y1 + distance(X2, Y2)) > 0:
          if useDLB:
            Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
          Make_2_Opt_Move(tour, i, j, position)
          improved = true
          break two_loops
  result = improved

proc LS_2_Opt_NDR(tour: var Tour_Array;
                  neighbor: Neighbor_Matrix;
                  neighborListLen: int = N-1;
                  useDLB: bool = true;
                  useFixedRadius: bool = true) =
  ## Optimizes the given tour using 2-opt with neighbor lists
  ## and with optional Don't Look Bits (DLB) and fixed radis
  var
    locallyOptimal: bool = false
    improved: bool
    DontLook: DLB_Array
    baseCity: City_Number
    position: City_Position_In_Tour

  let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
  position = Create_Position_In_Tour(tour)

  if useDLB:
    Set_DLB_off(DontLook, tour)  
  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      baseCity = tour[basePos]
      if useDLB and isDLB_on(DontLook, baseCity):
        continue
      improved = One_City_2_Opt_NDR(tour, basePos, neighbor, position,
                                    numberOfNeigbors, DontLook,
                                    useDLB, useFixedRadius)
      if improved:
        locallyOptimal = false
      else:
        if useDLB:
          Set_DLB_on(DontLook, baseCity)