Travelling salesman problem

A coach operator offers sightseeing tours of a city. The sightseeing tour starts and ends at stop A, and there are tourist attractions at B, C, D, E, F and G. The table below shows the distances in metres that the coach must travel between each of the seven stops.

The coach operator wants to find a route which starts and ends at A, visiting every tourist attraction once.

State the standard network problem that they must solve.

Use the nearest neighbour method to find an upper bound for the length of the coach

operator’s route starting at A.

Beginning by removing stop A to reduce the network, use an algorithm to determine a lower

bound for the length of the coach operator’s route.

By referring to your lower bound, comment on the length of the route found by the nearest

neighbour method.

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.

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 A, B, C, D, 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.

Draw the network on the vertices given in the Printed Answer Booklet.

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.

Show that the hiker does not need to travel as far as 50 km.

Use an appropriate algorithm to find the shortest distance from F to each of the other

viewpoints.

Complete the table in the Printed Answer Book to show the shortest distance between each

pair of viewpoints.

Use your answer to part (g) to find a lower bound for the distance the hiker must travel by

initially deleting vertex A.

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.

Fig. 1.1
Fig. 1.2

The shortest path from D to F has total weight 6.

Write down a path from D to F of total weight 6.

The total weight of the 12 arcs in the network is 56.

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.

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.

Use an appropriate algorithm to find a lower bound for the total weight of Sasha’s route.

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.

Comment on the suitability of this route as a solution to Sasha’s problem.

A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors.

The cameras at the junctions and the lengths of the 11 corridors between them, in metres, are shown in the table below.

Model this information as a network.

Use an appropriate algorithm to calculate the minimum distance from A to each of the other

vertices.

The run‑time of an algorithm for finding this minimum distance is proportional to the total number of comparisons used. For a network with n vertices, the worst case is when the algorithm is applied to a network based on the complete graph K_n.

In each pass

• A vertex is made permanent and the temporary label at all adjacent vertices that are not yet permanent are updated. This uses 1 comparison for every such vertex (adjacent to the permanent label) that previously already had a temporary label.

• The best temporary labels at all vertices that do not yet have permanent labels are then compared to determine the next vertex to become permanent. If there are k such vertices this involves k - 1 comparisons.

By considering the number of comparisons of each type in each iteration, show that the algorithm uses a total of 6 comparisons when it is applied to a network based on the complete

graph K₄.

You are given that the total number of comparisons used when the algorithm is applied to a network based on K_n is (n - 1)(n - 2).

A computer takes 0.03 seconds to apply this algorithm on a network based on K₇.

Calculate, to 1 decimal place, how many seconds it will take the computer to apply the

algorithm to a network based on K₇₀.

The manager wants to construct a tour (a closed route) that passes each camera.

Find a lower bound for the length of this tour by initially deleting D.

Find an upper bound for the length of this tour by using the nearest neighbour algorithm

starting from D.

Deduce the length of the shortest possible tour. Briefly explain your reasoning.

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

Determine the minimum cost of connecting the fields.

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.

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.

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

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 £900 to pave.

When this bridge is used, what can be determined about the minimum cost of

paving the route between C and E

connecting all the fields?