2-opt move

Starting from geometry

Considering a TSP on Euclidean plane we notice that the optimal tour must be “intersectionless”, that is the tour cannot cross over itself.

The tour without intersection must be shorter because of triangle inequities:

$$a \lt c_{1} + d_{1}$$ $$b \lt c_{2} + d_{2}$$ $$a + b \lt ( c_{1} + c_{2} ) + ( d_{1} + d_{2} )$$

Unfortunatelly, not all TSP cases are Euclidean or even metric... but does it change anything important to the idea focused on “crossings” of two links?

The condition for obtaining an improvement

We usually draw the schematic diagram of a tour as a circle with highlighted points:

Note that here we do not use triangle inequity, and still the tour can be shortened by exchanging two links (hence a name: 2-opt) if:

$$d(X1, Y1) + d(X2, Y2) \lt d(X1, X2) + d(Y1, Y2)$$

If the above condition is true, then when we remove links X1-X2 and Y1-Y2 and replace them with links X1-Y1 and X2-Y2, then the tour would become shorter.

This means than for any type of symmetric TSP the tour can be shortened if for some cities the following gain is positive:

proc Gain_From_2_Opt(X1, X2, Y1, Y2: City_Number): Length_Gain =
  ## Gain of tour length that can be obtained by performing
  ## given 2-opt move
  # Assumes: X2==successor(X1); Y2==successor(Y1)
  let del_Length = distance(X1, X2) + distance(Y1, Y2)
  let add_Length = distance(X1, Y1) + distance(X2, Y2)
  result = del_Length - add_Length

Beware

Note that lack of “crossings” is a necessary, but not sufficient condition for tour to be optimal. A tour without “crossings”, that is a tour which is already fully 2-opted may still be not optimal and then it could be shortened by some other types of moves.

The move

Suppose that we want to transform a tour by making the 2-opt move for:

var
  i, j: Tour_Index
  X1, X2, Y1, Y2: City_Number

X1 = tour[i]
Y1 = tour[j]

X2 = tour[(i+1) mod N]  # the successor of X1
Y2 = tour[(j+1) mod N]  # the successor of Y1

From the first look at the diagram it's clear that:

pos.     ...  i  i+1 ...  j  j+1 ...
before   ... -X1-X2- ... -Y1-Y2- ...
after    ... -X1-Y1- ... -X2-Y2- ...

But swapping only X2 and Y1 on their positions in tour would be an error.

The order of cities between X2 and Y1 also has been changed:

before   ... -X1-X2-b-c-d-Y1-Y2- ...
after    ... -X1-Y1-d-c-b-X2-Y2- ...

Therefore the proper solution is to reverse all the segment of tour from X2 to Y1 (see: Reversing a segment):

proc Make_2_Opt_Move(tour: var Tour_Array;
                     i, j: Tour_Index) =
  ## Performs given 2-opt move on array representation of the tour
  # We cut the cyclic tour in 2 places, by removing 2 links:
  #   L1: from t[i] to t[i+1]  and  L2: from t[j] to t[j+1]
  # and replacing them with
  #   L1': from t[i] to t[j]   and  L2': from t[i+1] to t[j+1]
  # This is equivalent to reversing order in segment from 'i+1' to 'j'
  Reverse_Segment(tour, (i+1) mod N, j)