312. 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.

312.1. The 2-opt move

Given a tour , the 2-opt move reverses the segment , giving .

Geometrically: it removes two non-adjacent edges and , and adds and — uncrossing the tour.

Improvement condition: do the swap iff

312.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

312.3. Complexity

• Per pass: pairs to check
• Number of passes: typically in practice
• Total: to reach a 2-opt local optimum

312.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.

312.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.

312.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 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

312.7. See also

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