Stop search after encountering the successor

Less popular speed-up is using search cut after encountering a successor of given city when iterating on its neighbors. The idea is based on the observation that lead to 2-opt fixed radius search.

We consider neighbours of city X1 to find a good candidate for Y1, the first of endpoints of second link to remove. If we make a 2-opt move, then Y1 would be the new tour successor of X1, so it should not be in distance from X1 greater then is X2, the current successor. Otherwise, the new link would be longer than the current one. Since we consider neighbors of X1 in ascending order of their distance from this city, encountering X2 during search means that all subsequent neighbors would give longer links to X1.

...
  for neighbor_1 in 0 .. numberOfNeigbors-1:
    Y2 = neighbor[X1][neighbor_1]
    j  = (position[Y2] + N - 1) mod N
    Y1 = tour[j]

    if (Y1 == X2):  # speed-up
      break
...

Analogous condition can be used in 3-opt, also for Z1, although justification in the case of 3-opt is not so strong, even when forcing only Y1 != X2.

Note that this condition rejects some valid 3-opt moves, Node Shifts that are used in 2.5-opt:

This speed-up is very effective and can be used instead of popular don’t look bits solution.

The full code for simple 3-opt and the speed-up in one loop only is as follows:

proc One_City_3_Opt_NC(tour: var Tour_Array;
                       basePos: Tour_Index;
                       neighbor: Neighbor_Matrix;
                       position: var City_Position_In_Tour;
                       numberOfNeigbors: int): 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)

        if (Y1 == X2):  # NOTE
          break

        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:
    Make_3_Opt_Move(tour,
                    goodMove.i,  goodMove.j,  goodMove.k,
                    goodMove.optCase,  position)
  result = improved

proc LS_3_Opt_NC(tour: var Tour_Array;
                 neighbor: Neighbor_Matrix;
                 neighborListLen: int = N-1) =
  var
    locallyOptimal: bool = false
    improved: bool
    baseCity: City_Number
    position: City_Position_In_Tour

  let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
  position = Create_Position_In_Tour(tour)
  
  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      baseCity = tour[basePos]
      improved = One_City_3_Opt_NC(tour, basePos, neighbor, position,
                                   numberOfNeigbors)
      if improved:
        locallyOptimal = false

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=200.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	106.52	114.46
	NN + 2opt	4721	88.17	90.89	94.52
	NN + 2opt Take Best	5119	87.53	89.09	91.25
	NN + 3opt-ND(24)	5851	86.44	87.94	89.65
	NN + 3opt-NC(24)	3589	85.76	87.89	89.86
2	NN	100	100.00	104.27	110.57
	NN + 2opt	3623	90.30	92.45	95.40
	NN + 2opt Take Best	3889	89.07	90.67	92.78
	NN + 3opt-ND(24)	5551	88.31	89.59	92.20
	NN + 3opt-NC(24)	2959	88.36	89.46	91.41
3	NN	100	100.00	110.24	122.10
	NN + 2opt	3839	91.03	94.61	97.58
	NN + 2opt Take Best	4450	90.34	91.70	94.47
	NN + 3opt-ND(24)	5808	88.72	90.63	92.96
	NN + 3opt-NC(24)	3634	88.82	90.71	92.56
4	NN	100	100.00	106.87	114.35
	NN + 2opt	3955	87.53	90.64	94.81
	NN + 2opt Take Best	4521	87.10	89.33	91.84
	NN + 3opt-ND(24)	5785	85.53	87.35	90.17
	NN + 3opt-NC(24)	3423	85.99	87.44	89.56
5	NN	100	100.00	106.86	113.89
	NN + 2opt	3723	90.16	93.61	96.94
	NN + 2opt Take Best	4421	89.79	92.18	95.17
	NN + 3opt-ND(24)	5982	88.61	90.61	92.40
	NN + 3opt-NC(24)	3691	88.57	90.66	94.46
6	NN	100	100.00	106.80	114.76
	NN + 2opt	4853	85.03	88.16	92.81
	NN + 2opt Take Best	5087	85.07	86.95	91.02
	NN + 3opt-ND(24)	5882	83.19	84.86	87.59
	NN + 3opt-NC(24)	3823	83.69	85.11	88.18
7	NN	100	100.00	104.23	110.78
	NN + 2opt	4487	86.00	88.67	92.58
	NN + 2opt Take Best	5287	84.92	86.93	88.92
	NN + 3opt-ND(24)	5882	83.92	85.59	88.45
	NN + 3opt-NC(24)	3923	83.63	85.60	88.26
8	NN	100	100.00	109.86	116.72
	NN + 2opt	5285	86.01	89.92	93.72
	NN + 2opt Take Best	5951	86.04	89.06	91.54
	NN + 3opt-ND(24)	5985	84.57	86.88	90.18
	NN + 3opt-NC(24)	3523	84.83	86.74	89.65
9	NN	100	100.00	104.99	110.15
	NN + 2opt	4321	87.50	90.42	93.91
	NN + 2opt Take Best	4721	87.01	88.96	90.70
	NN + 3opt-ND(24)	5951	85.97	87.41	89.39
	NN + 3opt-NC(24)	4055	85.51	87.37	89.05
10	NN	100	100.00	106.83	115.85
	NN + 2opt	4321	90.29	92.68	96.71
	NN + 2opt Take Best	4721	89.26	90.50	92.66
	NN + 3opt-ND(24)	5717	89.08	90.35	92.09
	NN + 3opt-NC(24)	3823	89.15	90.24	91.92