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