Introduction: Why the Traveling Salesman Problem Becomes a Systems Challenge at Scale
One technician, 40 stops, a shift that ends at 5 p.m. Which order do you visit them in? Get it wrong and the day loses an hour of driving, a few late arrivals and a pile of angry calls. The same puzzle shows up in parcel delivery, trucking, field service and outside sales.
The Traveling Salesman Problem (TSP) asks for the minimum-cost closed tour that visits each location once and returns to the start. On paper it is clean. On a real road network it gets messy: one-way streets, traffic, truck restrictions and stale addresses all break the tidy math.
This guide covers why TSP gets hard, which algorithms solve it, and how to build a workflow that holds up in production.
Key Takeaways
- No single TSP algorithm wins: exact methods prove optimality, heuristics deliver speed.
- Geocoding, matrix accuracy and directional costs matter as much as the solver.
- Real fleets turn TSP into the Vehicle Routing Problem (VRP).
- A staged workflow, from clean data to re-optimization, makes routes executable.
What Is TSP and Why Does It Become Hard at Scale?
Formalize the problem in business and graph terms
Stops are nodes. Travel costs are weighted edges. A route is a Hamiltonian cycle: every node once, then back home. The objective can be distance, time, fuel, cost or a weighted mix.
Here is a purely illustrative matrix (minutes) for a depot D and three stops A, B, C:
| From / To | D | A | B | C |
|---|---|---|---|---|
| D | 0 | 10 | 15 | 20 |
| A | 10 | 0 | 35 | 25 |
| B | 15 | 35 | 0 | 30 |
| C | 20 | 25 | 30 | 0 |
D→A→C→B→D costs 10+25+30+15 = 80 minutes. D→A→B→C→D costs 10+35+30+20 = 95 minutes. Same stops, a 15-minute swing. This is a made-up example, not a benchmark.
Understand the scaling problem
With the start fixed, a directed tour set has (n-1)! possibilities. Symmetric TSP halves that to (n-1)!/2, because reversed tours are identical, as the AMS feature column illustrates. Brute force collapses quickly as stops are added.
The optimization version of TSP is NP-hard. In practice, finding some route is easy. Searching an exploding solution space inside a planning window is the hard part.
Model real travel costs correctly
In symmetric TSP, A→B equals B→A. Roads rarely cooperate. One-way streets, turn restrictions and traffic make the problem asymmetric, and direction matters.
Straight-line distance misleads in logistics. You need a road-based matrix, which requires:
- Accurately geocoded stops
- A routing engine with directional costs and vehicle restrictions
- Departure-time assumptions for traffic
- A plan for unreachable pairs
Which Algorithms Can Solve TSP?
Exact algorithms: when proving optimality is worth the cost
- Brute force enumerates every tour. Fine for a handful of stops only.
- Held-Karp dynamic programming runs in O(n²·2ⁿ) time and O(n·2ⁿ) space. These are complexity classes, not runtime estimates.
- Branch and bound / mixed-integer programming gives optimality proofs. Gurobi's own TSP example is positioned for small instances.
A basic assignment model can return several disconnected loops (subtours). Two classic fixes exist. DFJ (1954) adds subtour-elimination constraints, often dynamically as cutting planes. MTZ (1960) adds ordering variables that rule out subtours with a compact model, though its relaxation is weaker.
At the extreme, Concorde solved all 110 TSPLIB instances, including an 85,900-city chip-layout problem. That is a research record, not a production runtime promise.
Heuristics and local search: when fast, strong routes matter more than proof
Nearest neighbor and greedy construction build a feasible tour quickly. Then 2-opt and 3-opt swap edges to remove crossings and wasteful detours.
Johnson and McGeoch's classic benchmarks measured excess over the Held-Karp lower bound, not the true optimum:
- Nearest neighbor: roughly 24-26% above the bound
- 2-opt: about 5% on 10,000-city random instances
- Lin-Kernighan: about 2.8% on large TSPLIB instances
Heuristics are fast and simple but carry no universal optimality guarantee, and results can vary with the starting tour. Those figures come from 1990s datasets, so treat them as direction, not promises.
Metaheuristics, approximation, and AI-assisted search
- Simulated annealing escapes local minima by accepting some worse moves.
- Genetic algorithms are most useful for producing better starting tours.
- Ant colony optimization uses pheromone-style reinforcement of short tours.
- Approximation such as Christofides guarantees 3/2 of optimal for symmetric metric TSP. It is a worst-case theory result.
- Neural solvers can compete in some settings but degrade under distribution shift.
So what's the best algorithm?
There is no winner. Decide by:
- Whether you need proof of optimality
- Number of stops
- Latency allowed
- How often data changes
- Constraint density
- Acceptable optimality gap
How to Build a TSP Solving Workflow That Works at Scale
Prepare reliable stops and operational inputs
Start with data hygiene:
- Geocode and validate addresses. Google's geocoder distinguishes rooftop from approximate matches, and the difference matters.
- Remove duplicates.
- Confirm depot and return rules.
- Flag mandatory and excluded stops.
- Keep service duration, priority, and time windows per stop.
Define the objective before the algorithm. Miles, minutes, fuel, tolls, labor hours, on-time rate, or a weighted blend all produce different routes.
Build and manage the travel-cost matrix
A road matrix needs directional costs, vehicle restrictions, traffic assumptions, and a departure time. Handle unreachable pairs explicitly, since OSRM, for example, can return null for them.
Scale forces batching. Google's Routes API caps a matrix request at 625 elements (100 with traffic-aware optimal), so larger jobs must be split. Cache stable pairs and update incrementally rather than rebuilding every time.
Encode constraints and solve progressively
Separate hard constraints (never violate) from soft ones (trade off with penalties). Over-hardening makes routes infeasible. Optional visits with drop penalties are one way to keep the model solvable.
Then solve in stages:
- Generate a feasible baseline.
- Improve with local or global search.
- Cap runtime or optimality gap.
- Keep the best valid solution if the optimum is out of reach.
Validate, execute, and re-optimize
Before dispatch, check:
- Route continuity and stop coverage
- Vehicle compatibility
- Working-hour compliance
- Time-window feasibility
- Driver route match to the model
After dispatch, track:
- Planned versus actual travel time
- Late or missed stops and deviations
- Solver latency and cost per route
Define re-optimization triggers for new orders, traffic shifts, vehicle loss, and service overruns.
When TSP Becomes the Vehicle Routing Problem
Distinguish the mathematical TSP from operational routing
Classic TSP has one vehicle, one tour, one depot. VRP splits stops across vehicles. US operations add constraints classic TSP ignores:
- Capacity limits and vehicle restrictions
- Driver shifts and service times
- Delivery windows and priority orders
- Skills and pickup-and-delivery pairs
For trucking, FMCSA rules allow 11 driving hours after 10 hours off, and no driving past the 14th consecutive hour on duty. A route that ignores these is unusable.
Choose the right problem formulation
TSP fits a single technician loop or one vehicle's closed tour. When you need multiple vehicles, open routes, pickup-and-delivery pairs, time-dependent travel, or live updates, use the matching VRP formulation instead.
A single-route TSP solver applied to a multi-vehicle fleet yields a mathematically valid sequence that nobody can drive.
Handle live operational changes
Rolling-horizon planning re-optimizes as requests arrive, while respecting work already in progress. Partial re-optimization absorbs new orders, failed deliveries, cancellations, and breakdowns without rebuilding the whole plan.
Where TSP Creates Business Value—and How to Measure It
Connect route quality to operational outcomes
Better sequencing reduces miles and fuel, trims labor hours, completes more stops, improves on-time performance, cuts idle time and tightens ETAs.
The pattern repeats across sectors:
- Last-mile: UPS reports ORION saves about 100 million miles and 10 million gallons of fuel a year. That is a full system, not one algorithm.
- Pest control: an Orkin franchise reported monthly fuel falling from about $2,700 to $2,100 for five technicians (operator-reported).
- Trucking, field service, ride-sharing, food delivery, NEMT: the same sequencing logic with different constraints.
Define a credible measurement framework
Baseline first, then track:
- Total miles and travel time
- Cost per stop
- Stops completed
- Late-arrival rate
- Route-planning time
- Constraint violations
- Driver and customer feedback
Control for demand mix, traffic, seasonality, fleet changes and service-area differences. Otherwise the solver gets credit for a quiet month.
Pilot before scaling
Run representative historical routes plus live scenarios against your current process. Compare feasibility, solution quality, compute time and business outcomes.
A near-optimal route delivered inside the planning window beats a perfect one that arrives after the trucks leave.
How to Choose a Production TSP Solver
Evaluate the solver against the real workload
Checklist:
- Stop volume and vehicle count
- Matrix scale
- Asymmetric and time-dependent costs
- Hard and soft constraints
- Required latency
- Optimality-gap visibility
- Dynamic re-routing
- API limits and integration needs
Test with your own data. Euclidean benchmark rankings do not transfer to road matrices with directional costs and unreachable pairs.
Compare build, library, API, and platform approaches
| Approach | Trade-off |
|---|---|
| Build in-house | Full control; you own modeling, maintenance and map data |
| Open-source or commercial libraries (OR-Tools, VROOM, jsprit, Timefold, Gurobi) | Strong solvers; you still supply matrices, formulation and integration |
| Routing APIs | Fast start; constraint depth and limits vary |
| Full platform | Least engineering; less low-level control |
Check licenses too. LKH is distributed for academic and non-commercial use, and Concorde requires arrangement for other uses. Also weigh mapping-data updates, observability, security, deployment model, support and pricing predictability.
NextBillion.ai for enterprise routing workloads
NextBillion.ai fits businesses whose TSP workloads involve real delivery or field-service complexity. Relevant capabilities:
- Distance matrices up to 5,000 × 5,000
- Truck-compliant routing with vehicle-specific restrictions
- Road Editor App for custom road attributes, applied directly to the routing engine
- 50+ hard and soft constraints
- Route optimization for up to 10,000 stops in a single problem
- Per-vehicle, per-order or fixed-monthly pricing
- Cloud-agnostic and on-premise Kubernetes deployment
- Integration with fleet systems such as Samsara and Geotab
These capabilities line up with the criteria above: accurate inputs, constraint-aware optimization, re-optimization, and a clear path from experiments to production. Verify current specifications against official documentation, and compare results on your own routes in a trial.
Frequently Asked Questions
What is the best TSP algorithm?
It depends on instance size, optimality needs, constraints, data volatility and response time. Exact methods prove optimality; heuristics and metaheuristics scale.
How can the traveling salesman problem be solved?
Build a cost matrix, define the objective and constraints, pick an exact or approximate method, solve within a time budget, then validate the tour.
Can AI solve the traveling salesman problem?
AI can guide search, support prediction and decomposition, and help re-optimization. Neural solvers can degrade on unfamiliar data, and results still depend on accurate inputs and a sound model.
Why is the traveling salesman problem hard?
Possible tours grow factorially and the problem is NP-hard. Asymmetric road costs, time windows, vehicle rules and live changes add further complexity.
Has anyone solved the traveling salesman problem?
Specific instances, including 85,900 cities, have been solved exactly. No fast universal method exists, so large operational cases rely on high-quality approximate solutions.
