Optimization with 2-OPT

I’m dividing this post into 2 parts:

Part 1 (this post): Discuss the technique definition, idea and time complexity

Part 2: Applies this technique to a real problem by implementing an heuristic algorithm for the Traveling Salesman Problem.

The 2-OPT technique was first proposed by Croes in 1958. In his paper he defines the technique as an optimized solution for the Traveling Salesman Problem for both symmetric and asymmetric instances (the latter requiring more work). There’s no guarantee that this technique will find a global optimum answer, instead, the returning answer is usually said to be 2-optimal, making it an heuristic. What it actually does is to gradually improve an, initially given, feasible answer (local search) until it reaches a local optimum and no more improvements can be made. Improvements are done using what he calls of “‘inversions’”.

Accordingly to Croes own words the technique can be described as:

Find a trial Solution \(s \in S\), for which M(s) is as small as we can make it at a first try.

Apply some transformations, called ‘inversions’, which transforms this trial solutions into some other elements of S, whose measures are progressive smaller.

Check C for elements which might be included in the final s at an advantage. If there are any such elements try to find a transformation which decreases the measure of the sequence.

The idea is to repeat the above procedure until there’s no improvement. Although real world observations indicated that the algorithm converges quickly, theoretically it can take exponential time.

Why Does It Works?

It works because it removes crossings, the image below illustrates this issue. Removing crossings

This is the same as changing E,A,C,B,D,F,E into E,A,B,C,D,F,E. Visually one can intuitively associate this to a rectangle and note that A,C and B,D are like diagonals which would then be greater than the laterals A,B and C,D. This is obviously a generalization though.

Wikipedia gives a good example of this procedure:

2optSwap(route, i, k) {
     1. take route[1] to route[i-1] and add them in order to new_route
     2. take route[i] to route[k] and add them in reverse order to new_route
     3. take route[k+1] to end and add them in order to new_route
     return new_route;
 }

Here is an example of the above with arbitrary input:

example route: A ==> B ==> C ==> D ==> E ==> F ==> G ==> H ==> A  
   example i = 4, example k = 7  
   new_route:  
       1. (A ==> B ==> C)  
       2. A ==> B ==> C ==> (G ==> F ==> E ==> D)  
       3. A ==> B ==> C ==> G ==> F ==> E ==> D (==> H ==> A)

This is the complete 2-opt swap making use of the above mechanism:

   repeat until no improvement is made {
       start_again:
       best_distance = calculateTotalDistance(existing_route)
       for (i = 0; i < number of nodes eligible to be swapped - 1; i++) {
           for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
               new_route = 2optSwap(existing_route, i, k)
               new_distance = calculateTotalDistance(new_route)
               if (new_distance < best_distance) {
                   existing_route = new_route
                   goto start_again
               }
           }
       }
   }

In python (considering your tour is {A,B,C,D,E,F,G,A}, that is, contains the start point again in the end) the complete procedure will be:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def two_opt(route):
     best = route
     improved = True
     while improved:
          improved = False
          for i in range(1, len(route)-2):
               for j in range(i+1, len(route)):
                    if j-i == 1: continue # changes nothing, skip then
                    new_route = route[:]
                    new_route[i:j] = route[j-1:i-1:-1] # this is the 2woptSwap
                    if cost(new_route) < cost(best):
                         best = new_route
                         improved = True
          route = best
     return best

Convergence

Although fast convergence is not guaranteed it is commonly observed in many real world applications of this technique. A recent study approximates it to be in the order of the number of cities. This makes it a popular heuristic with many practical applications in TSP, VRP and CVRP. It can also be used in other metaheuristic algorithms such as Genetic Algorithms and Simulated Annealing.

Time Complexity

Much has been researched about its time complexity, theoretical proves are rather complex and a recommended reading is given for this in the “References” section of this post. What appears to be the most intuitive and common answer for this procedure is \(O(n!)\). At each iteration the algorithm can apply at most \(O(n^2)\) inversions but the number of overall iterations is weakly bounded by \(O(n!)\) since by removing a crossing the algorithm can consequently create new ones leading to the worst case scenario where all possibilities are tested.

Applications

Jump to Part 2 for a hands-on algorithm explaining how to implement a 2-OPT to solve the Traveling Salesman Problem.

I’m dividing this post into 2 parts:

Why Does It Works?

Convergence

Time Complexity

Applications

References

Related Posts