## Tuesday, March 14, 2017

### Or-opt idea

Or-opt is an algorithm proposed by Ilhan Or in 1976: a segment consisting of 3, 2 or 1 consecutive cities is shifted to other position in tour. This means that Or-opt is a restricted version of 3-opt and therefore it should be somewhat faster, but produce worse tours than full 3-optimization.

### Or-opt move

Each move used by Or-opt is just Segment Shift:

proc Make_Segment_Shift_Move(tour: var Tour_Array;
i, j, k: Tour_Index) =
## Performs given Segment Shift move
Shift_Segment(tour, i, j, k)


### Gain from Or-opt move

proc Gain_From_Segment_Shift(X1, X2, Y1, Y2, Z1, Z2: City_Number):
Length_Gain =
## Gain of tour length which can be obtained by performing Segment
## Shift
# Cities from X2 to Y1 would be moved from its current position,
# between X1 and Y2, to position between cities Z1 and Z2.
# Assumes: X1!=Z1
#          X2==successor(X1); Y2==successor(Y1); Z2==successor(Z1)
let del_Length = distance(X1, X2) + distance(Y1, Y2) + distance(Z1, Z2)
let add_Length = distance(X1, Y2) + distance(Z1, X2) + distance(Y1, Z2)


### Or-opt using the first improving move

proc LS_Or_opt_Take_First(tour: var Tour_Array) =
## Optimizes the given tour using Or-opt
# Shortens the tour by repeating Segment Shift moves for segment
# length equal 3, 2, 1 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, k: Tour_Index
X1, X2, Y1, Y2, Z1, Z2: City_Number

while not locallyOptimal:
locallyOptimal = true

for segmentLen in countdown(3, 1):

block two_loops:
for pos in 0 .. N-1:
i = pos
X1 = tour[i]
X2 = tour[(i + 1) mod N]

j = (i + segmentLen) mod N
Y1 = tour[j]
Y2 = tour[(j + 1) mod N]

for shift in segmentLen+1 .. N-1:
k  = (i + shift) mod N
Z1 = tour[k]
Z2 = tour[(k + 1) mod N]

if Gain_From_Segment_Shift(X1, X2, Y1, Y2, Z1, Z2) > 0:
Make_Segment_Shift_Move(tour, i, j, k)
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 Or-opt algorithms. Random planar problems, N=100.
Problem # Method Time Best Avg Worst
1NN100100.00111.23122.80
NN + 2opt146093.9696.65100.64
NN + Or-opt646094.6497.26102.54
NN + 2opt + Or-opt312692.2994.5997.28
2NN100100.00110.64119.25
NN + 2opt126886.9390.1995.17
NN + Or-opt810689.0093.09101.05
NN + 2opt + Or-opt321885.3088.3391.93
3NN100100.00109.22115.52
NN + 2opt107585.4889.2093.58
NN + Or-opt654386.9192.3598.14
NN + 2opt + Or-opt312585.0187.1990.52
4NN100100.00111.96119.75
NN + 2opt136087.3791.0296.94
NN + Or-opt707987.9295.32104.80
NN + 2opt + Or-opt291985.8389.1994.70
5NN100100.00109.49117.46
NN + 2opt107593.4396.66103.79
NN + Or-opt468793.1297.78103.31
NN + 2opt + Or-opt283192.2894.29100.36
6NN100100.00105.35112.56
NN + 2opt125387.0290.9798.85
NN + Or-opt614687.4392.79100.48
NN + 2opt + Or-opt291386.8489.1894.75
7NN100100.00107.32117.78
NN + 2opt125390.0694.1497.89
NN + Or-opt635392.1895.90100.65
NN + 2opt + Or-opt343988.4491.2895.44
8NN100100.00115.11124.44
NN + 2opt166688.1091.0897.24
NN + Or-opt687990.6596.09102.98
NN + 2opt + Or-opt374686.1688.8492.96
9NN100100.00108.46113.81
NN + 2opt114692.3597.09101.10
NN + Or-opt542094.4099.33105.41
NN + 2opt + Or-opt291391.6794.7798.97
10NN100100.00108.04117.50
NN + 2opt114688.2093.3098.54
NN + Or-opt583388.5895.29102.31
NN + 2opt + Or-opt281388.1291.3494.55