3-opt with DLB

Procedures to calculate the gain from 3-opt move and to make 3-opt move assume that their parameters (cities and their indices in tour) are given in the order of ascending indices of tour array (modulo N). Therefore we need a function to recognize whether three indices are in this order, or: whether in this orientation the middle index is between the two boundary indices.

proc Between(a, x, b: Tour_Index): bool =
  ## Returns true if `x` is between `a` and `b` in cyclic sequence
  ## with established orientation of nondescending indices
  # That is: when one begins a forward traversal of the tour
  # at position `a', then position `x` is reached before position `b'.
  # Returns true if and only if:
  #   a < x < b  or  b < a < x  or  x < b < a
  if (b > a):
    result = (x > a) and (x < b)
  elif (b < a):
    result = (x > a) or (x < b)
  else:
    result = false

Note the additional speed-up: the link between base city X1 and its tour neighbor X2 is not considered when at least one of these cities has its don’t-look bit set to on.

proc One_City_3_Opt_DLB(tour: var Tour_Array,
                        basePos: Tour_Index,
                        DontLook: var DLB_Array): bool =
  type
    Move3 = object
      i, j, k: Tour_Index
      optCase: Reconnection_3_optCase
  var
    improved: bool
    i, j, k: Tour_Index
    X1, X2, Y1, Y2, Z1, Z2: City_Number
    gainExpected: Length_Gain
    optCase: Reconnection_3_optCase
    goodMove: Move3

  improved = false
  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]

      if isDLB_on(DontLook,X1) or isDLB_on(DontLook,X2):  # NOTE
        continue

      for counter_2 in 0 .. N-1:
        j = counter_2 # second cut after j
        Y1 = tour[j]
        Y2 = tour[(j+1) mod N]

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

        # examine 2-opt move (see: opt3_case_1 .. opt3_case_3)
        gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
        if gainExpected > 0:
          goodMove = Move3(i: i,  j: j,  k: j,
                           optCase: opt3_case_1)
          improved = true
          break three_loops

        for counter_3 in 0 .. N-1:
          k = counter_3  # third cut after k
          Z1 = tour[k]
          Z2 = tour[(k+1) mod N]
          if (X1 == Z1) or (Y1 == Z1):
            continue

          if not Between(i, j, k):
            continue

          # examine pure 3-opt cases
          for optCase in [opt3_case_6, opt3_case_7]:
            gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1, Z2,
                                           optCase)
            if gainExpected > 0:
              goodMove = Move3(i: i,  j: j,  k: k,
                               optCase: optCase)
              improved = true
              break three_loops
      # end_block three_loops
  if improved:
    Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
    if goodMove.optCase > opt3_case_3:
      Set_DLB_off(DontLook, [Z1, Z2])
    Make_3_Opt_Move(tour,
                    goodMove.i,  goodMove.j,  goodMove.k,
                    goodMove.optCase)
  result = improved

proc LS_3_Opt_DLB(tour: var Tour_Array) =
  ## Optimizes the given tour using 3-opt with Don't Look Bits (DLB)
  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_3_Opt_DLB(tour, basePos, DontLook)
      if not improved:
        Set_DLB_on(DontLook, baseCity)
      else:
        locallyOptimal = false

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 3-opt and 3-opt with DLB algorithms. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	107.94	117.16
	NN + 2opt	1268	90.06	92.88	101.40
	NN + 3opt	75093	88.61	89.92	91.77
	NN + 3opt-DLB	28125	88.61	90.07	92.72
2	NN	100	100.00	109.67	122.62
	NN + 2opt	1146	88.91	94.14	101.71
	NN + 3opt	73646	88.89	90.41	93.56
	NN + 3opt-DLB	27919	88.99	90.85	94.98
3	NN	100	100.00	107.04	118.01
	NN + 2opt	940	91.11	94.74	98.25
	NN + 3opt	72920	88.77	91.19	93.11
	NN + 3opt-DLB	25933	88.86	91.53	93.85
4	NN	100	100.00	107.40	118.32
	NN + 2opt	975	89.03	92.56	97.91
	NN + 3opt	72856	87.99	89.56	92.33
	NN + 3opt-DLB	25681	87.99	89.80	93.41
5	NN	100	100.00	104.79	113.38
	NN + 2opt	1460	81.19	84.60	89.37
	NN + 3opt	72706	79.82	81.76	84.73
	NN + 3opt-DLB	29166	79.82	81.98	85.00
6	NN	100	100.00	104.66	115.85
	NN + 2opt	1360	82.98	86.03	90.66
	NN + 3opt	68539	82.39	83.59	85.12
	NN + 3opt-DLB	26979	82.39	83.59	85.56
7	NN	100	100.00	109.45	118.42
	NN + 2opt	1360	88.10	92.88	97.84
	NN + 3opt	78639	86.66	88.83	91.93
	NN + 3opt-DLB	28026	86.66	89.14	92.78
8	NN	100	100.00	104.37	112.02
	NN + 2opt	1046	88.50	91.59	97.77
	NN + 3opt	75313	86.40	88.34	91.11
	NN + 3opt-DLB	26040	86.75	88.92	95.75
9	NN	100	100.00	108.32	118.64
	NN + 2opt	1566	91.31	94.95	100.77
	NN + 3opt	66460	90.46	92.05	95.71
	NN + 3opt-DLB	25726	90.59	92.12	95.83
10	NN	100	100.00	107.87	122.61
	NN + 2opt	1146	89.12	93.21	99.11
	NN + 3opt	69066	87.98	89.43	93.58
	NN + 3opt-DLB	26666	87.98	89.67	92.78