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.
- Use a minimum spanning tree, doubled and then short-cut, to find an upper bound.
- Find a lower bound by deleting a node, and use both bounds to bracket the answer.
COMMON MISCONCEPTION
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 requires each node to be visited exactly once, and it needs a complete network satisfying the triangle inequality, so that no direct route is longer than a route through a third node.
Converting between them is routine. Replace each pair's distance by the shortest path between them. The result is a complete network obeying the triangle inequality, so the practical problem has become a classical one, and any tour found there translates back into a route for the original network.
Upper bounds
Any actual tour is an upper bound. The nearest neighbour algorithm supplies one quickly: from the current node go to the nearest unvisited one, repeat, and return to the start at the end. Run it from several starting nodes and take the smallest result, which costs very little and often improves the bound sharply.
There is a second method the specification names. Find a minimum spanning tree for the whole network and double its weight. That corresponds to walking out and back along every branch, so it certainly covers every node and gives a bound, though a weak one. Then take short cuts, skipping past nodes already visited, and each short cut brings the bound down until what is left is a genuine tour.
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.
Start at B instead and nearest neighbour gives B A E D C B, which comes to 109 and happens to be optimal. Same algorithm, better bound, no extra cleverness.
Lower bounds
A lower bound comes from a different idea altogether. 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 structure of that shape, so no tour can be shorter than the total.
Repeat with different deleted nodes and take the largest answer, since the largest lower bound is the strongest one. Quote the final result as an inequality bracketing the optimal tour, and say when the two bounds are close enough to settle the question.
GUIDED PRACTICE
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.
ASSESSMENT FOCUS
- 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 do not forget the return edge.
- For a lower bound, name the deleted node and show both the tree and the two edges.
- For an upper bound from a spanning tree, double the weight first and then show each short cut.
- 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
48 + 9 + 11 = 68. No tour can be shorter than 68, though the best tour may well be longer.
Any tour at all is an upper bound, and nearest neighbour finds one quickly, rarely the best one.
Doubling a minimum spanning tree also gives an upper bound, which short cuts then improve.
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.
Or read them with their worked answers on the the travelling salesman problem questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Distinguish the practical and classical problems and convert between them.
- Use the nearest neighbour algorithm to find an upper bound.
- Use a minimum spanning tree, doubled and then short-cut, to find an upper bound.
- Find a lower bound by deleting a node, and use both bounds to bracket the answer.
Open the full revision checklist to see every objective in the course in one place.