| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2020 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Standard +0.3 This is a standard application of nearest neighbour algorithm and lower bound techniques from the Decision Maths syllabus. The question requires methodical execution of well-defined algorithms with clear procedures: (a) apply nearest neighbour from depot, (b) delete depot and find minimum spanning tree plus two shortest edges, (c) compare bounds. While it involves multiple steps and careful table reading, it requires no novel insight or problem-solving—just accurate application of textbook algorithms, making it slightly easier than average. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| Depot | \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | C | \(\boldsymbol { D }\) | \(E\) | \(F\) | |
| Depot | - | 18 | 17 | 15 | 16 | 19 | 30 |
| \(\boldsymbol { A }\) | 18 | - | 29 | 20 | 25 | 35 | 21 |
| B | 17 | 29 | - | 26 | 30 | 16 | 14 |
| C | 15 | 20 | 26 | - | 28 | 31 | 27 |
| D | 16 | 25 | 30 | 28 | - | 34 | 24 |
| E | 19 | 35 | 16 | 31 | 34 | - | 28 |
| F | 30 | 21 | 14 | 27 | 24 | 28 | - |
4 Joe, a courier, is required to deliver parcels to six different locations, $A , B , C , D , E$ and $F$.
Joe needs to start and finish his journey at the depot.\\
The distances, in miles, between the depot and the six different locations are shown in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& Depot & $\boldsymbol { A }$ & $\boldsymbol { B }$ & C & $\boldsymbol { D }$ & $E$ & $F$ \\
\hline
Depot & - & 18 & 17 & 15 & 16 & 19 & 30 \\
\hline
$\boldsymbol { A }$ & 18 & - & 29 & 20 & 25 & 35 & 21 \\
\hline
B & 17 & 29 & - & 26 & 30 & 16 & 14 \\
\hline
C & 15 & 20 & 26 & - & 28 & 31 & 27 \\
\hline
D & 16 & 25 & 30 & 28 & - & 34 & 24 \\
\hline
E & 19 & 35 & 16 & 31 & 34 & - & 28 \\
\hline
F & 30 & 21 & 14 & 27 & 24 & 28 & - \\
\hline
\end{tabular}
\end{center}
The minimum total distance that Joe can travel in order to make all six deliveries, starting and finishing at the depot, is $L$ miles.
4
\begin{enumerate}[label=(\alph*)]
\item Using the nearest neighbour algorithm starting from the depot, find an upper bound for $L$.\\
4
\item By deleting the depot, find a lower bound for $L$.\\
4
\item Joe starts from the depot, delivers parcels to all six different locations and arrives back at the depot, covering 134 miles in the process.
Joe claims that this is the minimum total distance that is possible for the journey. Comment on Joe's claim.
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2020 Q4 [7]}}