The travelling salesman problemEdexcel International A Level Maths: Subtopic test

1. 1
   A sales representative must visit four towns $P$, $Q$, $R$ and $S$, starting and finishing at $P$. Every pair of towns is joined by a direct road. The distances in km are $PQ=12$, $PR=15$, $PS=9$, $QR=8$, $QS=14$ and $RS=11$. Each town is to be visited exactly once.

   (a)

   How many different tours are there, starting and finishing at $P$, if a tour and its reverse are counted as the same?

   [1 mark]

   • A$2$
   • B$6$
   • C$3$
   • D$24$

   (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

   (c)

   Find the length of the shortest tour for the classical problem.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A driver starts at a depot $H$, delivers to three shops $A$, $B$ and $C$, and returns to $H$. The only roads are $HA=5$, $HB=7$ and $HC=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 $H$, so $H$ must be revisited
   • CThe distances do not satisfy the triangle inequality
   • D$H$ is not joined to every shop

   (b)

   What is the length of the shortest route that starts at $H$, visits every shop and returns to $H$?

   [1 mark]

   • A$16$
   • B$24$
   • C$48$
   • D$32$

   (c)

   A fourth shop $D$ is added, joined only to $C$ by a road of length $3$ km. Find the length of the shortest route that visits all four shops and returns to $H$.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Four offices $W$, $X$, $Y$ and $Z$ are joined by a complete network of direct links. The lengths in km are $WX=20$, $WY=35$, $WZ=25$, $XY=15$, $XZ=30$ and $YZ=10$.

   (a)

   Show that the triangle inequality is not satisfied by this network.

   [3 marks]

   (b)

   Find the shortest tour that visits each office exactly once, starting and finishing at $W$, and give its length.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A bus must visit five stops $A$, $B$, $C$, $D$ and $E$, starting and finishing at $A$. The only roads, with lengths in km, are $AB=4$, $BC=5$, $CD=6$, $DA=7$ and $BE=3$. Stop $E$ is joined to the rest of the network only by $BE$.

   (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 $A$, in which a stop may be revisited, and give its length.

   [6 marks]

   (b)

   A new road $EC$ of length $x$ km is built. Show that there is now a tour visiting each stop exactly once, and find the values of $x$ for which this tour is shorter than the route found in (a).

   [6 marks]

   Total for question 4: 12 marks

End of questions