What is a 2-opt swap in the context of TSP?

Conditions

• Applied to a valid TSP tour.
• Involves exactly two edge removals and reconnections.

Reasoning, step by step

1. Identify two edges in the current tour.
2. Remove the two edges.
3. Reconnect the four endpoints in a different configuration to form a new valid tour.
4. Compare the length of the new tour to the old one.
5. If the new tour is shorter, accept it as the new current solution.

Example

The video shows a 2-Opt swap being applied to a self-crossing greedy route, successfully eliminating the intersection and reducing the total distance from 8969 km to 8570 km.

Common misconceptions

• Believing that a 2-opt swap can only fix self-intersections.
• Assuming that a 2-opt swap always improves the tour length.

Watch the explanation

Explore next

• How does a 2-Opt swap work to improve a route?
• What is the process of Local Search optimization and what is its main limitation?
• Why does the Greedy Algorithm fail to find the optimal solution for TSP?