Classical vs Practical TSP

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.

2. (a) 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 . Rachel must visit each collection point. 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. Make your method clear. Starting at B, a second upper bound of 293 km was found.
(c) 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 .
(d) By deleting B, find a second lower bound. Make your method clear.
(e) State the better lower bound of these two, giving a reason for your answer.
(f) 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. (a) Explain the difference between the classical and the practical travelling salesperson problem. 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.
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. You must state your route and its length.
(c) Starting by deleting A, and all of its arcs, find a lower bound for the route length.
(d) Use your results to write down the smallest interval which you are confident contains the optimal length of the route.

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.