The Travelling Salesman problem

The Travelling Salesman problem Test

Spec 3.2 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

The Travelling Salesman problem

Total 27 marks

Name

Class

Date

  1. 1
    A salesman must visit each of towns A, B, C, D and E once, starting and finishing at A. The distances in km between the towns are: AB 12, AC 10, AD 14, AE 8, BC 3, BD 7, BE 9, CD 6, CE 11 and DE 12.
    (a)
    Using the nearest neighbour algorithm starting at A, which town is visited immediately after E?
    [1 mark]
    • AC
    • BD
    • CE
    • DB
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    What is the weight of the minimum spanning tree for the five towns?
    [1 mark]
    • A26
    • B40
    • C24
    • D33
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the shortest route.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: route A–E–B–C–D–A (nearest unvisited town each time, then back to A)
    A1: upper bound 40 km

    Accept: 8 + 9 + 3 + 6 + 14

    Total for question 1: 4 marks

  2. 2
    A courier must visit depots A, B, C, D and E and return to the start. The only direct roads and their lengths in km are: AB 6, BC 4, CD 5, DE 3, AE 12, BD 11 and CE 10.
    (a)
    What is the least distance between depots A and D?
    [1 mark]
    • A17
    • B18
    • C15
    • D12
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    Which statement describes the practical Travelling Salesman problem?
    [1 mark]
    • AEvery vertex is visited exactly once and the network must be complete
    • BEvery vertex is visited at least once, and a vertex or arc may be used more than once
    • CThe route may leave out some vertices
    • DThe route does not have to return to its start
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Find the least distance between B and D, and the least distance between C and E.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: B to D = 9 (B–C–D, not the road BD of 11)
    B1: C to E = 8 (C–D–E, not the road CE of 10)

    Total for question 2: 4 marks

  3. 3
    A delivery driver must visit five shops A, B, C, D and E, starting and finishing at A, and visiting each shop exactly once. The distances in km between the shops are: AB 15, AC 22, AD 25, AE 18, BC 10, BD 20, BE 12, CD 14, CE 16 and DE 9. These distances satisfy the triangle inequality.
    (a)
    Find a lower bound for the length of the shortest route by deleting shop A.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: minimum spanning tree of B, C, D and E, using BC 10, BE 12 and DE 9, weight 31
    M1: adds the two shortest arcs from A, AB 15 and AE 18

    A1: lower bound 64 km

    Accept: 31 + 15 + 18
    (b)
    Use the nearest neighbour algorithm starting at A to find an upper bound, and hence write down an interval in which the length of the shortest route must lie.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: A–B–C–D–E–A (nearest unvisited shop each time)
    A1: upper bound 15 + 10 + 14 + 9 + 18 = 66 km

    M1: uses lower bound from (a)

    A1: 64 ≤ shortest route ≤ 66

    Accept: follow-through from (a)

    Total for question 3: 7 marks

  4. 4
    An engineer must inspect six sites A, B, C, D, E and F, visiting each site once and returning to the start. The distances in km between the sites are: AB 11, AC 14, AD 20, AE 17, AF 9, BC 8, BD 15, BE 13, BF 12, CD 10, CE 16, CF 18, DE 7, DF 19 and EF 12. These distances satisfy the triangle inequality.
    (a)
    (i) Use Kruskal's algorithm to find a minimum spanning tree for the six sites, and state its weight.
    (ii) Hence find an upper bound by doubling the weight of the tree.

    (iii) Show that a shortcut gives an improved upper bound, and state the route and its length.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) arcs selected in order of size: DE 7, BC 8, AF 9, CD 10, AB 11 (BF 12 and EF 12 would form cycles)
    A1: (i) weight 45

    B1: (ii) upper bound 90 km

    M1: (iii) shortcut: from E go directly to F instead of retracing the tree

    A1: (iii) route F–A–B–C–D–E–F, length 9 + 11 + 8 + 10 + 7 + 12 = 57 km

    R1: (iii) the shortcut is valid because EF = 12 is less than E–D–C–B–A–F = 45 (triangle inequality)
    (b)
    By deleting site A, find a lower bound for the length of the shortest route. Use it, with your answer to (a), to decide whether the route of length 57 km is the shortest possible. Justify your answer.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: minimum spanning tree of B, C, D, E and F (DE 7, BC 8, CD 10, and BF or EF 12)
    A1: weight 37

    M1: adds the two shortest arcs from A, AF 9 and AB 11

    A1: lower bound 57 km

    R1: the lower bound equals the upper bound of 57 km

    B1: so the shortest route is exactly 57 km, and F–A–B–C–D–E–F is optimal

    Accept: follow-through from their upper bound in (a)(iii) for the conclusion

    Total for question 4: 12 marks

End of questions

Subtopic tests