Travelling salesman problem

The travelling salesman problem, or TSP, is a famous puzzle in combinatorial optimization.

It asks a simple question about efficiency. Given a list of cities and the distances between every pair, what is the shortest route? This route must visit every city exactly once. Finally, the traveler must return to the original starting city. This creates a closed loop known as a Hamiltonian cycle.

Solving this helps save time, fuel, and money in many industries.

To solve this, mathematicians use a model called a weighted graph.

In this model, cities are called vertices. The paths between them are called edges. Each edge has a weight, which represents a cost like distance or time. There are two main types of TSP. In a symmetric TSP, the distance is the same in both directions. This halves the number of possible solutions. In an asymmetric TSP, the distances change based on direction. This happens because of one-way streets, traffic, or different airfares.

Finding the perfect answer is computationally difficult. In 1972, Richard M. Karp proved the Hamiltonian cycle problem is NP-complete. This means the TSP is NP-hard. As you add more cities, the time needed to find the best route grows superpolynomially. This makes it much harder than simple math problems. Because of this, researchers often use heuristics. These are clever strategies that find a very good answer quickly, even if it is not the absolute shortest.

History shows a long journey of discovery for this problem. While a 1832 handbook mentioned tours through Germany, formal math came later. In the 19th century, William Rowan Hamilton studied similar ideas through his icosian game.

In the 1930s, Karl Menger helped define the problem. Later, Merrill M. Flood studied it to solve school bus routing. The name "travelling salesman problem" first appeared in a 1949 RAND Corporation report by Julia Robinson. The problem became very popular in scientific circles during the 1950s and 1960s.

Major breakthroughs happened at the RAND Corporation. Researchers George Dantzig, Delbert Ray Fulkerson, and Selmer M. Johnson developed the cutting plane method. They expressed the problem as an integer linear program. Using these new methods, they solved an instance with 49 cities perfectly. They used only 26 cuts to find the optimal tour. They also used branch-and-bound algorithms for the first time.

In 1976, Christofides and Serdyukov independently created a new algorithm. Their method ensures the solution is at most 1.5 times the optimal length.

Modern technology allows us to tackle massive versions of this puzzle. In the 1990s, the Concorde program was developed for high-level solutions. In 2006, researchers solved a version with 85,900 cities. This specific problem involved a microchip layout. Today, we can find solutions for millions of cities within a 2% to 3% margin of error. One famous "world tour" problem was solved within 0.05% of the best possible answer. This shows how much computing power has grown.

This math is essential for many modern systems. In warehouses, it helps workers pick orders from shelves efficiently. In manufacturing, it guides robots that drill holes in microchips. It even helps scientists sequence DNA fragments. Astronomers use it to move telescopes between stars quickly. Even Google uses versions of this to route data between processing nodes. What began as a simple travel puzzle now powers much of our high-tech world.