Traveling Salesman Problem (TSP)

The TSP is a classic NP-hard problem, meaning no known algorithm can solve all instances in polynomial time. As the number of cities grows, the solution space expands factorially: for n cities, there are (n-1)!/2 possible tours. A 20-city problem has ~6×10¹⁶ possible routes, making brute-force enumeration computationally intractable. This intractability drives the need for heuristic and metaheuristic solution methods in practical applications.

A valid TSP solution must form a Hamiltonian cycle—a closed loop that visits every node exactly once and returns to the origin. This distinguishes the TSP from simpler pathfinding problems. The constraint eliminates subtours and ensures the route is a single, continuous circuit. In graph-theoretic terms, the solution is a Hamiltonian cycle of minimum total edge weight in a weighted complete graph.

The TSP has two primary variants based on distance reciprocity:

• Symmetric TSP (STSP): The cost from city A to B equals the cost from B to A. Common in Euclidean distance problems.
• Asymmetric TSP (ATSP): Costs differ by direction, modeling one-way streets, airfares, or time-dependent travel. ATSP is more general and computationally harder, requiring directed graph representations.

A metric TSP satisfies the triangle inequality: the direct path between two cities is never longer than a path through an intermediate city. This property enables approximation algorithms with provable guarantees, such as the Christofides algorithm which achieves a 3/2-approximation ratio. Non-metric instances lack this property and are significantly harder to approximate, often requiring general-purpose solvers.

Despite NP-hardness, exact solvers can handle surprisingly large instances using:

• Branch and Bound: Systematically partitions the solution space, pruning suboptimal branches using lower-bound heuristics like the Held-Karp 1-tree relaxation.
• Cutting Plane Methods: Iteratively adds linear constraints to eliminate fractional solutions in integer programming formulations.
• Branch and Cut: Combines both approaches and is the backbone of the Concorde TSP Solver, which has optimally solved instances with over 85,000 cities.

For large-scale or real-time applications, approximate methods dominate:

• Nearest Neighbor: A greedy constructive heuristic that builds a tour by always visiting the closest unvisited city. Fast but can produce poor solutions.
• 2-opt and 3-opt: Local search improvements that iteratively swap edges to eliminate crossings and reduce tour length.
• Lin-Kernighan Heuristic (LKH): A powerful variable-depth local search that remains the gold standard for near-optimal solutions on massive instances.
• Ant Colony Optimization and Genetic Algorithms: Bio-inspired metaheuristics that explore the solution space through population-based search.

A direct generalization of TSP where a fleet of vehicles with limited capacity must service a set of customers. VRP adds constraints like vehicle capacity, time windows, and depot returns, making it the practical logistics counterpart to TSP's theoretical purity. Real-world applications include last-mile delivery, waste collection, and school bus routing.

A declarative paradigm where you state the rules of the problem rather than the steps to solve it. Unlike TSP's explicit route construction, constraint programming lets a solver handle the search. Key techniques include:

• Arc consistency to prune impossible values
• Backtracking search with constraint propagation
• Global constraints like all_different for visit uniqueness Ideal for highly constrained scheduling and routing variants.

The mathematical backbone for solving TSP exactly. MILP formulates TSP using binary decision variables (1 if edge is used, 0 otherwise) and linear constraints. The subtour elimination constraints prevent disconnected cycles. Commercial solvers like Gurobi and CPLEX use MILP with branch-and-cut to solve instances with thousands of nodes to proven optimality.

A probabilistic metaheuristic inspired by metallurgical annealing. The algorithm accepts worse solutions with a probability that decreases over time, escaping local optima that trap greedy TSP solvers. Key parameters:

• Temperature schedule: controls cooling rate
• Neighborhood structure: often 2-opt or 3-opt edge swaps
• Acceptance probability: exp(-ΔE / T) Excels on large TSP instances where exact methods fail.

The Held-Karp algorithm solves TSP exactly in O(n²·2ⁿ) time using dynamic programming. It builds solutions by defining state dp[mask][i] as the shortest path visiting the set of cities in mask and ending at city i. While still exponential, this is dramatically faster than naive O(n!) enumeration and remains the fastest known exact algorithm for general TSP.

An exact algorithm that systematically partitions the solution space while using lower bounds to prune unpromising branches. For TSP, common bounding techniques include:

• Minimum spanning tree lower bound
• 1-tree relaxation
• Assignment problem relaxation When a branch's lower bound exceeds the best known solution, that entire subtree is discarded, dramatically reducing search space.