Maths › Decision Mathematics 1 › The travelling salesman problem
The travelling salesman problem
Visit every node once and come back. Nobody knows a quick way to find the best tour, so the paper settles for trapping it between a bound above and a bound below.
Builds on Minimum spanning trees: Prim and Kruskal and Route inspection.
IN THIS TOPIC
- Distinguish the practical and classical problems and convert between them.
- Use the nearest neighbour algorithm to find an upper bound.
- Find a lower bound by deleting a node and use both to bracket the answer.
WHAT YOU PROBABLY THINK
The nearest neighbour algorithm gives the shortest tour, since it never wastes a move.
Two versions of the problem
The practical problem allows nodes to be visited more than once, which is what a real delivery round permits. The classical problem insists each node is visited exactly once, and needs a complete network satisfying the triangle inequality: no direct route longer than a route through a third node.
Converting between them is routine. Replace each pair's distance by the shortest path between them, which produces a complete network obeying the triangle inequality, and the practical problem becomes a classical one. Any tour found there translates back into a route for the original network.
WORKED EXAMPLE
Nearest neighbour from A
Apply the nearest neighbour algorithm from A to the five-node network with AB 20, AC 35, AD 42, AE 25, BC 30, BD 34, BE 28, CD 12, CE 40, DE 22.
From A the nearest is B (20). From B, the unvisited nearest is E (28), then from E it is D (22), then C (12).
Returning from C to A costs 35.
Tour A B E D C A, length 20 + 28 + 22 + 12 + 35 = 117. The best possible tour is 109, so the algorithm has missed it: the opening claim is false.
Bracketing the answer
Any tour at all is an upper bound, and the nearest neighbour algorithm supplies one quickly. Running it from several starting nodes and taking the smallest gives a better bound for very little extra work.
A lower bound comes from a different idea. Delete one node together with all its edges, find a minimum spanning tree on what is left, then add back the two shortest edges from the deleted node. Every tour contains a spanning structure of that kind, so no tour can be shorter. Repeating with different deleted nodes and taking the largest gives the best bound available.
YOUR TURN
A lower bound
For the same network, find a lower bound by deleting A.
Show the working
Removing A leaves B, C, D, E. Its minimum spanning tree takes CD 12, DE 22 and BE 28, total 62.
The two shortest edges from A are AB 20 and AE 25, total 45.
Lower bound = 62 + 45 = 107.
With the upper bound of 117, the optimal tour T satisfies 107 ≤ T ≤ 117. It is in fact 109, so neither bound is tight.
THE EXAM BIT
- Say which version of the problem you are working with and convert if necessary.
- Give the nearest neighbour tour as a sequence of nodes, and add the return edge.
- For a lower bound, name the deleted node and show both the tree and the two edges.
- Quote the final answer as an inequality bracketing the optimal tour.
CHECK YOURSELF
Deleting node P leaves a minimum spanning tree of weight 48, and the two shortest edges from P are 9 and 11. State the lower bound.
Show a hint
Add the three pieces.
Show the answer
4
8
+
9
+
1
1
=
6
8
.
N
o
t
o
u
r
c
a
n
b
e
s
h
o
r
t
e
r
t
h
a
n
6
8
,
t
h
o
u
g
h
t
h
e
b
e
s
t
t
o
u
r
m
a
y
w
e
l
l
b
e
l
o
n
g
e
r
.
The nearest neighbour algorithm gives a valid tour and so an upper bound, but rarely the best one.
A lower bound comes from deleting a node, finding a minimum spanning tree on the rest, and adding back the two shortest edges from it.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Distinguish the practical and classical problems and convert between them.
- Use the nearest neighbour algorithm to find an upper bound.
- Find a lower bound by deleting a node and use both to bracket the answer.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.