The Traveling Salesman Problem: Why the Shortest Route Is Hard
The traveling salesman problem asks for the shortest route that visits every city once and returns to the start, simple to state but very hard to solve.
The traveling salesman problem asks for the shortest possible route that visits each city on a list exactly once and returns to the starting city. The question is easy to state and easy to check: given a route, you can add up its length in a moment. Finding the shortest route among all the possible ones is much harder, and no known method does it quickly for large lists.
How many routes are there?
For a small list the answer can be found by checking every route. With n cities, there are (n − 1)! orderings of the visits, and if a round trip and its reverse count as one, the number of distinct tours is half that. For 10 cities that is 181,440 tours, which a computer checks in well under a second. For 20 cities it is about 6.1 × 10¹⁶ tours.
If a computer checked one tour per microsecond, checking all 20-city tours would take about 1,900 years. Adding one more city multiplies the work by the new number of cities. This explosive growth is the core difficulty, and it is why the problem is a standard example in computational complexity.
Why is the problem so hard?
The traveling salesman problem belongs to a class called NP-hard. Its decision version, which asks whether a route shorter than some given length exists, is NP-complete. Richard Karp showed in 1972 that many important problems can be reduced to one another, and this problem is among that group. No efficient exact method has been found for any of them, and whether one exists is the open question of whether P equals NP.
The problem is also not the same as finding a short path between two places. Dijkstra's algorithm finds the shortest path between two points efficiently. The salesman must visit every city, and the order in which he visits them is the whole problem.
How do people solve it in practice?
Solvers use a range of methods, from exact to approximate. Each one trades time against certainty.
| Method | How it works | Result |
|---|---|---|
| Exact search | Searches the tours and cuts off branches that cannot be shortest | Best route, but time grows very fast |
| Nearest neighbour | Always moves to the closest unvisited city | Very fast, often about 25 percent longer than the best |
| 2-opt and Lin–Kernighan | Swaps pairs of links until no swap shortens the tour | Usually within a few percent of the best |
| Christofides algorithm | Builds a tour from a spanning tree and a matching | Guaranteed within 1.5 times the best, for distances that obey the triangle rule |
Exact methods have improved a great deal. In 1954 George Dantzig, Ray Fulkerson and Selmer Johnson solved an instance with 49 cities, one in each of the 48 contiguous US states and Washington, D.C. Later work has solved instances with tens of thousands of cities, but these exact solutions use large amounts of computing time and clever pruning, and they do not change the general picture.
Where does the problem appear?
The structure appears in many practical tasks. Delivery companies plan routes for vehicles that must visit many addresses. Factories plan the order in which a drilling machine visits holes in a circuit board, and warehouses plan the path that a picker takes through shelves. DNA sequencing and the layout of microchips also involve similar orderings of many items.
In these settings, a route that is close to the best is usually good enough. A solver that finds a tour a few percent above the optimum can save large amounts of time and fuel, even though it cannot prove that the tour is the shortest possible.
What does the problem teach?
The traveling salesman problem shows the difference between finding an answer and checking one. A proposed route can be verified quickly, but the search for the best route grows faster than any simple formula. Many algorithms that work well on small inputs become impractical as the list grows. The big O notation used to describe such growth is one of the main tools for explaining why.
The problem is also a good example of dynamic programming, a technique that saves work by reusing answers to smaller subproblems. Dynamic programming can solve the traveling salesman problem exactly, but only for small lists, because the number of subproblems still grows much faster than the list itself.
Tags
algorithms complexity theory graph theory optimization
Related articles
- P vs NP
- Bellman–Ford Algorithm
- Breadth-First Search
- Dynamic Programming
- Dijkstra's Shortest Path Algorithm
- Heaps and Priority Queues: How a Binary Heap Works