| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2021 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Complete Table by Inspection |
| Difficulty | Moderate -0.3 This is a standard D1 travelling salesman problem requiring routine application of nearest neighbour algorithm and lower bound techniques. Part (a) involves simple inspection of a network diagram to complete a table, parts (b)-(d) are textbook TSP algorithms, and part (e) is a standard Chinese Postman variant. While multi-part with several marks, each component follows well-rehearsed procedures with no novel problem-solving required, making it slightly easier than average. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree7.04e Route inspection: Chinese postman, pairing odd nodes |
**(a)** B2, 1, 0 (2)
At least two of the six values correct (in either table) – these are the bold values. The two values can be the same (for example, 42 in both cells AC and CA would score this mark)
Fully correct (the six bold values in both tables)
**(b)** M1
Nearest neighbour route starting at A – must have at least A – D – E – F – C – B – …
Allow if stated in terms of arcs (AD, DE, EF, FC, CB,…) rather than nodes (note that arcs AD and DA are equivalent and so therefore AD, ED, EF, FC, CB,… is acceptable)
A1 (2)
CAO on length (136) and route (must return to A and can be stated in terms of arcs rather than nodes)
**(c)** B1 (1)
CAO (ADEFCFBGBA or in terms of arcs, e.g., AD, DE, EF, FC, CF, FB, BG, GB, BA)
**(d)** B1
CAO on the weight of the RMST (using arcs BE, EF, CF, DE, BG) – accept either 64 or $12 + 6 + 11 + 15 + 20$ – could be seen or implied by later working as part of the lower bound calculation
M1
Adding correct two least weighted arcs from A ($17(AD) + 21(AB)$) to their RMST length where their RMST length $x$ is $58 \leq x \leq 70$
A1 (3)
CAO (102). If this answer is stated with no working then award B0M1A1
**(e)** M1
Correct three distinct pairings of the correct four odd nodes (A, C, E and G)
A1
Any two rows correct including pairings and totals
A1
All three rows correct including pairings and totals
A1
CAO correct edges clearly stated and not just in their working as AB, BG, CF and EF – must be these arcs. Do not accept AG, ABG or AG via B (and similarly for CE)
A1ft (5)
Follow through their value of their smallest pairing total + 291
**Condone lack of, or incorrect units throughout this question**
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{44ddb176-e265-4545-b438-c1b5ffb40852-05_618_1105_237_479}
\captionsetup{labelformat=empty}
\caption{Figure 3\\[0pt]
[The total weight of the network is 291]}
\end{center}
\end{figure}
Figure 3 models a network of roads. The number on each edge gives the length, in km , of the corresponding road. The vertices, A, B, C, D, E, F and G, represent seven towns. Derek needs to visit each town. He will start and finish at A and wishes to minimise the total distance travelled.
\begin{enumerate}[label=(\alph*)]
\item By inspection, complete the two copies of the table of least distances in the answer book.
\item Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Derek's route. Write down the route that gives this upper bound.
\item Interpret the route found in (b) in terms of the towns actually visited.
\item Starting by deleting A and all of its arcs, find a lower bound for the route length.
Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G .
\item By considering the pairings of all relevant nodes, find the length of Clive's route. State the edges that need to be traversed twice. You must make your method and working clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2021 Q4 [13]}}