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)

Scheme	Marks

RMST weight = 85 + 35 + 83 + 80 = 283 (seconds)	M1 A1
Lower bound = 283 + 75 + 88 = 446 (seconds)	A1
	(3)

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