Single vehicle, no capacity, returns to start: find the minimum-distance closed tour visiting each of N nodes exactly once. The foundational combinatorial-optimization problem — every VRP-family problem inherits its backbone (academic name: TSP).
In plain words
Sound familiar?
- We run a single-vehicle field-service operation — a technician visits 8-15 customers per day, the sequence is set by the technician's intuition.
- In a mid-sized manufacturing business a sales representative runs a regional tour one day a week (15-40 supplier or customer visits); single vehicle, no capacity constraint, the order is not optimum.
- We run a PCB drilling machine or an automated pick-and-place machine — the drill or placement head visits 500-5,000 points, the sequence sits in the machine programmer's hand.
- We plan an underground cable-laying route or a pipe-laying sequence — single crew, single tour, no capacity binding.
- An automated warehouse robot (single-pick AS/RS) builds rack-visit tours — robot has no capacity binding or carries one object at a time.
- Urban cold-chain supplier tour (single vehicle, small load constraint); the order is set by the driver's habit.
- Our node count is 50-500 — workable scale for an exact MIP solver, yet 'TSP is NP-hard, must be heuristic' intuition pushes us to a heuristic only.
Why it matters
How it's solved
Technical depth
How it's solved
Technical depthIn one sentence: First build the pairwise distance matrix (real road distance, symmetric or asymmetric), then by scale — for under 1,000 stops, run an exact MIP solver; above that, run k-opt local search (Lin-Kernighan family) — to get the tour in minutes.
In the Operations Research (the discipline that uses math and computers to solve business decisions) literature this problem is the Travelling Salesman Problem (TSP), studied for 70+ years and the foundational problem of modern combinatorial optimization. Canonical statement: given N nodes (cities, customers, drill points, cable junctions) and a pairwise distance (or time, or cost) matrix, find the minimum-total-cost Hamiltonian tour (closed tour visiting each node once) that visits each node exactly once and returns to the start. Single vehicle, no capacity, no time windows, depot always the start node. Solution in three stages:
1. Modelling. Inputs: node list (per node a location or identifier tag), pairwise distance matrix (Euclidean, real road distance, or time — road-based for urban routing, Manhattan for a machine head), symmetry (if distance A→B = B→A, symmetric TSP; otherwise — e.g., one-way streets — asymmetric TSP / ATSP), metric property (if triangle inequality holds, metric TSP, and a 3/2-approximation heuristic with guarantee applies). Objective: minimum total tour cost. Constraints: each node visited exactly once + a single closed tour (subtours forbidden).
2. Solver-driven decision. Three main academic approaches: (i) Exact branch-and-cut MIP (branch-and-cut — tree search with cutting-plane tightening) — the cutting-plane method was introduced in the 1950s; mature solvers have cracked TSP instances up to 85K+ nodes exactly. For field scale (50-500 nodes), commercial or mature open-source MIP (Mixed-Integer Linear Programming — optimisation with some 0/1 variables and some continuous) solvers finish in minutes. (ii) Dynamic programming (Held-Karp) — the 1960s-era O(n²·2^n) DP formulation; practical for n < 25, a teaching reference. (iii) Heuristic — Lin-Kernighan family — k-opt local search (rip out k edges from the tour, rewire to the best alternative); the modern LKH (Lin-Kernighan-Helsgaun) implementation stays within 0.1-1% of optimum up to million-node scale and is the reference heuristic for 1,000+ node field instances. Building-block heuristics: nearest-neighbor, Christofides 3/2-approximation (for metric TSP), savings algorithm, 2-opt, 3-opt local search.
3. Field integration. Output, depending on use, is layered three ways: (a) field-service operation — ordered stop list + navigation in the driver mobile app, assigned at day start, generally not re-optimized intra-day; (b) machine programming — drill or pick-and-place sequence embedded in the NC program of a PCB drilling or pick-and-place machine, computed once per part batch; (c) cable or pipe routing — the route plan of a field engineer, a one-off decision before the dry run. The TSP module is typically embedded inside a routing software or a line-programming package — rarely sold as a stand-alone product. Quarterly operations committee: actual tour distance vs plan, driver-time variance, additional-tour count.
Alternatives
Intuitive sequencing + spreadsheet
FreeZero license
Who it fits: Very small scale (under 10 stops/day), what the planner holds in their head
- + Zero software cost
- + Planner field knowledge counts
- + Phone response to live ETA changes
- − Beyond 20 stops the human mind deviates 20-40% from optimum
- − Inconsistent — sequence differs day to day
- − No measurement — distances are not logged
- − Collapses fast if multi-vehicle or capacity is needed (becomes VRP)
General routing / field-service software (embedded TSP module)
Enterprise100-400 TRY/vehicle/month subscription or 200K-800K TRY one-off license
Who it fits: Field-service operation (10-50 vehicles), single-vehicle tour, no capacity
- + Tour-ordering engine is in place — nearest-neighbor + local improvement is typical
- + Driver mobile app, navigation, customer info integrated
- + Local maps and traffic data
- − Algorithm transparency is low — 'which method is used' is rarely answered clearly
- − A solver with optimum guarantee is typically absent, only fast approximation
- − Beyond 500 stops, gap to the best tour widens
Open-source solver + custom TSP module
Open SourceLicense free; in-house build 8-16 weeks or 200K-800K TRY consultancy
Who it fits: Operation with a tech team, machine programming (PCB, CNC), specialized field route
- + Solvers with optimum guarantee are available open-source
- + Industry-standard heuristic tools that stay near optimum up to million-stop scale are open-source
- + Variants such as one-way-street tours and profit-based tours can be adapted
- − Requires in-house optimisation specialist + integration team
- − From initial prototype to field system takes 3-6 months
- − Maintenance stays in-house
Industry-specific machine-programming package (PCB / CNC)
Enterprise500K-3M TRY embedded inside the machine software package
Who it fits: Automated PCB drilling, pick-and-place, laser cutting — machine-builder package
- + Drill / pick-and-place head sequence is calibrated by the machine builder
- + Machine-program output loads directly to the machine
- + Operator training comes with the machine
- − Tied to the machine builder — re-buy for a different machine
- − Algorithm is opaque, gap to the best tour cannot be measured
- − Customisation (e.g., drill-bit change penalty) is hard
Recommendation
Ask in the meeting
- Which approach is used in the tour-ordering engine — solver with optimum guarantee, nearest-neighbor + local improvement, industry-standard heuristic, or only nearest-neighbor?
- Does the distance matrix support one-way streets and direction-dependent travel time, or are A→B and B→A always assumed equal?
- How is the distance matrix generated — straight-line, real road-based, or traffic-dependent travel-time matrix? Refresh cadence?
- What is the solve time for typical instance sizes — 100, 500, 1,000 stops?
- Is the percentage gap to the best possible tour reported by the module?
- When the problem grows from a single vehicle to capacitated multi-vehicle routing (capacity, multiple tours, depot return), can the same infrastructure be re-used, or is it a separate module?
- If the contract ends, in what format can we export tour data (stop positions, generated tours, distance matrices)?
Technical details
Editor’s note
This problem is known on the operations floor as “tour planning”, “visit ordering” or “route sequencing”. The academic name is unambiguous: Travelling Salesman Problem (TSP). TSP is the foundational problem of operations research — VRP (#002), PDPTW (#046), Berth Allocation (#026) and dozens of other routing / scheduling problems are structural extensions of TSP. The structural distinction is sharp: TSP is single vehicle, single closed tour, no capacity, depot-returning, no time windows. VRP adds multiple vehicles + depot + capacity; VRPTW adds time windows; PDPTW adds source-destination pairing and precedence. Buying a vendor’s “routing module” without testing which of these structures it actually solves means you learn months later — when a multi-vehicle need arises — that the infrastructure does not stretch.
The point most often skipped in the segment: the practical applicability threshold of modern exact TSP solvers. The practitioner’s intuition often runs “TSP is NP-hard (the class of problems whose solve time blows up with size), exact is impossible, we must use heuristics”. The reality is different: mature branch-and-cut solvers have cracked 85K+ node instances exactly; a 100-500 node field instance reaches optimum in minutes on a modern MIP solver. Heuristics (nearest-neighbor + 2-opt) are the default in most products — they deviate 15-30% from optimum on real field data sets. Practical rule: under 1,000 nodes, operational TSP is exact-MIP-solvable; in the 1,000-100K node range, the LKH heuristic stays within 0.1-1% of optimum. The “we must use a heuristic” intuition is wrong; the decision cannot be made without knowing the instance scale.
Second skipped point: the symmetric vs asymmetric TSP distinction. Urban routes with one-way streets, motorway on/off ramps, or direction-dependent travel time yield an asymmetric distance matrix — distance A→B differs from B→A. Most product TSP modules assume symmetry; fed asymmetric data, they produce a wrong optimum. Asymmetric TSP (ATSP) needs a different formulation.
Step-by-step — for the SMB
Stage 1 — Measure first, plan later. At least 8-12 weeks of tour data: per tour — number of stops, stop locations, actual tour distance (vehicle odometer), tour duration, driver identity, whether the sequence was changed intra-day, whether customer-visit windows were honoured. Distance matrix: typical road distance and time between every visited node pair (off-peak vs peak traffic). Without this inventory you cannot tell which software will deliver which result.
Stage 2 — Extract the knowledge capital. Estimate the gap of current intuitive sequencing from optimum: on a 30-50 node single-day data set, compute the exact tour with an open-source MIP solver, compare with the driver’s real tour. A 15-30% gap is typical. This gap is the cornerstone of the software business case. If node count varies day to day, build separate averages for typical vs peak days.
Stage 3 — Pilot. 6-10 weeks. For one vehicle or machine, run the TSP module in parallel with current intuitive sequencing. The decision stays with the driver / operator; the system advises. Success criteria written before the pilot: average tour distance -10% minimum, tour duration -8%, driver satisfaction neutral or positive.
Stage 4 — Rollout. 4-9 months to full fleet or machine park. Quarterly operations committee: actual tour distance vs plan, driver-time variance, customer-window-hit report, machine-head-time report.
Risks — what can go wrong
- Static travel-time assumption. A distance matrix built on single-point average travel times shifts 50-100% from the actual peak-traffic time. Hour-banded travel-time matrices (e.g., a 30-minute arc-time profile) are needed; during the pilot, planned vs actual travel times must be compared.
- Is field service time inside the model? A field technician spends 30-90 minutes at each stop; if this service time is not in the tour plan, the sequence is mathematically optimum but operationally unworkable. Service time per node should be modelled as a fixed or probabilistic value.
- Node count grows, heuristic drifts from optimum. With 50 nodes nearest-neighbor + 2-opt is within 5-10% of optimum; at 500 nodes the gap is 15-25%; at 5,000 nodes 30%+. As scale grows, transition to LKH or exact MIP is required; freezing the heuristic intuition compounds loss with growth.
- Single-vendor routing-software lock-in. Without a contract clause for “annual export of tour data, distance matrices and solution history in a standard format”, leaving the system means losing the operation’s tour-history memory. Customer locations and visit-window data are the core of that memory.
A technical view of the solution method
| Approach | Typical scale | Solve time | Guaranteed optimum? |
|---|---|---|---|
| Intuitive sequencing (planner + head) | <20 nodes | instant | No, 60-80% optimum |
| Nearest-neighbor + 2-opt | 20-200 nodes | seconds | No, 85-95% optimum |
| Christofides 3/2-approximation (metric TSP) | 50-500 nodes | seconds | 3/2 approximation guarantee |
| Dynamic programming (Held-Karp) | <25 nodes | minutes | Yes (exact) |
| Branch-and-cut MIP (Princeton-Georgia Tech group) | 50-100K nodes | minutes-hours | Yes (within bound) |
| Lin-Kernighan / LKH | 1K-1M+ nodes | minutes-hours | No, within 0.1-1% of optimum |
| Metaheuristic (tabu, genetic, ant colony) | flexible | flexible | No, good practical quality |
TSP variants — pick by the field:
- Symmetric TSP: distance A→B = B→A. Inter-city roads, airline distance, PCB drilling. Simplest and most-studied variant.
- Asymmetric TSP (ATSP): direction-dependent distance. Urban one-way streets, direction-dependent travel time. A bit harder to model, branch-and-cut still applies.
- Euclidean TSP: nodes in a plane, distance is straight-line. PCB drilling, in-line factory operations.
- Metric TSP: triangle inequality holds (distance A→C ≤ A→B + B→C). The Christofides 3/2-approximation guarantee applies.
- TSP with profits / OP: nodes carry a value (profit); visiting every node is not mandatory. The “priority customer” variant for field service.
Objective function choice:
- Objective 1 — Minimum total distance / fuel: Fuel + driver-time focus.
- Objective 2 — Minimum total time: Driver time / machine cycle focus.
- Objective 3 — Minimum maximum stop time (minmax TSP): Fair allocation or safety focus.
Academic references
Listed in the sources block of this page’s frontmatter.
Sources
- Dantzig, G., Fulkerson, R. and Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Operations Research, 2(4), 393-410. Foundational cutting-plane breakthrough.
- Lin, S. and Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516. Basis of the modern heuristic family.
- Applegate, D., Bixby, R., Chvátal, V. and Cook, W. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press. Canonical book of the Princeton-Georgia Tech research-group exact branch-and-cut solver.
- Held, M. and Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196-210. The O(n²·2^n) DP formulation.
- Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130. LKH — within 0.1-1% of optimum up to million-node scale.
- YÖK Thesis Center — keyword: ‘gezgin satıcı’ or ‘TSP’ or ’tour optimisation’ — 30+ theses from TR academia. tez.yok.gov.tr
Glossary
- Travelling Salesman Problem
- The foundational combinatorial-optimisation problem of finding the minimum-cost Hamiltonian tour that visits every node in a graph exactly once and returns to the start.
- Branch-and-Cut
- The exact MIP solution framework that combines branch-and-bound with cutting-plane methods — at each node of the search tree, valid inequalities (cuts) tighten the LP relaxation before branching.
- MIP
- An optimization model where some decision variables are forced to be whole numbers (e.g. number of trucks, number of shifts).
- VRP
- The decision of which vehicles, leaving from one or more depots, visit which customers in which order.
Related problems
From One Node to Another — How Do I Compute the Shortest Path on a Weighted Graph?
For SMBs that need to compute the fastest or shortest route between two points: 10-50-vehicle field-service teams (plumbing, electrical, appliance repair), urban courier/parcel operations, or dispatch centres coordinating emergency response. Every day brings hundreds of 'how do I get from A to B fastest right now' questions; the answer shifts with traffic, road closures and vehicle type. A wrong route costs the technician one or two jobs missed for the day, the courier a late delivery, and the firm a customer. Manual or by-eye routing typically leaves 20-60 wasted minutes per vehicle per day on the table compared with a network-aware route calculation.
Multiple Plants, Multiple Customers — How Much Does Each Plant Ship to Each Customer to Minimise Total Freight?
For food, packaging or textile producers shipping weekly from 3-8 plants or regional warehouses to 20-100 customers. The weekly decision is: which plant ships how much to which customer, given fixed plant capacities, stated customer demands, and a different per-unit cost (distance + vehicle + contract terms) for each plant-customer pair. The goal is the lowest total freight bill across the network. A 'nearest plant' or 'we've always done it this way' habit typically leaves 10-20% extra fuel and vehicle cost on the table compared with a systematic allocation.