| Exam Board | AQA |
|---|---|
| Module | Further Paper 3 Discrete (Further Paper 3 Discrete) |
| Year | 2021 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.5 This is a straightforward application of the nearest neighbour algorithm with a standard network diagram, followed by a simple reasoning question about the effect of removing an edge. The algorithm is mechanical (repeatedly select nearest unvisited vertex), and part (b) requires only basic observation that the algorithm's route likely didn't use CE anyway. Slightly easier than average due to the routine nature of the procedure, though the time calculation adds minor arithmetic complexity. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method |
| Answer | Marks | Guidance |
|---|---|---|
| Hamiltonian cycle \(O\)–\(F\)–\(D\)–\(E\)–\(C\)–\(A\)–\(B\)–\(O\) (condone omission of \(B\)–\(O\)) | M1 | AO 3.1a; correct Hamiltonian cycle using nearest neighbour algorithm |
| \((10 + 6 + 6 + 13 + 7 + 13 + 12) = 67\) miles | A1 | AO 1.1b |
| Time to drive \(= (67/40) \times 60 = 100.5\) minutes | A1F | AO 1.1b; correct total time using their total distance |
| Time for 6 deliveries \(= 6 \times 30 = 180\) minutes | M1 | AO 1.1a |
| Upper bound \(T = 100.5 + 180 = 280.5\) | A1 | AO 3.2a; CAO |
| Answer | Marks | Guidance |
|---|---|---|
| As \(CE\) cannot be used, \(AE\) and then \(AC\) must be used instead; new Hamiltonian cycle \(O\)–\(F\)–\(D\)–\(E\)–\(A\)–\(C\)–\(B\)–\(O\); \((10 + 6 + 6 + 14 + 7 + 8 + 12) = 63\) miles | M1 | AO 2.4; explains \(CE\) was part of cycle and \(A\) is now nearest neighbour to \(E\), so \(AE\) used instead |
| Upper bound on \(T\) reduces by 6 to 274.5 | A1 | AO 2.2a |
## Question 4(a):
Hamiltonian cycle $O$–$F$–$D$–$E$–$C$–$A$–$B$–$O$ (condone omission of $B$–$O$) | M1 | AO 3.1a; correct Hamiltonian cycle using nearest neighbour algorithm
$(10 + 6 + 6 + 13 + 7 + 13 + 12) = 67$ miles | A1 | AO 1.1b
Time to drive $= (67/40) \times 60 = 100.5$ minutes | A1F | AO 1.1b; correct total time using their total distance
Time for 6 deliveries $= 6 \times 30 = 180$ minutes | M1 | AO 1.1a
Upper bound $T = 100.5 + 180 = 280.5$ | A1 | AO 3.2a; CAO
---
## Question 4(b):
As $CE$ cannot be used, $AE$ and then $AC$ must be used instead; new Hamiltonian cycle $O$–$F$–$D$–$E$–$A$–$C$–$B$–$O$; $(10 + 6 + 6 + 14 + 7 + 8 + 12) = 63$ miles | M1 | AO 2.4; explains $CE$ was part of cycle and $A$ is now nearest neighbour to $E$, so $AE$ used instead
Upper bound on $T$ reduces by 6 to 274.5 | A1 | AO 2.2a
---4 Derrick, a tanker driver, is required to deliver fuel to 6 different service stations $A , B$, $C , D , E$ and $F$.
Derrick needs to begin and finish his delivery journey at the refinery $O$.\\
The distances, in miles, between the 7 locations which have a direct road between them are shown in the network below.\\
\includegraphics[max width=\textwidth, alt={}, center]{59347089-ea4a-4ee6-b40e-1ab78aa7cdc3-06_921_1440_628_303}
Derrick spends 30 minutes at each service station to complete the fuel delivery.\\
When driving, the tanker travels at an average speed of 40 miles per hour.\\
The minimum total time that it takes Derrick to travel to and deliver fuel to all 6 service stations, starting and finishing at the refinery, is $T$ minutes.
4
\begin{enumerate}[label=(\alph*)]
\item Using the nearest neighbour algorithm starting from the refinery, find an upper bound for $T$\\
4
\item Before setting off to make his fuel deliveries, Derrick is notified that, due to a low bridge, the road represented by CE is not suitable for tankers to travel along.
State, with a reason, the effect this new information has on your answer to part (a).\\[0pt]
[2 marks]
\end{enumerate}
\hfill \mbox{\textit{AQA Further Paper 3 Discrete 2021 Q4 [7]}}