7.04c Travelling salesman upper bound: nearest neighbour method

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.

\(\mathbf { 5 }\) & 4 & - & - & 2
\hline

1. Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
2. Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
3. (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.
   (B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is \(\mathbf { 3 2 1 5 4 3 . }\) Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
4. By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
5. In the incomplete 5-node network of journey times, find a quickest route starting at node \(\mathbf { 5 }\) and using each of the 7 arcs at least once. Give the time of your route. 4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC . The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables.

   Driving times	to A	to W
   From G	20 min	15 min

   \multirow{2}{*}{Train journey}	To V			To LB
   	normal time	probability of delay	delay	normal time	probability of delay	delay
   From A	1 hr 40 min	0.05	10 min	1 hr 45 min	0.05	10 min
   From W	1 hr 30 min	0.10	20 min	1 hr 35 min	0.10	20 min

   \multirow{2}{*}{ Tube journey }	To KC
   \cline { 2 - 4 }	normal time	probability of delay	delay
   From V	7 min	0.20	2 min
   From LB	9 min	0.10	2 min

   Helen wants to choose the route which will give the shortest expected journey time.
6. Draw a decision tree to model Helen's decisions and the possible outcomes.
7. Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time. As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
8. Find the value of the radio information, explaining your calculation.
9. Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?

1. Perform the fourth iteration of the algorithm, and show that there is no change to either matrix in the final iteration.
2. Show how to use the matrices to give the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex 2.
3. Draw the complete network of shortest distances.
4. 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.
5. 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.

4. This question should be answered on the sheet provided. A travelling salesman problem relates to the network represented by the following table of distances in kilometres. You may assume that the network satisfies the triangle inequality. Showing your method clearly, use

1. the nearest neighbour algorithm, beginning with \(A\),
2. Prim's algorithm with \(H\) deleted,
   to show that the minimum distance travelled, \(d \mathrm {~km}\), satisfies the inequality \(357 \leq d \leq 371\).
   (11 marks)

1. \begin{figure}[h] \end{figure} The network in Figure 1 shows the shortest distance by road, in kilometres, between five villages. Find the best achievable upper bound for a tour of the network, of minimum length, using the nearest neighbour algorithm.

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} The network in Figure 3 shows the distances, in miles, between a newspaper distributor based at area \(A\), and five areas, \(B , C , D , E\), and \(F\), to which the distributor must deliver newspapers. Each morning a delivery van has to set out from \(A\) and visit each of these areas before again returning to \(A\), and the driver wishes to keep the total mileage to a minimum.

1. Draw a complete network showing the shortest distances between the six areas.
   (3 marks)
2. Obtain a minimum spanning tree for the complete network and hence find an upper bound for the length of the driver's route.
   (5 marks)
3. Improve this upper bound to find an upper bound of less than 55 miles.
4. By deleting \(A\), find a lower bound for the total length of the route.

1. This question should be answered on the sheet provided.

\begin{figure}[h] \end{figure} The network in Figure 1 shows the distances, in miles, between the five villages in which Sarah is planning to enquire about holiday work, with village \(A\) being Sarah's home village.

1. Illustrate this situation as a complete network showing the shortest distances.
   (2 marks)
2. Use the nearest neighbour algorithm, starting with \(A\), to find an upper bound to the length of a tour beginning and ending at \(A\).
   (2 marks)
3. Interpret the tour found in part (b) in terms of the original network.
   (2 marks)
   

7. This question should be answered on the sheet provided. A tinned food producer delivers goods to six supermarket warehouses, \(B , C , D , E , F\) and \(G\), from its base, \(A\). The distances, in kilometres, between each location are given in the table below. \section*{Please hand this sheet in for marking}

2. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 1 shows a network in which the nodes represent five major rides in a theme park and the arcs represent paths between these rides. The numbers on the arcs give the length, in metres, of the paths.

1. By inspection, add additional arcs to make a complete network showing the shortest distances between the rides.
   (2 marks)
2. Use the nearest neighbour algorithm, starting at \(A\), and your complete network to find an upper bound to the length of a tour visiting each ride exactly once.
3. Interpret the tour found in part (b) in terms of the original network.

6. This question should be answered on the sheet provided. A furniture company in Leeds is considering opening outlets in six other cities.
The table below shows the distances, in miles, between all seven cities.

1. Starting with Leeds, obtain and draw a minimum spanning tree for this network of cities showing your method clearly.
   (4 marks)
   A representative of the company is to visit each of the areas being considered. He wishes to plan a journey of minimum length starting and ending in Leeds and visiting each of the other cities in the table once. Assuming that the network satisfies the triangle inequality,
2. find an initial upper bound for the length of his journey,
3. improve this upper bound to find an upper bound of less than 575 miles.
4. By deleting Leeds, find a lower bound for his journey.

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} A band is going on tour to play gigs in six towns, including their home town, \(A\). The network in Figure 1 shows the distances, in miles, between the various towns. The band must begin and end their tour at \(A\) and visit each of the other towns once, and they wish to keep the total distance travelled as small as possible.

1. By inspection, draw a complete network showing the shortest distances between the towns.
2. Use your complete network and the nearest neighbour algorithm, starting at \(A\), to find an upper bound for the total distance travelled.
3. 1. Use your complete network to obtain and draw a minimum spanning tree and hence obtain another upper bound for the total distance travelled.
   2. Improve this upper bound using two shortcuts to find an upper bound below 225 miles.
4. By deleting \(A\), find a lower bound for the total distance travelled.
5. State an interval of as small a width as possible within which \(d\), the minimum distance travelled, in miles, must lie. \section*{Please hand this sheet in for marking}

   Stage	Previous tournament	Current tournament
   \multirow[t]{3}{*}{1}	G	J K L
   	\(H\)	J K L
   	I	J K L
   \multirow[t]{3}{*}{2}	D	G H I
   	\(E\)	G H I
   	\(F\)	G H I
   \multirow[t]{3}{*}{3}	A	D E F
   	\(B\)	D E F
   	C	D E F
   4	None	A B C

   \section*{Please hand this sheet in for marking}
   1. \includegraphics[max width=\textwidth, alt={}, center]{073926c5-03cc-41d4-82bf-315740ead663-8_684_992_461_427}
   2. \section*{Sheet for answering question 6 (cont.)}
   3. 2. \(\_\_\_\_\)
   5. \(\_\_\_\_\)

6 A graph is shown in Fig. 1.1.
The graph is weighted to form the network represented by the weighted matrix in Fig. 1.2. The weights represent distances in km.
A dash (-) means that there is no direct arc between that pair of vertices. \begin{figure}[h] \end{figure} \begin{table}[h] \end{table} The shortest path from D to F has total weight 6.

1. Write down a path from D to F of total weight 6. The total weight of the 12 arcs in the network is 56.
2. Use the route inspection algorithm to calculate the total weight of the least weight route that covers every arc at least once, starting at vertex A.
3. Determine the total weight of the least weight route that covers every arc at least once, starting at vertex B but finishing at any vertex. Sasha wants to find a continuous route through every vertex, starting and finishing at vertex A, with the least total weight.
4. 1. Use an appropriate algorithm to find a lower bound for the total weight of Sasha's route.
   2. Use the Nearest Neighbour Algorithm, starting at vertex A, to find an upper bound for the total weight of Sasha's route. Sasha decides to use the route \(A - B - F - E - C - D - A\).
5. Comment on the suitability of this route as a solution to Sasha's problem.

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.

6. \begin{figure}[h] \end{figure} [The weight of the network is \(20 x + 17\) ]

1. Explain why it is not possible to draw a network with an odd number of vertices of odd valency. Figure 3 represents a network of 12 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
2. During rush hour one day \(x = 9\)
   1. Starting at A, use Prim's algorithm to find a minimum spanning tree. You must state the order in which you select the arcs of your tree.
   2. Calculate the weight of the minimum spanning tree. You are now given that \(x > 3\) A route that minimises the total time taken to traverse each road at least once needs to be found. The route must start and finish at the same vertex. The route inspection algorithm is applied to the network in Figure 3 and the time taken for the route is 162 minutes.
3. Determine the value of \(x\), showing your working clearly.

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.