Key Takeaways Classic TSP is one closed route for one traveler or vehicle that visits every required location exactly once and minimizes a defined travel cost.For symmetric costs with a fixed start and reverse tours treated as equivalent, the distinct-tour count is (n-1)!/2, but modern exact methods do not simply enumerate every tour.The optimization problem is NP-hard; the bounded yes-or-no decision version is NP-complete. Those labels are related but not interchangeable.An algorithm guarantee applies only under its stated assumptions. Christofides' 3/2 guarantee is for metric TSP, while nearest neighbor, 2-opt, and Lin-Kernighan are heuristics without a universal optimality certificate.Multiple vehicles, capacities, time windows, pickups, optional stops, breaks, or live changes usually turn a pure TSP into a VRP or another constrained routing model. A driver has one vehicle, a fixed list of stops, and one question: which visit order has the lowest travel cost? If the route starts and ends at the same depot, visits every required location exactly once, and has no capacity, time-window, or assignment decision, the task matches the classic traveling salesman problem. Change any of those rules and you may be solving a different model. The University of Waterloo’s TSP project states the standard problem precisely: given locations and the travel cost between each pair, find the cheapest closed tour through them all. That compact definition is why TSP is useful. It isolates sequence from the many other decisions that make delivery and field-service routing operationally difficult. This guide shows you how to write the model, count the brute-force search space correctly, distinguish optimization hardness from decision complexity, and compare exact, approximation, and heuristic methods without inventing a universal stop limit. You will also see where TSP stops being the right abstraction. The final sections translate the theory into a route-model decision, a pilot scorecard, and a clear boundary for what route-planning software can and cannot prove. I work on route planning at Upper, where the TSP model is the starting point and almost never the finishing one. What Is the Traveling Salesman Problem? The traveling salesman problem asks for the minimum-cost closed tour that visits every required location exactly once and returns to its starting location. A TSP instance has locations, a travel-cost value for each allowed movement, and an objective. The cost may represent distance, time, money, risk, or another additive measure. The output is an ordered cycle and its total cost. The model is small enough to state in one sentence, but every word matters. A route that can end anywhere is an open path problem. A plan with several vehicles is a multiple-TSP or VRP. A plan that may skip low-priority stops is a prize-collecting or optional-visit variant. Model element Classic TSP rule Question to verify Traveler or vehicle Exactly one Is one resource serving every location? Start and end Same location Must the route return to its origin? Visits Every required location exactly once Can a stop be skipped, repeated, or split? Travel cost Known for each movement Is cost symmetric, asymmetric, static, and additive? Objective Minimum total tour cost Are workload, lateness, overtime, or balance also objectives? Other constraints None in the basic model Do capacity, windows, breaks, skills, or precedence apply? What Do the Graph Terms Mean? Locations are vertices, direct movements are edges or arcs, and their costs are weights. A tour that visits every vertex once is a Hamiltonian cycle. TSP selects the Hamiltonian cycle with minimum total weight in the given graph. A complete graph assumes a direct cost exists between every pair. A road network does not need a literal direct road between every stop; a routing engine can first calculate the shortest usable travel cost for each origin-destination pair and place those values in a matrix. With the model fixed, the next question is how many tours a naive method would need to compare. Why Does the Number of Possible TSP Tours Grow So Quickly? The number grows factorially because each position in the tour can be filled by one of the remaining locations. For a symmetric TSP, fix the start so rotations are not counted as new tours. The remaining locations can be ordered in (n-1)! ways. Because a tour and its reverse have the same cost under symmetric travel, divide by 2. The distinct count is therefore (n-1)!/2. This formula does not apply unchanged to every variant. In an asymmetric problem, reversing a tour can change its cost, so the reverse may be a different candidate. Open paths, fixed end points, optional visits, and multiple travelers also change the count. Locations Distinct symmetric closed tours Compared with the live page 5 12 Correct 10 181,440 Correct 15 43,589,145,600 Live page doubled the count 20 60,822,550,204,416,000 Correct Formula and scope: University of Waterloo’s number-of-tours explanation. Would Brute Force on 20 Locations Really Take About 1.9 Billion Years? At one full-tour evaluation per second, checking 60,822,550,204,416,000 candidates would take about 1.93 billion years. The arithmetic is valid for that artificial enumeration rate and symmetric count. It is not a benchmark for a modern solver. Exact solvers prune, bound, relax, and cut away large parts of the search space. Factorial candidate growth explains why enumeration is a poor method, but it does not establish a fixed location count beyond which exact solution is impossible. That distinction leads to the complexity labels that are often compressed into one inaccurate sentence. Is the Traveling Salesman Problem NP-Hard or NP-Complete? The optimization TSP is NP-hard, while the decision form that asks whether a tour exists below a stated cost bound is NP-complete. An optimization problem asks for the best tour and its cost. A decision problem asks a yes-or-no question, such as whether any tour has cost at most B. NP-complete is a class for decision problems, so applying that label directly to the optimization task is imprecise. The historical attribution matters too. Stephen Cook’s 1971 work established the first NP-completeness result for Boolean satisfiability. Richard Karp’s 1972 reducibility paper then included a traveling-salesman decision formulation among a set of hard combinatorial problems. Saying Cook proved TSP NP-complete skips that step and blurs two different problem forms. What Does the P Versus NP Connection Mean for Route Planners? It means there is no known algorithm that solves every general TSP instance to proven optimality in polynomial time. It does not mean modest instances are unsolvable, every large instance is equally hard, or heuristics are automatically unreliable. Instance structure, cost geometry, preprocessing, bounds, solver design, hardware, time limit, and the need to prove optimality all affect practical difficulty. Your operating decision should therefore be based on evidence from representative instances, not a universal stop threshold. Exact methods make that evidence explicit by either proving an optimum or reporting what remains unproven. Which Exact Algorithms Can Solve TSP? Exact TSP methods include exhaustive search, subset dynamic programming, integer programming with branch-and-cut, and specialized solvers that combine strong bounds with targeted search. Exact means the method can certify that no cheaper tour exists when it finishes successfully. It does not mean every method searches the same way, or that a solver will produce the certificate within your operating deadline. Choose an exact method when the optimum itself matters, when the instance is a benchmark, or when you need a lower bound or optimality gap to evaluate a faster heuristic. Exact approach Core idea Useful when Main limitation Exhaustive enumeration Evaluate every distinct tour Tiny teaching or test instances Factorial search Held-Karp dynamic programming Store the best path for each visited subset and endpoint Small exact benchmarks and algorithm study Exponential time and memory Integer programming + branch-and-cut Relax the tour model, add violated cuts, and branch when needed Exact research and structured operational instances Proof time varies sharply by instance Specialized exact solver Combine cuts, bounds, branching, and implementation refinements Benchmarks or exact TSP work May not model wider route constraints How Does Held-Karp Dynamic Programming Differ From Brute Force? Held-Karp reuses the best partial route for a visited subset instead of recalculating every permutation independently. Its standard time bound is O(n^2 2^n), with exponential memory. That is a major theoretical improvement over factorial enumeration, but still grows too quickly for a fixed universal claim about practical instance size. Original research record: IBM’s Held-Karp publication page describes the 1961 conference paper and its recursion approach. Can Exact TSP Scale Beyond 20 or 25 Locations? Yes, on some instances and with specialized methods. The Concorde TSP Solver reports optimal solutions for all 110 TSPLIB instances, the largest with 85,900 cities. Waterloo’s milestone record runs from a 49-city solution in 1954 to the 85,900-point solution 52 years later. Those milestones do not mean any 85,900-stop road problem is easy. They show why statements such as ‘exact TSP stops working above 25 cities’ are not defensible without naming the model, instance, algorithm, hardware, time limit, and proof requirement. When proof is not the operating objective, approximation and heuristic methods trade certificates for speed or broader model support. Which TSP Heuristics and Approximation Algorithms Are Useful? Nearest neighbor, local search, Lin-Kernighan, and Christofides can all be useful, but they have different assumptions and different kinds of evidence. A heuristic is judged by the tours it finds, how quickly it finds them, and how consistently it performs on relevant instances. An approximation algorithm also provides a worst-case bound, but only for the problem class covered by its proof. Do not turn empirical success into a universal guarantee. A method that performs well on Euclidean benchmarks can behave differently on asymmetric travel times, nonmetric penalties, or a constrained vehicle-routing model. Method Output evidence Required assumption Do not claim Nearest neighbor Fast feasible starting tour A defined cost matrix Always within 50% of optimal 2-opt Locally improved tour under two-edge swaps Feasible starting tour A fixed global optimality gap Lin-Kernighan Strong empirical heuristic results Usually symmetric TSP formulation Every result is optimal Christofides Tour no more than 3/2 of optimum Nonnegative symmetric metric costs and triangle inequality The bound applies to arbitrary routing Metaheuristic or hybrid Best-known result under a time budget Defined implementation and benchmark A universal near-optimal percentage Why Must Christofides’ Guarantee Be Scoped? Cornell’s Christofides algorithm note states the 3/2 approximation for metric TSP and lists the needed conditions: nonnegative symmetric distance and the triangle inequality. If your cost includes direction-dependent traffic, penalties, time-window violations, or other nonmetric terms, the proof does not transfer automatically. Implementation details matter as well. Google’s routing-options documentation says its CHRISTOFIDES first-solution strategy uses a maximal-matching variant and does not guarantee the metric 3/2 factor. A method name alone is not a certificate. What Does Lin-Kernighan Prove? The 1973 Lin-Kernighan paper reports strong results on the authors’ tested symmetric instances. It also describes the procedure as a heuristic and distinguishes statistical confidence from a proof of optimality. Use that evidence pattern: name the tested set and result, then keep the limitation beside it. See it in action Apply the model to one representative route Import real stops, preserve your travel and service rules, and compare the generated route with the same baseline before expanding the workflow. Review Route Planning → The next decision is not which algorithm sounds most advanced. It is which evidence your use case requires. How Should You Choose an Exact or Heuristic TSP Method? Choose from the required certificate, problem assumptions, decision deadline, instance structure, change rate, and cost of a poor result. Start with the output contract. If the work is a research benchmark, you may need a proven optimum or a certified gap. If the route must be released in minutes and changed during the day, a strong feasible solution with repeatable service performance may be more valuable than a late proof. Then test the actual matrix and rules. Stop count alone is not a sufficient selector. Decision need Preferred evidence Candidate method family Acceptance gate Teaching or tiny benchmark Proven optimum Enumeration or simple exact DP Matches independently checked answer Exact research benchmark Optimum, lower bound, and certificate Branch-and-cut or specialized exact solver Gap reaches zero within budget Daily static one-route plan Stable feasible tour and baseline improvement Constructive heuristic plus local search No rule failure; repeatable score Fast replan Good solution inside a strict time budget Warm-started local or metaheuristic search Change handled before release deadline Constrained multi-vehicle operation Feasible assignment, sequence, and operating metrics VRP solver or route-planning workflow Every hard constraint passes Which Pilot Gates Should Be Fixed Before Solving? Input gate: every required location is present once, coordinates or addresses resolve, and the travel matrix has the intended units. Model gate: start, end, visit, direction, optional-stop, and resource rules match the real operation. Feasibility gate: no capacity, time, skill, break, or precedence rule has been omitted merely to force a tour. Quality gate: compare total cost, worst route, lateness, overtime, and manual corrections with the same baseline work. Proof gate: label the result as proven optimal, bounded by a stated gap, or heuristic. Do not mix those statuses. Timing gate: include import, matrix creation, solve, review, correction, and release time, not solver runtime alone. Change gate: replay a late stop, cancellation, unavailable resource, or matrix update and record what moves. If the feasibility gate introduces more than one vehicle or operational constraints, the model boundary has already moved beyond basic TSP. How Is TSP Different From VRP and Delivery Route Planning? TSP sequences one closed tour, while vehicle routing and delivery planning also assign work across resources and enforce operating constraints. Google’s official routing overview calls TSP the one-vehicle case and treats VRP as the generalization for multiple vehicles. It separately documents capacity, time-window, resource, and optional-visit variants. That boundary is more useful than describing every multi-stop plan as TSP. A route-planning workflow also includes data preparation, driver or vehicle assignment, review, release, navigation handoff, live changes, completion status, and performance measurement. The solver model is one decision component inside that workflow. Problem or workflow Resources Visit rule Typical added rules Classic TSP 1 All once; return to start None in the basic model Open TSP 1 All once; different end allowed Fixed or free end Multiple TSP Several Partition visits among tours Shared depot, route count, balance Capacitated VRP Several Assign and sequence all demand Vehicle capacity and order demand VRP with time windows Several Assign and sequence within windows Service time, availability, lateness Pickup and delivery One or several Paired visits with order Precedence and changing onboard load Route-planning workflow Drivers, vehicles, and office Plan, release, operate, and revise Skills, breaks, proof, changes, oversight See it in action See when one TSP tour becomes a vehicle routing problem Compare the multi-vehicle, capacity, time-window, pickup-and-delivery, and operating constraints that change the model. Read the Vehicle Routing Guide → Where Does Capacity Change the Decision? If every stop has demand and every vehicle has a limit, the planner must decide both assignment and sequence. A short tour that overloads a vehicle is not feasible. Capacity must be checked at the route start and after every pickup or delivery when onboard demand changes. Capacity fields still do not certify physical packing, axle distribution, cargo securement, hazmat compatibility, or temperature-zone placement. Those decisions require their own data and qualified process. See it in action Map capacity before stops are assigned Define matching demand and vehicle-limit fields, then test pickups, deliveries, unassigned work, and exceptions on a representative day. Explore Capacity Optimization → Once the model is right, TSP ideas can still support several operating contexts without turning every context into a pure TSP. Where Is TSP Applied Outside a Textbook? TSP applies wherever one resource must sequence required visits or actions under an additive cost, but the model should be extended when real constraints change that rule. Delivery sequencing is the familiar example. The same structure can describe one technician visiting required jobs, one salesperson visiting accounts, one picker visiting storage locations, or one machine moving among required work points. Each is a true TSP only if the one-resource, visit-once, closed-tour, additive-cost assumptions hold. Google’s TSP example documentation also points to circuit-board drilling as a geometric example. A tool head can be modeled as visiting required drill locations while minimizing travel between them. Production rules such as tool changes, precedence, or multiple heads would require a richer model. Why Are Road Travel Costs Often Asymmetric? One-way streets, turn restrictions, direction-specific traffic, road access, and different start or end locations can make travel from A to B cost something different from B to A. In that case, do not divide the candidate count by 2 and do not rely on a symmetric-metric guarantee without rechecking its assumptions. Travel time can also change by departure time. A static matrix represents one chosen planning condition; time-dependent routing needs a model that updates costs as the route progresses. Applications show where a model may fit. Validation shows whether the generated answer actually satisfies the work. How Do You Validate a TSP or Route-Optimization Result? Validate the input, model, feasibility, objective, proof status, planning effort, and field execution against the same baseline instance. A shorter tour is not automatically a better operating plan. If the matrix is stale, a stop is missing, or a time window was excluded, the solver may optimize the wrong problem perfectly. Keep input and model checks ahead of route-length comparisons. Use both a normal day and one stress case. Preserve every manual correction so the test includes the work needed to make the result executable. Test area Measure Pass condition Failure response Input Locations, matrix coverage, units, timestamps Complete, valid, and traceable Repair source data and rebuild matrix Model Start/end, visit, resource, and hard-rule fit Matches the written operating contract Change the model, not the result label Feasibility Capacity, windows, skills, breaks, precedence Zero hidden hard-rule failures Stop release and expose the conflict Objective Distance, time, cost, lateness, workload Improves agreed objective within guardrails Reweight or separate conflicting goals Proof status Optimal, bounded, or heuristic Status and gap are visible Remove unsupported optimality language Planning effort Import through approved release Meets the operating deadline Find manual cleanup or review bottleneck Execution Overrides, late work, missed stops, completion No critical regression; changes traceable Repair data, rules, or change handling What Can a Public Customer Result Prove? WinWaste is evidence for a route-planning and field-execution workflow, not for a particular TSP algorithm. Its public story describes cart-replacement routes across a 5-person field team. Planning time changed from 45-60 minutes to under 10 minutes, while completed stops per crew per day changed from 40-50 to 55-65. Measure Before Upper After Upper Daily route-planning time 45-60 minutes Under 10 minutes Stops completed per crew per day 40-50 55-65 Public customer source and complete context: WinWaste success story. These results belong to WinWaste and are not a forecast for another operation. The useful evidence pattern is the limitation: named operation, comparable before-and-after units, and no claim that one algorithm caused the full result. Use the same discipline for your pilot. That scorecard provides a practical answer to the guide’s final question: where does TSP theory fit in an Upper workflow? Conclusion: Where Does Upper Fit After the TSP Model? Upper fits after you translate the mathematical tour into an operational route-planning test with stops, vehicles, drivers, constraints, review steps, and exception scenarios. TSP gives you a clean sequencing question and a language for cost, feasibility, optimality, bounds, approximations, and heuristics. It does not decide whether a one-vehicle closed tour is the right representation of your work. For delivery and field operations, first name the model. Add vehicles, capacities, time windows, pickups, service durations, driver availability, and operating changes where they apply. Then compare route quality and planning effort with the same baseline day. Upper can be evaluated for route planning and capacity-aware assignment against a representative route day. This article does not claim that Upper proves a global TSP optimum, exposes a solver gap, implements a named research algorithm, or replaces specialized mathematical-programming software. Bring one representative route day, its hard constraints, and the scorecard you will use to accept or reject the result. Book an Upper demo to review that route-planning workflow against your actual operating rules. The most common questions concern route closure, cost matrices, optimality, heuristics, multiple vehicles, and the point where TSP becomes a constrained routing problem. Use the answers below as model checks. A changed assumption can change both the algorithm family and the meaning of a good result. What Are the Frequently Asked Questions About the Traveling Salesman Problem? 1. Does a TSP route have to return to the starting point? Classic TSP does. If the route may end somewhere else, model an open TSP or a path variant and state whether the end is fixed or chosen by the solver. 2. Can TSP minimize time or cost instead of distance? Yes. Edge weights can represent any additive travel measure, including time or monetary cost. State the unit, timestamp or scenario, direction, and any penalties so readers know what the objective means. 3. Is Google Maps solving the traveling salesman problem? A map can provide point-to-point distances, travel times, or directions. A TSP solver still needs to choose the visit order, and a route operation may require constraints beyond the map matrix. Do not infer the optimization model from the navigation interface alone. 4. Is nearest neighbor always close to optimal? No universal 50% guarantee applies to general nearest-neighbor TSP. Treat it as a fast construction heuristic, then benchmark it on representative instances and compare it with local improvement or a lower bound. 5. What is the multiple traveling salesman problem? Multiple TSP partitions required visits among several travelers, often from a common depot. If capacity, time windows, distinct starts, driver rules, or pickup-and-delivery constraints matter, a VRP formulation is usually more expressive. 6. When should a business use VRP instead of TSP? Use VRP when work must be assigned across multiple vehicles or when vehicle-specific constraints affect feasibility. The model should represent capacity, time, skills, service, breaks, and optional work instead of hiding them after sequencing. 7. Why can routing software return a good route without proving it is optimal? Proving that no better route exists can take much longer than finding a strong feasible route. A solver may stop at a time limit and return its best result. Ask whether it reports an optimum, a bound or gap, or only a heuristic solution.
