## Monday, March 6, 2017

### 3-opt move cases

In 2-opt move we remove 2 links from cyclic tour, this way obtaining 2 open segments, which we can manipulate and combine them to get a new tour. In 3-opt we remove 3 links, obtaining 3 segments to manipulate. This gives us eight combinations (including the tour identical with the initial one).

 equals original tour case = 0 X1 X2 Y1 Y2 Z1 Z2 a b c equivalent to a single 2-opt move case=1 case=2 case=3 a'bc (=ac'b') abc' ab'c equivalent to two subsequent 2-opt moves case=4 case=5 case=6 ab'c' (=a'cb) a'b'c a'bc' equivalent to three subsequent 2-opt moves case=7 a'b'c' (=acb)

### Gain from 3-opt move

The table with diagrams shows that, unlike in the case of 2-opt, the gain expected from a 3-opt depends also on additional parameter: the type (case) of reconnection.

type
Reconnection_3_Opt_Case = enum
opt3_case_0, opt3_case_1, opt3_case_2, opt3_case_3,
opt3_case_4, opt3_case_5, opt3_case_6, opt3_case_7

proc Gain_From_3_Opt(X1, X2, Y1, Y2, Z1, Z2: City_Number;
optCase: Reconnection_3_optCase): Length_Gain =
## Gain of tour length which can be obtained by performing 3-opt move
# Assumes: X2==successor(X1); Y2==successor(Y1); Z2==successor(Z1)
# Keep compliance with the move proc: make sure that the orientation
# of the cities is in accordance with the orientation of the array
# that is: X1->Y1->Z1 or Y1->Z1->X1 or Z1->X1->Y1, but not Z1->Y1->X1
# Note:    Keep cases consistent with ones in Move_3_Opt proc
var

# the cyclic tour is built from three segments: abc
#   segment a = Z2..X1 (could be = ..X1 & Z2..)
#   segment b = X2..Y1
#   segment c = Y2..Z1
# v' means reversed segment v

case optCase
of opt3_case_0:
return 0  # original tour remains without changes

# 2-OPT MOVES
# move equal to a single 2-opt move
of opt3_case_1:   #  a'bc;  2-opt (i,k)
del_Length = distance(X1, X2) + distance(Z1, Z2)
add_Length = distance(X1, Z1) + distance(X2, Z2)
of opt3_case_2:   #  abc';  2-opt (j,k)
del_Length = distance(Y1, Y2) + distance(Z1, Z2)
add_Length = distance(Y1, Z1) + distance(Y2, Z2)
of opt3_case_3:   #  ab'c;  2-opt (i,j)
del_Length = distance(X1, X2) + distance(Y1, Y2)
add_Length = distance(X1, Y1) + distance(X2, Y2)

# PURE 3-OPT MOVES
# NOTE: all 3 edges to be removed, so the same formula for del_Length
# A) move equal to two subsequent 2-opt moves, asymmetric
of opt3_case_4:   # ab'c'
add_Length = distance(X1, Y1) + distance(X2, Z1) + distance(Y2, Z2)
of opt3_case_5:   # a'b'c
add_Length = distance(X1, Z1) + distance(Y2, X2) + distance(Y1, Z2)
of opt3_case_6:   # a'bc'
add_Length = distance(X1, Y2) + distance(Z1, Y1) + distance(X2, Z2)
# B) move equal to three subsequent 2-opt moves, symmetric
of opt3_case_7:   # a'b'c'
add_Length = distance(X1, Y2) + distance(Z1, X2) + distance(Y1, Z2)
#  else: return 0  # there are only 8 cases of 3-opt reconnecion (0..7)

# cases 4..7 have the same formula for del_Length
if optCase in opt3_case_4 .. opt3_case_7:
del_Length = distance(X1, X2) + distance(Y1, Y2) + distance(Z1, Z2)



### The move

We use the same diagrams to implement 3-opt move:

proc Make_3_Opt_Move(tour: var Tour_Array;
i, j, k: Tour_Index;
optCase: Reconnection_3_optCase) =
## Performs given 3-opt move on tour array representation of the tour
# Note:    Keep cases consistent with ones in Gain_From_3_Opt proc
# Keep compliance with the gain proc: make sure that the orientation
# of the tuple [i,j,k] is in accordance with the orientation
# of the array, that is: k>j>i or i>k>j or j>k>i, but not
# i>j>k nor j>k>i nor k>i>j

# the cyclic tour is built from three segments: abc
#   segment a = [k+1 .. i} (could be = [0..i] & [k+1..N-1])
#   segment b = [i+1 .. j]
#   segment c = [j+1 .. k]
# v' means reversed segment v

case optCase
of opt3_case_0:
# IDENTITY
#   nothing to do, the tour remains without changes

# 2-OPT MOVES
of opt3_case_1:    #  a'bc = a[bc]'
Reverse_Segment(tour, (k+1) mod N, i)
of opt3_case_2:    #  abc'
Reverse_Segment(tour, (j+1) mod N, k)
of opt3_case_3:    #  ab'c
Reverse_Segment(tour, (i+1) mod N, j)

# PURE 3-OPT MOVES
#   A) moves equal to two subsequent 2-opt moves, asymmetric:
of opt3_case_4:    # ab'c'
Reverse_Segment(tour, (j+1) mod N, k)
Reverse_Segment(tour, (i+1) mod N, j)
of opt3_case_5:    # a'b'c
Reverse_Segment(tour, (k+1) mod N, i)
Reverse_Segment(tour, (i+1) mod N, j)
of opt3_case_6:    # a'bc'
Reverse_Segment(tour, (k+1) mod N, i)
Reverse_Segment(tour, (j+1) mod N, k)
#   B) move equal to three subsequent 2-opt moves, symmetric
of opt3_case_7:    # a'b'c' (=acb)
# NB: this move can be implemented by reversing all segments
# without changing their order (a'b'c'), that is as a sequence
# of three 2-opt moves:
Reverse_Segment(tour, (k+1) mod N, i)
Reverse_Segment(tour, (i+1) mod N, j)
Reverse_Segment(tour, (j+1) mod N, k)
# NB: but also can be seen as changing order of segments
# without reversing them (acb). For example:
# when 0 <= i < j < k <= N-1:
#   tour[int(i+1) .. k] = tour[int(j+1) .. k] &
#                         tour[int(i+1) .. j]
#  else: return 0  # there are only 8 cases of 3-opt reconnecion (0..7)


### Why use 3-opt moves?

Each 3-opt move is either identical with 2-opt move or is equal to a sequence of two or three 2-opt moves. Now that 3-opt is more complicated and slower than 2-opt, why would we ever use 3-opt?

It is possible that there exists a sequence of 2-opt moves that improves the tour and it begins with 2-opt move that increases the length of the tour. But because of this “bad” move when we use 2-optimization only, this sequence of moves will not be executed.