Traveling Salesman Problem Explained With an Example

Quick answer: The traveling salesman problem (TSP) asks for the shortest route that visits each city in a list exactly once and returns to the start. With n cities there are (n − 1)!/2 possible tours, so brute force fails quickly: 20 cities already give about 60 quadrillion tours. The problem is NP-hard, and no fast algorithm is known for all cases, yet clever methods solve real instances with tens of thousands of stops exactly, and good approximations are fast.

A delivery driver must visit 20 addresses and return to the depot. What is the shortest route? This sounds like a simple puzzle, but it is one of the most famous hard problems in mathematics and computer science: the traveling salesman problem.

The Problem

Given \(n\) cities and the distance between every pair, find the shortest round trip that visits each city exactly once. Each such route is called a tour.

A Four-City Example

Take four cities A, B, C and D with these distances (in km):

ABCD
A02910
B2064
C9603
D10430

Starting from A, there are only \(\frac{3!}{2} = 3\) different tours:

TourLength
A → B → C → D → A2 + 6 + 3 + 10 = 21
A → B → D → C → A2 + 4 + 3 + 9 = 18 (shortest)
A → C → B → D → A9 + 6 + 4 + 10 = 29

With four cities you can check every tour by hand. The trouble starts as the list grows.

Why Brute Force Fails

For the usual symmetric TSP (where A to B costs the same as B to A) with \(n \ge 3\) cities, fix the starting city. The remaining \(n – 1\) cities can be visited in \((n-1)!\) orders, and each tour is counted twice (forward and backward), so there are

\[ \frac{(n-1)!}{2} \text{ tours}. \]

CitiesPossible tours
512
10181,440
15about 43.6 billion
20about \(6.1 \times 10^{16}\)
30about \(4.4 \times 10^{30}\)

Checking every tour for 30 cities would take longer than the age of the universe, even at a trillion tours per second.

Is There a Fast Method?

The number of tours alone does not prove the problem is hard, because clever algorithms avoid checking tours one by one. The Held–Karp dynamic programming algorithm (1962) solves any instance in about \(n^2 2^n\) steps, far fewer than \((n-1)!/2\), but still exponential, and it remains the best known worst-case bound for exact solutions in general.

Finding the shortest tour is NP-hard, and the decision version (“is there a tour of length at most \(B\)?”) is NP-complete. An exact polynomial-time algorithm that solves every TSP instance would imply \(P = NP\), settling the famous P vs NP problem.

How Real Instances Get Solved Anyway

  • Exact methods: linear programming with “cutting planes” and branch-and-bound, used by the Concorde solver, prove optimality without checking every tour. A team led by William Cook found and proved an optimal tour for an 85,900-point circuit-board instance (pla85900) in 2005 to 2006, and in 2024 to 2025 proved an optimal 81,998-stop walking tour of bars across South Korea, using estimated walking times from a routing engine.
  • Approximations: for the symmetric metric TSP, where distances obey the triangle inequality (going directly is never longer than going via a third city), Christofides’ algorithm (1976) always finds a tour at most 1.5 times the optimum. In 2020, Anna Karlin, Nathan Klein and Shayan Oveis Gharan improved this worst-case guarantee, by a tiny amount, for the first time in over 40 years. Without the triangle inequality, no such guarantee is possible unless P = NP.
  • Heuristics: methods like 2-opt and Lin–Kernighan quickly find tours that are often within a few percent of the best in practice, though without a proven worst-case bound.

Where It Is Used

Delivery routing, drilling holes in circuit boards, scheduling telescope observations, DNA sequencing and manufacturing all involve TSP-like problems. Its cousin, crossing every edge once, is the easy problem Euler solved for the bridges of Königsberg.

Common Misconceptions

“Always go to the nearest city next.” That greedy rule is fast but can produce tours much longer than the best one.

“NP-hard means unsolvable.” No. It means no fast method is known for every case; many practical instances are solved exactly or very nearly.

Watch: The Traveling Salesman Problem in Video

If you learn better by watching, these videos are worth your time.

What is the Traveling Salesman Problem? (AlphaOpt). A clear introduction to the problem and why it is hard.
The Traveling Salesman Problem: When Good Enough Beats Perfect (Reducible). A tour of heuristics and approximation algorithms.

Check Your Understanding

Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.

Answer each question and press Submit to see your result right away.

1. How many tours are there for 5 cities?
Found a bug? Let us know!
2. How many tours are there for 10 cities?
Found a bug? Let us know!
3. What is the shortest tour in the four-city example?
Found a bug? Let us know!
4. What approximation guarantee does Christofides’ algorithm give?
Found a bug? Let us know!
5. An exact polynomial-time algorithm for every TSP instance would settle which problem?
Found a bug? Let us know!

Frequently Asked Questions

What is the traveling salesman problem?

Finding the shortest round trip that visits each of a set of cities exactly once and returns to the start.

Why is the traveling salesman problem hard?

The number of possible tours grows like a factorial, and even the best known exact algorithms take exponential time in the worst case. Finding the shortest tour is NP-hard.

Is the traveling salesman problem NP-complete?

The decision version, asking whether a tour of length at most B exists, is NP-complete. The optimization version, finding the shortest tour, is NP-hard.

Has the traveling salesman problem been solved?

Not in general, but specific instances with tens of thousands of cities have been solved exactly with advanced methods.

Where is the traveling salesman problem used?

In delivery routing, logistics, circuit board manufacturing, scheduling and genome sequencing.

Keep Exploring

Sources and Further Reading

Related to This Article

What people say about "Traveling Salesman Problem Explained With an Example - Effortless Math"?

No one replied yet.

Leave a Reply