2-Opt Algorithm

2-opt is a simple local search algorithm for the traveling salesman problem, first proposed by Croes in 1958 building on a move already suggested by Flood. It works by taking a route that crosses over itself and reordering it so that it no longer does, comparing every valid combination of the swap, and the technique also applies to related problems such as the vehicle routing problem and its capacitated variant with minor modification.