The Travelling Salesman problemEdexcel A-Level Further Maths: Mind map

Exam questions on The Travelling Salesman problem

1. A salesman must visit each of towns A, B, C, D and E once, starting and finishing at A. The distances in km between the towns are: AB 12, AC 10, AD 14, AE 8, BC 3, BD 7, BE 9, CD 6, CE 11 and DE 12.
   Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the shortest route.2 marks
2. A courier must visit depots A, B, C, D and E and return to the start. The only direct roads and their lengths in km are: AB 6, BC 4, CD 5, DE 3, AE 12, BD 11 and CE 10.
   Find the least distance between B and D, and the least distance between C and E.2 marks
3. A delivery driver must visit five shops A, B, C, D and E, starting and finishing at A, and visiting each shop exactly once. The distances in km between the shops are: AB 15, AC 22, AD 25, AE 18, BC 10, BD 20, BE 12, CD 14, CE 16 and DE 9. These distances satisfy the triangle inequality.
   Find a lower bound for the length of the shortest route by deleting shop A.3 marks