Questions on the travelling salesman problem

Question 1

State the difference between the practical and classical travelling salesman problems, and how one is turned into the other.

Accepted 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.

Question 2

State the triangle inequality, and state what it guarantees about a table built by replacing every distance by the shortest path between the two vertices.

Accepted Answer

For any three vertices, the direct distance from one to another is no greater than the distance by way of the third: d(u, w) ≤ d(u, v) + d(v, w). B1.
A table of shortest paths always satisfies it, because a route from u to w by way of v is one of the routes the shortest u to w path was chosen from, and so cannot be shorter than it. B1.

Question 3

A practical travelling salesman problem is set on a network with vertices P, Q, R, S whose only edges are PQ 5, QR 4, RS 6 and PS 20. Write down the table of shortest distances between every pair, and state why the completed table gives a classical problem.

Accepted Answer

Work out the shortest path for each of the six pairs. PQ = 5, QR = 4 and RS = 6 along their edges. PR = 5 + 4 = 9 by P, Q, R. QS = 4 + 6 = 10 by Q, R, S. PS = 5 + 4 + 6 = 15 by P, Q, R, S, which beats the direct edge of 20. M1 for the shortest paths, A1 for all six distances.
The table is now complete, so every pair of vertices has a distance and a tour may visit each vertex exactly once; and being built from shortest paths it obeys the triangle inequality, so no detour can shorten anything. Those are the two conditions the classical problem asks for. B1.
A tour of the classical problem is read back as a route of the practical one by expanding each leg into its shortest path, and a leg like P to S then passes through Q and R a second time. That is what the practical problem allows and the classical one does not.

Question 4

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.

Accepted 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.

Question 5

Find a lower bound for the same network by deleting A.

Accepted 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 the tree is part of the answer.

Question 6

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.

Accepted 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.

Question 7

Explain why deleting a different node can give a better lower bound, and what you should do about it.

Accepted 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.

Question 8

A complete network has vertices P, Q, R, S, T with PQ 9, PR 15, PS 12, PT 20, QR 7, QS 14, QT 18, RS 10, RT 16 and ST 11. Apply the nearest neighbour algorithm starting at P, and then starting at R. State the best upper bound your work gives for the optimal tour.

Accepted Answer

From P the nearest is Q at 9; from Q the nearest unvisited vertex is R at 7; from R it is S at 10; from S it is T at 11; and the return T to P costs 20, which must be taken whatever its length. Tour P Q R S T P, length 9 + 7 + 10 + 11 + 20 = 57. M1 for the method from P, A1 for 57.
From R the nearest is Q at 7; from Q it is P at 9; from P it is S at 12; from S it is T at 11; and the return T to R costs 16. Tour R Q P S T R, length 7 + 9 + 12 + 11 + 16 = 55. M1 for the method from R, A1 for 55.
Both are genuine tours and so both are upper bounds; the smaller is the stronger statement, so the best upper bound here is 55. B1.
Different starting vertices give different tours because the algorithm looks only one step ahead and the closing edge is forced whatever its length. The run from P was trapped into paying 20 to get home; the run from R pays 16 and comes out shorter.

Question 9

A complete network has vertices P, Q, R, S, T with PQ 9, PR 15, PS 12, PT 20, QR 7, QS 14, QT 18, RS 10, RT 16 and ST 11. Find the lower bound for the optimal tour obtained by deleting T.

Accepted Answer

Remove T and every edge meeting it, leaving P, Q, R, S with PQ 9, PR 15, PS 12, QR 7 and RS 10. M1 for the deletion.
Their minimum spanning tree takes QR 7, then PQ 9, then RS 10, three arcs for four vertices, weight 26. A1.
The two shortest edges at T are ST 11 and RT 16, totalling 27. B1.
Lower bound = 26 + 27 = 53. A1.
No tour can be shorter than this. Deleting T from any tour leaves a path through the other four vertices, which is a spanning tree of the reduced network and so weighs at least 26, together with the two edges at T, which weigh at least 27.

Question 10

A network has edges AB 20, AC 35, AD 42, AE 25, BC 30, BD 34, BE 28, CD 12, CE 40, DE 22, and the tour A B C D E A has length 109. Find the lower bound obtained by deleting C. Hence state the length of the optimal tour, justifying your answer.

Accepted 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 gives only 107, so the choice of vertex matters.

Question 11

A complete network has vertices A to F with AB 31, AC 14, AD 26, AE 22, AF 31, BC 20, BD 18, BE 38, BF 41, CD 12, CE 19, CF 25, DE 22, DF 24, EF 9. Apply the nearest neighbour algorithm starting at A, and then starting at D. Find the best upper bound your work gives for the optimal tour.

Accepted Answer

From A the nearest is C at 14, then D at 12, then B at 18, then E at 38, then F at 9, and the return F to A costs 31. Tour A C D B E F A, length 14 + 12 + 18 + 38 + 9 + 31 = 122.
From D the nearest is C at 12, then A at 14, then E at 22, then F at 9, then B at 41, and the return B to D costs 18. Tour D C A E F B D, length 12 + 14 + 22 + 9 + 41 + 18 = 116.
Both are genuine tours, so both are upper bounds, and the smaller is the stronger statement: the best upper bound here is 116.
M1 for the nearest neighbour method from A, A1 for that tour, A1 for 122, M1 for the method from D, A1 for 116, B1 for taking the smaller as the upper bound.
Different starts give different tours because the algorithm looks only one step ahead and the closing edge is forced whatever its length.

Question 12

For the same network, use Kruskal's algorithm to find the minimum spanning tree, and hence write down an upper bound for the optimal tour. Improve that bound by short-cutting a walk around the tree.

Accepted Answer

Kruskal takes the edges in increasing order, rejecting any that would close a cycle: EF 9, CD 12, AC 14, BD 18, CE 19. Five edges join six vertices, so the tree is finished, with weight 9 + 12 + 14 + 18 + 19 = 72.
Walking every tree edge twice visits every vertex and returns to the start, so 2 × 72 = 144 is an upper bound.
The walk from A reads A C D B D C E F E C A. Listing each vertex at its first appearance and travelling direct from there gives the tour A C D B E F A, of length 14 + 12 + 18 + 38 + 9 + 31 = 122. Short-cutting can never lengthen the walk, because the triangle inequality holds.
M1 for Kruskal's algorithm, A1 for the five tree edges, A1 for 72, B1 for doubling to 144, M1 for short-cutting to a tour, A1 for a tour and its length.
The short-cut is not unique, and a different walk gives a different tour: A C E F E C D B D C A short-cuts to A C E F D B A, of length 14 + 19 + 9 + 24 + 18 + 31 = 115, better than the 116 nearest neighbour managed. Any such tour is a valid upper bound, so take the smallest one the work produces.

Question 13

For the same network, find the lower bound obtained by deleting C. By interchanging two vertices in the tour A C D B E F A, find a shorter tour than any found so far. State what your two bounds together prove about the optimal tour, and what they do not.

Accepted Answer

Delete C and every edge meeting it, leaving A, B, D, E and F. Kruskal on those takes EF 9, BD 18, AE 22 and DE 22, so the tree weighs 71. The two shortest edges at C are CD 12 and CA 14, total 26. Lower bound = 71 + 26 = 97. Deleting A instead leaves a tree of weight 58 and two shortest edges AC 14 and AE 22, giving 58 + 36 = 94, so C is the better vertex to remove and 97 is the bound to quote.
Interchanging B and D in A C D B E F A gives A C B D E F A, of length 14 + 20 + 18 + 22 + 9 + 31 = 114, shorter than any tour found so far.
So 97 ≤ T ≤ 114.
What that proves: a tour of length 114 exists, because one has been written down, and no tour anywhere in this network is shorter than 97.
What it does not prove: it does not say which tour is optimal, nor how long the optimal tour is. Neither end of the bracket need be attained. Optimality is proved only when a lower bound equals the length of a tour that has actually been found, and here the two differ by 17. Checking all 60 tours gives 107, a value neither bound reaches, so the bracket really is loose at both ends.
M1 for deleting C, A1 for the tree edges, A1 for 71, B1 for the two shortest edges at C, A1 for 97, M1 for the interchange giving a shorter tour, A1 for 114, B1 for what the bounds do and do not establish.

Question 14

A complete network has vertices P, Q, R, S, T with PQ 9, PR 15, PS 12, PT 20, QR 7, QS 14, QT 18, RS 10, RT 16 and ST 11. Deleting T gives a lower bound of 53, and the tour P S T R Q P has length 55. Find the lower bound obtained by deleting P instead, say which of the two bounds should be quoted, and state what the work proves about the optimal tour and what it does not.

Accepted Answer

Delete P and every edge meeting it, leaving Q, R, S, T with QR 7, QS 14, QT 18, RS 10, RT 16 and ST 11. The minimum spanning tree takes QR 7, then RS 10, then ST 11, three arcs for four vertices, weight 28. M1 for deleting P, A1 for the tree QR, RS, ST and its weight.
The two shortest edges at P are PQ 9 and PS 12, totalling 21. B1.
Lower bound = 28 + 21 = 49. A1.
Every deletion gives a valid lower bound, so the largest available is the strongest statement: 53, from deleting T, is the one to quote, and 49 adds nothing to it. B1.
Together with the tour of 55 this gives 53 ≤ optimal tour ≤ 55. What it proves: a tour of length 55 exists, since one is written down, and no tour of this network is shorter than 53. What it does not prove: which tour is optimal, or that either end of the bracket is attained. B1.
Optimality is settled only when a lower bound equals the length of a tour actually found. Here the two differ by 2, and a complete search of the twelve distinct tours does give 55, so the tour happens to be optimal and this work does not show it.

Question 15

A complete network has vertices P, Q, R, S, T with PQ 9, PR 15, PS 12, PT 20, QR 7, QS 14, QT 18, RS 10, RT 16 and ST 11. Find its minimum spanning tree, use it to write down an upper bound for the optimal tour, and improve that bound by short-cutting a walk around the tree starting at P.

Accepted Answer

Kruskal takes the edges in increasing order, rejecting any that would close a cycle: QR 7, PQ 9, RS 10, then ST 11. Four arcs join five vertices, so the tree is finished. M1 for the algorithm, A1 for the four arcs QR, PQ, RS, ST.
Weight 7 + 9 + 10 + 11 = 37. A1.
Walking every tree edge twice visits every vertex and returns to the start, so 2 × 37 = 74 is an upper bound. B1.
The tree is the path P–Q–R–S–T, so the walk from P reads P Q R S T S R Q P. Listing each vertex at its first appearance and travelling direct from there gives the tour P Q R S T P, of length 9 + 7 + 10 + 11 + 20 = 57. A1.
Short-cutting can never lengthen the walk, because the triangle inequality holds here, so 57 is a better upper bound than 74. It is not the best one available: nearest neighbour started at R gives 55. Any tour at all is an upper bound, so the smallest one the work produces is the one to quote.