The Traveling Salesman Problem
The traveling salesman problem asks for the shortest route visiting every city once and returning to the start.
The problem
Given a set of cities and the distances between each pair, the traveling salesman problem (TSP) seeks the shortest possible tour that visits every city exactly once and returns to the origin. It is a canonical hard optimization problem with applications in logistics, manufacturing, and circuit design.
Decision and optimization forms
The decision form ("is there a tour shorter than L?") is NP-complete. The optimization form ("find the shortest tour") is NP-hard, since a fast optimizer would answer the decision question too. The difference is why one is called complete and the other hard.
Why brute force fails
With n cities there are on the order of (n-1)!/2 distinct tours. For 20 cities that is over 10^16 tours; for 50 it dwarfs any computer. Exhaustive search is hopeless beyond tiny instances, so exact solvers use branch-and-bound and cutting planes to prune the search space.
Approximation for metric TSP
When distances satisfy the triangle inequality (metric TSP), good approximation algorithms exist. The Christofides algorithm guarantees a tour within 1.5 times the optimum. The general TSP, without the triangle inequality, cannot be approximated to any constant factor unless P equals NP.
Heuristics in practice
- Nearest neighbor: always go to the closest unvisited city
- 2-opt and 3-opt: remove crossings by reversing route segments
- Lin-Kernighan: a powerful local search used in state-of-the-art solvers
A hard problem people still solve
Despite its NP-hardness, TSP instances with tens of thousands of cities are solved to proven optimality with modern solvers, and near-optimal tours for millions of points are found with heuristics. TSP shows that intractable in theory does not mean unsolvable in practice for the instances that arise.