2-opt with Fixed Radius Search

Fixed radius search uses the property of the inequity which a 2-opt move must meet to improve a tour. We can benefit from this even more, but only when we consider links in the two orientations and the two symmetric forms.

forward (ABCD)	backward (DCBA)
implementation
look forward	look backward

Using this scheme we cannot miss an improving move even if we restrict possible choices to one inequity.

Example implementation:

type
  Orientation = enum forward, backward

proc One_City_2_Opt_R(tour: var Tour_Array,
                         basePos: Tour_Index): 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:
          Make_2_Opt_Move(tour, i, j)
          improved = true
          break two_loops
  result = improved

proc LS_2_Opt_R(tour: var Tour_Array) =
  ## Optimizes the given tour using 2-opt with fixed radius search
  var
    locallyOptimal: bool = false
    improved: bool

  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      improved = One_City_2_Opt_R(tour, basePos)
      if improved:
        locallyOptimal = false