7.04d Travelling salesman lower bound: using minimum spanning tree

7. \includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-3_738_1052_466_516} The network in the diagram above 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.

1. Obtain a minimum spanning tree for the network using Kruskal's algorithm, stating the order in which you select the arcs.
2. Use your answer to part (a) to determine an initial upper bound for the length of the route.
3. Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km . State the corresponding route.
4. Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.
5. By deleting C, and all of its arcs, find a lower bound for the length of the route.
6. Use your results to write down the smallest interval which you are confident contains the optimal length of the route.
   (2) (Total 16 marks)

2.

1. Explain the difference between the classical and the practical travelling salesperson problems. The table below shows the distances, in km, between six data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\), and F .

   	A	B	C	D	E	F
   A	-	77	34	56	67	21
   B	77	-	58	58	36	74
   C	34	58	-	73	70	42
   D	56	58	73	-	68	38
   E	67	36	70	68	-	71
   F	21	74	42	38	71	-

   Rachel must visit each collection point. She will start and finish at A and wishes to minimise the total distance travelled.
2. Starting at A, use the nearest neighbour algorithm to obtain an upper bound. Make your method clear. Starting at B, a second upper bound of 293 km was found.
3. State the better upper bound of these two, giving a reason for your answer. By deleting A, a lower bound was found to be 245 km .
4. By deleting B, find a second lower bound. Make your method clear.
5. State the better lower bound of these two, giving a reason for your answer.
6. Taking your answers to (c) and (e), use inequalities to write down an interval that must contain the length of Rachel's optimal route.
   

2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F. Toby must visit each town at least once. He will start and finish at A and wishes to minimise the total distance.

1. Use the nearest neighbour algorithm, starting at A , to find an upper bound for the length of Toby's route.
2. Starting by deleting A, and all of its arcs, find a lower bound for the route length.

2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F. Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.

1. Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz's route. You must state the shortcut(s) you use and the length of your upper bound.
   (2)
2. Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Liz's route.
3. Starting by deleting F , and all of its arcs, find a lower bound for the length of Liz's route.
4. Use your results to write down the smallest interval which you are confident contains the optimal length of the route.

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.

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

   	A	B	C	D	E	F
   A	-	65	48	15	30	40
   B	65	-	50	51	35	26
   C	48	50	-	37	20	34
   D	15	51	37	-	17	25
   E	30	35	20	17	-	14
   F	40	26	34	25	14	-

   The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Keith needs to visit each town, starting and finishing at A , and wishes to minimise the total distance he will travel.
2. Starting at A, use the nearest neighbour algorithm to obtain an upper bound. You must state your route and its length.
3. Starting by deleting A, and all of its arcs, find a lower bound for the route length.
4. Use your results to write down the smallest interval which you are confident contains the optimal length of the 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.

3. The network represented by the table shows the least distances, in km, between seven theatres, A, \(\mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { 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 \mathrm {~km}\), where \(21 < x < 27\)

1. 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.
2. Use your answer to (a) to determine an initial upper bound for the length of Jasmine's route.
3. 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 \(\mathrm { F } - \mathrm { E } - \mathrm { B } - \mathrm { A } - \mathrm { G } - \mathrm { D } - \mathrm { C } - \mathrm { F }\).
4. 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.
5. Find \(x\), making your method clear.
6. Write down the smallest interval that you can be confident contains the optimal length of Jasmine's route. Give your answer as an inequality.

4. The table shows the least distances, in km, between six towns \(A , B , C , D , E\) and \(F\).

1. Starting at \(A\), and making your method clear, find an upper bound for the travelling salesman problem using the nearest neighbour algorithm.
2. By deleting \(A\), and all of its arcs, find a lower bound for the travelling salesman problem.
3. Write down an inequality about the length of the optimal route.

4. \begin{figure}[h] \end{figure} The network in Figure 2 shows the distances, in km , of the cables between seven electricity relay stations \(A , B , C , D , E , F\) and \(G\). An inspector needs to visit each relay station. He wishes to travel a minimum distance, and his route must start and finish at the same station. By deleting C, a lower bound for the length of the route is found to be 129 km .

1. Find another lower bound for the length of the route by deleting \(F\). State which is the best lower bound of the two.
2. By inspection, complete the table of least distances. The table can now be taken to represent a complete network.
3. Using the nearest-neighbour algorithm, starting at \(F\), obtain an upper bound to the length of the route. State your route.

1. Perform the fourth (final) iteration of the algorithm.
2. Explain how to use the final matrices to find the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex \(\mathbf { 3 }\), and give the distance and route.
3. Draw the complete network of shortest distances.
4. Apply the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to your complete network of shortest distances. Give the Hamilton cycle it produces, its length, and the corresponding route through the original network.
5. By considering vertex 2 and its arcs, construct a lower bound for the length of the solution to the travelling salesperson problem in the original network.
6. Explain what you can deduce from your answers to parts (iv) and (v). 4 Noel is designing a hotel patio. It will consist of decking and paving.
   Decking costs \(\pounds 4\) per \(\mathrm { m } ^ { 2 }\) and paving costs \(\pounds 2\) per \(\mathrm { m } ^ { 2 }\). He has a budget of \(\pounds 2500\).
   Noel prefers paving to decking, and he wants the area given to paving to be at least twice that given to decking. He wants to have as large a patio as possible.
   Noel's problem is formulated as the following LP.
   Let \(x\) be the number of \(\mathrm { m } ^ { 2 }\) of decking.
   Let \(y\) be the number of \(\mathrm { m } ^ { 2 }\) of paving. $$\begin{aligned} \text { Maximise } \quad P & = x + y \\ \text { subject to } 2 x + y & \leqslant 1250 \\ 2 x - y & \leqslant 0 \\ x & \geqslant 0 \\ y & \geqslant 0 \end{aligned}$$

1. Use the simplex algorithm to solve this LP. Pivot first on the positive element in the \(y\) column. Noel would like to have at least \(200 \mathrm {~m} ^ { 2 }\) of decking.
2. Add a line corresponding to this constraint to your solution tableau from part (i), and modify the resulting table either for two-stage simplex or the big-M method. Hence solve the problem. Noel finally decides that he will minimise the annual cost of maintenance, which is given by \(\pounds ( 0.75 x + 1.25 y )\), subject to the additional constraint that there is at least \(1000 \mathrm {~m} ^ { 2 }\) of patio.
3. Starting from your solution to part (ii), use simplex to solve this problem.

Draw the complete network of shortest distances.
(ii) Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
(iii) By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.
(b) Solve the route inspection problem in the original network, and say how you can be sure that your solution is optimal. 4 A factory's output includes three products. To manufacture a tonne of product \(\mathrm { A } , 3\) tonnes of water are needed. Product B needs 2 tonnes of water per tonne produced, and product C needs 5 tonnes of water per tonne produced. Product A uses 5 hours of labour per tonne produced, product B uses 6 hours and product C uses 2 hours. There are 60 tonnes of water and 50 hours of labour available for tomorrow's production.

1. Formulate a linear programming problem to maximise production within the given constraints.
2. Use the simplex algorithm to solve your LP, pivoting first on your column relating to product C.
3. An extra constraint is imposed by a contract to supply at least 8 tonnes of A . Use either two stage simplex or the big M method to solve this revised problem.

2 A government has just created a new ministry, the Ministry of Administrative Affairs. The ministry is to have four departments:
the Administration
the Bureaucracy
the Certification Service
the Duplication Section.
Each of these departments is to be established in a separate office on one of four existing sites. The diagram shows the direct journey times in minutes between these four sites. \includegraphics[max width=\textwidth, alt={}, center]{52b8153f-e655-4852-a0f8-6f1c1e9c9170-3_342_403_721_829}

1. Use Floyd's algorithm to find the shortest journey times between the four office sites.
2. Draw a network showing your shortest times.
3. Use appropriate algorithms to find upper and lower bounds for the optimum solution to the Travelling Salesperson Problem in the original network, briefly explaining the steps taken.
4. A van is to be organised to deliver bundles of paperwork between the departments. Why might the optimum solution to the TSP be useful in planning this, and why might it not be?
5. Journeys to locations 2 and 3, from locations 1 and 4, are subject to a congestion charge which is equivalent in costing terms to 15 minutes of journey time. What sort of network would be needed to model this?

3 The weights on the network represent distances. \includegraphics[max width=\textwidth, alt={}, center]{eb4e9c34-7d8f-4118-b7ec-edcd9567077f-4_451_544_324_740}

1. The answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
   (A) Complete the two tables for iteration 4.
   (B) Use the final route table to give the shortest route from vertex \(\mathbf { 3 }\) to vertex \(\mathbf { 5 }\).
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
2. Using the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 5 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
3. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
4. Interpret your Hamilton cycle in part (iii) in terms of the original network.
5. Give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Give the length of your walk.

3 Five towns, 1, 2, 3, 4 and 5, are connected by direct routes as shown. The arc weights represent distances. \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-4_632_540_312_744}

1. The printed answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
   (A) Complete the two tables for iteration 4.
   (B) Use the final route table to give the shortest route from vertex 5 to vertex 2.
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
2. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 4 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
3. Interpret your Hamilton cycle from part (ii) in terms of towns actually visited.
4. Find an improved Hamilton cycle by applying the nearest neighbour algorithm starting from one of the other vertices.
5. Using the complete network of shortest distances (excluding loops), find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 4 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
6. Given that the sum of the road lengths in the original network is 43 , give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Show your methodology. Give the length of your walk.

5

1. Write down a way in which the nearest neighbour method can fail to solve the problem of finding a least weight cycle through all the vertices of a network.
2. Explain why, when trying to find a least weight cycle through all the vertices of a network, an ad hoc method may be preferable to an algorithmic approach. The distance matrix below represents a network connecting six viewpoints \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F . The distance matrix shows the direct distances between each pair of viewpoints where a direct route exists.
   The distances are measured in km.
   A blank shows that there is no direct route between the two viewpoints.

   	A	B	C	D	E	F
   A		6		4
   B	6		5	2	9
   C		5		15	7	6
   D	4	2	15		5
   E		9	7	5
   F			6

3. Draw the network on the vertices given in the Printed Answer Booklet.
4. Apply the nearest neighbour method, starting from A. A hiker wants to travel between the six viewpoints, starting and finishing at A.
   The hiker must visit every viewpoint at least once, but may visit a viewpoint more than once.
5. Show that the hiker does not need to travel as far as 50 km .
6. Use an appropriate algorithm to find the shortest distance from F to each of the other viewpoints.
7. Complete the table in the Printed Answer Book to show the shortest distance between each pair of viewpoints.
8. Use your answer to part (g) to find a lower bound for the distance the hiker must travel by initially deleting vertex A.

5 The manager of a farm shop wants to pave routes on the farm so that, after visiting the shop, customers can visit the animals in fields A, B, C, D and E.
The table shows the cost, in \(\pounds\), of making a paved path between each pair of fields.
A river means that it is not possible to make a paved path between C and E .

1. Determine the minimum cost of connecting the fields.
2. 1. By applying the lower bound algorithm to each vertex in turn, determine a best lower bound for \(P\), the minimum cost of making a circular tour (cycle) of paved paths that visits each field once.
   2. By applying the nearest neighbour algorithm, starting at each vertex in turn, find a best upper bound for \(P\). You do not need to attempt any route improvements.
   3. Give the order in which the fields are visited in a circular tour of paved paths that corresponds to the best upper bound found in part (b)(ii).
3. Give a practical reason why the total cost of paving for the project might be more than the best upper bound found in part (b)(ii). It becomes possible to use an existing bridge to make a paved route between C and E . Using this bridge, there is a new indirect route from A to D that costs less than \(\pounds 900\) to pave.
4. When this bridge is used, what can be determined about the minimum cost of
   1. paving the route between C and E
   2. connecting all the fields?

1 Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F . She wants to find a suitable route that does not involve her driving too far.

1. Which standard network problem does Fiona need to solve? The shortest distances between clients, in km, are given in the matrix below.

   	A	B	C	D	E
   A	-	12	8	6	4
   B	12	-	10	8	10
   C	8	10	-	13	10
   D	6	8	13	-	10
   E	4	10	10	10	-

2. Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations.
   State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. The distance from Fiona's house to each client, in km, is given in the table below.

   	A	B	C	D	E
   F	2	11	9	7	5

3. Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route.
4. (a) Find all the cycles that result from using the nearest neighbour method, starting at F .
   (b) Use these to find an upper bound for the length of Fiona's route.
5. Fiona wants to drive less than 35 km . Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length.

1. The table below shows the distances, in km , between six data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

Ferhana must visit each data collection point. She will start and finish at A and wishes to minimise the total distance she travels.

1. Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the distance Ferhana must travel. Make your method clear.
   (2)
2. Starting by deleting B , and all of its arcs, find a lower bound for the distance Ferhana must travel. Make your calculation clear.
   (3)
   

4.

1. Explain the difference between the classical and the practical travelling salesperson problems. The table below shows the distances, in km, between seven museums, A, B, C, D, E, F and G.

   	A	B	C	D	E	F	G
   A	-	25	31	28	35	30	32
   B	25	-	34	24	27	32	39
   C	31	34	-	40	35	27	29
   D	28	24	40	-	37	35	36
   E	35	27	35	37	-	28	31
   F	30	32	27	35	28	-	33
   G	32	39	29	36	31	33	-

   Fran must visit each museum. She will start and finish at A and wishes to minimise the total distance travelled.
2. Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Fran's route. Make your method clear. Starting at D, a second upper bound of 203 km was found.
3. State whether this is a better upper bound than the answer to (b), giving a reason for your answer. A reduced network is formed by deleting \(G\) and all the arcs that are directly joined to \(G\).
4. 1. Use Prim's algorithm, starting at A, to construct a minimum spanning tree for the reduced network. You must clearly state the order in which you select the arcs of your tree.
   2. Hence calculate a lower bound for the length of Fran's route. By deleting A, a second lower bound was found to be 188 km .
5. State whether this is a better lower bound than the answer to (d)(ii), giving a reason for your answer.
6. Using only the results from (c) and (e), write down the smallest interval that you can be confident contains the length of Fran's optimal route.
   

1. \section*{Question 1 continued}

1. The table above shows the least distances, in km, between six cities, A, B, C, D, E and F. Mohsen needs to visit each city, starting and finishing at A , and wishes to minimise the total distance he will travel.

1. Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Mohsen's route. You must state your route and its length.
2. Starting by deleting A and all of its arcs, find a lower bound for the length of Mohsen's route.
3. Use your answers from (a) and (b) to write down the smallest interval that you can be confident contains the optimal length of the route.

3. The table below shows the least distances, in km, between six towns, A, B, C, D, E and F. Mei must visit each town at least once. She will start and finish at A and wishes her route to minimise the total distance she will travel.

1. Starting with the minimum spanning tree in the answer book, use the shortcut method to find an upper bound below 520 km for Mei's route. You must state the shortcut(s) you use and the length of your upper bound.
2. Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Mei's route.
3. Starting by deleting E, and all of its arcs, find a lower bound for the length of Mei's route. Make your method clear.

4. \begin{figure}[h] \end{figure} Figure 3 models a network of roads. The number on each edge gives the length, in km , of the corresponding road. The vertices, A, B, C, D, E, F and G, represent seven towns. Derek needs to visit each town. He will start and finish at A and wishes to minimise the total distance travelled.

1. By inspection, complete the two copies of the table of least distances in the answer book.
2. Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Derek's route. Write down the route that gives this upper bound.
3. Interpret the route found in (b) in terms of the towns actually visited.
4. Starting by deleting A and all of its arcs, find a lower bound for the route length. Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G .
5. By considering the pairings of all relevant nodes, find the length of Clive's route. State the edges that need to be traversed twice. You must make your method and working clear.