3-opt with min-max lenght of link – example

proc One_City_3_Opt_NDM(tour: var Tour_Array;
                        basePos: Tour_Index;
                        neighbor: Neighbor_Matrix;
                        position: var City_Position_In_Tour;
                        numberOfNeigbors: int;
                        DontLook: var DLB_Array;
                        minLenInSet: Length;
                        maxLenInTour: var Length): bool =
  type
    Move3 = object
      i, j, k: Tour_Index
      optCase: Reconnection_3_optCase
      gain: Length_Gain
  var
    improved: bool
    i, j, k: Tour_Index
    ii, jj, kk: Tour_Index
    X1, X2, Y1, Y2, Z1, Z2: City_Number
    A1, A2, B1, B2, C1, C2: City_Number
    gainExpected: Length_Gain
    goodMove: Move3
    d1, d2: Length
  
  improved = false
  goodMove.gain = 0
  block three_loops:
    
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
      else:
        i  = (N + basePos - 1) mod N
      X1 = tour[i]
      X2 = tour[(i+1) mod N]
 
      for neighbor_1 in 0 .. numberOfNeigbors-1:
        Y2 = neighbor[X1][neighbor_1]
        j  = (position[Y2] + N - 1) mod N
        Y1 = tour[j]

        if (Y1 != X1) and (Y1 != X2):
          gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
          if gainExpected > goodMove.gain:
            improved = true
            goodMove = Move3(i: i,  j: j,  k: j,
                             optCase: opt3_case_1, gain: gainExpected)
        else:
          continue
          
        d2 = distance(X1, Y1) + minLenInSet
        if d2 + minLenInSet > distance(X1, X2) + 2 * maxLenInTour:
           break
        d1 = distance(X1, X2) + distance(Y1, Y2) + maxLenInTour
        if d2 + minLenInSet > d1:
           continue

        for neighbor_2 in 0 .. numberOfNeigbors-1:
          Z2 = neighbor[X1][neighbor_2]
          k  = (position[Z2] + N - 1) mod N
          Z1 = tour[k]

          if (Z2 == Y2) or (Z1 == Y2) or
             (Z1 == X1) or (Z1 == X2) or
             (Y1 == X1) or (Y1 == X2):
              continue

          if d2 + distance(Y1, Z1) > d1:
            break

          if Between(i, j, k):
            jj = j
            kk = k
            (A1, A2, B1, B2, C1, C2) = (X1, X2, Y1, Y2, Z1, Z2)
          else:
            jj = k
            kk = j
            (A1, A2, B1, B2, C1, C2) = (X1, X2, Z1, Z2, Y1, Y2)

          for optCase in opt3_case_4 .. opt3_case_7:
            gainExpected = Gain_From_3_Opt(A1, A2, B1, B2, C1, C2,
                                           optCase)
            if gainExpected > goodMove.gain:
              improved = true
              goodMove = Move3(i: i,  j: jj,  k: kk,
                               optCase: optCase, gain: gainExpected)

  if improved:
    A1 = tour[goodMove.i]
    A2 = tour[(goodMove.i + 1) mod N]
    B1 = tour[goodMove.j]
    B2 = tour[(goodMove.j + 1) mod N]
    C1 = tour[goodMove.k]
    C2 = tour[(goodMove.k + 1) mod N]
    Set_DLB_off(DontLook, [A1, A2, B1, B2, C1, C2])
    Make_3_Opt_Move(tour,
                    goodMove.i,  goodMove.j,  goodMove.k,
                    goodMove.optCase,  position)

    case goodMove.optCase
    of opt3_case_1:
      maxLenInTour = max( maxLenInTour, max(distance(A1,B1),
                          distance(A2,B2)) )
    of opt3_case_4:
      maxLenInTour = max( maxLenInTour, max(distance(A1,B1),
                          max(distance(A2,C1),
                              distance(B2,C2)) ) )
    of opt3_case_5:
      maxLenInTour = max( maxLenInTour, max(distance(A1,C1),
                          max(distance(A2,B2),
                              distance(B1,C2)) ) )
    of opt3_case_6:
      maxLenInTour = max( maxLenInTour, max(distance(A1,B2),
                          max(distance(A2,C2),
                              distance(B1,C1)) ) )
    of opt3_case_7:
      maxLenInTour = max( maxLenInTour, max(distance(A1,B2),
                          max(distance(A2,C1),
                              distance(B1,C2)) ) )
    else:
      echo "Should not happen: ", goodMove.optCase
      maxLenInTour = distance(tour[0], tour[N-1])
      for pos in 0 .. N-2:
        maxLenInTour = max(maxLenInTour,
                           distance(tour[pos], tour[pos+1]))
    #end goodMove.optCase

  result = improved

proc LS_3_Opt_NDM(tour: var Tour_Array;
                  neighbor: Neighbor_Matrix;
                  neighborListLen: int = N-1) =
  ## Optimizes the given tour using 3-opt with neighbor lists
  ## Don't Look Bits (DLB) and min-max Links
  var
    locallyOptimal: bool = false
    improved: bool
    DontLook: DLB_Array
    baseCity: City_Number
    position: City_Position_In_Tour
    maxLenInTour: Length

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

#[
  # NOTE: minLenInSet is constant for the dataset
  minLenInSet = high(Length)
  for city_A in 0 .. N-1:
    for city_B in (city_A+1) .. N-1:
      minLenInSet = min(minLenInSet, distance(city_A, city_B))
]#

  maxLenInTour = distance(tour[0], tour[N-1])
  for pos in 0 .. N-2:
    maxLenInTour = max(maxLenInTour, distance(tour[pos], tour[pos+1]))

  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_3_Opt_NDM(tour, basePos, neighbor, position,
                                    numberOfNeigbors, DontLook,
                                    minLenInSet, maxLenInTour)
      if not improved:
        Set_DLB_on(DontLook, baseCity)
      else:
        locallyOptimal = false