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.

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)

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

2B1: cao, clear answer.

Mark scheme (b)

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

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

2A1: 257 cao

Scheme	Marks
257 is the better upper bound, it is lower.	B1ft
	(1)

Scheme	Marks
Better lower bound is 254, it is higher	B1ft
	(1)