| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Describe route inspection algorithm |
| Difficulty | Moderate -0.5 This is a standard textbook application of the Chinese Postman/Route Inspection algorithm. Part (a) requires recall of the algorithm steps, part (b) is mechanical application to find odd vertices and pair them, and part (c) involves a simple modification. The algorithm is procedural with no novel insight required, making it easier than average, though the multi-part structure and need for careful execution prevents it from being trivial. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| (a) e.g. locate all odd vertices and identify all ways of pairing these. For each way find total of minimum times between pairs. Choose lowest total. Minimum time is total of all arcs + lowest total found above | B3 | |
| (b) Odd vertices are \(A, B, C\) and \(D\). Minimum \(AB\) and \(CD = 20 + 80 = 100\). \(AC\) and \(BD = 40 + 60 = 100\). \(AD\) and \(BC = 40 + 20 = 60\); lowest is 60. Total = sum of all arcs + 60 = 1460 + 60 = 1520 seconds. Route: e.g. FGHIJKLDEAGIBCDEABCIJLF | M1 A1; A1; A1 | |
| (c) Odd vertices now \(C\) and \(D\), minimum \(CD = 200\). New total = 1440 + 200 = 1640 seconds. Removal of arc has increased total time as it provided a useful link | M1 A1; B1 | (11) |
**(a)** e.g. locate all odd vertices and identify all ways of pairing these. For each way find total of minimum times between pairs. Choose lowest total. Minimum time is total of all arcs + lowest total found above | B3 |
**(b)** Odd vertices are $A, B, C$ and $D$. Minimum $AB$ and $CD = 20 + 80 = 100$. $AC$ and $BD = 40 + 60 = 100$. $AD$ and $BC = 40 + 20 = 60$; lowest is 60. Total = sum of all arcs + 60 = 1460 + 60 = 1520 seconds. Route: e.g. FGHIJKLDEAGIBCDEABCIJLF | M1 A1; A1; A1 |
**(c)** Odd vertices now $C$ and $D$, minimum $CD = 200$. New total = 1440 + 200 = 1640 seconds. Removal of arc has increased total time as it provided a useful link | M1 A1; B1 | (11) |
---5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{63f3ba38-8bca-4684-957f-aca7104f2f3e-05_863_1061_223_360}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{center}
\end{figure}
The network in Figure 2 represents the streets near Randolph Square in Newtown, Edinburgh. The weightings represent the average time, in seconds, taken to travel along each road in either direction. The large values for the roads $C D$ and $J L$ are due to traffic lights.
In the course of his work, a van driver must travel along each road at least once each day. He starts and finishes at his depot, $F$, and wishes to minimise the total time that this takes.
\begin{enumerate}[label=(\alph*)]
\item Describe an appropriate algorithm that can be used to find this minimum time.\\
(3 marks)
\item Apply this algorithm to find a route that the driver can take and state the total time he can expect to spend on this journey each day.\\
(5 marks)\\
The section of road $A B$ is to be turned into a pedestrian precinct.
\item Assuming that the driver must still travel along all the other roads at least once each day, find the modified time he can expect to spend on his daily journey
Comment on your answer.\\
(3 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q5 [11]}}