History of Edge-Exchange Search
The Traveling Salesman Problem, introduced in Part 14, is NP-hard. The methods here do not prove optimality; they search for progressively better tours by changing a small number of edges.
The enduring idea is not a particular benchmark percentage. It is the neighborhood: define which nearby tours are reachable by one move, then keep moving to a shorter neighbor until the chosen neighborhood contains no improvement.
The Construct–Improve Pipeline
Construct
Nearest Neighbor supplies a complete feasible tour quickly. Its job is to give local search somewhere sensible to begin.
Improve
2-opt or 3-opt changes a few edges while preserving one cycle. Every accepted move reduces tour length.
Stop
Stop at local optimality, a time budget, a pass limit, or a sufficiently small improvement threshold.
Diversify
Try multiple start cities, random restarts, or perturbations because one local optimum need not be globally best.
Nearest Neighbor Constructive Heuristic
Choose a start city
Mark it visited. Different starts can produce different tours, so a single start is a design choice rather than an invariant.
Take the cheapest immediate step
Move from the current city to its nearest unvisited city; use a deterministic tie-breaker for repeatable output.
Close the cycle
After the last unvisited city, return to the start—even if that closing edge is expensive.
Simple upgrades
Run Nearest Neighbor from several starts and keep the shortest result, or use spatial indexes and candidate lists when scanning every unvisited city is too expensive.
2-Opt Local Search
Choose two nonadjacent tour edges $(A,B)$ and $(C,D)$. Removing them creates two paths. There is exactly one nontrivial way to reconnect those paths into a different undirected cycle: add $(A,C)$ and $(B,D)$, which reverses the segment from $B$ through $C$.
Only four distances change, so the move can be evaluated in constant time:
$$\Delta = d(A,C) + d(B,D) - d(A,B) - d(C,D)$$
Accept when $\Delta < 0$. First improvement applies the first profitable move and restarts scanning; best improvement evaluates the whole neighborhood and applies the most profitable move. Both finish at a 2-opt local optimum, but may reach different tours.
Array operation behind the geometry
For a tour array, replacing $(A,B)$ and $(C,D)$ with $(A,C)$ and $(B,D)$ is exactly a reversal of the contiguous segment $B \ldots C$.
3-Opt Local Search
Remove three mutually nonadjacent edges. The tour becomes three path segments that can be reordered and reversed. For a symmetric tour there are up to seven non-original reconnections: three are effectively 2-opt moves and four are genuine 3-opt moves.
A clear reference implementation may build and score candidate tours explicitly, costing $O(n^4)$ per exhaustive pass. Optimized implementations compare only changed edges in $O(1)$ per reconnection, reducing a full three-cut scan to $O(n^3)$ before candidate-set pruning.
Worked Example: Removing a Crossing
Consider square corners $A(0,0)$, $B(0,1)$, $C(1,0)$, and $D(1,1)$ with the crossing tour $A \to D \to B \to C \to A$.
Euclidean crossing fact
For four points in general position, uncrossing two tour edges strictly shortens the route by the triangle inequality. Therefore, a 2-opt local optimum in a Euclidean instance has no geometric crossings.
Complexity & Performance
| Method | Role | Neighborhood or pass | What stopping means |
|---|---|---|---|
| Nearest Neighbor | Constructive | $O(n^2)$ with a full scan at every step | All cities have been inserted |
| 2-opt | Local improvement | $O(n^2)$ candidate pairs per exhaustive pass | No improving 2-edge exchange exists |
| 3-opt | Richer local improvement | $O(n^3)$ triples with constant-time deltas | No improving tested 3-edge exchange exists |
| Lin–Kernighan | Variable-depth search | Adaptive; practical cost depends on candidate sets and rules | No accepted variable-depth move, or budget reached |
Total runtime is the cost per pass multiplied by the number of accepted moves and restarts. Tour quality is instance-dependent, so report the achieved length, runtime, start strategy, and—when an exact optimum or lower bound is available—the relative gap:
$$\text{gap} = \frac{L_{\text{heuristic}} - L_{\text{reference}}}{L_{\text{reference}}} \times 100\%$$
Implementation
The Python tab includes a deliberately clear 3-opt reference implementation that rebuilds candidate tours. The C++ and Java tabs focus on the most common production baseline—deterministic Nearest Neighbor followed by first-improvement 2-opt.
Real-World Applications
Route construction
Build an initial stop order quickly, then improve it before applying time-window, capacity, or driver constraints in a richer vehicle-routing model.
Tool-path planning
Reduce nonproductive movement among drilling, cutting, inspection, or pick-and-place locations.
Ordering problems
Whenever items have pairwise transition costs, a tour heuristic can provide a fast ordering—even when “distance” is not geographic.
Anytime optimization
Return the current tour at any deadline. More passes or restarts can improve it without sacrificing feasibility.
Exercises
1. Start-city sensitivity
Run Nearest Neighbor from every city of the same instance. Plot the resulting tour lengths and explain why rotation symmetry does not make these runs equivalent.
2. Prove the crossing claim
Use the triangle inequality to show that replacing two crossing Euclidean edges by the appropriate uncrossed pair cannot increase length.
3. Map the 3-opt neighborhood
List the seven non-original reconnections after cutting three nonadjacent edges. Identify the three that reduce to 2-opt and the four genuine 3-opt moves.
4. Escape a local minimum
Add double-bridge perturbations or simulated annealing over 2-opt moves. Compare the best-of-ten result with one deterministic run under the same time budget.
Limitations
- Local is neighborhood-relative: a 2-optimal tour may still have a profitable 3-opt or variable-depth move.
- Starting tours matter: deterministic construction plus deterministic first improvement explores only one basin of attraction.
- No optimality certificate: a locally optimal tour does not reveal its distance from the global optimum unless a separate exact solver or lower bound is available.
- Naive scans scale poorly: full $O(n^2)$ and $O(n^3)$ neighborhoods require candidate lists, geometric filtering, or time budgets on large instances.
- Model assumptions matter: asymmetric costs, forbidden edges, capacities, and time windows require modified move-feasibility checks.
Heuristic versus approximation algorithm
These local-search methods aim for good empirical tours but do not supply Christofides' proven $3/2$ bound for metric TSP. Use Christofides' algorithm when that worst-case certificate is required.