The travelling salesman problem

The travelling salesman problem Test

Spec 3.2 · Edexcel International A Level 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 International A Level Maths

The travelling salesman problem

Total 27 marks

Name

Class

Date

  1. 1
    A sales representative must visit four towns PP, QQ, RR and SS, starting and finishing at PP. Every pair of towns is joined by a direct road. The distances in km are PQ=12PQ=12, PR=15PR=15, PS=9PS=9, QR=8QR=8, QS=14QS=14 and RS=11RS=11. Each town is to be visited exactly once.
    (a)
    How many different tours are there, starting and finishing at PP, if a tour and its reverse are counted as the same?
    [1 mark]
    • A22
    • B66
    • C33
    • D2424
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    Which statement describes the classical travelling salesman problem, as opposed to the practical problem?
    [1 mark]
    • AEach vertex is visited exactly once
    • BA vertex may be visited more than once
    • CNot every vertex needs visiting
    • DThe route need not return to the start
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Find the length of the shortest tour for the classical problem.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: all three tours considered, PQRSP=40PQRSP=40, PQSRP=52PQSRP=52, PRQSP=46PRQSP=46
    A1: shortest tour
    PQRSPPQRSP (or PSRQPPSRQP) of length 4040 km

    Total for question 1: 4 marks

  2. 2
    A driver starts at a depot HH, delivers to three shops AA, BB and CC, and returns to HH. The only roads are HA=5HA=5, HB=7HB=7 and HC=4HC=4, with lengths in km. The driver may pass through a junction more than once.
    (a)
    Why can the classical travelling salesman problem not be solved on this network?
    [1 mark]
    • AThe network is not connected
    • BEach shop is joined only to HH, so HH must be revisited
    • CThe distances do not satisfy the triangle inequality
    • DHH is not joined to every shop
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    What is the length of the shortest route that starts at HH, visits every shop and returns to HH?
    [1 mark]
    • A1616
    • B2424
    • C4848
    • D3232
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    A fourth shop DD is added, joined only to CC by a road of length 33 km. Find the length of the shortest route that visits all four shops and returns to HH.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: every road travelled twice, 2(5+7+4+3)2(5+7+4+3)
    A1:
    3838 km
    Accept: route
    HH-AA-HH-BB-HH-CC-DD-CC-HH

    Total for question 2: 4 marks

  3. 3
    Four offices WW, XX, YY and ZZ are joined by a complete network of direct links. The lengths in km are WX=20WX=20, WY=35WY=35, WZ=25WZ=25, XY=15XY=15, XZ=30XZ=30 and YZ=10YZ=10.
    (a)
    Show that the triangle inequality is not satisfied by this network.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: considers a triangle with its longest side, for example XZXZ against XY+YZXY+YZ
    A1:
    XY+YZ=15+10=25<30=XZXY+YZ=15+10=25<30=XZ
    B1: the triangle inequality requires the longest side to be no more than the sum of the other two, so it fails

    Accept: any correct statement that
    XZ>XY+YZXZ>XY+YZ
    (b)
    Find the shortest tour that visits each office exactly once, starting and finishing at WW, and give its length.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: all three tours considered, in either direction
    A1:
    WXYZW=20+15+10+25=70WXYZW=20+15+10+25=70
    A1:
    WXZYW=20+30+10+35=95WXZYW=20+30+10+35=95 and WYXZW=35+15+30+25=105WYXZW=35+15+30+25=105
    B1: shortest tour
    WW-XX-YY-ZZ-WW of length 7070 km

    Total for question 3: 7 marks

  4. 4
    A bus must visit five stops AA, BB, CC, DD and EE, starting and finishing at AA. The only roads, with lengths in km, are AB=4AB=4, BC=5BC=5, CD=6CD=6, DA=7DA=7 and BE=3BE=3. Stop EE is joined to the rest of the network only by BEBE.
    (a)
    (i) Explain why the classical travelling salesman problem has no solution on this network.
    (ii) Find the shortest route that visits every stop and returns to
    AA, in which a stop may be revisited, and give its length.
    [6 marks]
    Show the mark scheme

    Mark scheme

    R1: (i) EE is joined only to BB
    R1: so a route entering
    EE must leave by the same road, and BB cannot be visited only once
    B1: (ii) the road
    BEBE must be travelled twice, 2×3=62\times3=6
    M1: the other four stops need the whole cycle
    ABCDABCD, 4+5+6+7=224+5+6+7=22
    A1: route
    AA-BB-EE-BB-CC-DD-AA
    A1: length
    2828 km
    Accept: the route in reverse, or starting at another vertex
    (b)
    A new road ECEC of length xx km is built. Show that there is now a tour visiting each stop exactly once, and find the values of xx for which this tour is shorter than the route found in (a).
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: tour using BEBE and ECEC so that each stop is visited once, AA-BB-EE-CC-DD-AA
    A1: the tour does not use
    BCBC
    A1: length
    4+3+x+6+7=20+x4+3+x+6+7=20+x
    M1: compares
    20+x20+x with 2828
    A1:
    x<8x<8
    R1: when
    x<8x<8 the new tour is shorter, and when x≥8x\geq8 the route in (a) is still the shortest

    Total for question 4: 12 marks

End of questions

Subtopic tests