2-opt


In optimization, 2-opt is a simple local search algorithm for solving the traveling salesman problem.
The 2-opt algorithm was first proposed by Croes in 1958, although the basic move had already been suggested by Flood. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not.
- A B - - A - B -
× >
- C D - - C - D -
A complete 2-opt local search will compare every possible valid combination of the swapping mechanism. This technique can be applied to the travelling salesman problem as well as many related problems. These include the vehicle routing problem as well as the capacitated VRP, which require minor modification of the algorithm.
This is the mechanism by which the 2-opt swap manipulates a given route:
procedure 2optSwap
Here is an example of the above with arbitrary input:
This is the complete 2-opt swap making use of the above mechanism:
repeat until no improvement is made
Note: If you start/end at a particular node or depot, then you must remove this from the search as an eligible candidate for swapping, as reversing the order will cause an invalid path.
For example, with depot at A:
A → B → C → D → A
Swapping using node and node would yield
C → B → A → D → A
which is not valid.