← Back to Teeline

The Traveling Salesman Problem

Given a list of cities and the distances between them, find the shortest possible route that visits every city exactly once and returns to the start. That's the whole problem — easy to state to a child, and still, after decades of research, one of the most studied problems in computer science.

Why it's hard

The number of possible routes grows factorially with the number of cities: 10 cities have 181,440 distinct tours; 20 cities have over 60 quadrillion. Checking every one isn't an option, so exact algorithms (like the Bellman-Held-Karp and Branch and Bound solvers here) only stay practical for a few dozen cities. TSP is NP-hard: no known algorithm solves every instance quickly, and most researchers believe none exists. Beyond that scale, the field turns to heuristics and metaheuristics — local search, simulated annealing, genetic algorithms, and more — that trade the guarantee of optimality for a solution that's good enough, fast enough. Teeline implements 17 of them; see the algorithm docs for how each one works.

Where it shows up

Despite the toy-sounding name, the same structure appears anywhere something has to visit a set of points in the best order: delivery and courier route planning, drilling holes in a circuit board, positioning a telescope or a robotic arm, picking items in a warehouse, even sequencing DNA fragments. Any time "visit all of these, minimize the cost of moving between them" comes up, it's a TSP variant underneath.

Further reading

• Travelling salesman problem (Wikipedia) — formulations, algorithms, and complexity, with a full reference list.
• The Traveling Salesman Problem (University of Waterloo) — history, applications, and record-setting tours, maintained by researcher William Cook.
• Concorde — the reference exact TSP solver, which has proven optimality on instances with tens of thousands of cities.
• TSPLIB — the benchmark instance library Teeline reads (.tsp files), with problems sourced from real applications and research.

Ready to see it solved? Load a dataset and try a few algorithms against each other.