Route inspection and the travelling salesman problem Decision 1

Papers
A level Paper 3D; AS Paper 2 (option 27)
Level
AS and A level
Spec
D1.3.1, D1.3.2
Booklet
Nothing is given.
Since 2018
38 question parts, 112 marks

Notes, worked examples and practice for this topic are being written by our tutors. The past-paper questions below are ready now: work each one on paper, then open the mark scheme and the examiner's comment.

Past-paper questions

Print this topic as a pack questions first, then the mark schemes

Tap a question to zoom it. Mark scheme and examiner's comment open under each question.
June 2025 · AS Paper 2 (Decision 1) · Q3(c) 5 marks
Ruby manages road maintenance from her office located at junction B. She needs to walk along each road at least once, starting and finishing at her office. Road AE is temporarily blocked so she is unable to walk along it. Ruby wishes to minimise her journey time. (c) (i) Use an appropriate algorithm to find the roads that Ruby needs to traverse twice. You must make your method and working clear. (ii) Calculate Ruby’s journey time. (5)
June 2025 · AS Paper 2 (Decision 1) · Q3(d) 2 marks
Ruby can save some time by choosing to start her route from any junction and to finish at her home at A. Road AE is still blocked and Ruby again wishes to minimise her journey time. (d) (i) Write down the junction at which Ruby should start. (ii) Calculate how much time she would save. (2)
June 2025 · Paper 3D (Decision 1) · Q3(c) 3 marks
The final time matrix after completion of Floyd’s algorithm is shown below. A B C E F G A – B – C – – E – F – G – Albert must visit each village. He will start and finish at B and wishes to minimise the total time taken to visit each village. (c) (i) Use the nearest neighbour algorithm, starting at B, to find a Hamiltonian cycle in the complete network of shortest times shown above. (ii) Find the total travel time for this cycle. (iii) Given that he travels the Hamiltonian cycle found in (c)(i), interpret this cycle in terms of the actual villages visited by Albert. (3)
June 2025 · Paper 3D (Decision 1) · Q4(b) 5 marks
On Monday afternoon, Turvi needs a route that traverses each corridor at least once. She plans to start at J and finish at A and wants to minimise the distance travelled. (b) (i) By considering the pairings of all relevant nodes, find the corridors that would need to be traversed twice. You must make your method and working clear. (ii) State the total length of this route. (5)
June 2025 · Paper 3D (Decision 1) · Q4(c) 2 marks
Turvi discovers that she cannot walk along corridors AB, CD and JK because they are being decorated. Turvi walks from J to A travelling along all the other corridors at least once. She does this in the minimum distance possible. (c) Determine the difference between the length of the route Turvi travels and the length of the route found in (b). You must make the values used in your calculation clear. (2)
June 2024 · AS Paper 2 (Decision 1) · Q3(c) 1 mark
The warehouse manager wants to check that all of the walkways are in good condition. Their inspection route starts at B and finishes at C. The inspection route must traverse each walkway at least once and be as short as possible. (c) State the arcs that are traversed twice. (1)
June 2024 · AS Paper 2 (Decision 1) · Q3(d) 1 mark
(d) State the number of times that H appears in the inspection route. (1)
June 2024 · AS Paper 2 (Decision 1) · Q3(e) 2 marks
The warehouse manager finds that the total length of the inspection route is 172 metres. (e) Determine the value of x and the value of y (2)
June 2024 · Paper 3D (Decision 1) · Q2(d) 1 mark
A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled. (d) Use your answer to part (b) to calculate an initial upper bound for the length of the historian’s route. (1)
June 2024 · Paper 3D (Decision 1) · Q2(e) 3 marks
(e) (i) Use the nearest neighbour algorithm, starting at D, to find an upper bound for the length of the historian’s route. (ii) Write down the route which gives this upper bound. (3)
June 2024 · Paper 3D (Decision 1) · Q2(f) 1 mark
Using the nearest neighbour algorithm, starting at F, an upper bound of length 352 miles was found. (f) State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer. (1)
June 2024 · Paper 3D (Decision 1) · Q2(g) 2 marks
(g) By deleting A and all of its arcs, find a lower bound for the length of the historian’s route. (2)
June 2024 · Paper 3D (Decision 1) · Q2(h) 1 mark
By deleting J and all of its arcs, a lower bound of length 274 miles was found. (h) State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer. (1)
June 2024 · Paper 3D (Decision 1) · Q3(b) 6 marks
Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K. Abi wishes to minimise the total distance required to traverse every track. (b) By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must • state which tracks she will repeat in her route • state the total length of her route (6)
June 2024 · Paper 3D (Decision 1) · Q3(c) 2 marks
The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H. Tarig wishes to minimise the total length of his inspection route. (c) Determine which route, Abi’s or Tarig’s, is shorter. You must make your working clear. (2)
June 2023 · AS Paper 2 (Decision 1) · Q5(c) 6 marks
Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road. You are given that x > 1.6 A route is required that • starts and finishes at the same vertex • traverses each road at least once • minimises the total time taken The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes. Given that the inspection route contains two roads that need to be traversed twice, (c) determine the range of possible values of x, making your reasoning clear. (6)
June 2023 · Paper 3D (Decision 1) · Q5(a) 5 marks
5. A B H C G F E J Figure 5 [The total weight of the network is 423] Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road. The table below shows the shortest distances, in miles, between the nine towns. A B C E F G H J A – B – C – – E – F – G – H – J – Table of shortest distances A route is needed that minimises the total distance required to traverse each road at least once. The route must start at F and finish at J. (a) (i) By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice. (ii) State the total length of this route. (5)
June 2023 · Paper 3D (Decision 1) · Q5(c) 2 marks
Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels. (c) Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete’s route. Write down the route that gives this upper bound. (2)
June 2023 · Paper 3D (Decision 1) · Q5(d) 2 marks
(d) By deleting G and all of its arcs, find a lower bound for the length of Pete’s route. (2)
June 2023 · Paper 3D (Decision 1) · Q5(e) 1 mark
Pete decides to take the route he found in (c). (e) Interpret the route in terms of the actual towns visited. (1)
June 2022 · AS Paper 2 (Decision 1) · Q3(d) 6 marks
An extra cycle track of length 9 km is to be added to the network. It will either go directly between C and D or directly between E and G. Daisy plans to cycle along every track in the new network, starting and finishing at H. Given that the addition of either track CD or track EG will not affect the final values obtained in (c), (d) use a suitable algorithm to find out which of the two possible extra tracks will give Daisy the shortest route, making your method and working clear. You must • state which tracks Daisy will repeat in her route • state the total length of her route (6)
June 2022 · Paper 3D (Decision 1) · Q2(b) 2 marks
The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E. (b) (i) State the edges that will need to be traversed twice. (ii) Find the length of Blanche’s route. (2)
June 2022 · Paper 3D (Decision 1) · Q2(c) 5 marks
It is now decided to start the inspection route at A and finish at K. Blanche must minimise the length of her route and travel along each track at least once. (c) By considering the pairings of all relevant nodes, find the length of Blanche’s new route. You must make your method and working clear. (5)
June 2022 · Paper 3D (Decision 1) · Q3(c) 4 marks
The final distance matrix after completion of Floyd’s algorithm is shown in Table 3. A B C E F A – B – C – – E – F – Table 3 Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled. (c) (i) Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances. (ii) Find the length of each of the two cycles. (iii) State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka’s route. (4)
Nov 2021 · Paper 3D (Decision 1) · Q3(c) 2 marks
A B C E F G H J Table 2 Table 2 shows the distances, in miles, between town J and towns A, B, C, D, E, F, G and H. Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels. (c) Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav’s route. You must state your route and its length. (2)
Nov 2021 · Paper 3D (Decision 1) · Q3(d) 2 marks
(d) Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav’s route. (2)
Nov 2021 · Paper 3D (Decision 1) · Q4(c) 4 marks
The final time matrix after completion of Floyd’s algorithm is shown below. A B C E F A – B – C – – E – F – A route is needed that minimises the total time taken to traverse each road at least once. The route must start at B and finish at E. (c) Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear. (4)
Nov 2021 · Paper 3D (Decision 1) · Q4(d) 1 mark
(d) Write down the length of the route. (1)
Oct 2020 · AS Paper 2 (Decision 1) · Q3(c) 6 marks
A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex. Given that the time taken to traverse this route is 318 minutes, (c) use an appropriate algorithm to determine the value of x, showing your working clearly. (6)
Oct 2020 · Paper 3D (Decision 1) · Q3(c) 3 marks
The final time matrix after completion of Floyd’s algorithm is shown below. Final time matrix A B C E A – B – C – – E – (c) (i) Use the nearest neighbour algorithm, starting at A, to find a Hamiltonian cycle in the complete network of shortest times. (ii) Find the time taken for this cycle. (iii) Interpret the cycle in terms of the actual villages visited. (3)
Oct 2020 · Paper 3D (Decision 1) · Q6(b) 9 marks
The weights on the arcs in Figure 4 represent distances. The weight on arc EF is x where 12 < x < 26 and the weight on arc DG is y where 0 < y < 10 An inspection route of minimum length that traverses each arc at least once is found. The inspection route starts and finishes at A and has a length of 409 It is also given that the length of the shortest route from F to G via A is 140 (b) Using appropriate algorithms, find the value of x and the value of y. (9)
June 2019 · AS Paper 2 (Decision 1) · Q4(b) 1 mark
An inspection route starting at A and finishing at H is found. The route traverses each arc at least once and is of minimum length. (b) State the arcs that are traversed twice. (1)
June 2019 · AS Paper 2 (Decision 1) · Q4(c) 1 mark
(c) State the number of times that vertex C appears in the inspection route. (1)
June 2019 · AS Paper 2 (Decision 1) · Q4(d) 1 mark
(d) Determine the length of the inspection route. (1)
June 2019 · Paper 3D (Decision 1) · Q2(b) 4 marks
On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G. (b) Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear. (4)
June 2019 · Paper 3D (Decision 1) · Q2(c) 1 mark
(c) Find the length of Naasir’s route. (1)
June 2019 · Paper 3D (Decision 1) · Q2(d) 3 marks
On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B. (d) (i) Determine the possible starting and finishing points so that the length of Naasir’s route is minimised. You must give reasons for your answer. (ii) Find the length of Naasir’s new route. (3)
June 2019 · Paper 3D (Decision 1) · Q3(d) 4 marks
Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table. (d) (i) State the cycle obtained using the nearest neighbour algorithm. (ii) State the length of this cycle. (iii) Interpret the cycle in terms of the actual villages visited. (iv) Prove that Mabintou’s cycle is not optimal. (4)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.