| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Calculate Specific Tour Length |
| Difficulty | Moderate -0.5 This is a standard D1 travelling salesman problem requiring routine application of algorithms (nearest neighbour, lower bound by deletion). Part (a)(i) is simple arithmetic from a table, (a)(ii) and (b) follow textbook procedures with no novel insight needed. The calculations are straightforward with only 5 vertices, making this easier than average A-level maths but typical for D1 module work. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| Rialto ( \(R\) ) | St Mark's ( \(S\) ) | Murano ( \(M\) ) | Burano (B) | Lido (L) | |
| Rialto ( \(R\) ) | - | 15 | 55 | 75 | 25 |
| St Mark's ( \(S\) ) | 15 | - | 90 | 60 | 20 |
| Murano ( \(M\) ) | 55 | 90 | - | 25 | 80 |
| Burano (B) | 75 | 60 | 25 | - | 50 |
| Lido ( \(L\) ) | 25 | 20 | 80 | 50 | - |
6 Mia is on holiday in Venice. There are five places she wishes to visit: Rialto $( R )$, St Mark's $( S )$, Murano ( $M$ ), Burano ( $B$ ) and Lido ( $L$ ). Boat services connect the five places. The table shows the times, in minutes, to travel between the places.
Mia wishes to keep her travelling time to a minimum.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Rialto ( $R$ ) & St Mark's ( $S$ ) & Murano ( $M$ ) & Burano (B) & Lido (L) \\
\hline
Rialto ( $R$ ) & - & 15 & 55 & 75 & 25 \\
\hline
St Mark's ( $S$ ) & 15 & - & 90 & 60 & 20 \\
\hline
Murano ( $M$ ) & 55 & 90 & - & 25 & 80 \\
\hline
Burano (B) & 75 & 60 & 25 & - & 50 \\
\hline
Lido ( $L$ ) & 25 & 20 & 80 & 50 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Find the length of the tour $S R M B L S$.
\item Find the length of the tour using the nearest neighbour algorithm starting from $S$.
\end{enumerate}\item By deleting Burano ( $B$ ), find a lower bound for the length of the minimum tour.
\item Sketch a network showing the edges that give the lower bound found in part (b) and comment on its significance.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2005 Q6 [13]}}