Nearest Neighbour Algorithm

8 Tony delivers paper to five offices, \(A , B , C , D\) and \(E\). Tony starts his deliveries at office \(E\) and travels to each of the other offices once, before returning to office \(E\). Tony wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the offices.

4 David, a tourist, wishes to visit five places in Rome: Basilica ( \(B\) ), Coliseum ( \(C\) ), Pantheon ( \(P\) ), Trevi Fountain ( \(T\) ) and Vatican ( \(V\) ). He is to start his tour at one of the places, visit each of the other places, before returning to his starting place. The table shows the times, in minutes, to travel between these places. David wishes to keep his travelling time to a minimum.

1. 1. Find the total travelling time for the tour TPVBCT.
   2. Find the total travelling time for David's tour using the nearest neighbour algorithm starting from \(T\).
   3. Explain why your answer to part (a)(ii) is an upper bound for David's minimum total travelling time.
2. 1. By deleting \(B\), find a lower bound for the total travelling time for the minimum tour.
   2. Explain why your answer to part (b)(i) is a lower bound for David's minimum total travelling time.
3. Sketch a network showing the edges that give the lower bound found in part (b)(i) and comment on its significance.

7 Rupta, a sales representative, has to visit six shops, \(A , B , C , D , E\) and \(F\). Rupta starts at shop \(A\) and travels to each of the other shops once, before returning to shop \(A\). Rupta wishes to keep her travelling time to a minimum. The table shows the travelling times, in minutes, between the shops.

4 Sarah is a mobile hairdresser based at \(A\). Her day's appointments are at five places: \(B , C , D , E\) and \(F\). She can arrange the appointments in any order. She intends to travel from one place to the next until she has visited all of the places, starting and finishing at \(A\). The following table shows the times, in minutes, that it takes to travel between the six places.

1. Sarah decides to visit the places in the order \(A B C D E F A\). Find the travelling time of this tour.
2. Explain why this answer can be considered as being an upper bound for the minimum travelling time of Sarah's tour.
3. Use the nearest neighbour algorithm, starting from \(A\), to find another upper bound for the minimum travelling time of Sarah's tour.
4. By deleting \(A\), find a lower bound for the minimum travelling time of Sarah's tour.
5. Sarah thinks that she can reduce her travelling time to 75 minutes. Explain why she is wrong.

4 Pam has seven employees. When it snows they all need to be contacted by telephone.
The table shows the expected time, in minutes, that it will take Pam and her employees to contact each other.

1. Use the nearest neighbour method, starting from Pam, to find a cycle through all the employees and Pam. If there is a choice of names choose the one that occurs first alphabetically. Calculate the total weight of this cycle.
2. Apply Prim's algorithm to the copy of the table in the answer book, starting by crossing out the row for Pam and looking down the column for Pam. List the arcs in the order in which they were chosen. Draw the resulting minimum spanning tree and calculate its total weight.
3. Find a lower bound for the minimum weight cycle through Pam and her seven employees by initially removing Gita from the minimum spanning tree. Pam realises that it takes less time if she splits the employees into teams.
4. Use the minimum spanning tree to suggest how to split the employees into two teams, so that Pam contacts the two team leaders and they each contact the members of their team. Using this solution, find the minimum elapsed time by which all the employees can be contacted.

5 This question uses the same network as question 4.
The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres. \includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-5_680_1154_431_459} Gus wants to hunt for the treasure. He assumes that the treasure is located at a vertex, but he does not know which one.

1. (a) Use the nearest neighbour method starting at \(G\) to find an upper bound for the length of the shortest closed route through every vertex.
   (b) Gus follows this route, but starting at \(A\). Write down his route, starting and ending at \(A\).
2. Use Prim's algorithm on the network, starting at \(A\), to find a minimum spanning tree. You should write down the arcs in the order they are included, draw the tree and give its total weight (in units of 100 metres).
3. (a) Vertex \(H\) and all arcs joined to \(H\) are removed from the original network. Write down the weight of the minimum spanning tree for vertices \(A , B , C , D , E , F\) and \(G\) in the resulting reduced network.
   (b) Use this minimum spanning tree for the reduced network to find a lower bound for the length of the shortest closed route through every vertex in the original network.
4. Find a route that passes through every vertex, starting and ending at \(A\), that is longer than the lower bound from part (iii)(b) but shorter than the upper bound from part (i)(a). Give the length of your route, in metres. Assume that Gus travels along paths at a rate of \(x\) minutes for every 100 metres and that he spends \(y\) minutes at each vertex hunting for the treasure. Gus starts by hunting for the treasure at \(A\). He then follows the route from part (iv), starting and finishing at \(A\) and hunting for the treasure at each vertex. Unknown to Gus, the treasure is found before he gets to it, so he has to search at every vertex. Gus can take at most 2 hours from when he starts searching at \(A\) to when he arrives back at \(A\).
5. Use this information to write down a constraint on \(x\) and \(y\). The treasure was at \(H\) and was found 40 minutes after Gus started. This means that Gus takes more than 40 minutes to get to \(H\).
6. Use this information to write down a second constraint on \(x\) and \(y\).

7 A tour guide wants to find a route around eight places of interest: Queen Elizabeth Olympic Park ( \(Q\) ), Royal Albert Hall ( \(R\) ), Statue of Eros ( \(S\) ), Tower Bridge ( \(T\) ), Westminster Abbey ( \(W\) ), St Paul's Cathedral ( \(X\) ), York House ( \(Y\) ) and Museum of Zoology ( \(Z\) ). The table below shows the travel times, in minutes, from each of the eight places to each of the other places.

1. Use the nearest neighbour method to find an upper bound for the minimum time to travel to each of the eight places, starting and finishing at \(Y\). Write down the route and give the time in minutes.
2. The Answer Book lists the arcs by increasing order of weight (reading across the rows). Apply Kruskal's algorithm to this list to find the minimum spanning tree for all eight places. Draw your tree and give its total weight.
3. (a) Vertex \(Q\) and all arcs joined to \(Q\) are temporarily removed. Use your answer to part (ii) to write down the weight of the minimum spanning tree for the seven vertices \(R , S , T , W , X , Y\) and \(Z\).
   (b) Use your answer to part (iii)(a) to find a lower bound for the minimum time to travel to each of the eight places of interest, starting and finishing at \(Y\). The tour guide allows for a 5 -minute stop at each of \(S\) and \(Y\), a 10 -minute stop at \(T\) and a 30 -minute stop at each of \(Q , R , W , X\) and \(Z\). The tour guide wants to find a route, starting and ending at \(Y\), in which the tour (including the stops) can be completed in five hours (300 minutes).
4. Use the nearest neighbour method, starting at \(Q\), to find a closed route through each vertex. Hence find a route for the tour, showing that it can be completed in time.

1. \begin{figure}[h] \end{figure} 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.

1. By inspection, complete the two copies of the table of least distances in your answer book.
2. 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.
3. 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. 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.

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.

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.

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}

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)
   

1. \section*{Question 1 continued}

6

1. Mark is staying at the Grand Hotel ( \(G\) ) in Oslo. He is going to visit four famous places in Oslo: Aker Brygge ( \(A\) ), the National Theatre ( \(N\) ), Parliament House ( \(P\) ) and the Royal Palace ( \(R\) ). The figures in the table represent the walking times, in seconds, between the places.

   	Grand Hotel ( \(G\) )	Aker Brygge (A)	National Theatre ( \(N\) )	Parliament House (P)	Royal Palace (R)
   Grand Hotel ( \(G\) )	-	165	185	65	160
   Aker Brygge (A)	165	-	155	115	275
   National Theatre ( \(N\) )	185	155	-	205	125
   Parliament House (P)	65	115	205	-	225
   Royal Palace (R)	160	275	125	225	-

   Mark is to start his tour from the Grand Hotel, visiting each place once before returning to the Grand Hotel. Mark wishes to keep his walking time to a minimum.
   1. Use the nearest neighbour algorithm, starting from the Grand Hotel, to find an upper bound for the walking time for Mark's tour.
   2. By deleting the Grand Hotel, find a lower bound for the walking time for Mark's tour.
   3. The walking time for an optimal tour is \(T\) seconds. Use your answers to parts (a)(i) and (a)(ii) to write down a conclusion about \(T\).
2. Mark then intends to start from the Grand Hotel ( \(G\) ), visit three museums, Ibsen ( \(I\) ), Munch ( \(M\) ) and Viking ( \(V\) ), and return to the Grand Hotel. He uses public transport. The table shows the minimum travelling times, in minutes, between the places.

   \backslashbox{From}{To}	Grand Hotel ( \(G\) )	Ibsen (I)	Munch ( \(M\) )	Viking ( \(\boldsymbol { V }\) )
   Grand Hotel ( \(\boldsymbol { G }\) )	-	20	17	30
   Ibsen (I)	15	-	32	16
   Munch (M)	26	18	-	21
   Viking ( \(\boldsymbol { V }\) )	19	27	24	-

   1. Find the length of the tour \(G I M V G\).
   2. Find the length of the tour GVMIG.
   3. Find the number of different possible tours for Mark.
   4. Write down the number of different possible tours for Mark if he were to visit \(n\) museums, starting and finishing at the Grand Hotel.

1. The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Jas needs to visit each town, starting and finishing at D , and wishes to minimise the total distance she travels.

1. Starting at D , use the nearest neighbour algorithm to obtain an upper bound for the length of the route. You must state your route and its length.
2. Starting by deleting D , and all of its arcs, find a lower bound for the route length.

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]

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]

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)

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]

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]