Travelling Salesman

Topic

Edexcel

Edexcel · Old spec

A2 June 2025 Q3

EdexcelCurrent spec10 marksShortest Path Travelling Salesman

Figure 1: network on villages A to G with arcs AG 11, GF 12, GE 24 (one-way from G to E), GC 47, AE 35, AB 9 (one-way from A to B), AD 25 (one-way from A to D), BF 35, BD 8, BC 40, CD 17, FE 14, FD 31, ED 11 — Figure 1

Direct roads between seven villages, A, B, C, D, E, F and G, are represented in Figure 1. The weight on each arc is the time, in minutes, taken to travel along the corresponding road. Three roads, AB, AD and GE, are one-way, as indicated by the arrow on the corresponding arc.

Floyd’s algorithm is to be used to find the complete network of shortest times between the seven villages.

(a) Set up an initial time matrix for this network. (2)

The time matrix after three iterations of Floyd’s algorithm is shown below.

	A	B	C	D	E	F	G
A	–	9	49	17	35	44	11
B	∞	–	40	8	∞	35	87
C	∞	40	–	17	∞	75	47
D	∞	8	17	–	11	31	64
E	35	44	84	11	–	14	46
F	∞	35	75	31	14	–	12
G	11	20	47	28	24	12	–

(b) Perform the next two iterations of Floyd’s algorithm that follow from the table above.
You should show only the time matrix after each iteration. (5)

The final time matrix after completion of Floyd’s algorithm is shown below.

	A	B	C	D	E	F	G
A	–	9	34	17	28	23	11
B	54	–	25	8	19	33	45
C	58	25	–	17	28	42	47
D	46	8	17	–	11	25	37
E	35	19	28	11	–	14	26
F	23	32	42	25	14	–	12
G	11	20	45	28	24	12	–

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)

Mark scheme (a)

Scheme

Marks

	A	B	C	D	E	F	G
A	-	9	∞	25	35	∞	11
B	∞	-	40	8	∞	35	∞
C	∞	40	-	17	∞	∞	47
D	∞	8	17	-	11	31	∞
E	35	∞	∞	11	-	14	∞
F	∞	35	∞	31	14	-	12
G	11	∞	47	∞	24	12	-

B2, 1, 0

1.1b
1.1b

(2)

Notes

a1B1: At least three rows and three columns correct (condone at most 2 empty cells but accept consistent blanks for the leading diagonal)

a2B1: CAO

Mark scheme (c)

Scheme	Marks	AO
(i) NNA starting at B: B – D – E – F – G – A – C – B	B1	2.2a
(ii) Time taken: 8 + 11 + 14 + 12 + 11 + 34 + 25 = 115 (minutes)	B1	1.1b
(iii) Actual villages visited: BDEFGA\(\underline{\text{BD}}\)C\(\underline{\text{D}}\)B	B1	2.2a
	(3)
	(10 marks)

Notes

ci1B1: CAO (Nearest neighbour cycle starting at B – must include return to B) (condone the use of arcs BD DE EF FG GA AC CB – must be written in this manner and not AG or BC)

cii2B1: Correct time

ciii3B1: Correct route – must be stated as nodes

A2 June 2024 Q2

EdexcelCurrent spec13 marksMinimum Spanning Trees Travelling Salesman

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

	A	B	C	D	E	F	G	H	J
A	–	50	59	26	50	40	87	63	59
B	50	–	28	61	79	63	45	64	48
C	59	28	–	33	57	35	70	36	45
D	26	61	33	–	24	64	71	37	33
E	50	79	57	24	–	40	64	30	31
F	40	63	35	64	40	–	47	70	71
G	87	45	70	71	64	47	–	34	67
H	63	64	36	37	30	70	34	–	33
J	59	48	45	33	31	71	67	33	–

(a) Use Prim’s algorithm, starting at D, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree. (3)

(b) State the weight of the minimum spanning tree found in part (a). (1)

Diagram 1: the nine vertices A, B, C, D, E, F, G, H and J with no arcs — Diagram 1

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)

(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)

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)

(g) By deleting A and all of its arcs, find a lower bound for the length of the historian’s route. (2)

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)

Mark scheme (a)

Scheme	Marks	AO
Prim’s starting at D: DE, AD, EH; EJ, CD, BC; GH, CF	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: First three arcs correctly chosen in order {DE, AD, EH, …} or first four nodes correctly chosen in order{D, E, A, H,…}. If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of the matrix {3, -, -, 1, 2, -, -, 4, -} so please check the top of the matrix carefully. If they start at any other vertex M1 only for the first three arcs in order (Starting at A AD DE EH).

A1: First six arcs correctly chosen in order {DE, AD, EH, EJ, CD, BC, …} or all nine nodes correctly chosen in order{D, E, A, H, J, C, B, G, F}. Order of nodes may be seen at the top of the matrix so for the first two marks accept {3, 7, 6, 1, 2, 9, 8, 4, 5} (do not condone any missing numbers e.g. the number 9 must be above F)

A1: CSO – all arcs correctly stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Scheme	Marks	AO
Weight of MST is 241 (miles)	B1	1.1b
	(1)

Scheme	Marks	AO
	B1	1.1b
	(1)

Scheme	Marks	AO
482 (miles)	B1ft	1.1b
	(1)

Mark scheme (e)

Scheme	Marks	AO
NNA starting at D: D – E – H – J – C – B – G – F – A – D 24 + 30 + 33 + 45 + 28 + 45 + 47 + 40 + 26 = 318 (miles)	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: Nearest neighbour route starting at D – must have at least D – E – H – J – C – B – … allow if stated in terms of arcs (DE EH HJ JC CB) but not for just numbering across the matrix

A1: CAO route (must return to D and can be stated as arcs DE EH HJ JC CB BG GF FA AD)

A1: CAO length (318)

Mark scheme (f)

Scheme	Marks	AO
The best upper bound is the one found in (e) as 318 is less than both 352 and 482	dB1ft	2.2a
	(1)

Notes

dB1ft: Follow through their value from (e) (must include reason e.g. 318 is the lowest of the values found, but they do not need to mention the other values) Must score at least M1 in (e)

Mark scheme (g)

Scheme	Marks	AO
(241 – 26) + 26 + 40 = 281 (miles)	M1 A1	3.1b 2.2a
	(2)

Notes

M1: (weight of their MST from (b) or 241 only) – 26 + 26(AD) + 40(AF) (oe so may not see the – 26 + 26). A correct answer of 281 can imply this (and the next) mark. Alternatively may delete A and find RMST (215) and add AD (26) and AF (40)

A1: 281

Mark scheme (h)

Scheme	Marks	AO
The best lower bound is the one found in (g) as 281 is greater than 274	dB1ft	2.2a
	(1)
	(13 marks)

Notes

dB1ft: Follow through their “281” with 274 and makes conclusion (e.g. 281 is the bigger value, but they do not need to mention 274). Must be a smaller value than their answer to (f) and must score at least M1 in (g)

A2 June 2023 Q5

EdexcelCurrent spec13 marksMinimum Spanning Trees Route Inspection Travelling Salesman

Figure 5: network on A to J with arcs AB 34, AG 8, AF 20, AD 42, BE 50, BH 21, BC 17, GD 23, GF 48, FD 22, FE 65, CE 33, CJ 10, HJ 12, EJ 18 — 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	D	E	F	G	H	J
A	–	34	51	31	79	20	8	55	61
B	34	–	17	65	45	54	42	21	27
C	51	17	–	82	28	71	59	22	10
D	31	65	82	–	87	22	23	86	92
E	79	45	28	87	–	65	87	30	18
F	20	54	71	22	65	–	28	75	81
G	8	42	59	23	87	28	–	63	69
H	55	21	22	86	30	75	63	–	12
J	61	27	10	92	18	81	69	12	–

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)

(b) Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. (3)

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)

(d) By deleting G and all of its arcs, find a lower bound for the length of Pete’s route. (2)

Pete decides to take the route he found in (c).

(e) Interpret the route in terms of the actual towns visited. (1)

Mark scheme (a)

Scheme	Marks	AO
(i) Route must start at F and finish at J therefore need to consider pairings of the nodes F, C, D and G	M1	3.1b
CD + FG = 82 + 28 = 110 CF + DG = 71 + 23 = 94 CG + DF = 59 + 22 = 81	A1 A1	1.1b 1.1b
Repeated roads: CB, BA, AG, and DF	A1	2.2a
(ii) Length of route = 423 + 81 = 504 (miles)	A1ft	2.2a
	(5)

Notes

M1: The correct three pairings of the correct four nodes (F, C, D and G)

A1: Two rows correct including pairings and totals

A1: All three rows correct including pairings and totals

A1: CAO (CB, BA, AG, DF only but in any order) – must be stated as edges so A0 for any of CG or CBAG or CG via B and A

A1ft: 423 + weight of their shortest pairing

Mark scheme (b)

Scheme	Marks	AO
Prim’s starting at A: AG, AF, DF, AB, BC, CJ, HJ, EJ	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: First three arcs correctly chosen in order {AG, AF, DF, …} or first four nodes correctly chosen in order{A, G, F, D,…}. If any explicit rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of one of the tables{1, -, -, 4, -, 3, 2, -, -} so please check the top of the tables carefully

A1: First five arcs correctly chosen in order {AG, AF, DF, AB, BC, …} or all nine nodes correctly chosen in order{A, G, F, D, B, C, J, H, E}. Order of nodes may be seen at the top of one of the tables so for the first two marks accept {1, 5, 6, 4, 9, 3, 2, 8, 7} (do not condone any missing numbers e.g. the number 9 must be above E)

A1: CSO – all arcs correct stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of one of the tables unless the correct list of arcs (in the correct order) is also seen)

Mark scheme (c)

Scheme	Marks	AO
NNA starting at G: G – A – F – D – B – C – J – H – E – G 8 + 20 + 22 + 65 + 17 + 10 + 12 + 30 + 87 = 271	M1 A1	1.1b 1.1b
	(2)

Notes

M1: Nearest neighbour route starting at G – must have at least G – A – F – D – B – C – … allow if stated in terms of arcs

A1: CAO on length (271) and route (must return to G and can be stated in terms of arcs)

Mark scheme (d)

Scheme	Marks	AO
(141 – 8) + 8 + 23 = 164 (miles)	M1 A1	3.1b 2.2a
	(2)

Notes

M1: For one of the following

RMST arcs: AF, DF, AB, BC, CJ, HJ, EJ (stated in any order) – condone AG added too but must be removed at some later stage (e.g. subtracting 8 at some point)
RMST weight calculation: 20 + 22 + 34 + 17 + 10 + 12 + 18 (not just 20, 22, etc.)
RMST weight stated: 133 or 141 – 8
Lower bound stated: 164

A1: CAO (164)

Scheme	Marks	AO
GAFD GA BCJH J E JCBA G	B1	3.2a
	(1)
	(13 marks)

A2 June 2022 Q3

EdexcelCurrent spec10 marksShortest Path Travelling Salesman

3. The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one-way only.

	A	B	C	D	E	F
A	–	12	32	24	29	11
B	12	–	17	8	∞	∞
C	32	17	–	4	12	∞
D	24	∞	4	–	∞	13
E	∞	∞	12	18	–	12
F	11	∞	∞	13	12	–

Table 1

(a) By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book. (2)

Diagram 1: vertices A to F with arcs BC 17, BD 8 (one-way from B to D), CD 4, CE 12, ED 18 (one-way from E to D), EF 12, DF 13; vertex A has no arcs — Diagram 1

Floyd’s algorithm is to be used to find the complete network of shortest distances between the six classrooms.

The distance matrix after two iterations of Floyd’s algorithm is shown in Table 2.

	A	B	C	D	E	F
A	–	12	29	20	29	11
B	12	–	17	8	41	23
C	29	17	–	4	12	40
D	24	36	4	–	53	13
E	∞	∞	12	18	–	12
F	11	23	40	13	12	–

Table 2

(b) Perform the next two iterations of Floyd’s algorithm that follow from Table 2. You should show the distance matrix after each iteration. (4)

The final distance matrix after completion of Floyd’s algorithm is shown in Table 3.

	A	B	C	D	E	F
A	–	12	24	20	23	11
B	12	–	12	8	24	21
C	28	17	–	4	12	17
D	24	21	4	–	16	13
E	23	29	12	16	–	12
F	11	23	17	13	12	–

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)

Scheme	Marks	AO
	M1 A1	1.1b 1.1b
	(2)

Mark scheme (c)

Scheme

Marks

Nearest neighbour routes:

E – C – D – F – A – B – E	Length = 76
E – F – A – B – D – C – E	Length = 59

The cycle that begins E – F –… is the better upper bound as the value is the smaller of the two

M1
A1
A1
A1

3.4
1.1b
1.1b
2.4

(4)

(10 marks)

Notes

(c) M1: Either cycle correct (must include returning to E) – nodes must be in the correct order and therefore not reversed but allow if stated in terms of arcs. If only one cycle correct then M1 only

A1: Both cycles correct – nodes must be in the correct order but allow if stated in terms of arcs

A1: Both cycles and corresponding lengths correct

A1: Correct reasoning that the smallest (oe) value is the better upper bound – dependent on all previous marks in this part (cso)

A2 October 2021 Q3

EdexcelCurrent spec8 marksMinimum Spanning Trees Travelling Salesman

	A	B	C	D	E	F	G	H
A	–	24	42	48	34	37	32	22
B	24	–	40	35	30	41	39	44
C	42	40	–	21	26	45	38	36
D	48	35	21	–	32	37	29	27
E	34	30	26	32	–	34	40	28
F	37	41	45	37	34	–	43	41
G	32	39	38	29	40	43	–	38
H	22	44	36	27	28	41	38	–

Table 1

Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H.

(a) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree. (3)

(b) State the weight of the minimum spanning tree. (1)

	A	B	C	D	E	F	G	H
J	31	27	50	29	43	25	49	35

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)

(d) Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav’s route. (2)

Mark scheme (a)

Scheme	Marks	AO
Prim’s starting at A: AH, AB, DH; CD, CE; DG, EF	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

(a) M1: First three arcs correctly chosen in order {AH, AB, DH, …} or first four nodes correctly chosen in order {A, H, B, D,…}. If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of the matrix {1, 3, -, 4, -, -, -, 2} so please check the top of the matrix carefully

A1: First five arcs correctly chosen in order {AH, AB, DH, CD, CE, …} or all eight nodes correctly chosen in order {A, H, B, D, C, E, G, F}. Order of nodes may be seen at the top of the matrix so for the first two marks accept {1, 3, 5, 4, 6, 8, 7, 2} (do not condone any missing numbers e.g. the number 8 must be above F)

A1: cso – all arcs correct stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Scheme	Marks	AO
Weight of MST is 183 (miles)	B1	2.2a
	(1)

Mark scheme (c)

Scheme	Marks	AO
NNA: J – F – E – C – D – H – A – B – G – J	B1	1.1b
Upper bound is 267 (miles)	B1	2.2a
	(2)

Notes

(c) B1: cao (for route – must return to J)

B1: cao (for upper bound of 267)

Scheme	Marks	AO
183 + 27 + 25 =…	M1	3.1b
… = 235 (miles)	A1	2.2a
	(2)
	(8 marks)

A2 October 2020 Q3

EdexcelCurrent spec9 marksShortest Path Travelling Salesman

Figure 2: network on A, B, C, D and E with arcs AB 8, AC 4, AD 7, BC 3, BE 10, CE 6, DE 1 and DC 1 (one-way from D to C) — Figure 2

Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc.

Floyd’s algorithm is to be used to find the complete network of shortest times between the five villages.

(a) Set up initial time and route matrices. (2)

The matrices after two iterations of Floyd’s algorithm are shown below.

Time matrix

	A	B	C	D	E
A	–	8	4	7	18
B	8	–	3	15	10
C	4	3	–	11	6
D	7	15	1	–	1
E	18	10	6	1	–

Route matrix

	A	B	C	D	E
A	A	B	C	D	B
B	A	B	C	A	E
C	A	B	C	A	E
D	A	A	C	D	E
E	B	B	C	D	E

(b) Perform the next two iterations of Floyd’s algorithm that follow from the tables above. You should show the time and route matrices after each iteration. (4)

The final time matrix after completion of Floyd’s algorithm is shown below.

Final time matrix

	A	B	C	D	E
A	–	7	4	7	8
B	7	–	3	10	9
C	4	3	–	7	6
D	5	4	1	–	1
E	6	5	2	1	–

(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)

Mark scheme (c)

Scheme	Marks	AO
(i) NNA: A – C – B – E – D – A	B1	1.1b
(ii) 4 + 3 + 9 + 1 + 5 = 22 minutes	dB1	1.1b
(iii) A – C – B – C – E – D – C – A	B1	3.2a
	(3)
	(9 marks)

Notes

(c)(i) B1: CAO

(c)(ii) dB1: CAO – not from A – C – D – E – B – A

(c)(iii) B1: CAO

A2 June 2019 Q3

EdexcelCurrent spec14 marksShortest Path Travelling Salesman

Figure 2: network on A, B, C, D and E with arcs AB 15, AC 7, AD 18, AE 3 (one-way from A to E), CB 5 (one-way from C to B), CD 4, CE 9, DE 3 — Figure 2

The network in Figure 2 shows the direct roads linking five villages, A, B, C, D and E. The number on each arc represents the length, in miles, of the corresponding road. The roads from A to E and from C to B are one-way, as indicated by the arrows.

(a) Complete the initial distance and route tables for the network provided in the answer book. (2)

Initial distance table (answer book)

	A	B	C	D	E
A
B
C
D
E

Initial route table (answer book)

	A	B	C	D	E
A
B
C
D
E

(b) Perform the first three iterations of Floyd’s algorithm. You should show the distance table and the route table after each of the three iterations. (5)

After five iterations of Floyd’s algorithm the final distance table and partially completed final route table are shown below.

Distance table

	A	B	C	D	E
A	–	12	7	6	3
B	15	–	22	21	18
C	7	5	–	4	7
D	11	9	4	–	3
E	14	12	7	3	–

Route table

	A	B	C	D	E
A	A
B	A	B
C	A	B	C
D	C	C	C	D
E	D	D	D	D	E

(c)

(i) Explain how the partially completed final route table can be used to find the shortest route from E to A.

(ii) State this route. (3)

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)

Mark scheme (c)

Scheme	Marks	AO
(i) Start at E(5^th row) and read across to the A (1^st column), there is a D there so the route from E to A is via D	B1	2.4
Now consider both E to D and D to A – for E reading across to the D (4^th column), there is a D indicating that the shortest path from E to D is ED. For D reading across to the A (1^st column), there is a C indicating that the shortest path from D to A is via C	dB1	2.4
(ii) EDCA	B1	2.2a
	(3)

Notes

(c) B1: Row E column A is D so the route is E to A via D (or implies that the order of the nodes in the route is EDA) or D implied from general argument or Row E column A is D therefore the route begins ED (in all cases must clearly imply row E and column A)

dB1: Row D column A is C therefore the route goes via C (before A) or complete general argument that allows the route from D to A to be found or allow those who say that row D column A is C so the route is EDC and then row C column A is A

B1: CAO (EDCA)

Mark scheme (d)

Scheme	Marks	AO
(i) NNA: D – E – C – B – A – D	B1	1.1b
(ii) 3 + 7 + 5 + 15 + 6 = 36 miles	B1	1.1b
(iii) D – E – D – C – B – A – E – D	B1	3.2a
(iv) e.g. the cycle A – E – D – C – B – A has a length of 30 miles \(\lt\) 36 miles so Mabintou’s route is not optimal	B1	2.4
	(4)
	(14 marks)

Notes

(d)(i) B1: CAO (D – E – C – B – A – D)

(ii) B1: CAO (36 – no units required)

(iii) B1: CAO (D – E – D – C – B – A – E – D) or mentions that the cycle would visit E twice and D three times (or visit D before the end of the cycle – if D visited once stated and it is not clear that this isn’t the start or finish then B0) or mention of E to C via D and A to D via E

(iv) B1: A correct cycle stated (e.g. a cyclic permutation of A – E – D – C – B – A) with corresponding correct length – dependent on second B mark in this part (so must have had 36 in (d)(ii))

D2 June 2019 Q1

EdexcelOld spec5 marksTravelling Salesman

	A	B	C	D	E	F
A	–	53	47	39	35	40
B	53	–	32	46	41	43
C	47	32	–	51	47	37
D	39	46	51	–	36	49
E	35	41	47	36	–	42
F	40	43	37	49	42	–

The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Jas needs to visit each town, starting and finishing at D, and wishes to minimise the total distance she travels.

(a) Starting at D, use the nearest neighbour algorithm to obtain an upper bound for the length of the route. You must state your route and its length. (2)

(b) Starting by deleting D, and all of its arcs, find a lower bound for the route length. (3)

Mark scheme (a)

Scheme	Marks
NNA: D – E – A – F – C – B – D	M1
36 + 35 + 40 + 37 + 32 + 46 = 226 (km)	A1
	(2)

Notes

a1M1: Nearest neighbour starting at D – must get to at least D – E – A – F – C – Or correct length stated

a1A1: Both route and length correctly stated (route must return to D) If double 226 A0. Do not isw.

Mark scheme (b)

Scheme	Marks
RMST weight = 144 (km)	B1
144 + 39 + 36 = 219 (km)	M1 A1
	(3)
	5 marks

Notes

b1B1: CAO for RMST weight (either 144 or 35 + 40 + 37 + 32) – maybe implied by later working

b1M1: Adding 39 and 36 (the two least weighted arcs) to their RMST length – this mark maybe implied by the correct value for the lower bound

b1A1: CAO – if 219 seen without working then award all 3 marks in (b)

D2 June 2017 Q1

EdexcelOld spec7 marksTravelling Salesman

	A	B	C	D	E	F
A	–	83	75	82	69	97
B	83	–	94	103	77	109
C	75	94	–	97	120	115
D	82	103	97	–	105	125
E	69	77	120	105	–	88
F	97	109	115	125	88	–

The table above shows the least distances, in km, between six towns, A, B, C, D, E and F.

(a) Starting at A, and making your working clear, find an initial upper bound for the travelling salesperson problem for this network, using

(i) the minimum spanning tree method,

(ii) the nearest neighbour algorithm.

(5)

By deleting A, and all of its arcs, a lower bound for the travelling salesperson problem for this network is found to be 500 km.

By deleting B, and all of its arcs, the corresponding lower bound is found to be 474 km.

(b) Using the results from (a) and the given lower bounds, write down the smallest interval that you can be confident contains the solution to the travelling salesperson problem for this network. (2)

Mark scheme (a)

Scheme	Marks
(i) Prim’s starting from A: AE, AC, BE, AD; EF	M1 A1
\(2 \times 391 = 782\)	B1
(ii) Nearest neighbour: A – E – B – C – D – F – A	M1
69 77 94 97 125 97 = 559	A1
	(5)

Notes

a1M1: First four arcs (or first five nodes: A, E, C, B, D or equivalent numbers across the top of the table {1, 4, 3, 5, 2, -}) selected correctly. Award M1 only for a correct tree with no working or for a correct tree starting at a different node

a1A1: CAO (order of arcs correct or all six nodes correct: A, E, C, B, D, F – but not just the numbers across the top of the table)

a1B1: CAO (782) – must follow from the correct MST (so dependent on at least the M mark in (a)(i)) – do not isw if attempt at short cuts reduces this value

a2M1: Nearest neighbour A – E – B – C – D – F – (condone lack of return to start) or correct route length of 559. Accept AE, EB, BC, CD, DF but do not accept weights only

a2A1: CAO both route (either in terms of vertices or arcs but not weights) and length correct

Mark scheme (b)

Scheme	Marks
\(500 \leqslant \text{length} \leqslant 559\) (accept \(500 \lt \text{length} \leqslant 559\))	B2, 1, 0
	(2)
	7 marks

Notes

b1B1: Any indication of an interval from 500 to their 559 (their 559 > 500 and is the smallest value from either the MST method or NN method – must have stated two values in (a) but ignore how these values were derived)

b2B1: \(500 \leqslant \text{length} \leqslant 559\) or \(500 \lt \text{length} \leqslant 559\) (no ft on this mark) – accept set notation e.g. [500,559] or (500, 559]

D2 June 2016 Q1

EdexcelOld spec10 marksTravelling Salesman

(a) Explain the difference between the classical travelling salesperson problem and the practical travelling salesperson problem. (2)

	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	–

The table above shows the least direct distances, in miles, between seven towns, A, B, C, D, E, 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. (3)

(d) Use your results to write down the smallest interval which you can be confident contains the optimal length of Yiyi’s route. (2)

Mark scheme (a)

Scheme	Marks
e.g. in the practical problem each vertex must be visited at least once. In the classical problem each vertex must be visited just once	B2, 1, 0
	(2)

Notes

a1B1: Understands the difference is connected to the number of times each vertex may be visited (but maybe incorrectly attributed). Must be an attempt at a difference (so must refer to both the classical and practical problems explicitly). Technical language (vertex/node) must be correct. Need not imply each/every/all (oe) vertices for this first mark

a2B1: Correctly identifies which is classical and which is practical and correctly states the difference. Must imply that each/every/all (oe) vertices are visited, so for example, ‘the practical problem visits a vertex at least once while the classical visits a vertex only once’ is B1B0 (note that B0B1 is not possible in (a))

Mark scheme (b)

Scheme	Marks
A – D – C – F – B – E – G – A 12+16+19+25+14+41+22 = 149	M1 A1
A – D – C – F – G – E – B – A 12+16+19+25+41+14+31 = 158	A1
	(3)

Notes

b1M1: Either one correct route, must return to A, or one correct length stated (do not isw in part (b) if correct lengths seen but are then doubled)

b1A1: One correct route, must return to A and corresponding length correct

b2A1: Both routes correct and their corresponding lengths correct

Mark scheme (c)

Scheme	Marks
RMST weight = 86 (miles)	B1
86 + 12 + 15 = 113 (miles)	M1 A1
	(3)

Notes

c1B1: CAO for RMST weight (either 86 or 20 + 16 + 14 + 19 + 17) – maybe implied by later working

c1M1: Adding 12 + 15 (the two least weighted arcs) to their RMST length (the length of their RMST must be in the interval \(66 \leqslant \text{RMST} \leqslant 106\)) – this mark maybe implied by the correct value for the lower bound

c1A1: CAO - if 113 seen without working then award all 3 marks in (c)

Mark scheme (d)

Scheme	Marks
113 \(\leqslant\) optimal distance \(\leqslant\) 149	B2, 1, 0
	(2)
	10 marks

Notes

d1B1: Their numbers correctly used, accept any inequalities or any indication of interval from their 113 to their 149 (so 113 – 149 can score this mark). This mark is dependent on two totals seen in (b), however, neither of the two totals need to be correct. Please note that UB > LB for this mark

d2B1: CAO (no follow through on their values) including correct inequalities or equivalent set notation (but condone \(113 \lt \text{optimal distance} \leqslant 149\))

D2 June 2015 Q3

EdexcelOld spec12 marksTravelling Salesman

	A	B	C	D	E	F	G
A	–	\(x\)	41	43	38	21	30
B	\(x\)	–	27	38	19	29	51
C	41	27	–	24	37	35	40
D	43	38	24	–	44	52	25
E	38	19	37	44	–	20	28
F	21	29	35	52	20	–	49
G	30	51	40	25	28	49	–

The network represented by the table shows the least distances, in km, between seven theatres, A, B, C, D, E, F and G.

Jasmine needs to visit each theatre at least once starting and finishing at A. She wishes to minimise the total distance she travels. The least distance between A and B, is \(x\) km, where \(21 \lt x \lt 27\)

(a) Using Prim’s algorithm, starting at A, obtain a minimum spanning tree for the network.
You should list the arcs in the order in which you consider them. (2)

(b) Use your answer to (a) to determine an initial upper bound for the length of Jasmine’s route. (1)

The nearest neighbour algorithm starting at F gives a route of F – E – B – A – G – D – C – F.

(d) State which of these two nearest neighbour routes gives the better upper bound. Give a reason for your answer. (2)

Starting by deleting A, and all of its arcs, a lower bound of 159 km for the length of the route is found.

(e) Find \(x\), making your method clear. (3)

(f) Write down the smallest interval that you can be confident contains the optimal length of Jasmine’s route. Give your answer as an inequality. (2)

Mark scheme (a)

Scheme	Marks
Prim: AF, EF, BE, BC, CD, DG	M1 A1
	(2)

Notes

a1M1: Must be using Prim’s algorithm not NNA – if any arc creates a cycle then M0. First four arcs (or all 7 nodes / or numbers across the top of the matrix) selected correctly. Award M1 only for a correct tree with no working. Award M1 only for the first four arcs (oe) selected correctly if starting at a different node than A

a1A1: CAO (order of arc selection clear)

Mark scheme (c)

Scheme	Marks
A F E B C D G A	B1
21 20 19 27 24 25 30 = 166 (km)	B1
	(2)

Notes

c1B1: CAO – must be either in terms of nodes or arcs (not weights)

c2B1: CAO (166)

Mark scheme (d)

Scheme	Marks
Starting at F route length is \(153 + x\)	B1
With \(x \gt 21\), \(153 + x\) is greater than 166 so the better upper bound is the one starting at A	DB1
	(2)

Notes

d1B1: Either \(153 + x\) or states a value in the interval 174 < value < 180 or considers one of the intervals 174 < value < 180 or 175 \(\leqslant\) value \(\leqslant\) 179

d2DB1: Correct argument that A gives the better upper bound. Must be considering either \(x \gt 21\) or \(x \geqslant 22\) with 153 (so expect to see as a minimum the mention of > 174 or \(\geqslant\) 175) – must be clear that the upper bound starting at A is the better upper bound. This mark is dependent on the previous B mark in (d)

Mark scheme (e)

Scheme	Marks
Length of RMST = 115	B1
\(115 + 21 + x = 159 \therefore x = 23\) (km)	M1 A1
	(3)

Notes

e1B1: CAO (length of RMST) – the length (115 or 19 + 20 + 27 + 24 + 25) must be either explicitly stated or seen in their working (not just implied by their working)

e1M1: Adding the correct two least values (21 and \(x\)) to their RMST length (their RMST may be incorrect but must contain only 5 arcs) and equating to 159. Accept, for example, \(136 + x = 159\) or \(136 + 23 = 159\) or \(115 + 21 + 23 = 159\) or equivalent calculations using the length of their RMST

e1A1: CAO (must be clear that (\(x\) =) 23 not just embedded in a calculation)

Mark scheme (f)

Scheme	Marks
159 \(\leqslant\) optimal \(\leqslant\) 166 [accept 159 < optimal \(\leqslant\) 166]	B2,1,0
	(2)
	12 marks

Notes

f1B1: Any indication of an interval containing 159 (as a lower bound) and their stated better upper bound from (d)

f2B1: CAO either 159 \(\leqslant\) optimal (oe) \(\leqslant\) 166 or 159 < optimal (oe) \(\leqslant\) 166

D2 June 2014 (R) Q2

EdexcelOld spec10 marksTravelling Salesman

(a) Explain the difference between the classical and the practical travelling salesperson problem. (2)

	A	B	C	D	E	F
A	–	65	48	15	30	40
B	65	–	50	51	35	26
C	48	50	–	37	20	34
D	15	51	37	–	17	25
E	30	35	20	17	–	14
F	40	26	34	25	14	–

The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Keith needs to visit each town, starting and finishing at A, and wishes to minimise the total distance he will travel.

(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. You must state your route and its length. (3)

(d) Use your results to write down the smallest interval which you are confident contains the optimal length of the route. (2)

Mark scheme (a)

Scheme	Marks
In the practical problem each vertex must be visited at least once. In the classical problem each vertex must be visited just once.	B2, 1, 0
	(2)

Notes

a1B1: Understands the difference is connected to the number of times each vertex may be visited.

a2DB1: Correctly identifies which is classical and which is practical and correctly states the difference.

Mark scheme (b)

Scheme	Marks
A D E F B C A 15 + 17 + 14 + 26 + 50 + 48 = 170	M1 A1 A1
	(3)

Notes

b1M1: Nearest neighbour A – D – E – F – B – C – or accept 145623 across top of table (condone lack of return to start).

b1A1: Route correctly stated, must return to A, accept link back to A.

b2A1: Length correctly stated. Do not ISW if candidates then go on to double the route length.

Residual minimum spanning tree B–F 26, F–E 14, E–D 17, E–C 20 — Mark scheme (c)

Mark scheme (d)

Scheme	Marks
122 \(\leqslant\) length \(\leqslant\) 170	B2,1,0
	(2)
	10 marks

Notes

d1B1ft: Their correct numbers correctly used (their upper bound must be a cycle and their lower bound must have scored M1 in (c)), accept any inequalities or any indication of interval from their 122 to their 170.

d2B2: CAO including correct inequalities (but condone 122 < length \(\leqslant\) 170).

D2 June 2014 Q2

EdexcelOld spec10 marksTravelling Salesman

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, B, C, D, 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.

	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	–

(a) Show that there are two nearest neighbour routes that start from A. You must make the routes and their lengths clear. (4)

(b) Starting by deleting F, and all of its arcs, find a lower bound for the time taken for the robot’s route. (3)

(c) Use your results to write down the smallest interval which you are confident contains the optimal time for the robot’s route. (3)

Mark scheme (a)

Scheme	Marks
A E F B C D A and A E F D B C A 35+75+88+80+108+85 = 471 35+75+88+100+80+130 = 508	M1 A1 A1 A1
	(4)

Notes

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).

Residual minimum spanning tree D–A–E–B–C with arcs 85, 35, 83, 80 — Mark scheme (b)

Mark scheme (c)

Scheme	Marks
446 \(\leqslant\) time \(\leqslant\) 471 [accept 446 < time \(\leqslant\) 471]	B3,2,1,0
	(3)
	10 marks

Notes

c1B1ft: their 471 (must be a cycle) as an upper bound – allow recovery in this part.

c2B1ft: any indication of interval from their 446 (must come from six arcs) to their 471.

c3B1: 446 \(\leqslant\) time \(\leqslant\) 471 or 446 < time \(\leqslant\) 471

D2 June 2013 (R) Q2

EdexcelOld spec8 marksTravelling Salesman

2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.

	A	B	C	D	E	F
A	–	122	217	137	109	82
B	122	–	110	130	128	204
C	217	110	–	204	238	135
D	137	130	204	–	98	211
E	109	128	238	98	–	113
F	82	204	135	211	113	–

Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.

(a) Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz’s route. You must state the shortcut(s) you use and the length of your upper bound. (2)

(b) Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Liz’s route. (2)

(d) Use your results to write down the smallest interval which you are confident contains the optimal length of the route. (1)

Mark scheme (a)

Scheme	Marks
E.g. If use CD as shortcut get 807 or if use CF + AD get 793	M1 A1
	(2)

Notes

a1M1: Their plausible shortcut leading to a value < 810 and a length below 810 stated.

a1A1: CAO – shortcut and length must be consistent.

(Examples shortcuts: CD = 807, CF + AD = 793, CF + BD = 664, AD + EF + FC = 715, DF + FC = 785 etc.)

D2 June 2013 Q1

EdexcelOld spec12 marksTravelling Salesman

	A	B	C	D	E
A	–	15	19	25	20
B	15	–	15	15	25
C	19	15	–	22	11
D	25	15	22	–	18
E	20	25	11	18	–

The table shows the least distances, in km, between five hiding places, A, B, C, D and E.

Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A, and wishes to minimise the total distance travelled.

(a) Use Prim’s algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear. (2)

(b) Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie’s route. (1)

(d) State the better upper bound from your answers to (b) and (c). (1)

(e) Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie’s route. (4)

(f) Consider your answers to (d) and (e) and hence state an optimal route. (1)

Minimum spanning tree: AB 15, BC 15, CE 11, BD 15 — Mark scheme (a)

Mark scheme (c)

Scheme	Marks
A B C E D A 15 15 11 18 25 = 84 and A B D E C A 15 15 18 11 19 = 78	M1 A1 A1
	(3)

Notes

c1M1 Nearest Neighbour either A-B-C-E-D- or A-B-D-E-C- (condone lack of return to start). Accept 12354 or 12534 across the top of the matrix.

c1A1 1 route and length CAO (Do not ISW if route length is doubled)

c2A1 both routes and lengths CAO (Do not ISW if route lengths are doubled)

Residual minimum spanning tree AC 19, CE 11, ED 18, with dashed arcs from B: BA 15, BC 15, BD 15 — Mark scheme (e)

Mark scheme (f)

Scheme	Marks
The route is ABDECA (The optimal route length is 78, since upper bound = lower bound)	B1
	(1)
	(12 marks)

Notes

f1B1 CAO, accept any start point for the correct tour, but must return to start. Dependent on their answer to part (d) = their answer to part (e).

D2 June 2012 Q2

EdexcelOld spec7 marksTravelling Salesman

2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.

	A	B	C	D	E	F
A	-	16	25	21	12	15
B	16	-	24	22	21	12
C	25	24	-	18	30	27
D	21	22	18	-	15	12
E	12	21	30	15	-	18
F	15	12	27	12	18	-

Toby must visit each town at least once. He will start and finish at A and wishes to minimise the total distance.

(a) Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of Toby’s route. (3)

(b) Starting by deleting A, and all of its arcs, find a lower bound for the route length. (4)

Mark scheme (a)

Scheme	Marks
A E D F B C A 12 15 12 12 24 25 = 100 km	1M1 1A1 2A1
	(3)

Notes

a1M1 NN Each vertex visited at least once, accept 156324 across top of table (condone lack of return to start).

a1A1 Route CAO must be stated, must return to A, accept link back to A.

a2A1 Length CAO 100. Do not ISW if candidates then go on to double the route length.

Residual minimum spanning tree BF 12, FD 12, DC 18, DE 15, with dashed arcs AF 15 and AE 12 — Mark scheme (b)

D2 June 2011 Q1

EdexcelOld spec10 marksTravelling Salesman

Figure 1: network of six towns. AB 24, AC 11, AD 23, AE 22, BC 8, BE 20, BF 32, CE 9, DE 27, DF 31, EF 17 — Figure 1

The network in Figure 1 shows the distances, in km, between six towns, A, B, C, D, E and F. Mabintou needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.

(a) By inspection, complete the two copies of the table of least distances in your answer book. (3)

(b) Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Mabintou’s route. Write down the route which gives this upper bound. (3)

Mark scheme (a)

Scheme

Marks

	A	B	C	D	E	F
A	-	19	11	23	20	37
B	19	-	8	42	17	32
C	11	8	-	34	9	26
D	23	42	34	-	27	31
E	20	17	9	27	-	17
F	37	32	26	31	17	-

B3, 2, 1, 0

(3)

Notes

The entries to be found are shown in bold.

1B1 One double entry correct

2B1 Two double entries correct

3B1 Three double entries correct

Residual minimum spanning tree CB 8, CE 9, ED 27, EF 17, with dashed arcs AC 11 and AB 19 — Mark scheme (c)

D2 June 2010 Q1

EdexcelOld spec11 marksTravelling Salesman

1. The table below shows the least costs, in pounds, of travelling between six cities, A, B, C, D, E and F.

	A	B	C	D	E	F
A	-	36	18	28	24	22
B	36	-	54	22	20	27
C	18	54	-	42	27	24
D	28	22	42	-	20	30
E	24	20	27	20	-	13
F	22	27	24	30	13	-

Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.

(a) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this network. (2)

(b) Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky’s route. (1)

(c) Show that there are two nearest neighbour routes that start from A. You must make your routes and their lengths clear. (3)

(d) State the best upper bound from your answers to (b) and (c). (1)

(e) Starting by deleting A, and all of its arcs, find a lower bound for the route length. (4)

Mark scheme (c)

Scheme	Marks
A C F E B D A 18 24 13 20 22 28 Length 125	M1 A1
A C F E D B A 18 24 13 20 22 36 Length 133	A1
	(3)

Notes

1M1: One Nearest Neighbour each vertex visited at least once (condone lack of return to start)

1A1: One correct route and length CAO – must return to start.

2A1: Second correct route and length CAO – must return to start.

Residual minimum spanning tree CF 24, FE 13, EB 20, ED 20, with dashed arcs AC 18 and AF 22 — Mark scheme (e)

D2 June 2009 Q2

EdexcelOld spec12 marksTravelling Salesman

2. (a) Explain the difference between the classical and the practical travelling salesperson problems. (2)

The table below shows the distances, in km, between six data collection points, A, B, C, D, E, and F.

	A	B	C	D	E	F
A	-	77	34	56	67	21
B	77	-	58	58	36	74
C	34	58	-	73	70	42
D	56	58	73	-	68	38
E	67	36	70	68	-	71
F	21	74	42	38	71	-

Rachel must visit each collection point. She will start and finish at A and wishes to minimise the total distance travelled.

(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. Make your method clear. (3)

Starting at B, a second upper bound of 293 km was found.

By deleting A, a lower bound was found to be 245 km.

(d) By deleting B, find a second lower bound. Make your method clear. (4)

(e) State the better lower bound of these two, giving a reason for your answer. (1)

(f) Taking your answers to (c) and (e), use inequalities to write down an interval that must contain the length of Rachel’s optimal route. (1)

Mark scheme (a)

Scheme	Marks
In the classical problem each vertex must be visited only once. In the practical problem each vertex must be visited at least once.	B2, 1, 0
	(2)

Notes

1B1: Generous, on the right lines bod gets B1

2B1: cao, clear answer.

Mark scheme (b)

Scheme	Marks
A F D B E C A {1 4 6 3 5 2}	M1 A1
\(21 + 38 + 58 + 36 + 70 + 34 = 257\)	A1
	(3)

Notes

1M1: Nearest Neighbour each vertex visited once (condone lack of return to start)

1A1: Correct route cao – must return to start.

2A1: 257 cao

Residual minimum spanning tree: CA 34, AF 21, FD 38, AE 67 — Mark scheme (d)

D2 June 2008 Q7

EdexcelOld spec16 marksTravelling Salesman

Network of distances in km between weather data collection points A to H

The network in the diagram above shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.

(a) Obtain a minimum spanning tree for the network using Kruskal’s algorithm, stating the order in which you select the arcs. (2)

(b) Use your answer to part (a) to determine an initial upper bound for the length of the route. (1)

(c) Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km. State the corresponding route. (4)

(d) Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route. (3)

(e) By deleting C, and all of its arcs, find a lower bound for the length of the route. (4)

(f) Use your results to write down the smallest interval which you are confident contains the optimal length of the route. (2)

Minimum spanning tree with short cuts HD 111 and AB 102 dashed — Mark scheme (c)

D2 June 2007 Q1

EdexcelOld spec11 marksTravelling Salesman

Network of distances in miles between gift shops A to G

The network above shows the distances, in miles, between seven gift shops, \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\).

The area manager needs to visit each shop. She will start and finish at shop A and wishes to minimise the total distance travelled.

(a) By inspection, complete the two copies of the table of least distances below. (4)

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
\(A\)	–		15	36		53	23
\(B\)		–	17	38	49	80	49
\(C\)	15	17	–	21		62	32
\(D\)	36	38	21	–	11	42
\(E\)		49		11	–	31	61
\(F\)	53	80	62	42	31	–	30
\(G\)	23	49	32		61	30	–

(b) Starting at A, and making your method clear, find an upper bound for the route length, using the nearest neighbour algorithm. (3)

D2 June 2006 Q3

EdexcelOld spec11 marksTravelling Salesman

3. A college wants to offer five full-day activities with a different activity each day from Monday to Friday. The sports hall will only be used for these activities. Each evening the caretaker will prepare the hall by putting away the equipment from the previous activity and setting up the hall for the activity next day. On Friday evening he will put away the equipment used that day and set up the hall for the following Monday.

The 5 activities offered are Badminton (\(B\)), Cricket nets (\(C\)), Dancing (\(D\)), Football coaching (\(F\)) and Tennis (\(T\)). Each will be on the same day from week to week.

The college decides to offer the activities in the order that minimises the total time the caretaker has to spend preparing the hall each week.

The hall is initially set up for Badminton on Monday.

The table below shows the time, in minutes, it will take the caretaker to put away the equipment from one activity and set up the hall for the next.

		To
	Time	\(B\)	\(C\)	\(D\)	\(F\)	\(T\)
From	\(B\)	–	108	150	64	100
	\(C\)	108	–	54	104	60
	\(D\)	150	54	–	150	102
	\(F\)	64	104	150	–	68
	\(T\)	100	60	102	68	–

(a) Explain why this problem is equivalent to the travelling salesman problem. (2)

A possible ordering of activities is

Monday	Tuesday	Wednesday	Thursday	Friday
\(B\)	\(C\)	\(D\)	\(F\)	\(T\)

(b) Find the total time taken by the caretaker each week using this ordering. (2)

(c) Starting with Badminton on Monday, use a suitable algorithm to find an ordering that reduces the total time spent each week to less than 7 hours. (3)

(d) By deleting \(B\), use a suitable algorithm to find a lower bound for the time taken each week. Make your method clear. (4)

Mark scheme (a)

Scheme	Marks
Each activity must be visited once and then we return to the starting activity, this must be done in a minimum time	B2, 1, 0
	(2)

Notes

B2 cao – all 3 bits in the context

B1 cloze ‘Bod’ is B1 (e.g. not in context; just ‘each activity once’ – but not all 3; …)

Mark scheme (c)

Scheme	Marks
Use nearest neighbour B F T C D B	M1 A1
\(64 + 68 + 60 + 54 + 150 = 396\) minutes (6.6 hours)	A1
	(3)

Notes

M1 each vertex visited once – either NN or 2 x mst-shortcut (BD)

A1 cao incl return to B (BFTCDB)

A1 cao (396)

(Corrected from the printed mark scheme: the time in hours is printed as “67 hours”; 396 minutes is 6.6 hours.)

Minimum spanning tree F to T 68, T to C 60, C to D 54 — Mark scheme (d)

D2 January 2006 Q6

EdexcelOld spec13 marksTravelling Salesman

Network of roads between the towns with distances in km

The network in the figure above, shows the distances in km, along the roads between eight towns, A, B, C, D, E, F, G and H. Keith has a shop in each town and needs to visit each one. He wishes to travel a minimum distance and his route should start and finish at A.

By deleting D, a lower bound for the length of the route was found to be 586 km.
By deleting F, a lower bound for the length of the route was found to be 590 km.

(a) By deleting C, find another lower bound for the length of the route. State which is the best lower bound of the three, giving a reason for your answer. (5)

(b) By inspection complete the table of least distances. (4)

	A	B	C	D	E	F	G	H
A	-	84	85	138	173		149	52
B	84	-	130	77	126	213	222	136
C	85	130	-	53	88	83	92
D	138	77	53	-	49			190
E	173	126	88	49	-	100	180	215
F		213	83		100	-	163	115
G	149	222	92		180	163	-	97
H	52	136		190	215	115	97	-

The table can now be taken to represent a complete network.

The nearest neighbour algorithm was used to obtain upper bounds for the length of the route: Starting at D, an upper bound for the length of the route was found to be 838 km.
Starting at F, an upper bound for the length of the route was found to be 707 km.

(c) Starting at C, use the nearest neighbour algorithm to obtain another upper bound for the length of the route. State which is the best upper bound of the three, giving a reason for your answer. (4)

Residual minimum spanning tree with the two least arcs from C dashed — Mark scheme (a)

Mark scheme (c)

Scheme

Marks

C	D	E	F	H	A	B	G	C
	53	49	100	115	52	84	222	92

M1 A1

\(\therefore\) Best upper bound is 707 starting at F

B1ft

(4)

(13 marks)

Notes

(Corrected from the printed mark scheme: the distance EF is printed as 120; it is 100, as in the network and the table.)

The scheme lists four marks for this part but prints only three codes.

D2 June 2005 Q2

EdexcelOld spec11 marksTravelling Salesman

Network of cables between relay stations A to G with distances in km

The network in the diagram shows the distances, in km, of the cables between seven electricity relay stations \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\). An inspector needs to visit each relay station. He wishes to travel a minimum distance, and his route must start and finish at the same station.

By deleting \(C\), a lower bound for the length of the route is found to be 129 km.

(a) Find another lower bound for the length of the route by deleting \(F\). State which is the better lower bound of the two. (5)

(b) By inspection, complete the table of least distances. (2)

The table can now be taken to represent a complete network.

(c) Using the nearest-neighbour algorithm, starting at \(F\), obtain an upper bound to the length of the route. State your route. (4)

Mark scheme (c)

Scheme	Marks
Tour, visits each vertex, order correct using table of least distances.	M1 A1
e.g. \(F\ C\ D\ A\ B\ E\ G\ F\) (actual route \(F\ C\ D\ C\ A\ B\ E\ G\ F\))	A1
upper bound of 138 km	A1
	(4)
	(11 marks)