| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Multiple Nearest Neighbour Routes |
| Difficulty | Moderate -0.3 This is a standard D2 travelling salesman question requiring routine application of nearest neighbour algorithm (twice) and lower bound calculation by deletion. The procedures are algorithmic and well-practiced, though the multiple nearest neighbour routes add slight complexity. Easier than average A-level maths as it's purely procedural with no novel problem-solving or proof required. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| A | B | C | D | E | F | |
| A | - | 90 | 130 | 85 | 35 | 125 |
| B | 90 | - | 80 | 100 | 83 | 88 |
| C | 130 | 80 | - | 108 | 106 | 105 |
| D | 85 | 100 | 108 | - | 110 | 88 |
| E | 35 | 83 | 106 | 110 | - | 75 |
| F | 125 | 88 | 105 | 88 | 75 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Part | Scheme | Marks |
| (a) | \(A \enspace E \enspace F \enspace B \enspace C \enspace D \enspace A\) and \(A \enspace E \enspace F \enspace D \enspace B \enspace C \enspace A\) \(35+75+88+80+108+85 = 471\) and \(35+75+88+100+80+130 = 508\) | M1 A1 A1 A1 |
| (b) | RMST weight \(= 85 + 35 + 83 + 80 = 283\) (seconds) Lower bound \(= 283 + 75 + 88 = 446\) (seconds) | M1 A1 A1 |
| (c) | \(446 \leq \text{time} \leq 471\) [accept \(446 \leq \text{time} \leq 471\)] | B3,2,1,0 |
| 10 marks |
| Part | Scheme | Marks | Guidance |
|------|--------|-------|----------|
| (a) | $A \enspace E \enspace F \enspace B \enspace C \enspace D \enspace A$ and $A \enspace E \enspace F \enspace D \enspace B \enspace C \enspace A$ $35+75+88+80+108+85 = 471$ and $35+75+88+100+80+130 = 508$ | M1 A1 A1 A1 | a1M1: Nearest neighbour either $A – E – F – B – C – D –$ or $A – E – F – D – B – C –$, condone lack of return to start. Accept 145623 or 156423 across top of table (numbers must be from NN not Prim). a1A1: One route correctly stated, must return to A, accept link back to A. a2A1: One route length correctly stated. Do not ISW if candidates then go on to double the route length in (a). a3A1: Second route and its length correctly stated. Do not ISW if candidates then go on to double the route length in (a). |
| (b) | RMST weight $= 85 + 35 + 83 + 80 = 283$ (seconds) Lower bound $= 283 + 75 + 88 = 446$ (seconds) | M1 A1 A1 | b1M1: Finding RST (maybe implicit) and using the correct two least lengths. Their RST must have only four arcs none of which are incident to F. b1a1: RMST correct or list of arcs or 283 or $85 + 35 + 83 + 80$ seen. b2A1: CAO 446 |
| (c) | $446 \leq \text{time} \leq 471$ [accept $446 \leq \text{time} \leq 471$] | B3,2,1,0 | c2B1ft: any indication of interval from their 446 (must come from six arcs) to their 471. c3B1: $446 \leq \text{time} \leq 471$ or $446 < \text{time} \leq 471$ |
| | | **10 marks** | |
---2. The table shows the least times, in seconds, that it takes a robot to travel between six points in an automated warehouse. These six points are an entrance, A , and five storage bins, $\mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F . The robot will start at A , visit each bin, and return to A . The total time taken for the robot's route is to be minimised.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 90 & 130 & 85 & 35 & 125 \\
\hline
B & 90 & - & 80 & 100 & 83 & 88 \\
\hline
C & 130 & 80 & - & 108 & 106 & 105 \\
\hline
D & 85 & 100 & 108 & - & 110 & 88 \\
\hline
E & 35 & 83 & 106 & 110 & - & 75 \\
\hline
F & 125 & 88 & 105 & 88 & 75 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Show that there are two nearest neighbour routes that start from A . You must make the routes and their lengths clear.
\item Starting by deleting F , and all of its arcs, find a lower bound for the time taken for the robot's route.
\item Use your results to write down the smallest interval which you are confident contains the optimal time for the robot's route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2014 Q2 [10]}}