3-opt Local Search

3-opt removes three edges and reconnects the three resulting segments in one of seven ways (2-opt only has one). Cases 1–3 reverse segments; cases 4–7 swap segments — the moves 2-opt cannot express. Each pass scans all triples and applies the single best-improving reconnection, repeating until no triple yields an improvement.