TravelingSalesmanProblem

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem. Given a set of cities and the distances between every pair of cities, the task is to find the shortest possible route that starts at a city, visits each other city exactly once, and returns to the starting city.

In its symmetric form the distance from i to j equals the distance from j to i; the asymmetric form allows directed distances.

The TSP is NP-hard; the decision version is NP-complete, and exact solutions become impractical as the number of cities grows. Exact approaches include dynamic programming (Held–Karp) with time O(n^2 2^n) and various branch-and-bound and cutting-plane techniques. For metric TSP, where triangle inequality holds, Christofides’ algorithm provides a 1.5-approximation.

Origins and history: The problem arose from mid-20th-century logistics and mathematical optimization. It was formalized for computation and analysis in the linear programming framework by Dantzig, Fulkerson, and Johnson in 1954, and has since become a central model in operations research and theoretical computer science.

Algorithms and approaches: Solving the TSP combines exact methods—such as branch-and-bound, dynamic programming, and modern LP-based cutting planes—with heuristics and metaheuristics, including nearest-neighbor, 2-opt and 3-opt swaps, simulated annealing, genetic algorithms, and ant colony optimization. Such techniques enable practical solutions for large instances.

Applications and impact: The TSP informs vehicle routing, delivery scheduling, and logistics planning, as well as manufacturing and circuit-board drilling. It also serves as a benchmark problem for testing optimization software and algorithms across disciplines.