7.04c Travelling salesman upper bound: nearest neighbour method

6 The diagram shows a nature reserve which has its entrance at \(A\), eight information signs at \(B , C , \ldots , I\), and fifteen grass paths. The length of each grass path is given in metres.
The total length of the grass paths is 1465 metres. \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-10_812_1192_584_424} To cut the grass, Ashley starts at the entrance and drives a mower along every grass path in the nature reserve. The mower moves at 7 kilometres per hour. 6

1. Find the least possible time that it takes for Ashley to cut the grass on all fifteen paths in the nature reserve and return to the entrance. Fully justify your answer.
   6
2. Brook visits every information sign in the nature reserve to update them, starting and finishing at the entrance. For the eight information signs, the minimum connecting distance of the grass paths is 510 metres. 6 (b)
   1. Determine a lower bound for the distance Brook walks to visit every information sign.
      Fully justify your answer.
      [0pt] [2 marks]
      6
   2. Using the nearest neighbour algorithm starting from the entrance, determine an upper bound for the distance Brook walks to visit every information sign.
      [0pt] [2 marks]
      6
   3. Brook takes one minute to update the information at one information sign. Brook walks on the grass paths at an average speed of 5 kilometres per hour. Ashley and Brook start from the entrance at the same time.
   6 (c) (i) Use your answers from parts (a) and (b) to show that Ashley and Brook will return to the entrance at approximately the same time. Fully justify your answer.
   6 (c) (ii) State an assumption that you have used in part (c)(i). \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-13_2488_1716_219_153} \(7 \quad\) Ali and Bex play a zero-sum game. The game is represented by the following pay-off matrix for Ali.

   \multirow{2}{*}{}	Bex
   	Strategy	\(\mathbf { B } _ { \mathbf { 1 } }\)	\(\mathbf { B } _ { \mathbf { 2 } }\)	\(\mathbf { B } _ { \mathbf { 3 } }\)
   \multirow{4}{*}{Ali}	\(\mathbf { A } _ { \mathbf { 1 } }\)	2	-1	3
   	\(\mathbf { A } _ { \mathbf { 2 } }\)	-4	-2	2
   	\(\mathbf { A } _ { \mathbf { 3 } }\)	0	1	1
   	\(\mathrm { A } _ { 4 }\)	-3	2	-2

4 Alun, a baker, delivers bread to community shops located in Aber, Bangor, Conwy, and E'bach. Alun starts and finishes his journey at the bakery, which is located in Deganwy.
The distances, in miles, between the five locations are given in the table below. The minimum total distance that Alun can travel in order to make all four deliveries, starting and finishing at the bakery in Deganwy is \(x\) miles. 4

1. Using the nearest neighbour algorithm starting from Deganwy, find an upper bound for \(x\)

5 Charlotte is visiting a city and plans to visit its five monuments: \(A , B , C , D\) and \(E\).
The network shows the time, in minutes, that a typical tourist would take to walk between the monuments on a busy weekday morning. \includegraphics[max width=\textwidth, alt={}, center]{ba9e9840-ce27-4ca7-ab05-50461d135445-06_902_1134_529_543} Charlotte intends to walk from one monument to another until she has visited them all, before returning to her starting place. 5

1. Use the nearest neighbour algorithm, starting from \(A\), to find an upper bound for the minimum time for Charlotte's tour.
   5
2. By deleting vertex \(B\), find a lower bound for the minimum time for Charlotte's tour.
   [0pt] [3 marks]
   5
3. Charlotte wants to complete the tour in 52 minutes. Use your answers to parts (a) and (b) to comment on whether this could be possible.
   5
4. Charlotte takes 58 minutes to complete the tour. Evaluate your answers to part (a) and part (b) given this information.
   5
5. Explain how this model for a typical tourist's tour may not be applicable if the tourist walked between the monuments during the evening.

4 Joe, a courier, is required to deliver parcels to six different locations, \(A , B , C , D , E\) and \(F\). Joe needs to start and finish his journey at the depot.
The distances, in miles, between the depot and the six different locations are shown in the table below. The minimum total distance that Joe can travel in order to make all six deliveries, starting and finishing at the depot, is \(L\) miles. 4

1. Using the nearest neighbour algorithm starting from the depot, find an upper bound for \(L\).
   4
2. By deleting the depot, find a lower bound for \(L\).
   4
3. Joe starts from the depot, delivers parcels to all six different locations and arrives back at the depot, covering 134 miles in the process. Joe claims that this is the minimum total distance that is possible for the journey. Comment on Joe's claim.

4 Derrick, a tanker driver, is required to deliver fuel to 6 different service stations \(A , B\), \(C , D , E\) and \(F\). Derrick needs to begin and finish his delivery journey at the refinery \(O\).
The distances, in miles, between the 7 locations which have a direct road between them are shown in the network below. \includegraphics[max width=\textwidth, alt={}, center]{59347089-ea4a-4ee6-b40e-1ab78aa7cdc3-06_921_1440_628_303} Derrick spends 30 minutes at each service station to complete the fuel delivery.
When driving, the tanker travels at an average speed of 40 miles per hour.
The minimum total time that it takes Derrick to travel to and deliver fuel to all 6 service stations, starting and finishing at the refinery, is \(T\) minutes. 4

1. Using the nearest neighbour algorithm starting from the refinery, find an upper bound for \(T\) 4
2. Before setting off to make his fuel deliveries, Derrick is notified that, due to a low bridge, the road represented by CE is not suitable for tankers to travel along. State, with a reason, the effect this new information has on your answer to part (a).
   [0pt] [2 marks]

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. \hfill [2]
2. Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Liz's route. \hfill [2]
3. Starting by deleting F, and all of its arcs, find a lower bound for the length of Liz's route. \hfill [3]
4. Use your results to write down the smallest interval which you are confident contains the optimal length of the route. \hfill [1]

Fred delivers bread to five shops, \(A\), \(B\), \(C\), \(D\) and \(E\). Fred starts his deliveries at shop \(B\), and travels to each of the other shops once before returning to shop \(B\). Fred wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the shops. $$\begin{array}{c|ccccc} & A & B & C & D & E \\ \hline A & - & 3 & 11 & 15 & 5 \\ B & 3 & - & 18 & 12 & 4 \\ C & 11 & 18 & - & 5 & 16 \\ D & 15 & 12 & 5 & - & 10 \\ E & 5 & 4 & 16 & 10 & - \end{array}$$

1. Find the travelling time for the tour \(BACDEB\). [1]
2. Use the nearest neighbour algorithm, starting at \(B\), to find another upper bound for the travelling time for Fred's tour. [3]
3. By deleting \(C\), find a lower bound for the travelling time for Fred's tour. [4]
4. Sketch a network showing the edges that give you the lower bound in part (c) and comment on its significance. [2]

Phil, a squash coach, wishes to buy some equipment for his club. In a town centre, there are six shops, \(G\), \(I\), \(N\), \(R\), \(S\) and \(T\), that sell the equipment. The time, in seconds, to walk between each pair of shops is shown in the table. Phil intends to check prices by visiting each of the six shops before returning to his starting point. $$\begin{array}{c|cccccc} & G & I & N & R & S & T \\ \hline G & - & 81 & 82 & 86 & 72 & 76 \\ I & 81 & - & 80 & 82 & 68 & 73 \\ N & 82 & 80 & - & 84 & 70 & 74 \\ R & 86 & 82 & 84 & - & 74 & 70 \\ S & 72 & 68 & 70 & 74 & - & 64 \\ T & 76 & 73 & 74 & 70 & 64 & - \\ \end{array}$$

1. Use the nearest neighbour algorithm starting from \(S\) to find an upper bound for Phil's minimum walking time. [4 marks]
2. Write down a tour starting from \(N\) which has a total walking time equal to your answer to part (a). [1 mark]
3. By deleting \(S\), find a lower bound for Phil's minimum walking time. [5 marks]

Answer this question on the insert provided. \includegraphics{figure_2}

1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight. [5]
2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(G\), and all the arcs joined to \(G\), removed. Hence find a lower bound for the travelling salesperson problem on the original network. [3]
3. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the travelling salesperson problem on the original network. [3]

The table shows the road distances in miles between five places in Great Britain. For example, the distance between Birmingham and Cardiff is 103 miles.

	Ayr
250		Birmingham
350	103		Cardiff
235	104	209		Doncaster
446	157	121	261	Exeter

1. Complete the network in the answer booklet to show this information. The vertices are labelled by using the initial letter of each place. [2]
2. List the ten arcs by increasing order of weight. Apply Kruskal's algorithm to the list. Any entries that are crossed out should still be legible. Draw the resulting minimum spanning tree and give its total weight. [4]

A sixth vertex, F, is added to the network. The distances, in miles, between F and each of the other places are shown in the table below.

	A	B	C	D	E
Distance from F	200	50	150	59	250

1. Use the weight of the minimum spanning tree from part (ii) to find a lower bound for the length of the minimum tour (cycle) that visits every vertex of the extended network with six vertices. [2]
2. Apply the nearest neighbour method, starting from vertex A, to find an upper bound for the length of the minimum tour (cycle) through the six vertices. [2]
3. Use the two least weight arcs through A to form a least weight path of the form \(SAT\), where \(S\) and \(T\) are two of \(\{B, C, D, E, F\}\), and give the weight of this path. Similarly write down a least weight path of the form \(UEV\), where \(U\) and \(V\) are two of \(\{A, B, C, D, F\}\), and give the weight of this path. You should find that the two paths that you have written down use all six vertices. Now find the least weight way in which the two paths can be joined together to form a cycle through all six vertices. Hence write down a tour through the six vertices that has total weight less than the upper bound. Write down the total weight of this tour. [8]

\includegraphics{figure_1} Figure 1 shows a network of roads connecting six villages \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\). The lengths of the roads are given in km.

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. [2] The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once. [3]
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages. [1]
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length. [2]

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

	A	B	C	D	E	F
A	\(-\)	85	110	175	108	100
B	85	\(-\)	38	175	160	93
C	110	38	\(-\)	148	156	73
D	175	175	148	\(-\)	110	84
E	108	160	156	110	\(-\)	92
F	100	93	73	84	92	\(-\)

1. Starting from \(A\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected. [4]
2. 1. Using your answer to part (a) obtain an initial upper bound for the solution of the travelling salesman problem. [2]
   2. Use a short cut to reduce the upper bound to a value less than 680. [4]
3. Starting by deleting \(F\), find a lower bound for the solution of the travelling salesman problem. [4]

The table shows the least distances, in km, between five towns, \(A\), \(B\), \(C\), \(D\) and \(E\). Nassim wishes to find an interval which contains the solution to the travelling salesman problem for this network.

1. Making your method clear, find an initial upper bound starting at \(A\) and using
   1. the minimum spanning tree method, [4]
   2. the nearest neighbour algorithm. [3]
2. By deleting \(E\), find a lower bound. [4]
3. Using your answers to parts (a) and (b), state the smallest interval that Nassim could correctly write down. [1]

(Total 12 marks)

A college wants to offer five full-day activities with a different activity each day from Monday to Friday. The sports hall will be used for these activities. Each evening the caretaker will prepare the hall by putting away the equipment from the previous activity and setting up the hall for the activity next day. On Friday evening he will put away the equipment used that day and set up the hall for the following Monday. The 5 activities offered are Badminton (\(B\)), Cricket nets (\(C\)), Dancing (\(D\)), Football coaching (\(F\)) and Tennis (\(T\)). Each will be on the same day from week to week. The college decides to offer the activities in the order that minimises the total time the caretaker has to spend preparing the hall each week. The hall is initially set up for Badminton on Monday. The table below shows the time, in minutes, it will take the caretaker to put away the equipment from one activity and set up the hall for the next.

	To
\cline{2-6} \multicolumn{1}{c|}{Time}	\(B\)	\(C\)	\(D\)	\(F\)	\(T\)
\(B\)	--	108	150	64	100
\(C\)	108	--	54	104	60
From \(D\)	150	54	--	150	102
\(F\)	64	104	150	--	68
\(T\)	100	60	102	68	--

1. Explain why this problem is equivalent to the travelling salesman problem. [2]
2. Find the total time taken by the caretaker each week using this ordering. A possible ordering of activities is

   Monday	Tuesday	Wednesday	Thursday	Friday
   \(B\)	\(C\)	\(D\)	\(F\)	\(T\)

   [2]
3. Starting with Badminton on Monday, use a suitable algorithm to find an ordering that reduces the total time spent each week to less than 7 hours. [3]
4. By deleting \(B\), use a suitable algorithm to find a lower bound for the time taken each week. Make your method clear. [4]

(Total 11 marks)

The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2. \includegraphics{figure_3} \includegraphics{figure_4}

1. Draw the complete network of shortest distances. [2]
2. Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network. [2]

A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3. \includegraphics{figure_5}

1. Draw the extended network and the complete 5-node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.) [3]
2. Produce the shortest distance matrix and the route matrix for the extended 5-node network. [3]
3. Apply the nearest neighbour algorithm to your \(5 \times 5\) distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network. [3]
4. By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm. [4]
5. In the original 5-node network find a shortest route starting at vertex 1 and using each of the 6 arcs at least once. Give the length of your route. [3]

This question should be answered on the sheet provided. The table below shows the distances in miles between five villages. Jane lives in village A and is about to take her daughter's friends home to villages B, C, D and E. She will begin and end her journey at A and wishes to travel the minimum distance possible.

	A	B	C	D	E
A	\(-\)	4	7	8	2
B	4	\(-\)	1	5	6
C	7	1	\(-\)	2	7
D	8	5	2	\(-\)	3
E	2	6	7	3	\(-\)

1. Obtain a minimum spanning tree for the network and hence find an upper bound for the length of Jane's journey. [4 marks]
2. Using a shortcut, improve this upper bound to find an upper bound of less than 15 miles. [2 marks]

This question should be answered on the sheet provided. The table below gives distances, in miles, for a network relating to a travelling salesman problem.

	A	B	C	D	E	F	G
A	\(-\)	83	57	68	103	91	120
B	83	\(-\)	78	63	41	82	52
C	57	78	\(-\)	37	59	63	74
D	68	63	37	\(-\)	60	52	62
E	103	41	59	60	\(-\)	48	51
F	91	82	63	52	48	\(-\)	77
G	120	52	74	62	51	77	\(-\)

1. Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of a tour beginning and ending at A and state the tour. [4 marks]
2. By deleting A, obtain a lower bound for the length of a tour. [4 marks]
3. Hence, write down an inequality which must by satisfied by d, the minimum distance travelled in miles. [1 mark]

A student is trying to find the solution to the travelling salesperson problem for a network. They correctly find two lower bounds for the solution: 15 and 19 They also correctly find two upper bounds for the solution: 48 and 51 Based on the above information only, which of the following pairs give the best lower bound and best upper bound for the solution of this problem? Tick \((\checkmark)\) one box. [1 mark]

Best Lower Bound	Best Upper Bound
15	48	\(\square\)
15	51	\(\square\)
19	48	\(\square\)
19	51	\(\square\)

The diagram represents a map of seven locations (A to G) and the direct road distances (km) between some of them. \includegraphics{figure_3} A delivery driver needs to start from his depot at D, make deliveries at each of A, B, F and G, and finish at D.

1. Write down a route from A to G of length 70 km. [1]

The table shows the length of the shortest path between some pairs of places.

	D	A	B	F	G
D	-
A		-			70
B			-	84
F			84	-
G		70			-

1. 1. Complete the table.
   2. Use the nearest neighbour method on the table, starting at D, to find the length of a cycle through D, A, B, F and G, ignoring possibly repeating E and C. [4]
2. By first considering the table with the row and column for D removed, find a lower bound for the distance that the driver must travel. [2]
3. What can you conclude from your previous answers about the distance that the driver must travel? [1]

A new road is constructed between D and F. Using this road the driver starts from D, makes the deliveries and returns to D having travelled just 172 km.

1. Find the length of the new road if
   1. the driver does not return to D until all the deliveries have been made,
   2. the driver uses the new road twice in making the deliveries. [4]