The Travelling Salesman Problem (Edexcel A Level Further Maths: Decision Maths 1)

Explain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.

Write your answer in the Answer Booklet.

	A	B	C	D	E	F	G
A	–	17	24	16	21	18	41
B	17	–	35	25	30	31
C	24	35	–	28	20	35	32
D	16	25	28	–	29	19	45
E	21	30	20	29	–	22	35
F	18	31	35	19	22	–	37
G	41		32	45	35	37	–

The table shows the least distances, in km, by road between seven towns, A, B, C, D, E, F and G. The least distance between B and G is  km, where  > 25

Preety needs to visit each town at least once, starting and finishing at A. She wishes to minimise the total distance she travels.

Starting by deleting B and all of its arcs, find a lower bound for Preety’s route.

Write your answer in the Answer Booklet.

Pretty found the nearest neighbour routes from each of A and C. Given that the sum of the lengths of these routes is 331 km,

find , making your method clear.

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