Traveling Salesman Problem (TSP)

The core mathematical constraint of TSP is the Hamiltonian cycle: a closed loop that visits every vertex exactly once before returning to the start. This distinguishes TSP from general shortest-path problems. In logistics, this maps directly to a single driver completing a full delivery tour. The constraint ensures no stop is skipped and no backtracking occurs unless mathematically optimal. For n cities, the number of possible tours is (n-1)!/2, making brute-force enumeration infeasible beyond roughly 20 stops.

TSP is classified as NP-hard, meaning no known algorithm can solve all instances to optimality in polynomial time. Computational effort grows factorially: a 50-city problem has roughly 10^62 possible tours. This intractability is why logistics platforms rely on heuristics and metaheuristics rather than exact solvers for real-world routing. The NP-hard nature of TSP directly motivates the use of Genetic Algorithms, Simulated Annealing, and Large Neighborhood Search in production systems.

In Symmetric TSP (STSP), the cost to travel from node A to B equals the cost from B to A—a valid assumption for Euclidean distance. In Asymmetric TSP (ATSP), directional costs differ due to one-way streets, turn restrictions, or time-dependent traffic. Last-mile delivery systems almost always model the ATSP variant because real road networks are directional. ATSP doubles the decision variables and is computationally harder to solve exactly.

Metric TSP is a constrained variant where edge costs satisfy the triangle inequality: the direct path between two nodes is never longer than a path through an intermediate node. Euclidean distances naturally obey this property. Metric TSP allows for approximation algorithms with provable guarantees—Christofides' algorithm, for example, produces a tour at most 1.5x the optimal length. Non-metric instances (e.g., airfares with arbitrary pricing) lack such guarantees.

Classical TSP assumes static inputs, but modern logistics demands dynamic re-optimization. New orders arrive mid-tour, traffic conditions shift, and delivery windows tighten. Dynamic TSP continuously resolves the problem as new information emerges, often using rolling-horizon approaches. This requires solving many small TSP instances in milliseconds rather than one large instance overnight. The algorithmic challenge shifts from pure optimality to anytime performance—returning the best solution found within a strict time budget.

In practice, pure TSP is rarely solved in isolation for logistics. It appears as a subproblem within richer frameworks like the Vehicle Routing Problem (VRP). Once a VRP solver assigns a set of stops to a specific vehicle, a TSP solver sequences those stops optimally. This decomposition—cluster first, route second—is a common heuristic strategy. The quality of the TSP solver directly impacts the overall VRP solution, making fast, near-optimal TSP heuristics critical infrastructure.