What Are Traveling Salesman Problems?

Traveling salesman problems (TSP) are a family of combinatorial optimization problems that ask for the shortest or lowest-cost route that visits each node in a given set exactly once and returns to the starting node. The canonical formulation involves a set of cities and a matrix of pairwise distances or costs: the goal is to find the Hamiltonian cycle of minimum total cost. The problem generalizes naturally to asymmetric variants, in which travel cost depends on direction, and to multi-objective and constrained variants, in which additional requirements such as time windows, vehicle capacity, or precedence constraints are imposed.

Traveling salesman problems sit at the intersection of combinatorial optimization, graph theory, and computational complexity. Their importance extends beyond the specific routing scenario that names them: TSP is a benchmark for evaluating optimization algorithms, and solutions developed for it have transferred to vehicle routing, job sequencing, and network design. The Cornell Computational Optimization wiki on the traveling salesman problem documents the mathematical formulations, integer programming relaxations, and algorithmic approaches that practitioners use.

Problem Formulation and Complexity

A TSP instance with n cities has (n-1)!/2 distinct tours for the symmetric case, a count that grows factorially and makes exhaustive enumeration impractical for even moderate n. Richard Karp's 1972 proof that the Hamiltonian cycle problem is NP-complete established that TSP in its decision form is NP-complete, implying that no polynomial-time exact algorithm is known (or expected, under standard complexity-theoretic assumptions). The optimization version of TSP, finding the minimum-cost tour, is NP-hard. This complexity motivates the large literature on approximation algorithms and heuristics that produce near-optimal solutions without guaranteeing the global optimum. A key result for the metric TSP (where costs satisfy the triangle inequality) is the Christofides-Serdyukov algorithm, which guarantees a solution at most 1.5 times the optimum. The shortest-path problem, which asks for the minimum-cost path between two nodes rather than a full tour, is polynomially solvable by algorithms such as Dijkstra's and Bellman-Ford, highlighting how the tour closure requirement fundamentally changes the complexity of TSP.

Exact and Approximation Algorithms

Branch-and-bound methods are the primary approach for finding provably optimal TSP solutions. The algorithm maintains an enumeration tree, pruning branches whose lower-bound cost exceeds the best tour found so far. Lower bounds are typically computed by solving a linear programming relaxation, often augmented by cutting planes from the subtour elimination constraints, yielding the branch-and-cut method implemented in the Concorde solver. Concorde has solved TSP instances with tens of thousands of cities to proven optimality. For large instances where proven optimality is not required, heuristic methods provide practical near-optimal solutions. Tour construction heuristics, including nearest neighbor and greedy insertion, quickly build an initial tour. Tour improvement heuristics, particularly 2-opt and 3-opt exchanges and the Lin-Kernighan move, iteratively remove and reinsert segments to reduce total cost. Metaheuristic methods, including simulated annealing, tabu search, genetic algorithms, and ant colony optimization, escape local optima by accepting or generating non-improving moves according to probabilistic or population-based rules. The Springer chapter on the traveling salesman problem surveys these approaches and their performance characteristics across different instance types.

Applications

Traveling salesman problems and their variants have applications across engineering, logistics, and scientific computing, including:

• Vehicle routing and last-mile delivery optimization in logistics networks
• Optimization of printed circuit board drilling sequences to minimize drill head travel
• Job sequencing on machine tools to reduce setup time between operations
• DNA sequencing, where sequence assembly is formulated as a TSP variant
• Telescope observation scheduling to minimize slew time between targets
• Network design and wiring layout in VLSI circuit fabrication