2.5-opt

2.5-opt algorithm, also known as 2h-opt, is an extension of 2-opt, that takes into account two simple alternative moves of 3-opt type. In its most internal loop it examines not only a 2-opt move, but also two Node Shifts:

before
after
variant A	variant B	variant C

2.5-optimization

proc LS_25_Opt_Take_First(tour: var Tour_Array) =
  ## Optimizes the given tour using 2.5-opt
  # Shortens tour by repeating 2.5-opt moves until no improvement
  # can by done: in every iteration immediatelly makes permanent
  # the first move found that gives any length gain.
  var
    locallyOptimal: bool = false
    i, j: Tour_Index
    X1, X2, Y1, Y2, V0: City_Number

  while not locallyOptimal:
    locallyOptimal = true
    block two_loops:
      for counter_1 in 0 .. N-3:
        i = counter_1
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
        for counter_2 in (counter_1+2) .. N-1:
          j = counter_2
          Y1 = tour[j]
          Y2 = tour[(j+1) mod N]

          if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
            Make_2_Opt_Move(tour, i, j)
            locallyOptimal = false
            break two_loops
          else:
            V0 = tour[(i+2) mod N]
            if V0 != Y1:
              if Gain_From_Node_Shift(X1, X2, V0, Y1, Y2) > 0:
                Make_Node_Shift_Move(tour, (i+1) mod N, j)
                locallyOptimal = false
                break two_loops
            else:
              V0 = tour[(N+j-1) mod N]
              if V0 != X2:
                if Gain_From_Node_Shift(V0, Y1, Y2, X1, X2) > 0:
                  Make_Node_Shift_Move(tour, j, i)
                  locallyOptimal = false
                  break two_loops

Note that this code could be improved to be more efficient:

var
    del_2_Length: Length
    dX1Y1, dX2Y2, dX2Y1: Length
...
        for counter_2 in (counter_1+2) .. N-1:
...
          del_2_Length = distance(X1, X2) + distance(Y1, Y2)
          dX1Y1 = distance(X1, Y1)
          dX2Y2 = distance(X2, Y2)
          if del_2_Length - (dX1Y1 + dX2Y2) > 0:
            Make_2_Opt_Move(tour, i, j)
            locallyOptimal = false
            break two_loops
          else:
            dX2Y1 = distance(X2, Y1)
            V0 = tour[(i+2) mod N]
            if V0 != Y1:
              if (del_2_Length + distance(X2, V0)) - 
                 (dX2Y2 + dX2Y1 + distance(X1, V0)) > 0:
                Make_Node_Shift_Move(tour, (i+1) mod N, j)
                locallyOptimal = false
                break two_loops
            else:
              V0 = tour[(N+j-1) mod N]
              if V0 != X2:
                if (del_2_Length + distance(Y1, V0)) - 
                   (dX1Y1 + dX2Y1 + distance(Y2, V0)) > 0:
                  Make_Node_Shift_Move(tour, j, i)
                  locallyOptimal = false
                  break two_loops

This reduces running times by about 25%. But since for other algorithms we used statistics for unimproved versions, the data below are also taken from runs of the basic version.

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.5-opt algorithms. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	108.79	119.13
	NN + 2opt	1360	82.41	86.28	91.53
	NN + 2.5opt	1973	82.24	86.10	90.26
2	NN	100	100.00	112.19	126.04
	NN + 2opt	1075	90.74	95.07	98.61
	NN + 2.5opt	1562	90.67	94.37	98.81
3	NN	100	100.00	106.74	115.58
	NN + 2opt	1253	89.08	92.96	98.44
	NN + 2.5opt	2813	88.87	92.03	94.75
4	NN	100	100.00	106.17	113.25
	NN + 2opt	1980	87.02	91.50	95.35
	NN + 2.5opt	1773	87.00	90.59	93.88
5	NN	100	100.00	106.40	116.05
	NN + 2opt	1046	87.49	92.30	97.11
	NN + 2.5opt	1559	87.03	91.54	96.61
6	NN	100	100.00	108.92	117.85
	NN + 2opt	1360	90.28	95.28	100.53
	NN + 2.5opt	1560	91.01	94.90	101.26
7	NN	100	100.00	105.35	112.60
	NN + 2opt	975	88.55	92.35	96.38
	NN + 2.5opt	2343	88.77	91.71	97.12
8	NN	100	100.00	114.47	122.94
	NN + 2opt	1046	91.33	94.80	99.07
	NN + 2.5opt	1873	91.10	94.69	101.03
9	NN	100	100.00	106.94	119.14
	NN + 2opt	1460	89.70	93.79	99.39
	NN + 2.5opt	1873	88.81	92.80	97.89
10	NN	100	100.00	108.41	117.03
	NN + 2opt	1460	88.86	93.74	97.66
	NN + 2.5opt	1666	88.64	92.83	98.34