3-opt with Neighbor Lists and DLB – simple

Compare the code below with the code for 2-opt with neighbor lists and DLB and notice that this algorithm is simplified, not truly bi-directional version.

proc One_City_3_Opt_ND(tour: var Tour_Array;
                       basePos: Tour_Index;
                       neighbor: Neighbor_Matrix;
                       position: var City_Position_In_Tour;
                       numberOfNeigbors: int;
                       DontLook: var DLB_Array): bool =
  type
    Move3 = object
      i, j, k: Tour_Index
      optCase: Reconnection_3_optCase
      gain: Length_Gain
  var
    improved: bool
    i, j, k: Tour_Index
    X1, X2, Y1, Y2, Z1, Z2: City_Number
    k_6, k_7:  Tour_Index
    Z1_6, Z2_6, Z1_7, Z2_7: City_Number
    gainExpected: Length_Gain
    goodMove: Move3
  
  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:
        # new edges in optCase=6: *X1-Y2*, Y1-Z1, X2-Z2
        # new edges in optCase=7: *X1-Y2*, X2-Z1, Y1-Z2
        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)

        for neighbor_2 in 0 .. numberOfNeigbors-1:
          # new edges in optCase=6: X1-Y2, *Y1-Z1*, X2-Z2
          Z1_6 = neighbor[Y1][neighbor_2]
          k_6  = position[Z1_6]
          Z2_6 = tour[(k_6 + 1) mod N]
          # new edges in optCase=7: X1-Y2, X2-Z1, *Y1-Z2*
          Z2_7 = neighbor[Y1][neighbor_2]
          k_7  = (position[Z2_7] + N - 1) mod N
          Z1_7 = tour[k_7]
          
          if Between(i, j, k_6):
            gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1_6, Z2_6,
                                           opt3_case_6)
            if gainExpected > goodMove.gain:
              improved = true
              goodMove = Move3(i: i,  j: j,  k: k_6,
                               optCase: opt3_case_6, gain: gainExpected)

          if Between(i, j, k_7):
            gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1_7, Z2_7,
                                           opt3_case_7)
            if gainExpected > goodMove.gain:
              improved = true
              goodMove = Move3(i: i,  j: j,  k: k_7,
                               optCase: opt3_case_7, gain: gainExpected)

  if improved:
    Set_DLB_off(DontLook,
                  [ tour[goodMove.i], tour[(goodMove.i + 1) mod N],
                    tour[goodMove.j], tour[(goodMove.j + 1) mod N],
                    tour[goodMove.k], tour[(goodMove.k + 1) mod N] ])
    Make_3_Opt_Move(tour,
                    goodMove.i,  goodMove.j,  goodMove.k,
                    goodMove.optCase,  position)
  result = improved

Some simple statistics

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

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	111.12	122.44
	NN + 2opt	1360	88.94	92.58	98.91
	NN + 2opt Take Best	1140	89.47	91.75	95.40
	NN + 3opt	79166	87.99	89.61	92.82
	NN + 3opt-ND(24)	4586	87.99	89.86	94.22
2	NN	100	100.00	107.46	119.61
	NN + 2opt	1146	90.85	94.70	100.03
	NN + 2opt Take Best	1046	88.59	92.09	97.39
	NN + 3opt	69473	87.22	89.89	94.23
	NN + 3opt-ND(24)	4586	87.22	89.87	93.04
3	NN	100	100.00	106.81	117.56
	NN + 2opt	681	88.92	93.34	97.90
	NN + 2opt Take Best	881	89.38	92.28	96.22
	NN + 3opt	66112	87.85	89.53	93.19
	NN + 3opt-ND(24)	4106	87.68	89.07	92.68
4	NN	100	100.00	108.58	116.96
	NN + 2opt	1460	85.60	88.52	92.28
	NN + 2opt Take Best	1253	85.40	86.87	89.81
	NN + 3opt	73226	83.14	84.80	87.22
	NN + 3opt-ND(24)	4586	83.15	85.01	87.43
5	NN	100	100.00	110.59	124.43
	NN + 2opt	1146	92.73	95.42	98.30
	NN + 2opt Take Best	940	91.43	93.58	97.02
	NN + 3opt	72393	90.91	92.32	94.66
	NN + 3opt-ND(24)	4166	90.91	92.27	93.67
6	NN	100	100.00	107.15	118.12
	NN + 2opt	1253	89.35	92.71	98.25
	NN + 2opt Take Best	939	88.74	90.81	92.73
	NN + 3opt	69373	87.94	89.63	91.73
	NN + 3opt-ND(24)	4373	88.20	90.00	92.09
7	NN	100	100.00	110.20	121.48
	NN + 2opt	1253	92.30	95.31	98.94
	NN + 2opt Take Best	939	91.53	93.94	97.52
	NN + 3opt	65306	90.41	91.74	94.38
	NN + 3opt-ND(24)	4273	90.41	91.63	93.30
8	NN	100	100.00	105.35	112.99
	NN + 2opt	1253	88.20	92.02	97.83
	NN + 2opt Take Best	833	88.69	90.72	95.39
	NN + 3opt	66980	87.66	88.77	94.75
	NN + 3opt-ND(24)	4273	87.66	89.34	92.54
9	NN	100	100.00	107.15	115.57
	NN + 2opt	781	92.08	95.79	100.95
	NN + 2opt Take Best	875	90.94	94.06	98.73
	NN + 3opt	71681	89.76	91.35	94.37
	NN + 3opt-ND(24)	4393	89.76	91.32	93.54
10	NN	100	100.00	106.56	113.89
	NN + 2opt	1253	87.07	90.87	94.98
	NN + 2opt Take Best	1040	86.66	88.63	91.83
	NN + 3opt	71353	86.01	87.64	90.86
	NN + 3opt-ND(24)	4273	86.01	87.41	91.10