| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Multiple Nearest Neighbour Routes |
| Difficulty | Moderate -0.3 This is a standard multi-part travelling salesman problem using textbook algorithms (Prim's, nearest neighbour, lower bound by deletion). Each part follows routine procedures with clear instructions and a small network (5 vertices), requiring systematic application rather than problem-solving insight. Slightly easier than average due to its algorithmic, step-by-step nature. |
| Spec | 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| A | B | C | D | E | |
| A | - | 15 | 19 | 25 | 20 |
| B | 15 | - | 15 | 15 | 25 |
| C | 19 | 15 | - | 22 | 11 |
| D | 25 | 15 | 22 | - | 18 |
| E | 20 | 25 | 11 | 18 | - |
| Answer | Marks | Guidance |
|---|---|---|
| (a) e.g. starting from A: AB, BD, BC, CE or AB, BC, CE, BD | M1A1 | (2) |
| (b) \(2 \times 56 = 112\) | B1 | (1) |
| Answer | Marks | Guidance |
|---|---|---|
| \(15 + 15 + 11 + 18 + 25 = 84\) and \(15 + 15 + 18 + 11 + 19 = 78\) | M1 A1 A1 | (3) |
| (d) 78 is the better upper bound | B1ft | (1) |
| (e) Lower bound \(= 48 + 15 + 15 = 78\) | 1M1A1 2M1A1 | (4) |
| Answer | Marks | Guidance |
|---|---|---|
| f1B1 CAO, accept any start point for the correct tour, but must return to start. Dependent on their answer to part (d) = their answer to part (e). | B1 | Total 12 |
**(a)** e.g. starting from A: AB, BD, BC, CE or AB, BC, CE, BD | M1A1 | (2)
**(b)** $2 \times 56 = 112$ | B1 | (1)
**(c)** $A \quad B \quad C \quad E \quad D \quad A$ and $A \quad B \quad D \quad E \quad C \quad A$
$15 + 15 + 11 + 18 + 25 = 84$ and $15 + 15 + 18 + 11 + 19 = 78$ | M1 A1 A1 | (3)
**(d)** 78 is the better upper bound | B1ft | (1)
**(e)** Lower bound $= 48 + 15 + 15 = 78$ | 1M1A1 2M1A1 | (4)
**(f)** The route is ABDECA
(The optimal route length is 78, since upper bound = lower bound)
a1M1 First three arcs (or all 5 nodes / or numbers across the top of the matrix) selected correctly (may start from any node). Award M1 only for a correct tree with no working.
a1A1 CAO (order of arc selection)
b1B1 112 CAO
c1M1 Nearest Neighbour either A-B-C-E-D- or A-B-D-E-C- (condone lack of return to start). Accept 12354 or 12534 across the top of the matrix.
c1A1 1 route and length CAO (Do not ISW if route length is doubled)
c2A1 both routes and lengths CAO (Do not ISW if route lengths are doubled)
d1B1ft their stated shortest (must be a number)
e1M1 Finding correct RMST (maybe implicit) 48 sufficient, or correct numbers. 3 arcs.
e1A1 CAO; tree or 48 or 11 + 18 + 19 seen.
e2M1 Adding 2 least arcs to B; 15 and 15 or two out of BA, BC or BD or 30 only
e2A1 CAO 78
f1B1 CAO, accept any start point for the correct tour, but must return to start. Dependent on their answer to part (d) = their answer to part (e). | B1 | Total 12
---1.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& A & B & C & D & E \\
\hline
A & - & 15 & 19 & 25 & 20 \\
\hline
B & 15 & - & 15 & 15 & 25 \\
\hline
C & 19 & 15 & - & 22 & 11 \\
\hline
D & 25 & 15 & 22 & - & 18 \\
\hline
E & 20 & 25 & 11 & 18 & - \\
\hline
\end{tabular}
\end{center}
The table shows the least distances, in km, between five hiding places, A, B, C, D and E.\\
Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A , and wishes to minimise the total distance travelled.
\begin{enumerate}[label=(\alph*)]
\item Use Prim's algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.
\item Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie's route.
\item Show that there are two nearest neighbour routes which start from A . State these routes and their lengths.
\item State the better upper bound from your answers to (b) and (c).
\item Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie's route.
\item Consider your answers to (d) and (e) and hence state an optimal route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2013 Q1 [12]}}