traveling salesman problem
A classic computationally hard optimization problem of finding the shortest route visiting many locations; exact solutions are intractable at scale, so logistics relies on approximations.
As defined in 171 | Christopher Mims on Our Interconnected Industrial Ecology
Other definitions
The classic optimization problem of finding the shortest route visiting a set of stops once each and returning; the number of possible routes grows factorially, making exact solutions infeasible for many stops.
The Deceptive Power of Maps (with Paulina Rowinska)A classic optimization problem of finding the shortest route visiting a set of cities; easy to state but computationally explosive because possible routes grow far faster than the number of cities.
Kevin Kelly on the Future of the Web and Everything Else 3/26/2007
Where it comes up · 8
- Tony Xu - A Human and Math Problem - [Founder’s Field Guide, EP. 28]3 claims
- Kevin Kelly on the Future of the Web and Everything Else 3/26/20072 claims
- AMA | August 20212 claims
- The Deceptive Power of Maps (with Paulina Rowinska)1 claim
- Michael Munger on Milk1 claim
- 151 | Jordan Ellenberg on the Mathematics of Political Boundaries1 claim
- 171 | Christopher Mims on Our Interconnected Industrial Ecology1 claim
- Don’t Believe AI Hype, This is Where it’s Actually Headed | Oxford’s Michael Wooldridge | AI History1 claim
Most important claims · 10 of 12Search all claims for “traveling salesman problem” →
- Logistics is saturated with high-stakes mathematics because a fraction-of-a-percent efficiency gain saves tens of millions of dollars; firms invest enormously (UPS spent $300 million ~20 years ago on its Orion routing software) to approximate solutions to intractable, NP-hard problems like the traveling salesman that could never be solved exactly before the heat death of the universe, with predictive analytics being one of the best mundane applications of machine learning.171 | Christopher Mims on Our Interconnected Industrial Ecology
- The number of possible routes for a delivery driver grows factorially with stops—five stops yield 120 possible routes, but 135 stops (a typical UPS day) produce more possible routes than there are stars in the universe—so even the most powerful computer cannot compute the optimal route each morning; companies instead use secret algorithms that produce a 'good enough' route quickly, perhaps 10% worse than optimal.The Deceptive Power of Maps (with Paulina Rowinska)
- DNA computing solves complex problems by exploiting massive parallelism: each possible solution is encoded as a DNA sequence, millions of variations are generated simultaneously, and the physical molecule that best fits the 'lock' (the puzzle) is extracted as the answer—useful for problems like the Traveling Salesman problem that don't scale on linear von Neumann machines.Kevin Kelly on the Future of the Web and Everything Else 3/26/2007
- DoorDash treats its business as a marriage between a math problem and a human problem, and it began by solving the human side because the required data about the physical world did not yet exist.Tony Xu - A Human and Math Problem - [Founder’s Field Guide, EP. 28]
- The Golden Age approach of 'divide and conquer'—splitting intelligence into separate faculties and building search algorithms for each—hit a fundamental ceiling: most real-world problems are NP-complete or harder, meaning no efficient algorithm exists, and exhaustive search becomes computationally impossible at realistic scales.Don’t Believe AI Hype, This is Where it’s Actually Headed | Oxford’s Michael Wooldridge | AI History
- DoorDash's problem was unsolved mathematically because consumer demand, merchant supply, and Dasher availability cannot be controlled or forecast like classic routing problems, so the team had to first collect structured information about physical-world human behavior before applying math.Tony Xu - A Human and Math Problem - [Founder’s Field Guide, EP. 28]
- Classic routing problems like the traveling salesman and multi-vehicle routing assume demand and supply can be forecast accurately, but in delivery, consumer hunger, driver acceptance, and merchant speed are all unknown, which made the problem genuinely unsolved.Tony Xu - A Human and Math Problem - [Founder’s Field Guide, EP. 28]
- The halting problem and the traveling salesman problem are not really related: the traveling salesman problem is merely hard (takes many steps), whereas the halting problem is literally unsolvable — there is no way to know just by inspecting a program whether it will halt, other than running it, which can only ever confirm halting within a finite time, never confirm non-halting.AMA | August 2021
- The halting problem and the traveling salesman problem are not really related: the traveling salesman problem is hard (takes many steps) but solvable, whereas the halting problem is literally unsolvable — there is no way to determine just by inspecting a program whether it will halt, since running it can only ever confirm halting within a finite time, never prove it never halts.AMA | August 2021
- While proving a problem like the traveling salesman is NP-hard, engineers in practice write algorithms that with very high probability find solutions nearly as good as optimal, so hard problems are routinely solved approximately even though provable optimal solutions are out of reach.151 | Jordan Ellenberg on the Mathematics of Political Boundaries