Travelling salesman problem

The network represented by the table shows the least distances, in km, between seven theatres, A, B, C, D, E, F and G. Jasmine needs to visit each theatre at least once starting and finishing at A. She wishes to minimise the total distance she travels. The least distance between A and B, is x km, where 21 < x < 27

Using Prim’s algorithm, starting at A, obtain a minimum spanning tree for the network. You should list the arcs in the order in which you consider them.

Use your answer to (a) to determine an initial upper bound for the length of Jasmine’s route.

Use the nearest neighbour algorithm, starting at A, to find a second upper bound for the length of the route.

The nearest neighbour algorithm starting at F gives a route of F – E – B – A – G – D – C – F.

State which of these two nearest neighbour routes gives the better upper bound. Give a reason for your answer.

Starting by deleting A, and all of its arcs, a lower bound of 159 km for the length of the route is found.

Find x, making your method clear.

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

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.

Show that there are two nearest neighbour routes that start from A. You must make the routes and their lengths clear.

Starting by deleting F, and all of its arcs, find a lower bound for the time taken for the robot’s route.

Use your results to write down the smallest interval which you are confident contains the optimal time for the robot’s route.

The table shows the least distances, in km, between five hiding places, A, B, C, D and E. Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A, and wishes to minimise the total distance travelled.

Use Prim’s algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.

Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie’s route.

Show that there are two nearest neighbour routes which start from A. State these routes and their lengths.

State the better upper bound from your answers to (b) and (c).

Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie’s route.

Consider your answers to (d) and (e) and hence state an optimal route.

The network in Figure 1 shows the distances, in km, between six towns, A, B, C, D, E and F. Mabintou needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.

By inspection, complete the two copies of the table of least distances in your answer book.

Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Mabintou’s route. Write down the route which gives this upper bound.

Starting by deleting A, and all of its arcs, find a lower bound for the route length.

Explain what is meant, in a network, by

a walk

a tour

The network in figure 2 shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.

Obtain a minimum spanning tree for the network using Kruskal’s algorithm, stating the order in which you select the arcs.

Use your answer to part (a) to determine an initial upper bound for the length of the route.

Starting from your initial upper bound use short cuts to find an upper bound, which is below 630km. State the corresponding route.

Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.

By deleting C, and all of its arcs, find a lower bound for the length of the route.

Use your results to write down the smallest interval which you are confident contains the optimal length of the route.