| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Asymmetric Distance Matrix |
| Difficulty | Moderate -0.8 This is a standard D1 travelling salesman problem requiring straightforward application of the nearest neighbour algorithm and basic understanding of upper bounds. Parts (a) and (b) are trivial table lookups, part (c)(i) is mechanical algorithm application, and part (c)(iii) requires only systematic enumeration of a few routes with constraints. No novel insight or complex problem-solving is needed. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method |
| \backslashbox{From}{To} | La Pedrera ( \(L\) ) | Nou Camp (N) | Olympic Village ( \(O\) ) | Park Guell (P) | Ramblas (R) | Sagrada Familia ( \(S\) ) |
| La Pedrera \(( L )\) | - | 35 | 30 | 30 | 37 | 35 |
| Nou Camp \(( N )\) | 25 | - | 20 | 21 | 25 | 40 |
| Olympic Village ( \(O\) ) | 15 | 40 | - | 25 | 30 | 29 |
| Park Guell ( \(P\) ) | 30 | 35 | 25 | - | 35 | 20 |
| Ramblas ( \(R\) ) | 20 | 30 | 17 | 25 | - | 25 |
| Sagrada Familia ( \(S\) ) | 25 | 35 | 29 | 20 | 30 | - |
| Answer | Marks |
|---|---|
| \(35 \quad 20 \quad 15 \quad = 70\) | B1 (1 mark) |
| Answer | Marks |
|---|---|
| \(35 \quad 40 \quad 25 \quad = 95\) | B1 (1 mark) |
| Answer | Marks |
|---|---|
| Any cycle | B1 (1 mark) |
| Answer | Marks | Guidance |
|---|---|---|
| \(20 \quad 25 \quad 15 \quad 35 \quad 25 \quad 25\) | M1 | Tour |
| M1, A1 (3 marks) | Every vertex; All correct |
| Answer | Marks |
|---|---|
| Tour; May be improved | E1, E1 (2 marks) |
| Answer | Marks | Guidance |
|---|---|---|
| \(= 138\) | M1, A1, B1 (3 marks) | Tour to every vertex with \(SR + N + P\); All correct |
## Question 8:
**Part (a)(i):**
$L \quad N \quad O \quad L$
$35 \quad 20 \quad 15 \quad = 70$ | B1 (1 mark) |
**Part (a)(ii):**
$L \quad O \quad N \quad L$
$35 \quad 40 \quad 25 \quad = 95$ | B1 (1 mark) |
**Part (b):**
Any cycle | B1 (1 mark) |
**Part (c)(i):**
$S \quad P \quad O \quad L \quad N \quad R \quad S$
$20 \quad 25 \quad 15 \quad 35 \quad 25 \quad 25$ | M1 | Tour
| M1, A1 (3 marks) | Every vertex; All correct
**Part (c)(ii):**
Tour; May be improved | E1, E1 (2 marks) |
**Part (c)(iii):**
$S \quad R \quad O \quad L \quad N \quad P \quad S$
$30 \quad 17 \quad 15 \quad 35 \quad 21 \quad 20$
$= 138$ | M1, A1, B1 (3 marks) | Tour to every vertex with $SR + N + P$; All correct
---8 Salvadore is visiting six famous places in Barcelona: La Pedrera $( L )$, Nou Camp $( N )$, Olympic Village $( O )$, Park Guell $( P )$, Ramblas $( R )$ and Sagrada Familia $( S )$. Owing to the traffic system the time taken to travel between two places may vary according to the direction of travel.
The table shows the times, in minutes, that it will take to travel between the six places.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
\backslashbox{From}{To} & La Pedrera ( $L$ ) & Nou Camp (N) & Olympic Village ( $O$ ) & Park Guell (P) & Ramblas (R) & Sagrada Familia ( $S$ ) \\
\hline
La Pedrera $( L )$ & - & 35 & 30 & 30 & 37 & 35 \\
\hline
Nou Camp $( N )$ & 25 & - & 20 & 21 & 25 & 40 \\
\hline
Olympic Village ( $O$ ) & 15 & 40 & - & 25 & 30 & 29 \\
\hline
Park Guell ( $P$ ) & 30 & 35 & 25 & - & 35 & 20 \\
\hline
Ramblas ( $R$ ) & 20 & 30 & 17 & 25 & - & 25 \\
\hline
Sagrada Familia ( $S$ ) & 25 & 35 & 29 & 20 & 30 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Find the total travelling time for:
\begin{enumerate}[label=(\roman*)]
\item the route $L N O L$;
\item the route $L O N L$.
\end{enumerate}\item Give an example of a Hamiltonian cycle in the context of the above situation.
\item Salvadore intends to travel from one place to another until he has visited all of the places before returning to his starting place.
\begin{enumerate}[label=(\roman*)]
\item Show that, using the nearest neighbour algorithm starting from Sagrada Familia $( S )$, the total travelling time for Salvadore is 145 minutes.
\item Explain why your answer to part (c)(i) is an upper bound for the minimum travelling time for Salvadore.
\item Salvadore starts from Sagrada Familia ( $S$ ) and then visits Ramblas ( $R$ ). Given that he visits Nou Camp $( N )$ before Park Guell $( P )$, find an improved upper bound for the total travelling time for Salvadore.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2006 Q8 [11]}}