Practise › Questions › The travelling salesman problem
The travelling salesman problem questions
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.
6 original questions · 26 marks · the the travelling salesman problem notes · Decision Mathematics 1
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
State the difference between the practical and classical travelling salesman problems, and how one is turned into the other.
Worked answer
The practical problem allows a node to be visited more than once; the classical problem visits each exactly once and needs a complete network obeying the triangle inequality. Replacing every pair's distance by the shortest path between them produces such a network, turning a practical problem into a classical one. B1 for the practical problem, B1 for the classical problem, B1 for the shortest-path conversion.Apply the nearest neighbour algorithm from A to the network with AB 20, AC 35, AD 42, AE 25, BC 30, BD 34, BE 28, CD 12, CE 40, DE 22.
Worked answer
From A the nearest is B at 20. From B the nearest unvisited vertex is E at 28, then from E it is D at 22, then C at 12. The return from C to A costs 35, and it must be taken whatever its length. Tour A B E D C A of length 117. This is an upper bound for the optimal tour, since it is a genuine tour. M1 for the nearest neighbour method, A1 for the tour, A1 for 117, B1 for the upper bound.Find a lower bound for the same network by deleting A.
Worked answer
Remove A and everything joined to it, leaving B, C, D and E. Their minimum spanning tree takes CD 12, then DE 22, then BE 28, total 62. The two shortest edges from A are AB 20 and AE 25, total 45. Lower bound = 62 + 45 = 107.
M1 for deleting A, A1 for the tree edges, A1 for 62, B1 for the two shortest edges at A, A1 for 107.
No tour can be shorter. Deleting A from any tour leaves a path through the others, which is a spanning tree of that reduced network and so weighs at least 62, plus two edges at A which weigh at least 45. Name the tree edges as well as the total, since one mark is for the tree itself.The tour A B C D E A has length 109. Use it with your answers above to bracket the optimal tour, and comment on the nearest neighbour result.
Worked answer
20 + 30 + 12 + 22 + 25 = 109, which is a better upper bound than the 117 nearest neighbour gave. So the optimal tour T satisfies 107 ≤ T ≤ 109. Nearest neighbour was eight worse than this tour: it is quick and always gives a valid tour, but it is not reliable. M1 for summing the tour, A1 for 109, B1 for the bracket, B1 for the comment.Explain why deleting a different node can give a better lower bound, and what you should do about it.
Worked answer
Each deletion gives a valid lower bound, but the bounds differ because the trees and the two shortest edges differ. Since every one is a genuine lower bound, the largest of them is the strongest statement available, so try several deletions and quote the largest result. B1 for every deletion giving a valid bound, B1 for why the bounds differ, B1 for quoting the largest.For the same network, find the lower bound obtained by deleting C instead of A. Hence state the length of the optimal tour, justifying your answer.
Worked answer
Remove C, leaving A, B, D and E with edges AB 20, AD 42, AE 25, BD 34, BE 28 and DE 22. The minimum spanning tree takes AB 20, then DE 22, then AE 25, total 67. The two shortest edges from C are CD 12 and BC 30, total 42. Lower bound = 67 + 42 = 109.
The tour A B C D E A has length 109, so 109 ≤ T ≤ 109 and the optimal tour is 109, achieved by A B C D E A.
M1 for deleting C, A1 for the tree edges, A1 for 67, B1 for the two shortest edges at C, A1 for 109, M1 for comparing with the known tour, A1 for the optimal tour.
When a lower bound and a known tour agree, the tour is proved optimal and no further search is needed. Deleting A gave only 107, so the choice of vertex matters. Try each in turn and quote the largest bound, since every one of them is valid and the largest is the most informative.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise the travelling salesman problem one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.