| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2016 |
| 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 algorithmic application of nearest neighbour and lower bound methods. Part (a) is definitional recall, parts (b-d) involve systematic but routine application of taught algorithms with clear procedures. The 'two routes' aspect adds minor complexity but this is typical textbook material requiring careful execution rather than problem-solving insight. |
| 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 | G | |
| A | - | 31 | 15 | 12 | 24 | 17 | 22 |
| B | 31 | - | 20 | 25 | 14 | 25 | 50 |
| C | 15 | 20 | - | 16 | 24 | 19 | 21 |
| D | 12 | 25 | 16 | - | 21 | 32 | 17 |
| E | 24 | 14 | 24 | 21 | - | 28 | 41 |
| F | 17 | 25 | 19 | 32 | 28 | - | 25 |
| G | 22 | 50 | 21 | 17 | 41 | 25 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Classical: must visit every town directly (Hamiltonian cycle required) | B1 | Direct connections only |
| Practical: can use shortest path between towns (repeated vertices allowed) | B1 | Accept equivalent wording |
| Answer | Marks | Guidance |
|---|---|---|
| From A: nearest is D (12), then G (17), then C (16), then F (19), then E (28), then B (14), return A (31) = 127 | M1 | Showing nearest neighbour process |
| Route: \(A \to D \to G \to C \to F \to E \to B \to A = 127\) | A1 | |
| Tie at second step: D→G (17) and D→C (16)... checking second route: \(A \to D \to C \to G \to F \to E \to B \to A\) | M1 | Identifying the tie |
| Second route total = \(12+16+21+25+28+14+31 = 147\) | A1 | Both routes and lengths stated |
| Answer | Marks | Guidance |
|---|---|---|
| Delete A and its arcs. Find minimum spanning tree on B,C,D,E,F,G: | M1 | |
| Edges: D-G(17), B-E(14), C-D(16), C-F(19), E-B already, G-D... | M1 | Correct MST |
| MST = \(14+16+17+19+21 = 87\) | A1 | |
| Add two shortest arcs from A: \(AC=15\) and \(AD=12\) | M1 | |
| Lower bound = \(87 + 15 + 12 = 114\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| \(114 \leqslant L \leqslant 127\) | B1 | ft their answers |
| B1 | Both endpoints correct |
## Question 1:
**(a)**
Classical: must visit every town directly (Hamiltonian cycle required) | B1 | Direct connections only
Practical: can use shortest path between towns (repeated vertices allowed) | B1 | Accept equivalent wording
**(b)**
From A: nearest is D (12), then G (17), then C (16), then F (19), then E (28), then B (14), return A (31) = **127** | M1 | Showing nearest neighbour process
Route: $A \to D \to G \to C \to F \to E \to B \to A = 127$ | A1 |
Tie at second step: D→G (17) and D→C (16)... checking second route: $A \to D \to C \to G \to F \to E \to B \to A$ | M1 | Identifying the tie
Second route total = $12+16+21+25+28+14+31 = 147$ | A1 | Both routes and lengths stated
**(c)**
Delete A and its arcs. Find minimum spanning tree on B,C,D,E,F,G: | M1 |
Edges: D-G(17), B-E(14), C-D(16), C-F(19), E-B already, G-D... | M1 | Correct MST
MST = $14+16+17+19+21 = 87$ | A1 |
Add two shortest arcs from A: $AC=15$ and $AD=12$ | M1 |
Lower bound = $87 + 15 + 12 = 114$ | A1 |
**(d)**
$114 \leqslant L \leqslant 127$ | B1 | ft their answers
| B1 | Both endpoints correct
---\begin{enumerate}
\item (a) Explain the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.
\end{enumerate}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G \\
\hline
A & - & 31 & 15 & 12 & 24 & 17 & 22 \\
\hline
B & 31 & - & 20 & 25 & 14 & 25 & 50 \\
\hline
C & 15 & 20 & - & 16 & 24 & 19 & 21 \\
\hline
D & 12 & 25 & 16 & - & 21 & 32 & 17 \\
\hline
E & 24 & 14 & 24 & 21 & - & 28 & 41 \\
\hline
F & 17 & 25 & 19 & 32 & 28 & - & 25 \\
\hline
G & 22 & 50 & 21 & 17 & 41 & 25 & - \\
\hline
\end{tabular}
\end{center}
The table above shows the least direct distances, in miles, between seven towns, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ and G. Yiyi needs to visit each town, starting and finishing at A, and wishes to minimise the total distance she will travel.\\
(b) Show that there are two nearest neighbour routes that start from A. State these routes and their lengths.\\
(c) Starting by deleting A, and all of its arcs, find a lower bound for the length of Yiyi's route.\\
(d) Use your results to write down the smallest interval which you can be confident contains the optimal length of Yiyi's route.\\
\hfill \mbox{\textit{Edexcel D2 2016 Q1 [10]}}