Traveling Salesman Problem: What is it? How to Solve It?

Introduction

If you manage delivery fleets, schedule field technicians, or coordinate sales teams across dozens of stops a day, you have already encountered a version of the Traveling Salesman Problem—whether you call it that or not. For retailers, 3PL providers, e-grocery platforms, and large-scale logistics operators, the challenge is identical: visit every customer location exactly once, return to base, and do it all in the shortest distance, least time, and lowest cost possible.

The Traveling Salesman Problem (TSP) is one of the most studied combinatorial optimization problems in mathematics and computer science. It asks a deceptively simple question: Given a list of cities and the distances between each pair, what is the shortest possible route that visits each city exactly once and returns to the origin? The answer, however, is anything but simple. TSP is classified as NP-hard, meaning no known algorithm can solve every instance in polynomial time. For just 10 cities, there are 181,440 unique routes to evaluate. Scale that to 50 or 500 stops—the reality for enterprise logistics—and manual planning becomes impossible.

This guide breaks down exactly what TSP is, why it matters for your operations, the algorithms used to solve it, and how AI-powered platforms like Locus turn this theoretical problem into a practical competitive advantage.

What is the Traveling Salesman Problem (TSP)? 

The Traveling Salesman Problem (TSP) is a combinatorial optimization problem that seeks the shortest possible route visiting a set of cities exactly once before returning to the starting city. In graph theory terms, it models cities as vertices, paths between them as weighted edges, and the goal is to find the minimum-weight Hamiltonian cycle—a closed loop that touches every vertex precisely once.

Despite its straightforward definition, TSP becomes exponentially more difficult as you add destinations:

Cities (n)	Unique Routes (Symmetric)	Computation Scale
6	60	Trivial
10	181,440	Seconds
15	~43.6 billion	Hours
20	~60.8 quadrillion	Infeasible by hand
25	~7.76 × 10²³	Requires heuristics/AI

Formula: For a symmetric TSP with n cities and a fixed starting point, the number of unique routes = (n?1)! / 2

This factorial growth is precisely why TSP has captivated mathematicians since the 1930s and remains deeply relevant to logistics professionals today. In 1954, Dantzig, Fulkerson, and Johnson solved an optimal tour for 49 U.S. cities—a landmark achievement that still stands as a milestone in optimization history.

TSP’s relevance spans industries well beyond sales: logistics and delivery routing, airline crew scheduling, microchip manufacturing (drilling holes in PCBs), DNA sequencing, warehouse pick-path optimization, and even computer-generated art.

Why Is TSP Classified as NP-Hard?

Understanding why TSP is NP-hard is critical for logistics leaders evaluating solution approaches. Here is what it means in practical terms:

• NP-hard means no known algorithm can guarantee an optimal solution for every instance in polynomial time—i.e., the computation time grows faster than any polynomial function of the input size.
• The decision version of TSP (“Does a tour of length ? L exist?”) is NP-complete, meaning it is at least as hard as every other problem in the NP class.
• Brute-force complexity is O(n!). Even with the best exact algorithm available—the Held-Karp algorithm at O(2? × n²)—solving for 30+ cities pushes against the limits of modern hardware.

What this means for your business: You cannot solve a 100-stop delivery route to mathematical perfection in any reasonable time. Instead, you need intelligent heuristics or AI-powered optimization that finds near-optimal routes within seconds. This is the gap that platforms like Locus fill—trading marginal optimality for massive operational speed.

Symmetric vs. Asymmetric TSP

TSP comes in two primary variants, and the distinction matters for real-world routing:

Feature	Symmetric TSP (STSP)	Asymmetric TSP (ATSP)
Distance A?B vs. B?A	Equal	May differ
Real-world example	Straight-line or highway distances	One-way streets, tolls, traffic patterns
Unique routes (n cities)	(n?1)! / 2	(n?1)!
Complexity	NP-hard	NP-hard
Common use	Theoretical benchmarks, air travel	Urban delivery, ride-sharing

Most real-world logistics problems are asymmetric: the time to travel from warehouse A to customer B is rarely the same as B back to A due to one-way roads, rush-hour traffic, and turn restrictions. Effective route optimization software must account for asymmetric distances to produce usable routes.

What is the Objective of TSP?

The formal problem statement has not changed since it was crystallized in the 1930s: “Given a list of cities and the distances between each pair, find the shortest possible route that visits each city exactly once and returns to the origin city.” It was one of the most well-formulated optimization problems of its era and remains a foundational model for logistics routing, operations research, and computer science curricula worldwide.

But TSP is no longer confined to a salesman plotting city-to-city routes on a paper map. Its variations now power solutions across the modern economy:

• Microchip manufacturing: A TSP variation optimizes the drill path for circuit board holes, minimizing machine travel time.
• DNA sequencing: Researchers use TSP-based models to determine the optimal order of DNA fragment assembly.
• Paint manufacturing: An asymmetric TSP variant can rearrange color batches to minimize changeover and cleaning costs.
• Warehouse operations: WMS pick-path optimization treats aisle locations as “cities” and picker routes as tours, reducing travel distances by up to 30%.

As enterprises accelerate digital transformation in 2026, TSP-inspired models are embedded into every layer of supply chain planning—from strategic network design to real-time last-mile dispatch.

Is the Traveling Salesman Problem solvable?

The short answer: exactly solvable for small instances, approximately solvable for everything else. The critical nuance is what “solvable” means in practice.

For theoretical benchmarks, researchers have solved TSP instances with tens of thousands of cities to proven optimality—but those computations required enormous processing power and time. For a delivery fleet dispatcher who needs routes in under 60 seconds every morning, “solvable” means finding a route that is within a few percentage points of optimal, fast enough to act on.

The pressure to solve TSP in logistics has never been greater:

• India’s e-commerce industry is projected to contribute $300 billion by 2030, with the entire fulfillment burden resting on last-mile delivery networks.
• Return logistics adds another layer of complexity—particularly in cash-on-delivery markets where it is impossible to predict whether a delivery will earn its cost back.
• Ride-sharing and carpooling create dynamic, multi-stop routing problems during rush hours where every additional passenger pickup deviates from the optimal path.

In all of these cases, the problem is not whether TSP can be solved—it is whether it can be solved fast enough, at scale, under real-world constraints. That is why enterprises increasingly rely on AI-driven route optimization rather than manual planning or static algorithms.

Why Is Solving TSP Crucial for Businesses?

For retailers, 3PL providers, e-grocery platforms, and field service companies, TSP is not an academic exercise—it is a daily operational bottleneck. When you run multiple vehicles across hundreds of stops with tight delivery windows, inefficient routing directly erodes margins.

Benefits of Solving TSP for Enterprise Operations

Benefit	Business Impact
Reduced fuel and labor costs	Shorter routes mean fewer miles driven, less fuel burned, and fewer driver hours billed.
Minimized carbon footprint	Optimized routes can cut CO? emissions proportionally to distance saved.
On-time customer meetings and deliveries	Meeting strict SLAs protects revenue and customer relationships.
Increased stops per route	More appointments or deliveries completed per vehicle per day without extending shift hours.
Improved last-mile customer experience	Predictable ETAs and reliable service build brand loyalty in competitive delivery markets.

Not solving TSP has a compounding cost: missed appointments reduce revenue, fuel waste increases operating expenses, and unpredictable ETAs erode customer trust. For field service and sales teams, the gap between an optimized and unoptimized route can mean the difference between hitting quarterly targets and falling short.

Why Is TSP Challenging to Solve in Practice? 

InThe mathematical complexity of TSP is only half the story. Real-world routing layers additional constraints that make the problem significantly harder:

• No centralized record of appointments: Scheduled and last-minute business visits are often tracked in silos—spreadsheets, emails, or phone calls.
• Traffic congestion: Travel times fluctuate throughout the day, making static routes unreliable.
• Last-minute schedule changes: A new high-priority customer request at 10 AM can invalidate the morning’s entire route plan.
• Strict customer time windows: B2B deliveries and field service calls often require arrival within a 30-minute or 1-hour window.
• Rising operational fleet costs: Fuel, insurance, and driver wages continue to climb, increasing the penalty for inefficiency.
• Vehicle and driver heterogeneity: Different vehicles have different capacities, and different drivers have different certifications or zone familiarity.

With just 10 cities and no constraints, you already face 181,440 possible routes. Add time windows, vehicle capacity limits, and real-time traffic—and the effective search space explodes. This is precisely why manual planning fails and why choosing the right route planning software is a strategic decision for logistics operations.

Using the Hungarian Method

The Hungarian method is often taught as an introductory approach to assignment-type problems related to TSP. If a delivery executive makes 15 stops in a day, even this structured method is too slow to solve by hand. The Hungarian method excels at assignment problems—matching drivers to orders, or vehicles to zones—at minimum cost, but it cannot produce complete multi-stop tours on its own. In practice, it is combined with routing algorithms when both assignment and sequencing need to be solved together.

TSP Algorithms: Exact and Heuristic Approaches

Solving TSP requires choosing between exact methods (guaranteed optimal but slow) and heuristics (fast but approximate). The right choice depends on your problem size and time constraints.

Comparison: TSP Algorithm Approaches

Algorithm	Type	Time Complexity	Guarantees Optimal?	Best For
Brute Force	Exact	O(n!)	? Yes	?10 cities
Held-Karp (DP)	Exact	O(2? × n²)	? Yes	?20–25 cities
Branch and Bound	Exact	Variable (pruned)	? Yes	?30 cities (with good bounds)
Nearest Neighbor	Heuristic	O(n²)	? No	Quick initial route, any size
2-opt / 3-opt	Local Search	O(n²) per iteration	? No	Refining heuristic solutions
AI/ML-based	Metaheuristic	Problem-dependent	? Near-optimal	Enterprise-scale (100+ stops)

1. The Brute-Force Approach

The brute-force method evaluates every possible route and selects the shortest. It guarantees optimality but is only practical for very small instances.

• Fixed starting city: Total routes = (n?1)!
• Symmetric TSP: Unique routes = (n?1)! / 2
• Example: 6 cities ? 60 unique routes. 10 cities ? 181,440 unique routes.

Because route count grows factorially, brute force is limited to theoretical demonstrations or problems with fewer than ~10 stops.

2. The Branch and Bound Method

Branch and bound also guarantees optimality but uses intelligent pruning to avoid evaluating routes that cannot beat the best solution found so far.

• The algorithm builds partial routes incrementally.
• If a partial route’s lower bound already exceeds the best complete tour, that branch is discarded.
• Example: A sales representative planning visits to 8 clients may only need to evaluate a fraction of the 2,520 possible routes because most branches are pruned early.

Branch and bound is significantly faster than brute force but still becomes computationally expensive beyond 25–30 cities.

3. The Nearest Neighbor Heuristic

The nearest neighbor method is a greedy heuristic that builds a tour by always moving to the closest unvisited city. It is fast but often produces suboptimal routes.

• Process: Start at any city ? move to the nearest unvisited city ? repeat ? return to start.
• Time complexity: O(n²)—fast enough for thousands of stops.
• Limitation: It only considers the immediate next step, often creating long “backtrack” segments near the end of the tour.

In practice, companies use nearest neighbor to generate an initial route, then improve it with 2-opt or 3-opt refinement (swapping edges to shorten the tour).

4. The Held-Karp Algorithm (Dynamic Programming)

The Held-Karp algorithm, published in 1962, is the most efficient known exact algorithm for TSP. It uses dynamic programming to avoid redundant calculations by storing solutions to subproblems.

• Time complexity: O(2? × n²)—exponentially faster than brute force’s O(n!).
• Space complexity: O(2? × n)—requires significant memory.
• Practical limit: ~20–25 cities on standard hardware.

How it works:

1. Define subproblems as the minimum cost of visiting a subset of cities ending at a specific city.
2. Build solutions bottom-up, combining smaller subsets into larger ones.
3. The final answer combines all subsets into a complete tour returning to the origin.

For 20 cities, Held-Karp evaluates roughly 20 × 2²? ? 20 million subproblems—manageable for a modern computer, and a massive improvement over the 60+ quadrillion routes brute force would require.

When to use it: Held-Karp is ideal for small-to-medium routing problems where you need a provably optimal solution—such as optimizing a technician’s daily schedule across 15–20 job sites.

Academic TSP solutions

Academic research continues to push the boundaries of TSP solutions. Here are the most notable approaches:

Machine Learning for Vehicle Routing

Researchers at MIT have applied machine learning to decompose large NP-complete problems like TSP into smaller sub-problems. By solving smaller segments first and recombining them, ML models accelerate the overall routing process for large-scale networks—a technique increasingly relevant as delivery volumes grow in 2026.

Zero Suffix Method

This method targets the classical symmetric TSP by simplifying route evaluation, reducing the calculation load compared to traditional exact methods. It is primarily used as a teaching tool and research benchmark.

Biogeography-Based Optimization (BBO)

Inspired by animal migration patterns, BBO treats potential solutions as “habitats” and improves them by exchanging features—mimicking how species adapt across ecosystems. It has shown promise for medium-scale TSP instances.

Meta-Heuristic Multi Restart Iterated Local Search (MRSILS)

MRSILS repeatedly restarts local searches from different starting points to escape local optima. It can outperform Genetic Algorithms, particularly when cities are grouped into geographic clusters—a common pattern in delivery logistics.

Multi-Objective Evolutionary Algorithm (MOEA)

Based on NSGA-II, this approach balances multiple objectives simultaneously—such as minimizing distance while also minimizing travel time or cost. It is designed for scenarios where trade-offs between competing goals must be managed.

Multi-Agent Systems

Multiple autonomous agents collaborate to plan routes across a set of cities with fixed resources. Each agent explores a portion of the solution space, and their combined results converge toward efficient global routes.

Real-world TSP Examples

TSP is far more than a classroom exercise. Its approximate solutions—powered by AI and machine learning—drive measurable results across global logistics.

Last-Mile Delivery

Last mile is the costliest leg of the supply chain. According to a Capgemini report, last-mile delivery accounts for 41% of total supply chain costs. By applying TSP-based optimization, retailers and 3PL providers reduce travel distances, group deliveries more efficiently, and complete more stops per route—directly improving margins. Understanding why your business needs route optimization starts with recognizing this cost reality.

UPS and ORION

UPS developed ORION (On-Road Integrated Optimization and Navigation), a route optimization platform solving TSP-class problems at massive scale. ORION saves UPS an estimated 100 million miles per year, reducing fuel consumption and improving delivery reliability across the network.

Amazon’s Last-Mile Routing Research Challenge

Amazon partnered with MIT and released operational routing data covering 9,000+ routes across U.S. cities to accelerate innovation in large-scale last-mile delivery optimization. The initiative demonstrates how e-commerce leaders depend on TSP-inspired models for daily operations.

Grocery and On-Demand Delivery

In e-grocery logistics, TSP-based routing systems balance delivery density with service speed. Research shows that dynamic routing can significantly improve delivery times in on-demand settings—a critical differentiator as consumer expectations for same-day and next-hour delivery intensify in 2026.

Warehouse Pick-Path Optimization

Inside fulfillment centers, WMS platforms use TSP algorithms to sequence picker routes through aisles. Treating shelf locations as “cities,” these systems minimize walking distances and increase picks per hour—a direct application of TSP that impacts throughput for every e-commerce and retail warehouse.

How does Artificial Intelligence technology help in solving the Traveling Salesman Problem? 

Classical algorithms provide the foundation, but Artificial Intelligence is what makes TSP solvable at enterprise scale under real-world conditions. AI combines mathematical optimization with real-time data analysis, historical pattern recognition, and constraint handling that static algorithms cannot match.

Here is how AI solves TSP for modern logistics operations:

Optimized Decisions for Every Vehicle and Route

Managing business appointments across multiple vehicles and sales teams is a nightmare without intelligent automation. AI-powered platforms generate optimal schedules by factoring in:

• Proximity between stops
• Vehicle capacity and type
• Customer time windows
• Driver certifications and zone familiarity
• Historical traffic patterns

These optimized schedules help businesses strictly adhere to Service Level Agreements (SLAs) while minimizing operational fleet costs.

Read more: The Definitive Guide to Logistics Route Optimization

With fuel prices volatile in the post-pandemic era—compounded by the 2022 Ukraine-Russia trade shocks—fuel has become a larger proportion of carrier operating costs. AI-optimized routing ensures your sales teams and delivery fleets complete the maximum number of stops by traveling the minimum distance.

Accurate Address Recognition

When you are racing between customer appointments, unclear addresses cause delays, missed stops, and wasted fuel. AI-powered route optimization software uses advanced geocoding to convert incomplete or ambiguous text addresses into precise geographical coordinates, reducing the chance of drivers arriving at wrong locations.

Reduced Cost Per Mile

According to the American Transport Research Institute’s “Analysis of the Operational Costs of Trucking: 2022 Update,” the average cost per mile decreased from $1.646 in 2020 to $1.585 in 2021. However, post-pandemic fuel recovery and geopolitical instability have pushed costs upward since then.

AI counters this trend by factoring in business goals and delivery constraints to recommend cost-minimizing routes. The result: more appointments completed per day at a lower per-mile cost—directly protecting margins for retailers, 3PLs, and field service operators.

Improved Fleet Productivity

What happens when drivers travel to locations with few business opportunities? The result is deadhead miles—empty, unproductive travel that inflates costs without generating revenue.

AI analyzes historical performance data to identify underperforming routes and redirect resources toward high-demand zones. Predictive capabilities help stakeholders rightsize fleet utilization and reduce empty miles, ensuring every trip generates value.

The Benefits of Route Optimization for Different Industries

TSP-based route optimization is not a one-size-fits-all proposition. The benefits of route optimization vary by industry:

Industry	Primary TSP Challenge	Key Optimization Benefit
Retail & E-commerce	High stop density, tight delivery windows	More deliveries per route, lower cost per order
3PL & Logistics	Multi-client routing, heterogeneous fleets	Improved fleet utilization, SLA compliance
Field Service	Skill-based scheduling, emergency dispatches	Higher first-time fix rates, reduced windshield time
E-Grocery	Perishable goods, same-day delivery pressure	Faster routes, maintained cold-chain integrity
Manufacturing	Supplier pickup loops, raw material routing	Reduced inbound transport costs

Regardless of vertical, the core principle is identical: find the shortest, most constraint-compliant route across all stops. The scale and constraints differ; the mathematical foundation does not.

Why Choose Locus to Solve TSP at Scale

Unlike generic route planners that optimize for distance alone, the Locus Dispatch Management Platform is engineered for the complexity of enterprise logistics:

• 250+ real-world business constraints: Vehicle capacity, customer time windows, driver certifications, traffic patterns, priority orders, and more—all processed simultaneously.
• Up to 20% cost reduction: Clients consistently report lower fuel, labor, and fleet operating expenses after deploying Locus.
• 66% faster planning cycles: What took hours of manual planning is completed in minutes, freeing dispatchers to manage exceptions rather than build routes.
• AI-powered geocoding: Converts incomplete or ambiguous addresses into precise coordinates, eliminating missed stops caused by address errors.
• No manual intervention: Algorithms generate the most efficient schedules automatically—even for the most complex, multi-stop, multi-vehicle scenarios.
• Proven across industries: Retailers, 3PLs, e-grocery platforms, and manufacturers worldwide rely on Locus for daily route optimization.

Locus does not just approximate a solution to the Traveling Salesman Problem—it solves it under the real-world constraints that matter to your business, every single day.

Conclusion

The Traveling Salesman Problem is a deceptively simple question with profound operational consequences. Its factorial complexity—O(n!)—means that even modest increases in stop count render manual planning useless. For 10 cities, there are 181,440 possible routes; for 20, over 60 quadrillion. Exact solutions are limited to small instances, while real enterprise routing demands near-optimal answers across hundreds of stops in seconds.

Heuristics like nearest neighbor and branch and bound provide fast starting points. The Held-Karp dynamic programming approach offers exact solutions for medium-sized problems. But for the scale, speed, and constraint-density that retailers, 3PLs, and field service companies face daily, AI-powered optimization is the only viable path.

TSP’s relevance is only growing. As e-commerce volumes increase, delivery windows tighten, and fuel costs remain volatile in 2026, the gap between optimized and unoptimized routing widens into a competitive chasm. Variants like the Vehicle Routing Problem (VRP) and asymmetric TSP extend the problem into real-time, multi-vehicle, multi-constraint territory—exactly where platforms like Locus operate.

The Locus Dispatch Management Platform transforms TSP from an unsolvable mathematical challenge into a daily operational advantage. By optimizing against 250+ real-world constraints, it delivers up to 20% cost reduction and 66% faster planning cycles—helping your teams complete more stops, burn less fuel, and meet every SLA.

Ready to solve TSP for your operations? Schedule a Demo with Locus today.