The Travelling Salesman Problem

A salesperson has to visit every town on a list once and return home, travelling as short a distance as possible. This is the travelling salesman problem (TSP): find the Hamiltonian cycle of least weight. It sounds simple, but no one knows a fast method that always finds the best answer for large graphs. Instead, you’ll learn to trap the answer between two numbers: an upper bound and a lower bound.

Key ideas

Why the TSP is hard

In a complete graph with $n$ vertices, the number of different Hamiltonian cycles (ignoring the starting point and direction) is

$$\frac{(n - 1)!}{2}$$

That’s $12$ cycles for $5$ towns, but nearly $240$ million for $13$ towns and about $3 \times 10^{62}$ for $50$. Checking them all quickly becomes impossible, even for a computer. That’s why we use algorithms that give good bounds.

Classical and practical problems

• In the classical TSP, the graph is complete and you visit each vertex exactly once.
• In the practical TSP, the graph may not be complete, and you’re allowed to pass through a vertex more than once (a delivery van can drive through a town twice).

To turn a practical problem into a classical one, make a table of least distances: for every pair of vertices, write the length of the shortest route between them, even if it passes through other vertices. Then work with this complete table. At the end, translate any “edge” of the table back into the real route it stands for.

Upper bound: the nearest-neighbour algorithm

1. Choose a starting vertex.
2. From the current vertex, go to the nearest vertex not yet visited.
3. Repeat until every vertex has been visited, then return to the start.

This gives a real Hamiltonian cycle, so its length is an upper bound: the best cycle can’t be longer. Different starting vertices can give different cycles. The best upper bound is the smallest one you find.

Lower bound: the deleted-vertex algorithm

1. Delete one vertex and all the edges joined to it.
2. Find the weight of a minimum spanning tree of the vertices that are left.
3. Add the weights of the two shortest edges from the deleted vertex.

The result is a lower bound: the best cycle can’t be shorter. Why? Take any Hamiltonian cycle and remove the deleted vertex: it loses two edges at that vertex (each at least as long as the two shortest), and what’s left is a path through all the other vertices, which is a spanning tree, so it weighs at least as much as the MST.

Deleting different vertices can give different values. The best lower bound is the largest one.

Interpreting the bounds

$$\text{best lower bound} \le \text{length of the optimal cycle} \le \text{best upper bound}$$

If the lower bound is itself the length of a Hamiltonian cycle (or equals an upper bound you’ve found), that cycle is optimal. Usually the deleted-vertex “network” isn’t a cycle, though, so the bound can’t be reached.

The deleted-vertex lower bound from Example 3: MST of the other vertices (blue) plus the two shortest edges from A (orange).

Worked examples

The road network for Examples 1 and 2 (distances in km).

Example 1: A table of least distances

A courier must visit the five depots P, Q, R, S, T in the figure (distances in km) and return to the start. Complete a table of least distances.

Solution. For each pair, find the shortest route, which may go through other vertices:

• P to S: P–Q–S $= 14$ or P–R–S $= 14$.
• P to T: there’s no road; P–R–T $= 16$ (P–Q–R–T is $17$).
• Q to S: the road QS $= 8$ beats Q–R–S $= 9$.
• Q to T: Q–R–T $= 11$ (or Q–S–T $= 11$).
• R to T: the road RT $= 7$ beats R–S–T $= 8$.
• All other pairs: the direct road is shortest.

	P	Q	R	S	T
P	–	6	9	14	16
Q	6	–	4	8	11
R	9	4	–	5	7
S	14	8	5	–	3
T	16	11	7	3	–

Example 2: Nearest-neighbour upper bound

Use the nearest-neighbour algorithm, starting at P, on the table from Example 1 to find an upper bound for the courier’s route. Write down the actual route on the roads.

Solution.

From	Unvisited options	Go to
P	Q 6, R 9, S 14, T 16	Q (6)
Q	R 4, S 8, T 11	R (4)
R	S 5, T 7	S (5)
S	T 3	T (3)
T	back to P	P (16)

Upper bound: $6 + 4 + 5 + 3 + 16 = 34$ km.

The step T to P ($16$) stands for the route T–R–P, so the actual route is P–Q–R–S–T–R–P. It passes through R twice, which is allowed in the practical problem.

(This isn’t the best possible route: P–Q–S–T–R–P is $6 + 8 + 3 + 7 + 9 = 33$ km. The nearest-neighbour algorithm gives a good cycle, not always the best one.)

Example 3: Upper and lower bounds for a classical problem

The table gives the travel times, in minutes, between five sites.

	A	B	C	D	E
A	–	12	10	15	8
B	12	–	3	7	9
C	10	3	–	6	11
D	15	7	6	–	14
E	8	9	11	14	–

• (a) Use the nearest-neighbour algorithm starting at A to find an upper bound.
• (b) Use the deleted-vertex algorithm, deleting A, to find a lower bound.
• (c) Write down an inequality for the length $L$ of the optimal cycle.

Solution. (a) From A the nearest is E ($8$). From E: B $9$, C $11$, D $14$, so B ($9$). From B: C $3$. From C: D $6$. Back to A: $15$.

$$\text{A–E–B–C–D–A:} \quad 8 + 9 + 3 + 6 + 15 = 41$$

The upper bound is $41$ minutes.

(b) Delete A. For B, C, D, E, Kruskal’s algorithm takes BC $3$, CD $6$, rejects BD $7$ (cycle B–C–D–B), and takes BE $9$. MST weight: $3 + 6 + 9 = 18$.

The two shortest edges from A are AE $8$ and AC $10$. Lower bound: $18 + 8 + 10 = 36$ minutes.

(c) $36 \le L \le 41$.

Example 4: Improving the bounds

For the table in Example 3, the lower bounds from deleting each vertex are A: $36$, B: $34$, C: $33$, D: $33$, E: $36$.

• (a) State the best lower bound.
• (b) A planner suggests the cycle A–C–D–B–E–A. Find its length and improve the inequality for $L$.

Solution. (a) The best lower bound is the largest: $36$ minutes.

(b) A–C–D–B–E–A has length $10 + 6 + 7 + 9 + 8 = 40$ minutes. Any Hamiltonian cycle gives an upper bound, and $40 \lt 41$, so

$$36 \le L \le 40$$

(In fact, checking all $12$ cycles on a computer shows $40$ is the optimum, but the bounds alone can’t prove that here.)

Common mistakes

Using a direct distance when a shorter route exists. In a practical problem, fill the table with least distances. In Example 1, the least distance from P to T is $16$ through R, even though there’s no road PT.

Choosing the wrong “best” bound. The best upper bound is the smallest upper bound; the best lower bound is the largest lower bound. Both squeeze the answer from either side.

Forgetting to return to the start. The nearest-neighbour cycle ends with the edge back to the starting vertex. Leaving it out gives a number that isn’t a bound at all.

Including the deleted vertex in the MST. Find the MST of the remaining vertices only, then add the two shortest edges from the deleted vertex, not one.

Thinking the lower bound is a route. The deleted-vertex network usually isn’t a cycle, so you can’t travel it. It just tells you no cycle can be shorter.

Not translating back to the real network. In a practical problem, an entry like T to P ($16$) stands for T–R–P. Give the real route when asked.

Practice

1. (Warm-up) How many different Hamiltonian cycles (ignoring starting point and direction) are there in $K_5$? In $K_6$?

Solution

$$K_5: \ \frac{4!}{2} = 12, \qquad K_6: \ \frac{5!}{2} = 60$$

2. (Warm-up) For a TSP, the nearest-neighbour algorithm from different starting vertices gives $52$, $49$ and $55$, and the deleted-vertex algorithm gives $41$, $44$ and $39$. Write down the best inequality for the length $L$ of the optimal cycle.

Solution

Best upper bound: the smallest, $49$. Best lower bound: the largest, $44$. So $44 \le L \le 49$.

3. (Warm-up) Explain why the length of any Hamiltonian cycle you find is an upper bound for the travelling salesman problem.

Solution

The optimal cycle is the shortest of all the Hamiltonian cycles. The cycle you found is one of them, so the optimal one is no longer than it.

4. (Core) A graph has edges AB $5$, BC $4$, CD $6$, AD $13$ and BD $7$.

• (a) Complete a table of least distances.
• (b) Use the nearest-neighbour algorithm, starting at A, to find an upper bound, and write down the actual route.

Solution

(a) A to C: A–B–C $= 9$. A to D: A–B–D $= 12$, shorter than the road AD $= 13$. B to D: the road BD $= 7$ beats B–C–D $= 10$.

	A	B	C	D
A	–	5	9	12
B	5	–	4	7
C	9	4	–	6
D	12	7	6	–

(b) A to B ($5$), B to C ($4$), C to D ($6$), D back to A ($12$). Upper bound: $5 + 4 + 6 + 12 = 27$.

D to A ($12$) is really D–B–A, so the route is A–B–C–D–B–A.

5. (Core) The table gives the distances, in km, between five towns.

	K	L	M	N	O
K	–	20	35	25	30
L	20	–	18	28	24
M	35	18	–	22	16
N	25	28	22	–	19
O	30	24	16	19	–

Use the nearest-neighbour algorithm, starting at K, to find an upper bound.

Solution

• K: L $20$, N $25$, O $30$, M $35$. Go to L.
• L: M $18$, O $24$, N $28$. Go to M.
• M: O $16$, N $22$. Go to O.
• O: N $19$. Go to N.
• N: back to K, $25$.

K–L–M–O–N–K: $20 + 18 + 16 + 19 + 25 = 98$ km.

6. (Core) For the table in Question 5, use the deleted-vertex algorithm, deleting K, to find a lower bound. What can you conclude?

Solution

Delete K. For L, M, N, O, Kruskal’s takes MO $16$, LM $18$, NO $19$ (then all four are connected). MST weight: $16 + 18 + 19 = 53$.

Two shortest edges from K: KL $20$ and KN $25$. Lower bound: $53 + 20 + 25 = 98$ km.

The lower bound equals the upper bound from Question 5, so $98 \le L \le 98$: the cycle K–L–M–O–N–K, of length $98$ km, is optimal.

7. (Core) Use the table of least distances from Example 1.

• (a) Use the nearest-neighbour algorithm starting at S to find an upper bound, and give the actual route.
• (b) Use the deleted-vertex algorithm, deleting T, to find a lower bound.

Solution

(a) S to T ($3$); T: R $7$, Q $11$, P $16$, so R ($7$); R: Q $4$, P $9$, so Q ($4$); Q to P ($6$); P back to S ($14$).

Upper bound: $3 + 7 + 4 + 6 + 14 = 34$ km. P to S ($14$) is really P–Q–S (or P–R–S), so one actual route is S–T–R–Q–P–Q–S.

(b) Delete T. For P, Q, R, S: Kruskal’s takes QR $4$, RS $5$, PQ $6$. MST weight $15$. Two shortest edges from T: TS $3$ and TR $7$. Lower bound: $15 + 3 + 7 = 25$ km.

8. (Challenge) For the courier problem in Examples 1 and 2:

• (a) Find the lower bound from deleting each of P, Q, R and S, and state the best lower bound.
• (b) Using the cycle P–Q–S–T–R–P, write the best inequality you can for the length $L$ of the optimal route.

Solution

(a) Using the table of least distances:

• Delete P: MST of Q, R, S, T is ST $3$, QR $4$, RS $5$ $= 12$; two shortest from P: $6 + 9$. Bound $27$.
• Delete Q: MST of P, R, S, T is ST $3$, RS $5$, PR $9$ $= 17$; two shortest from Q: $4 + 6$. Bound $27$.
• Delete R: MST of P, Q, S, T is ST $3$, PQ $6$, QS $8$ $= 17$; two shortest from R: $4 + 5$. Bound $26$.
• Delete S: MST of P, Q, R, T is QR $4$, PQ $6$, RT $7$ $= 17$; two shortest from S: $3 + 5$. Bound $25$.

With $25$ from deleting T (Question 7), the best lower bound is the largest: $27$ km.

(b) P–Q–S–T–R–P has length $6 + 8 + 3 + 7 + 9 = 33$ km, better than the nearest-neighbour bound of $34$. So $27 \le L \le 33$.

9. (Challenge) Explain carefully why the deleted-vertex algorithm always gives a lower bound for the classical travelling salesman problem.

Solution

Take any Hamiltonian cycle and the deleted vertex X. In the cycle, X is joined to exactly two other vertices, by two edges. Their total weight is at least the total of the two shortest edges from X.

Removing X and those two edges from the cycle leaves a path through all the other vertices. A path that includes every remaining vertex is a spanning tree of them, so its weight is at least the weight of their minimum spanning tree.

Adding these up: every Hamiltonian cycle weighs at least (MST of the remaining vertices) $+$ (two shortest edges from X). In particular, the optimal cycle does, so this total is a lower bound.