Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is the foundational combinatorial-optimisation problem of operations research: given N nodes and a pairwise cost (distance, time or money) matrix, find the closed tour that visits every node exactly once at minimum total cost. Formally NP-hard, yet in practice solvable to proven optimum by branch-and-cut at very large scale — the Princeton-Georgia Tech research-group solver has cracked instances with 85K+ nodes (Applegate, Bixby, Chvátal and Cook 2006); LKH (Helsgaun 2000) heuristic stays within 0.1-1% of optimum up to million-node scale. Variants include symmetric TSP (distance A→B = B→A), asymmetric TSP (ATSP, direction-dependent distance), Euclidean TSP, metric TSP (triangle inequality, Christofides 3/2 approximation guarantee), and TSP with profits. Foundational references: Dantzig, Fulkerson and Johnson (1954) for the cutting-plane breakthrough; Lin and Kernighan (1973) for the canonical heuristic; Held and Karp (1962) for the O(n²·2^n) dynamic programming formulation. TSP is the structural backbone of the entire vehicle-routing problem (VRP) family — VRP, VRPTW and PDPTW are extensions of TSP with capacity, time-window and pairing constraints added.