The Most Famous Optimization Problem
The traveling salesman problem (TSP) is deceptively simple to state: find the shortest round trip through N cities. Yet it is computationally one of the hardest problems known. With 15 cities, there are over 43 billion possible tours. With 50 cities, the number exceeds the atoms in the observable universe. No known algorithm can guarantee finding the optimal tour in polynomial time, and most computer scientists believe none exists — this is the essence of the P versus NP problem.
Greedy Start: Nearest Neighbor
The nearest-neighbor algorithm is the simplest TSP heuristic: start at a city, always go to the closest unvisited city, and return home at the end. It runs in O(n²) time and produces a reasonable tour, but it often makes locally optimal choices that lead to globally poor routes — particularly at the end when remaining cities may be far apart. Nearest-neighbor tours are typically 20–25 % longer than optimal, but they serve as excellent starting points for improvement algorithms.
Local Search: The 2-opt Algorithm
The 2-opt algorithm improves an existing tour by systematically testing all possible pairs of edges. If removing two edges and reconnecting the tour segments in the opposite order shortens the total distance, the swap is made. This process repeats until no improving swap exists — the tour is then '2-optimal.' The algorithm is remarkably effective: starting from a nearest-neighbor tour, 2-opt typically reduces distance by 15–25 %, reaching within 5–10 % of the true optimum.
Metaheuristics: Escaping Local Optima
A 2-optimal tour may still be far from globally optimal because it is trapped in a local minimum. Metaheuristics like simulated annealing, genetic algorithms, and ant colony optimization escape these traps by occasionally accepting worse solutions. Simulated annealing, inspired by the slow cooling of metals, accepts uphill moves with a probability that decreases over time. This allows the algorithm to explore broadly early on and converge to a near-optimal solution as the 'temperature' drops — often reaching within 1–2 % of the proven optimum.