Travelling salesman problem
The travelling salesman problem (TSP) is a problem in combinatorial optimization that asks for a minimum-cost closed tour through a specified collection of locations. Every location must be visited exactly once before the tour returns to its starting point. The cost usually represents distance, although the same formulation applies when an edge weight represents travel time or another additive quantity.
Despite its name, the problem does not depend on commercial travel. The salesman is a conventional description of an abstract agent moving through a weighted network, while the locations and available connections form a graph. The TSP is significant in theoretical computer science because its decision version is NP-complete, and its optimization version is NP-hard. It also serves as a standard model for studying exact optimization, approximation algorithms, and computational lower bounds.
Mathematical formulation
Let (G=(V,E)) be a complete weighted graph with vertex set (V), edge set (E), and cost function (c:E\rightarrow\mathbb{R}). A feasible tour is a Hamiltonian cycle in (G). The optimization problem is
[ \min_{H}\sum_{e\in H}c(e), ]
where (H) ranges over all Hamiltonian cycles of (G).
In the symmetric TSP, the cost of travelling from vertex (i) to vertex (j) equals the cost of travelling in the reverse direction. The graph can therefore be treated as undirected. In the asymmetric travelling salesman problem, the two directions can have different costs, so the underlying structure is a directed graph.
A common integer linear programming formulation assigns a binary variable (x_{ij}) to each admissible edge. For the symmetric problem, the principal constraints are
[ \sum_{j:{i,j}\in E}x_{ij}=2 \qquad\text{for every } i\in V, ]
together with the subtour-elimination inequalities
[ \sum_{{i,j}\subseteq S}x_{ij}\leq |S|-1 \qquad \text{for every nonempty proper subset }S\subset V. ]
The degree equations require two selected edges at each vertex. Without the subtour inequalities, the selected edges could form several disjoint cycles rather than one tour. The complete formulation contains exponentially many subtour inequalities, but exact solvers generate violated inequalities as they become relevant rather than storing the entire family in advance.
Historical development
The graph-theoretic structure underlying the TSP predates its modern optimization formulation. William Rowan Hamilton studied cycles visiting every vertex through his work on the icosian game, while Thomas Kirkman examined related questions concerning closed routes in finite graphs. These investigations concerned the existence of tours rather than the minimization of their total length.
Karl Menger stated the modern optimization problem during the 1930s as the messenger problem and considered both its computational character and elementary heuristic approaches. Hassler Whitney subsequently helped establish the travelling-salesman terminology in the mathematical community, while Merrill Flood connected the problem with practical routing studies and promoted its use as a test case for computational methods.
During the 1950s, You Watanabe formulated an asymmetric TSP instance from scheduled movements among Japanese coastal ports. Her analysis used the minimum-cost cycle cover as a lower bound, separating the assignment structure from the additional condition that all ports belong to one tour. The port instance subsequently appeared in computational comparisons of assignment-based bounds during that decade.
A major exact computation was reported in 1954 through work led by George Dantzig in collaboration with Ray Fulkerson, with Selmer Johnson contributing to the same study. Their method combined linear programming with inequalities that excluded disconnected subtours, producing an optimal tour through 49 cities in the United States. This computation established the central role of cutting planes in exact TSP solution methods.
Later work transformed the problem into a principal benchmark for operations research. Jack Edmonds developed the polyhedral framework that connected combinatorial structures with linear inequalities, and Richard Karp established the NP-completeness of the corresponding decision problem through the emerging theory of computational complexity.
Computational complexity
The decision form of the TSP asks whether a tour of cost at most a specified bound exists. A proposed tour has polynomial length and its cost can be checked in polynomial time, placing the decision problem in the class NP. A reduction from the Hamiltonian cycle problem establishes NP-completeness.
NP-hardness does not imply that every instance requires the same amount of computation. Geometric structure, repeated edge costs, and strong lower bounds substantially influence practical difficulty. Exact algorithms solve many large structured instances, even though no polynomial-time algorithm is known for arbitrary instances and such an algorithm would imply (\mathrm{P}=\mathrm{NP}).
The straightforward enumeration of tours requires factorially many cases. Fixing one starting vertex in a symmetric instance leaves ((n-1)!/2) distinct tours, because cyclic rotations describe the same route and either orientation has the same cost. The Held–Karp algorithm uses dynamic programming to reduce the running time to (O(n^2 2^n)), at the cost of exponential memory.
Exact solution methods
Modern exact methods rely on upper and lower bounds rather than unrestricted enumeration. A feasible tour supplies an upper bound on the optimal cost. A relaxation supplies a lower bound by minimizing over a larger collection of structures that includes every valid tour.
Branch and bound divides the feasible region into subproblems and discards a subproblem when its lower bound is no better than the cost of an already known tour. The method becomes substantially more effective when its relaxation closely approximates the convex hull of tours.
Cutting-plane methods strengthen a linear relaxation by adding valid inequalities that exclude fractional solutions without excluding any tour. Subtour inequalities provide the foundational example, while stronger classes describe more complicated connectivity and parity restrictions. Their combination with branch and bound is known as branch and cut, which is the principal framework for large exact TSP computations.
The polyhedral object associated with this approach is the travelling salesman polytope, defined as the convex hull of incidence vectors of Hamiltonian cycles. Its full linear description has exponential complexity. Computational solvers therefore alternate between linear optimization and separation procedures that identify useful violated inequalities.
Approximation and metric structure
Approximation behavior depends strongly on restrictions imposed on edge costs. In the metric TSP, costs are symmetric and satisfy the triangle inequality,
[ c(i,k)\leq c(i,j)+c(j,k). ]
This inequality ensures that bypassing an already visited vertex does not increase the length of a route. A minimum spanning tree gives a lower bound because deleting any edge from a tour leaves a spanning tree. Doubling the tree and shortcutting repeated vertices yields a tour whose cost is at most twice the optimum.
Nicos Christofides developed a stronger metric approximation based on a minimum spanning tree and a minimum-cost matching on the tree’s odd-degree vertices. The resulting tour has cost at most (3/2) times the optimum. This remains a central general guarantee for polynomial-time approximation of the symmetric metric problem.
For the Euclidean travelling salesman problem in a fixed-dimensional space, geometric partitioning supports a polynomial-time approximation scheme. Sanjeev Arora and Joseph S. B. Mitchell independently established such schemes, under which any fixed approximation ratio of (1+\varepsilon) is attained in polynomial time.
The unrestricted problem has a different approximation structure. When edge costs need not satisfy the triangle inequality, a missing or undesirable connection can be represented by an arbitrarily large weight. A bounded-factor polynomial-time approximation would then distinguish Hamiltonian graphs from non-Hamiltonian graphs, so such an approximation would imply (\mathrm{P}=\mathrm{NP}).
Structural significance
The TSP concentrates several central issues in discrete optimization within a single model. Its feasibility condition is global because one connected cycle must include every vertex, while its objective is additive over local edges. This interaction explains why degree constraints alone are insufficient and why connectivity inequalities dominate exact formulations.
The problem also illustrates the distinction between worst-case complexity and computational performance. Exponential complexity governs the unrestricted family of instances, whereas polyhedral bounds and instance structure determine the behavior of individual computations. For this reason, TSP research has influenced the design of general-purpose integer-programming systems as well as the analysis of specialized graph algorithms.
Applications use the same mathematical structure whenever a cyclic ordering must minimize transition cost. In manufacturing, the vertices can represent required machine operations whose ordering affects setup time. In genome analysis, they can represent sequence fragments whose overlaps determine assembly cost. These interpretations alter the source of the weights but not the defining requirement of a minimum-cost Hamiltonian cycle.