Friday, March 3, 2017

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 b c1 d1 d2 c2

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:

X1 X2 Y1 Y2

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:

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.

X1 X2 Y1 Y2 b c d r q p
X1 X2 Y1 Y2 b c d r q p

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)

19 comments:

  1. Whouldn't it be better if in the example links X1,Y1 and X2,Y2 were deleted and X1,X2 / Y1,Y2 created. I understand the idea but on 2D plane links that should be shorter (from algorithm point of view) will always be presented as longer ?

    ReplyDelete
  2. No, would not. Because it is the standard way of showing the idea of reconnecting links on the scheme of symmetric TSP -- to avoid suggesting a specific case (2D Euclidean), but focus on the _general_ idea. See the remark before: "for _any_ type of symmetric TSP...". Please look at schemes for 3-opt and notice that they are consistent.

    I am glad you read the notes carefully, thank you for comments.

    ReplyDelete
  3. How can this method be used in the asymmetric case? Thank you.

    ReplyDelete
  4. Please note that the entire site deals with "Basics of Local Optimization in the *Symmetric* Traveling Salesman Problem".

    Asymmetric case requires distinguishing distance(X,Y) and distance(Y,X). In 2-opt it unfortunatelly means that total cost for a segment is not the same when traversing it 'forward' and 'bacward'. While you can adapt the whole procedure to this fact, you can also use a trick to convert asymmetric problem into symmetric problem with double number of nodes (Jonker, Volgenant 1983).

    ReplyDelete
    Replies
    1. Thank you very much for your help

      Delete
  5. Converting asymmetric problem into symmetric problem can be obtained as follows:
    1. We replace each original city with two cities, say A and A'.
    2. We set distance between A and A' to 'minus infinity'. This way in the solution city A is always connected with city A'.
    3a. All distances 'from' original city are set as distances for city A
    3b. All distances 'to' original city are set as distances for city A'
    4. All distances between non-primed cities and all distances between primed cities are set to 'plus infinity'. This way we avoid connections between any two non-primed or two primed cities.

    ReplyDelete
    Replies
    1. Thank you very much for your help

      Delete
    2. thank you, learn a lot from here, why don't you continue this useful series with some popular metaheuristic algorithm, such as: GA, ILS, VNS...ect?

      Delete
    3. Thank you for your precisely worded question. As for now I am not going to discuss metaheuristic algorithms, because they are what they are: they operate on higher level of searching for a solution. But I cannot rule out that I will deal with them here one day.

      Delete
  6. Will the 2-opt method work on a 3-Dimensional TSP ?

    ReplyDelete
    Replies
    1. Yes.
      It does not assume anything about metric space of problem, except that the function of distance is symmetric, that is: d(pointA, pointB) = d(pointB, pointA)

      Delete
  7. How do you choose the arcs? Is something that no one can explain me. What is the criteria to select the arcs to be removed?

    ReplyDelete
    Replies
    1. The arc to remove and replace should satisfy the inequality that grants that this would shorten a tour. This is explained in 'Starting from geometry' section at the very beginning of this note.

      Delete
  8. Thank you for this clear explanation - I have one question :) Reverse_Segment(tour, (i+1) mod N, j)

    The reverse is happening between i + 1 and j, meaning that if j - i <= 1 tour will be unchanged, right?

    ReplyDelete
    Replies
    1. Basically it would not be possible to do a swap between X1 -> X2 and X2 -> b (EX: X1-b-X2-c-d-etc) assuming:
      i = index where X1 is found
      j = index where X2 is found

      Delete
    2. See "Reversing a segment " part, explanations there and the line of code:

      let inversionSize = ((N + endIndex - startIndex + 1) mod N) div 2

      "N + endIndex - startIndex" is always positive.

      Delete
  9. Hello. Don't know if it is to late but I'd like to thank you for such an elaborate explanation. Most articles don't give detailed explanations as the ones that can be found here.

    ReplyDelete