315. TSP 2opt

A simple but effective local search heuristic for the TSP. Iteratively replaces pairs of edges with a cheaper pair until no improvement is possible.

315.1. The 2-opt move

Given a tour $\dots \to 𝐴\to 𝐵\to \dots \to 𝐶\to 𝐷\to \dots$, the 2-opt move reverses the segment $𝐵\to \dots \to 𝐶$, giving $\dots \to 𝐴\to 𝐶\to \dots \to 𝐵\to 𝐷\to \dots$.

Geometrically: it removes two non-adjacent edges $\left(𝐴,𝐵\right)$ and $\left(𝐶,𝐷\right)$, and adds $\left(𝐴,𝐶\right)$ and $\left(𝐵,𝐷\right)$ — uncrossing the tour.

Improvement condition: do the swap iff

315.2. Algorithm

T ← initial tour (e.g., nearest neighbor)
Repeat:
    For each pair of non-adjacent edges (A,B), (C,D) in T:
        If c(A,C) + c(B,D) < c(A,B) + c(C,D):
            Perform 2-opt swap
            Break (or continue to next pair)
Until no improvement found
Return T

315.3. Complexity

• Per pass: $𝑂\left({𝑛}^2\right)$ pairs to check
• Number of passes: typically $𝑂\left(𝑛\right)$ in practice
• Total: $𝑂\left({𝑛}^3\right)$ to reach a 2-opt local optimum

315.4. Why it works

Each successful swap strictly decreases tour length. Since there are finitely many tours and the objective is bounded below, the process terminates.

315.5. 2-opt vs 3-opt vs Lin-Kernighan

Lin-Kernighan dynamically tries 2-opt, 3-opt, …, $𝑘$-opt moves with backtracking. LKH-3 (Helsgaun’s variant) is the state-of-the-art heuristic.

315.6. Practical tips

• Start from a good initial tour (savings algorithm, nearest-neighbor + 2-opt is standard)
• Use neighborhood lists — limit to $𝑘$ nearest neighbors per node to avoid $𝑂\left({𝑛}^2\right)$ pair checks
• First-improvement vs best-improvement — first-improvement (take the first beneficial swap) is usually faster
• Restart from multiple initial tours — local optima vary; multiple runs improve average quality

315.7. See also

• TSP — problem
• Christofides — approximation with worst-case guarantee
• Clarke-Wright — good initial tour for TSP / VRP
• Heuristics — broader local-search family