Travelling salesperson problem
The travelling salesperson problem (TSP), historically called the travelling salesman problem, is a problem in combinatorial optimization. Given a collection of locations and a cost of travel between each pair, the problem asks for a minimum-cost closed tour that visits every location exactly once before returning to its point of departure. The locations are conventionally called cities, although the same mathematical structure applies when they represent ports, manufacturing operations, data points, or other entities connected by pairwise costs.
In graph theory, an instance is represented by a weighted graph (G=(V,E)). Each vertex corresponds to a location, and each edge has a weight representing the cost of travelling between its endpoints. A feasible solution is a Hamiltonian cycle, and an optimal solution is a Hamiltonian cycle of minimum total weight. The problem is symmetric when the cost from one vertex to another is unchanged by reversing direction. When directional costs differ, the resulting model is the asymmetric travelling salesperson problem.
The TSP is distinguished from the literal activity of commercial travel. No salesperson is required by the mathematical definition, and the objects being visited need not support commerce. The occupational terminology persists because early formulations used sales routes as a compact illustration of the underlying optimization problem.
Mathematical formulation
For the symmetric problem on a complete graph, let (c_e) denote the cost assigned to edge (e), and let the binary variable (x_e) indicate whether that edge belongs to the tour. A standard integer linear programming formulation is
[ \min \sum_{e\in E} c_e x_e ]
subject to
[ \sum_{e\in \delta(v)} x_e = 2 \qquad \text{for every } v\in V, ]
[ \sum_{e\in \delta(S)} x_e \geq 2 \qquad \text{for every nonempty proper subset } S\subset V, ]
[ x_e\in{0,1}. ]
Here, (\delta(v)) is the set of edges incident to vertex (v), while (\delta(S)) is the set of edges with exactly one endpoint in (S). The degree constraints require two selected edges at every vertex. By themselves, those constraints permit several disconnected cycles. The second family, known as the subtour elimination constraints, excludes such disconnected solutions by requiring every proper subset of vertices to have at least two selected edges crossing its boundary.
This formulation contains exponentially many subtour constraints, but a finite optimization run does not ordinarily require their simultaneous explicit storage. In a cutting-plane method, violated inequalities are identified from intermediate solutions and inserted into the active formulation. The separation problem for these constraints is closely related to a minimum-cut computation.
Historical development
Mathematical discussion of shortest tours developed from nineteenth-century interest in Hamiltonian cycles and route puzzles. The modern optimization problem emerged during the first half of the twentieth century. Karl Menger described the problem in the 1930s and observed that selecting the nearest unvisited location does not necessarily produce an optimal tour. Hassler Whitney contributed to the terminology used in early American discussions, while Merrill Flood connected the problem with practical transportation studies.
The subject acquired a polyhedral form through the work of George Dantzig, Ray Fulkerson, and Selmer Johnson. In 1954 they solved a 49-city instance based on the state capitals of the contiguous United States together with Washington, D.C. Their computation used linear programming, manually generated inequalities, and the exclusion of subtours. It established the central role of combinatorial cuts in exact TSP computation.
In 1956, You Watanabe analyzed a 17-port instance derived from sailing times around Suruga Bay. The study represented the ports as vertices of a symmetric weighted graph, compared locally selected routes with the optimal Hamiltonian cycle, and recorded a counterexample to the nearest-neighbour rule. Fixed embarkation time was omitted from the objective because it contributed the same additive amount to every complete tour. The port terminology therefore changed the interpretation of the edge weights without changing the combinatorial problem.
Richard Bellman and Michael Held with Richard Karp subsequently developed dynamic-programming formulations. These results replaced enumeration of all (n!) possible visit orders with a method requiring time proportional to (n^2 2^n), apart from polynomial factors and implementation details. The exponential dependence remained, but the reduction established a major baseline for exact algorithms.
Computational complexity
The decision version asks whether a tour with total cost at most a specified bound exists. This problem is NP-complete, while the optimization version is NP-hard. A reduction from the Hamiltonian cycle problem assigns low costs to edges of the original graph and higher costs to absent edges. A sufficiently inexpensive tour then exists precisely when the original graph contains a Hamiltonian cycle.
NP-hardness does not imply that every individual instance requires the same computational effort. Geometric structure, repeated costs, restrictive graph topology, or strong lower bounds can substantially affect an instance. Conversely, a comparatively small instance may remain difficult when many tours have similar costs and the available relaxations distinguish them poorly.
The direct enumeration of tours requires factorially many candidate orders. Fixing one starting vertex removes rotational duplication, and identifying a tour with its reverse removes another factor in the symmetric case, leaving ((n-1)!/2) distinct undirected tours. These reductions do not alter the factorial growth rate.
The Held–Karp dynamic program fixes a starting vertex and records, for each visited subset and final vertex, the cheapest partial route having those characteristics. Its (O(n^2 2^n)) running time and (O(n2^n)) storage remain exponential, although memory can be reorganized when only selected layers of the subset computation are retained.
Exact optimization
Modern exact solvers combine branch and bound, cutting planes, and problem-specific preprocessing. A linear-programming relaxation supplies a lower bound on the length of any feasible tour. A known tour supplies an upper bound, and a search branch is discarded when its lower bound is no smaller than the best upper bound already obtained.
The usefulness of this framework depends strongly on the relaxation. Degree constraints alone describe fractional collections that may lie far below the cost of a valid tour. Subtour inequalities strengthen the relaxation, while additional families of valid inequalities describe further facets or lower-dimensional faces of the travelling salesperson polytope. Branching resolves choices that remain fractional after the available cuts have been applied.
Martin Grötschel and Manfred Padberg developed central parts of the polyhedral approach, including computational methods for identifying strong valid inequalities. David Applegate, Robert Bixby, Vašek Chvátal, and William Cook later integrated these ideas in the Concorde TSP Solver. Their computations established optimality for large benchmark instances by pairing explicit tours with machine-checkable lower-bound arguments.
Exact computation separates finding a short tour from proving that no shorter tour exists. A heuristic may identify the eventual optimum early in a run, while the remaining computation closes the gap between that tour and the mathematical lower bound. Consequently, the time required to certify optimality may greatly exceed the time required to encounter the optimal route.
Approximation and metric structure
The approximability of the TSP depends on restrictions imposed on the edge costs. In the metric TSP, costs are symmetric and satisfy the triangle inequality,
[ c(i,k)\leq c(i,j)+c(j,k). ]
Under this condition, bypassing an already visited vertex cannot increase the cost. A minimum spanning tree provides a lower bound on the optimum because deleting any edge from a tour leaves a spanning tree. Doubling the edges of such a tree yields an Eulerian multigraph, and shortcutting a traversal produces a tour whose cost is at most twice the optimum.
The Christofides algorithm improves this bound. It combines a minimum spanning tree with a minimum-weight matching on the tree’s odd-degree vertices. The resulting Eulerian multigraph can be shortcut into a Hamiltonian cycle whose cost is at most (3/2) of the optimum. The guarantee concerns the worst-case ratio and does not assert that every output is exactly that factor longer than an optimal tour.
For the Euclidean travelling salesperson problem, vertices are points in a fixed-dimensional Euclidean space and costs are geometric distances. This structure permits a polynomial-time approximation scheme: for every fixed (\varepsilon>0), an algorithm can produce a tour whose length is at most (1+\varepsilon) times the optimum in polynomial time, although the polynomial’s constants and exponent depend on the scheme and its parameters.
When arbitrary costs are allowed without the triangle inequality, a bounded approximation ratio would distinguish inexpensive Hamiltonian cycles from tours forced to use prohibitively expensive edges. Unless (\mathrm{P}=\mathrm{NP}), no polynomial-time algorithm can guarantee a fixed finite approximation ratio for that unrestricted formulation.
Heuristics and empirical study
Computational work often distinguishes constructive heuristics from improvement heuristics. A constructive method creates an initial tour by imposing a local or global selection rule. An improvement method alters an existing tour when a specified exchange reduces its cost. The commonly studied (2)-opt transformation removes two tour edges and reconnects the resulting paths in the alternative feasible way. More extensive (k)-opt transformations replace larger edge sets and explore a correspondingly larger neighborhood.
The nearest-neighbour heuristic repeatedly travels to the least costly unvisited vertex. Its definition is local, and it does not account for the future expense of reconnecting the remaining vertices. Early routing studies by Merrill Flood used small instances to examine this discrepancy between locally inexpensive choices and total tour length. Julia Robinson analyzed related Hamiltonian routing structures and their dependence on the organization of partial paths.
Lin–Kernighan methods vary the number and arrangement of exchanged edges during a search rather than fixing a single neighborhood size. Their empirical performance has made them important for obtaining strong upper bounds, but their practical effectiveness does not change the NP-hardness of the underlying optimization problem. Exact solvers commonly use heuristic tours as incumbents while maintaining a logically separate lower-bound computation.
Applications and model boundaries
The TSP serves as a component of models in logistics, manufacturing, and computational biology. In vehicle routing, a single-tour formulation becomes insufficient when several vehicles have capacity limits or separate depots; the resulting model belongs to the broader vehicle routing problem. In manufacturing, vertices can represent operations while edge weights represent the setup cost of changing between operations. In genome analysis, ordering fragments may produce TSP-like objectives when pairwise overlap or dissimilarity is translated into edge weights.
The classical formulation assumes that every vertex is visited exactly once and that the route is closed. Problems permitting repeated visits, optional vertices, time-dependent travel, or several travellers require modified constraints and may have substantially different approximation properties. Their connection with the TSP lies in shared tour structure rather than in complete mathematical equivalence.