Travelling Salesman Problem (TSP)

Key characteristics

TSP instances can be symmetric or asymmetric: symmetric TSP has distances that satisfy d(u,v)=d(v,u); asymmetric TSP does not. Special cases arise when distances obey the triangle inequality, such as Euclidean distances in the plane. Solutions are Hamiltonian cycles in a weighted graph, and the objective is to minimize total weight. The naive exact approach checks all permutations of vertices, which is factorial in complexity and impractical beyond very small sizes.

Historical development

The roots of TSP go back to recreational and mathematical puzzles of the 19th century, including work on Hamiltonian cycles. Formal study advanced in the early 20th century. Mathematicians and practitioners in Vienna and at Harvard investigated the problem in the 1930s. The name "travelling salesman problem" became common in mid-20th-century literature. Early work examined brute-force enumeration and simple heuristics such as the nearest-neighbour rule, noting their limitations for guaranteeing optimality. For further historical notes see materials linked through academic surveys and archives, for example historical overview and classic papers.

Algorithms and approaches

Exact algorithms include dynamic programming methods and branch-and-bound or cutting-plane techniques; these can solve moderate-sized instances optimally. Approximation and heuristic strategies are essential for larger problems. Common heuristics and metaheuristics include nearest neighbour, greedy insertion, 2-opt and 3-opt local improvement, simulated annealing, genetic algorithms, and ant colony optimisation. For metric TSP (triangle inequality), polynomial-time approximation schemes or constant-factor approximations exist in specialized settings. Practical implementations often combine fast heuristics with rigorous improvement phases; see algorithmic surveys and repositories at algorithm collections and research portals.

Applications and examples

Although called a "salesman" problem, TSP models many real-world routing and sequencing tasks: vehicle routing and logistics planning, circuit board drilling, DNA sequencing assembly, and scheduling. In applied settings the pure TSP is often extended with constraints (time windows, capacities, precedence), leading to richer vehicle routing problems. Simple instances—such as a dozen cities on a map—are useful for teaching algorithms, while large practical cases require tailored heuristics and engineering.

Notable facts and distinctions

• TSP is NP-hard in its decision and optimisation forms; no polynomial-time algorithm is known for the general case.
• Special cases like planar Euclidean TSP allow stronger approximation results and practical solvers that perform well on large inputs.
• Research combines theory (complexity, approximability) and practice (fast solvers, benchmark libraries); see community resources at benchmark archives and software galleries.

Because of its clear formulation and wide applicability, TSP remains a benchmark problem: progress in algorithms or computational power often shows up first in improved TSP solutions, making it a persistent focus of both theoretical inquiry and applied optimisation.