The deceptively simple puzzle that keeps the world's most powerful computers working overtime

The deceptively simple puzzle that keeps the world's most powerful computers working overtime
Image: Intellect (generated)

In short: The travelling salesman problem asks for the shortest possible route visiting every city exactly once before returning home. While it sounds like a basic navigation task, it is an NP-hard challenge that has stumped mathematicians for nearly a century, serving as a critical benchmark for optimization and computational complexity.

Formulated in 1930, the travelling salesman problem (TSP) is a cornerstone of combinatorial optimization. At its core, it asks for the most efficient path through a set of points, where the distance between each pair is known. Despite its straightforward definition, the problem is NP-hard, meaning that as the number of cities increases, the time required to find an optimal solution can grow superpolynomially. This complexity arises because, while it is easy to ensure a path locally visits each city once, ensuring a single global tour that connects all vertices is computationally difficult.

The problem has deep roots in 19th-century mathematics, with early contributions from William Rowan Hamilton and Thomas Kirkman. By the 1950s, researchers at the RAND Corporation, including George Dantzig, Delbert Ray Fulkerson, and Selmer M. Johnson, pioneered integer linear programming methods to tackle it. They famously solved a 49-city instance by constructing a tour and proving no shorter route existed using cutting plane methods. Today, the Concorde program remains a standard tool for finding optimal solutions, having successfully computed a tour for 85,900 cities in 2006.

Beyond pure theory, the TSP is essential for modern logistics, microchip manufacturing, and DNA sequencing. Because exact solutions are often impossible for massive datasets, scientists rely on approximation algorithms. The Christofides–Serdyukov algorithm, developed in 1976, guarantees a solution no more than 1.5 times longer than the optimal path for metric TSP. For even larger instances involving millions of cities, modern heuristics can consistently find solutions within 2–3% of the theoretical optimum, proving that while the perfect answer may remain elusive, near-perfect efficiency is well within our reach.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-travelling-salesman-problem.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…