2-opt with Neighbor Lists

proc One_City_2_Opt_N(tour: var Tour_Array;
                      basePos: Tour_Index;
                      neighbor: Neighbor_Matrix;
                      position: var City_Position_In_Tour;
                      numberOfNeigbors: int): bool =
  ## Optimizes the given tour using 2-opt with neighours lists
  # For each edge looks for improvement considering neigbours
  # in ascending order of their distance
  var
    improved: bool
    pos_Y2, i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number

  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[(i+1) mod N]  # == tour[basePos]

      for neighbor_number in 0 .. numberOfNeigbors-1:
        # after 2-opt move new tour would contain direct link X1-Y1,
        # so we look for city Y1 among cities that are close to city X1
        Y1 = neighbor[X1][neighbor_number]
        if direction == forward:
          j = position[Y1]
          Y2 = tour[(j+1) mod N]
        else:
          j  = (N + position[Y1] - 1) mod N  # pos[Y1] == j+1
          Y2 = tour[j]

        if (X2 == Y1) or (Y2 == X1):
          # 2-opt is for non-adjacent links only
          # by constuction X1 != Y1
          continue

        if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
          Make_2_Opt_Move(tour, i, j, position)
          improved = true
          break two_loops
  result = improved

proc LS_2_Opt_N(tour: var Tour_Array;
                       neighbor: Neighbor_Matrix;
                       neighborListLen: int = N-1) =
  ## Optimizes the given tour using 2-opt with neighbor lists
  var
    locallyOptimal: bool = false
    improved: bool
    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:
      improved = One_City_2_Opt_N(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 2-opt and 2-opt with neighbor lists (number of neighbors in parentheses). Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	113.18	126.03
	NN + 2opt	1253	92.30	95.93	101.34
	NN + 2opt-N(99)	939	92.98	95.97	101.72
	NN + 2opt-N(48)	520	92.89	95.89	101.72
	NN + 2opt-N(24)	313	92.89	95.56	101.72
2	NN	100	100.00	106.57	115.38
	NN + 2opt	875	86.02	90.98	96.83
	NN + 2opt-N(99)	1074	86.18	91.23	96.04
	NN + 2opt-N(48)	587	86.18	91.24	94.55
	NN + 2opt-N(24)	293	86.99	91.23	95.95
3	NN	100	100.00	106.76	115.62
	NN + 2opt	1566	82.10	84.87	92.41
	NN + 2opt-N(99)	933	82.80	85.41	90.72
	NN + 2opt-N(48)	526	83.05	85.70	91.73
	NN + 2opt-N(24)	306	82.10	85.66	90.70
4	NN	100	100.00	108.63	115.55
	NN + 2opt	1666	88.48	91.57	98.65
	NN + 2opt-N(99)	940	88.63	92.46	97.13
	NN + 2opt-N(48)	520	88.63	92.69	98.92
	NN + 2opt-N(24)	206	88.37	92.66	97.79
5	NN	100	100.00	107.56	119.38
	NN + 2opt	1046	91.27	94.17	98.35
	NN + 2opt-N(99)	933	90.99	94.80	100.14
	NN + 2opt-N(48)	419	91.85	94.73	98.68
	NN + 2opt-N(24)	206	90.70	94.69	100.00
6	NN	100	100.00	110.60	121.69
	NN + 2opt	1566	87.96	90.86	94.66
	NN + 2opt-N(99)	933	87.79	92.33	96.87
	NN + 2opt-N(48)	420	88.09	92.28	96.82
	NN + 2opt-N(24)	313	87.73	91.84	96.76
7	NN	100	100.00	111.52	123.61
	NN + 2opt	1146	90.06	94.45	97.38
	NN + 2opt-N(99)	833	91.00	94.72	98.71
	NN + 2opt-N(48)	419	90.69	94.67	97.86
	NN + 2opt-N(24)	313	90.64	94.52	97.86
8	NN	100	100.00	111.82	121.50
	NN + 2opt	1360	86.57	90.28	94.59
	NN + 2opt-N(99)	1040	86.77	90.28	95.18
	NN + 2opt-N(48)	519	86.64	90.09	94.81
	NN + 2opt-N(24)	313	86.77	89.86	95.55
9	NN	100	100.00	116.59	127.95
	NN + 2opt	1460	90.19	95.30	104.15
	NN + 2opt-N(99)	1040	90.82	96.62	105.77
	NN + 2opt-N(48)	626	90.82	96.74	105.77
	NN + 2opt-N(24)	313	90.82	96.60	105.77
10	NN	100	100.00	108.10	118.75
	NN + 2opt	881	89.68	94.35	98.28
	NN + 2opt-N(99)	874	89.96	94.64	97.56
	NN + 2opt-N(48)	487	91.84	94.73	99.41
	NN + 2opt-N(24)	200	91.23	94.23	99.17