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.
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.
References
- Croes, Georges A. “A method for solving traveling-salesman problems.” Operations research 6.6 (1958): 791-812.
- Englert, Matthias, Heiko Röglin, and Berthold Vöcking. “Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP.” Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2007.
- Wikipedia 2-opt
- Wikipedia - Heuristic
- Wikipedia - TSP
- Wikipedia - VRP
- Wikipedia - CVRP
- Technical Recipe - C++ Implementation of 2-opt to the “Att48” Travelling Salesman Problem
- StackExchange - Why doesnt 2 opt return an optimal solution
- 2-opt algorithm for traveling salesman
- Average-case approximation ratio of the 2-opt algorithm for the TSP