Fixed radius search – general idea

The condition

Suppose that for some X1, X2, Y1, Y2 occurs:

$$\begin{cases} d(X2, Y2) \ge d(X1, X2) \\ d(X1, Y1) \ge d(Y1, Y2) \end{cases}$$

Hence:

$$d(X1, Y1) + d(X2, Y2) \ge d(X1, X2) + d(Y1, Y2)$$

Therefore the inequity which a 2-opt move must meet to improve a tour::

$$d(X1, Y1) + d(X2, Y2) \lt d(X1, X2) + d(Y1, Y2)$$

holds if at least one of the two conditions is met:

$$\textrm{(a)} \enspace \enspace d(X2, Y2) \lt d(X1, X2)$$

or

$$\textrm{(b)} \enspace \enspace d(X1, Y1) \lt d(Y1, Y2)$$

Simple radius search with 2-opt

Note that for simplicity of the code below we do not change orientation and instead use both conditions.

proc LS_2_Opt_simpleRadius(tour: var Tour_Array) =
  var
    locallyOptimal: bool = false
    i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number
    radius: Length

  while not locallyOptimal:
    locallyOptimal = true
    block two_loops:
      for counter_1 in 0 .. N-1:
        i  = counter_1
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
        radius = distance(X1, X2)

        for counter_2 in 0 .. N-1:
          j = counter_2
          Y1 = tour[j]
          Y2 = tour[(j+1) mod N]
          if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
            continue

          if distance(X2, Y2) > radius:
            if distance(X1, Y1) > radius:
              continue

          if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
            Make_2_Opt_Move(tour, i, j)
            locallyOptimal = false
            break two_loops

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 simple radius search algorithms. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	107.63	117.95
	NN + 2opt	940	86.95	89.18	94.09
	NN + 2opt-simpleR	726	85.37	88.86	93.34
2	NN	100	100.00	107.02	114.02
	NN + 2opt	781	87.52	90.92	98.22
	NN + 2opt-simpleR	587	87.90	90.64	95.50
3	NN	100	100.00	108.09	121.54
	NN + 2opt	974	87.53	90.67	96.83
	NN + 2opt-simpleR	587	87.53	91.05	97.84
4	NN	100	100.00	109.31	118.36
	NN + 2opt	874	86.47	91.60	96.67
	NN + 2opt-simpleR	493	86.85	90.88	97.71
5	NN	100	100.00	108.73	120.07
	NN + 2opt	833	85.77	89.44	96.25
	NN + 2opt-simpleR	626	86.12	89.34	93.99
6	NN	100	100.00	106.37	114.14
	NN + 2opt	833	88.83	91.27	95.10
	NN + 2opt-simpleR	526	87.28	90.67	95.23
7	NN	100	100.00	108.36	116.70
	NN + 2opt	1074	82.51	86.73	91.88
	NN + 2opt-simpleR	681	82.81	86.53	91.64
8	NN	100	100.00	109.35	120.17
	NN + 2opt	681	95.20	97.46	103.04
	NN + 2opt-simpleR	487	94.32	97.70	102.40
9	NN	100	100.00	112.93	125.15
	NN + 2opt	975	90.51	94.84	100.73
	NN + 2opt-simpleR	587	90.97	95.14	99.15
10	NN	100	100.00	110.36	125.80
	NN + 2opt	833	87.38	92.33	97.47
	NN + 2opt-simpleR	626	87.80	92.02	97.50