Multiple Nearest Neighbour Routes

6 The network represents a railway system. The vertices represent the stations and the arcs represent the tracks. The weights on the arcs represent journey times between stations, in minutes. The sum of all the weights is 105 minutes. \includegraphics[max width=\textwidth, alt={}, center]{8f17020a-14bf-4459-9241-1807b954a629-5_981_1215_468_477} Norah wants to travel around the system visiting every station. She wants to start and end at \(A\) and she wants to complete her journey in the shortest possible time.

1. Apply the nearest neighbour method starting at \(A\) to find two suitable tours and calculate the journey time for each of these tours. Which of these answers gives the better upper bound for Norah's journey time?
2. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting vertex \(G\) and all the arcs that are directly joined to \(G\). Draw a diagram to show the arcs in your tree. Hence calculate a lower bound for Norah's journey time. Norah now decides that she wants to use every section of track in her journey. She still wants to start and end at \(A\) and to complete her journey in the shortest possible time.
3. Calculate the journey time for Norah's new problem. Show your working; quickest times between stations may be found by inspection. State which arcs Norah will have to travel twice and how many times she will pass through station \(D\).

1. The table below shows the least costs, in pounds, of travelling between six cities, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
   (2)
2. Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
   (1)
3. Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
4. State the best upper bound from your answers to (b) and (c).
5. Starting by deleting A , and all of its arcs, find a lower bound for the route length.

1. 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.

1. Use Prim's algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.
2. Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie's route.
3. Show that there are two nearest neighbour routes which start from A . State these routes and their lengths.
4. State the better upper bound from your answers to (b) and (c).
5. Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie's route.
6. Consider your answers to (d) and (e) and hence state an optimal route.

2. 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, \(\mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { 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.

1. Show that there are two nearest neighbour routes that start from A . You must make the routes and their lengths clear.
2. Starting by deleting F , and all of its arcs, find a lower bound for the time taken for the robot's route.
3. Use your results to write down the smallest interval which you are confident contains the optimal time for the robot's route.

1. (a) Explain the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.

The table above shows the least direct distances, in miles, between seven towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { 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.
(c) Starting by deleting A, and all of its arcs, find a lower bound for the length of Yiyi's route.
(d) Use your results to write down the smallest interval which you can be confident contains the optimal length of Yiyi's route.