Travelling Salesman

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.

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

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)

6

1. Sarah is solving a travelling-salesman problem.
   1. She finds the following upper bounds: \(32,33,32,32,30,32,32\). Write down the best upper bound.
   2. She finds the following lower bounds: 17, 18, 17, 20, 18, 17, 20. Write down the best lower bound.
2. Rob is travelling by train to a number of cities. He is to start at \(M\) and visit each other city at least once before returning to \(M\). The diagram shows the travelling times, in minutes, between cities. Where no time is shown, there is no direct journey available. \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-16_959_1122_1059_443} The table below shows the minimum travelling times between all pairs of cities.

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	\(\boldsymbol { B }\)	\(\boldsymbol { E }\)	\(\boldsymbol { L }\)	\(\boldsymbol { M }\)	\(\boldsymbol { N }\)
   \(\boldsymbol { B }\)	-	230	82	102	192
   \(\boldsymbol { E }\)	230	-	148	244	258
   \(\boldsymbol { L }\)	82	148	-	126	110
   \(\boldsymbol { M }\)	102	244	126	-	236
   \(\boldsymbol { N }\)	192	258	110	236	-

   1. Explain why the minimum travelling time from \(M\) to \(N\) is not 283 .
   2. Find an upper bound for the minimum travelling time by using the tour \(M N B E L M\).
   3. Write down the actual route corresponding to the tour \(M N B E L M\).
   4. Use the nearest-neighbour algorithm, starting from \(M\), to find another upper bound for the minimum travelling time of Rob's tour.
      [0pt] [4 marks] QUESTION
      1. (i) The best upper bound is \(\_\_\_\_\) (ii) The best lower bound is \(\_\_\_\_\)

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.

\includegraphics{figure_4} Figure 4 models a network of underground tunnels that have to be inspected. The number on each arc represents the length, in km, of each tunnel. Joe must travel along each tunnel at least once and the length of his inspection route must be minimised. The total weight of the network is 125 km. The inspection route must start and finish at A.

1. Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. [5]

Given that it is now permitted to start and finish the inspection at two distinct vertices,

1. state which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer. [2]

(Total 7 marks)

3 The diagram shows a network. The weights on the arcs represent distances in miles. The direct path between any two adjacent vertices is never longer than any indirect path. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-02_490_748_1372_699}

1. By deleting vertex \(U\) and all arcs connected to \(U\), find a lower bound for the length of the shortest cycle that visits every vertex of this network.
2. Find a vertex that can be used as the start vertex for the nearest neighbour method to give a cycle that passes through every vertex of this network. Give your cycle and its length.

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]

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]

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.

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)

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]

2. (a) Explain the difference between the classical and practical travelling salesman problems. \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-1_691_1297_1014_383} The network in the diagram above shows the distances, in kilometres, between eight McBurger restaurants. An inspector from head office wishes to visit each restaurant. His route should start and finish at \(A\), visit each restaurant at least once and cover a minimum distance.
(b) Obtain a minimum spanning tree for the network using Kruskal's algorithm. You should draw your tree and state the order in which the arcs were added.
(c) Use your answer to part (b) to determine an initial upper bound for the length of the route.
(d) Starting from your initial upper bound and using an appropriate method, find an upper bound which is less than 135 km . State your tour.

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]

7 Liam is taking part in a treasure hunt. There are five clues to be solved and they are at the points \(A , B , C , D\) and \(E\). The table shows the distances between pairs of points. All of the distances are functions of \(x\), where \(\boldsymbol { x }\) is an integer. Liam must travel to all five points, starting and finishing at \(A\).

1. The nearest point to \(A\) is \(C\).
   1. By considering \(A C\) and \(A B\), show that \(x < 10\).
   2. Find two other inequalities in \(x\).
2. The nearest neighbour algorithm, starting from \(A\), gives a unique minimum tour \(A C D E B A\).
   1. By considering the fact that Liam's tour visits \(D\) immediately after \(C\), find two further inequalities in \(x\).
   2. Find the value of the integer \(x\).
   3. Hence find the total distance travelled by Liam if he uses this tour.

3 Mark is driving around the one-way system in Leicester. The following table shows the times, in minutes, for Mark to drive between four places: \(A , B , C\) and \(D\). Mark decides to start from \(A\), drive to the other three places and then return to \(A\). Mark wants to keep his driving time to a minimum.

1. Find the length of the tour \(A B C D A\).
2. Find the length of the tour \(A D C B A\).
3. Find the length of the tour using the nearest neighbour algorithm starting from \(A\).
4. Write down which of your answers to parts (a), (b) and (c) gives the best upper bound for Mark's driving time.

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\)

4. (a) 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. Fran must visit each museum. She will start and finish at A and wishes to minimise the total distance travelled.
(b) 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.
(c) 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\).
(d) (i) 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.
(ii) 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 .
(e) State whether this is a better lower bound than the answer to (d)(ii), giving a reason for your answer.
(f) 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.

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?

5 [Figure 3, printed on the insert, is provided for use in this question.]

1. James is solving a travelling salesperson problem.
   1. He finds the following upper bounds: \(43,40,43,41,55,43,43\). Write down the best upper bound.
   2. James finds the following lower bounds: 33, 40, 33, 38, 33, 38, 38 . Write down the best lower bound.
2. Karen is solving a different travelling salesperson problem and finds an upper bound of 55 and a lower bound of 45 . Write down an interpretation of these results.
3. The diagram below shows roads connecting 4 towns, \(A , B , C\) and \(D\). The numbers on the edges represent the lengths of the roads, in kilometres, between adjacent towns. \includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-05_451_1034_1160_504} Xiong lives at town \(A\) and is to visit each of the other three towns before returning to town \(A\). She wishes to find a route that will minimise her travelling distance.
   1. Complete Figure 3, on the insert, to show the shortest distances, in kilometres, between all pairs of towns.
   2. Use the nearest neighbour algorithm on Figure 3 to find an upper bound for the minimum length of a tour of this network that starts and finishes at \(A\).
   3. Hence find the actual route that Xiong would take in order to achieve a tour of the same length as that found in part (c)(ii).