2-opt with Neighbor Lists and Best from given City

proc One_City_2_Opt_N_Best_From_City(tour: var Tour_Array;
                                     basePos: Tour_Index;
                                     neighbor: Neighbor_Matrix;
                                     position: var City_Position_In_Tour;
                                     numberOfNeigbors: int): bool =
  ## Makes the best of improving moves starting from given city
  type
    Move2 = object
      i, j: Tour_Index
      gain: Length_Gain
  var
    improved: bool
    pos_Y2, i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number
    gainExpected: Length_Gain
    bestMove: Move2

  improved = false
  bestMove.gain = 0
  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:
        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):
          continue

        gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
        if  gainExpected > bestMove.gain:
          bestMove = Move2(i: i,  j: j,  gain: gainExpected)
          improved = true
  if improved:
    Make_2_Opt_Move(tour, bestMove.i, bestMove.j, position)
  result = improved

proc LS_2_Opt_N_BC(tour: var Tour_Array;
                   neighbor: Neighbor_Matrix;
                   neighborListLen: int = N-1) =
  ## Optimizes tour using 2-opt with neighbor lists and fixed radius,
  ## for each city makes the best of improving moves that starts from it
  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_Best_From_City(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 algorithms. Random planar problems, N=200.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	109.58	116.87
	NN + 2opt	4421	89.66	92.50	96.98
	NN + 2opt Take Best	4953	87.93	90.77	92.79
	NN + 2opt-NR(24)	265	88.94	91.32	95.01
	NN + 2opt-ND(24)	231	88.72	92.77	96.39
	NN + 2opt-NDR(24)	134	89.36	92.05	95.94
	NN + 2opt-N-BC(24)	497	89.20	92.18	96.75
	NN + 2opt-NR-BC(24)	234	88.42	90.90	95.06
2	NN	100	100.00	106.22	113.13
	NN + 2opt	4289	88.27	91.20	95.07
	NN + 2opt Take Best	5053	88.53	90.12	92.64
	NN + 2opt-NR(24)	265	87.78	90.26	93.83
	NN + 2opt-ND(24)	265	88.96	91.51	94.93
	NN + 2opt-NDR(24)	131	87.83	90.79	93.90
	NN + 2opt-N-BC(24)	499	87.83	90.74	93.97
	NN + 2opt-NR-BC(24)	231	87.11	89.91	93.20
3	NN	100	100.00	110.81	122.10
	NN + 2opt	3503	90.58	94.09	99.85
	NN + 2opt Take Best	4259	90.31	93.01	96.21
	NN + 2opt-NR(24)	201	90.76	93.92	97.50
	NN + 2opt-ND(24)	175	90.50	94.74	100.37
	NN + 2opt-NDR(24)	125	91.10	94.47	99.50
	NN + 2opt-N-BC(24)	403	90.69	94.09	99.06
	NN + 2opt-NR-BC(24)	177	90.26	93.54	97.36
4	NN	100	100.00	108.19	115.51
	NN + 2opt	4155	89.16	92.48	97.91
	NN + 2opt Take Best	4821	88.63	91.13	94.83
	NN + 2opt-NR(24)	331	88.18	91.57	96.27
	NN + 2opt-ND(24)	234	89.36	93.08	96.79
	NN + 2opt-NDR(24)	131	88.74	91.82	96.09
	NN + 2opt-N-BC(24)	597	88.44	92.33	96.40
	NN + 2opt-NR-BC(24)	199	88.23	91.66	95.12
5	NN	100	100.00	105.47	111.66
	NN + 2opt	3100	88.44	91.20	94.82
	NN + 2opt Take Best	3125	87.93	90.83	93.19
	NN + 2opt-NR(24)	198	87.55	90.33	93.73
	NN + 2opt-ND(24)	198	88.04	91.80	95.37
	NN + 2opt-NDR(24)	123	88.07	90.98	95.03
	NN + 2opt-N-BC(24)	322	88.06	91.21	94.08
	NN + 2opt-NR-BC(24)	173	87.45	90.11	94.13
6	NN	100	100.00	106.99	115.27
	NN + 2opt	5119	88.61	91.70	95.36
	NN + 2opt Take Best	5553	86.74	89.36	92.40
	NN + 2opt-NR(24)	297	87.67	90.39	93.91
	NN + 2opt-ND(24)	234	87.99	91.14	94.90
	NN + 2opt-NDR(24)	131	87.63	90.75	93.93
	NN + 2opt-N-BC(24)	500	87.49	90.55	93.80
	NN + 2opt-NR-BC(24)	231	86.69	89.70	91.95
7	NN	100	100.00	109.06	119.98
	NN + 2opt	4853	87.43	90.86	95.27
	NN + 2opt Take Best	4753	86.14	89.41	94.34
	NN + 2opt-NR(24)	265	85.74	89.66	95.14
	NN + 2opt-ND(24)	265	87.58	91.12	96.98
	NN + 2opt-NDR(24)	134	86.64	90.15	96.67
	NN + 2opt-N-BC(24)	565	86.83	90.74	95.90
	NN + 2opt-NR-BC(24)	331	85.83	89.68	95.53
8	NN	100	100.00	106.79	113.15
	NN + 2opt	4953	87.26	91.30	95.33
	NN + 2opt Take Best	5651	87.65	89.53	92.11
	NN + 2opt-NR(24)	231	88.07	90.27	93.96
	NN + 2opt-ND(24)	234	88.31	91.60	95.67
	NN + 2opt-NDR(24)	131	88.13	90.99	95.28
	NN + 2opt-N-BC(24)	500	87.81	90.11	94.61
	NN + 2opt-NR-BC(24)	231	87.36	89.20	92.07
9	NN	100	100.00	104.58	109.98
	NN + 2opt	4089	87.86	91.80	95.52
	NN + 2opt Take Best	5019	87.18	89.66	91.63
	NN + 2opt-NR(24)	399	87.96	90.73	94.13
	NN + 2opt-ND(24)	231	88.53	91.94	94.86
	NN + 2opt-NDR(24)	365	88.24	91.06	94.24
	NN + 2opt-N-BC(24)	929	88.03	91.00	94.26
	NN + 2opt-NR-BC(24)	531	87.73	90.29	93.77
10	NN	100	100.00	106.10	113.14
	NN + 2opt	6682	88.46	90.90	94.87
	NN + 2opt Take Best	5585	87.82	89.72	91.80
	NN + 2opt-NR(24)	297	87.94	90.73	95.79
	NN + 2opt-ND(24)	234	87.70	91.51	94.74
	NN + 2opt-NDR(24)	165	87.96	91.18	96.28
	NN + 2opt-N-BC(24)	563	87.88	90.56	93.03
	NN + 2opt-NR-BC(24)	234	86.44	89.79	92.67