3-opt move

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).

3-opt move cases.
Symbol prime (') after a letter means that the segment is reversed.

equals original tour
case = 0
equivalent to a single 2-opt move
case=1	case=2	case=3
equivalent to two subsequent 2-opt moves
case=4	case=5	case=6
equivalent to three subsequent 2-opt moves
case=7

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
    del_Length, add_Length: Length

  # 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)

  result = del_Length - add_Length

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
  #   all links between cities are removed and added again;
  #   nothing to do, the tour remains without changes
    discard

  # 2-OPT MOVES
  #   one of the three links is removed and added again
  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
  #   all three links are removed, then other links between cities added
  #   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.