The traveling salesman problem (TSP) asks for the shortest round trip that visits every city in a list once, and classical exact software has solved a real instance with 85,900 cities. Machine learning methods published since 2016 produce near-optimal tours for about 100 cities, but peer-reviewed work finds that they do not yet scale to practical sizes on their own. The strongest recent results pair a neural model with an established heuristic rather than replacing it.
Key takeaways
- The Concorde solver found a provably optimal tour through 85,900 cities in 2005 and 2006, with no neural network involved.
- Neural solvers from 2016 to 2019 reached near-optimal tours on instances of up to 100 nodes.
- A 2020 study reported that end-to-end learned solvers perform well on very small graphs but fail to scale to practical sizes.
- A hybrid that feeds a neural model's output into the Lin-Kernighan-Helsgaun heuristic reports better results than the heuristic alone.
- Real delivery routing adds time windows and vehicle capacity, which makes it a related but harder family of problems.
Why the problem gets hard so quickly
A symmetric TSP with n cities has (n - 1)! / 2 distinct tours. The count outgrows any hardware improvement, so checking every route stops being an option almost immediately. The University of Waterloo's TSP site describes the problem as one for which no effective solution method is known in the general case, and it ties the problem to the P versus NP question.
| Cities | Distinct tours |
|---|---|
| 5 | 12 |
| 10 | 181,440 |
| 15 | 43,589,145,600 |
| 20 | 60,822,550,204,416,000 |
The figures come from the formula above and are plain arithmetic, not measurements. Practical solvers avoid brute force by pruning: they prove that whole families of tours cannot be shortest and discard them.
What classical solvers already achieve
Concorde, a program written in ANSI C and free for academic research, has produced optimal solutions for all 110 instances in the TSPLIB benchmark library. The largest is pla85900, a chip-layout problem from Bell Laboratories with 85,900 cities. Its optimal tour is 142,382,641 units long. The computation was carried out in 2005 and 2006 by a team that included David Applegate, Robert Bixby, Vasek Chvatal, William Cook, Daniel Espinoza, Marcos Goycoolea, and Keld Helsgaun, according to the Concorde project page for pla85900.
Exact answers are not always needed. Google's open-source OR-Tools routing library documents a 280-point circuit board example from TSPLIB that its default settings solve in under a second on a typical computer. The guide calls the result a good solution, not an optimal one, with a tour length of 2790. For a 13-city example it reports the optimal route.
On the theory side, Karlin, Klein, and Oveis Gharan showed in a paper presented at STOC 2021 that metric TSP can be approximated within a factor of 3/2 minus epsilon, where epsilon is greater than 10 to the power of negative 36. It improved on the long-standing 3/2 bound, and the margin is tiny.
Where learned solvers fit
Neural approaches treat tour building as a prediction task. Bello, Pham, Le, Norouzi, and Bengio posted "Neural Combinatorial Optimization with Reinforcement Learning" on November 29, 2016. A recurrent network reads city coordinates and outputs a visiting order, with the negative tour length as the training reward. The authors reported near-optimal results on two-dimensional Euclidean instances with up to 100 nodes.
Kool, van Hoof, and Welling followed with "Attention, Learn to Solve Routing Problems!", accepted at ICLR 2019. Their attention-based model came close to optimal on TSP instances of up to 100 nodes. With the same hyperparameters it also handled two vehicle routing variants, the orienteering problem, and a stochastic prize-collecting TSP.
The limit appeared soon after. Joshi, Cappart, Rousseau, and Laurent, in a paper accepted to CP 2021, reported that neural networks trained end to end perform well on very small graphs but fail to scale to practical sizes. They argued that extrapolating to larger instances needs a rethink of learning paradigms and evaluation protocols. The arXiv record of that study lists the revision history.
Hybrids and a checklist for reading claims
NeuroLKH, published at NeurIPS 2021 by Xin, Song, Cao, and Zhang, takes a different route. A neural network scores edges and adjusts node penalties, and those outputs steer the search of the Lin-Kernighan-Helsgaun heuristic. The authors state that a single trained model significantly outperforms the heuristic alone and generalizes to much larger instances. That is the authors' own claim from the abstract, and independent replication was not checked for this article.
When a new paper or product claims to beat classical routing, these questions help separate narrow wins from broad ones:
- How many cities were tested, and did the test sizes match the training sizes?
- Was the baseline an exact solver or a tuned heuristic such as LKH, or a weaker construction method?
- Does the reported gap to the optimal tour come from proven optima or from another heuristic's output?
- Are running times given for the whole pipeline, including training?
- Does the problem include real constraints such as time windows or vehicle capacity?
FAQ
Can AI find the optimal route for thousands of cities?
The documented optimal solution at that scale came from the classical Concorde solver, not from a neural network. Learned methods in the cited papers were evaluated mainly on instances of up to 100 nodes.
Is the traveling salesman problem the same as delivery route planning?
Not exactly. Delivery planning usually adds multiple vehicles, capacities, and delivery windows, which places it in the vehicle routing family. The Kool et al. paper tested its model on two vehicle routing variants.
Does a better approximation guarantee mean better routes in practice?
Not necessarily. The 2021 improvement over the 3/2 bound is a theoretical result with a very small margin, and a guarantee describes the worst case rather than typical performance.
Is Concorde free to use?
The project page says it is free for academic research use. Other uses require contacting William Cook for licensing options.
Related reading
- Algorithm families used on the salesman problem
- More approaches to the notorious salesman puzzle
- Strategies and future directions for the problem
- Timefold, a planning optimization solver
More in AI Blog.
Last verified: October 2026
Sources
- pla85900 solved instance page, University of Waterloo (Concorde project), 2026
- Concorde TSP Solver home page, University of Waterloo, 2026
- The Traveling Salesman Problem overview, University of Waterloo, 2026
- Traveling Salesperson Problem, OR-Tools routing guide, Google Developers, 2026
- Karlin AR, Klein N, Oveis Gharan S. A (Slightly) Improved Approximation Algorithm for Metric TSP, arXiv 2007.01409, STOC 2021
- Bello, Pham, Le, Norouzi, Bengio. Neural Combinatorial Optimization with Reinforcement Learning, arXiv 1611.09940, 2016
- Kool W, van Hoof H, Welling M. Attention, Learn to Solve Routing Problems!, ICLR 2019
- Joshi CK et al. Learning the TSP Requires Rethinking Generalization, CP 2021
- Xin L et al. NeuroLKH, NeurIPS 2021