## Thursday, March 16, 2017

### 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 X1 X2 Y1 Y2 after variant A variant B variant C X1 X2 Y1 Y2 X1 X2 Y1 Y2 X1 X2 Y1 Y2

### 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
1NN100100.00108.79119.13
NN + 2opt136082.4186.2891.53
NN + 2.5opt197382.2486.1090.26
2NN100100.00112.19126.04
NN + 2opt107590.7495.0798.61
NN + 2.5opt156290.6794.3798.81
3NN100100.00106.74115.58
NN + 2opt125389.0892.9698.44
NN + 2.5opt281388.8792.0394.75
4NN100100.00106.17113.25
NN + 2opt198087.0291.5095.35
NN + 2.5opt177387.0090.5993.88
5NN100100.00106.40116.05
NN + 2opt104687.4992.3097.11
NN + 2.5opt155987.0391.5496.61
6NN100100.00108.92117.85
NN + 2opt136090.2895.28100.53
NN + 2.5opt156091.0194.90101.26
7NN100100.00105.35112.60
NN + 2opt97588.5592.3596.38
NN + 2.5opt234388.7791.7197.12
8NN100100.00114.47122.94
NN + 2opt104691.3394.8099.07
NN + 2.5opt187391.1094.69101.03
9NN100100.00106.94119.14
NN + 2opt146089.7093.7999.39
NN + 2.5opt187388.8192.8097.89
10NN100100.00108.41117.03
NN + 2opt146088.8693.7497.66
NN + 2.5opt166688.6492.8398.34