The Travelling Salesman problemEdexcel A-Level Further Maths: Revision notes

The Travelling Salesman problem asks for the shortest closed route that visits every vertex of a network. The classical problem asks for a Hamiltonian cycle: each vertex is visited exactly once and you return to the start. It is set on a complete graph, where every pair of vertices is joined by an arc, and the arc weights satisfy the triangle inequality: for any three vertices, the direct distance is no more than the distance by way of the third vertex. The practical problem asks for the shortest route that visits every vertex at least once, returning to the start. The network need not be complete, so vertices and arcs may be repeated. There is no efficient algorithm that is certain to find the shortest tour. Instead we find an upper bound and a lower bound between which the answer must lie.

If the network is not complete, build a complete network in which the weight of each arc is the least distance between its two vertices in the original network. Use inspection or a shortest path algorithm, and write the answers in a table. Example: roads BD = 11, BC = 4 and CD = 5. The least distance from B to D is B–C–D = 9, not 11. The least distances automatically satisfy the triangle inequality, so the classical problem can now be solved on the new network. To give a route in the original network, replace each arc by the roads it represents.

Any tour is an upper bound, because the shortest tour cannot be longer than any tour you can find. Nearest neighbour algorithm: from the start vertex, travel to the nearest unvisited vertex, repeating until all are visited, then return to the start. The length is an upper bound. Start from different vertices to look for a smaller one. Minimum spanning tree method: find a minimum spanning tree with Kruskal's or Prim's algorithm. Walking round the tree twice visits every vertex and has length 2 × (weight of tree), which is an upper bound. Shortcuts: a walk that revisits a vertex can skip it by going directly to the next unvisited vertex. By the triangle inequality the direct arc is no longer than the route it replaces, so the new tour gives an improved upper bound.

To find a lower bound using a minimum spanning tree:

1. Delete one vertex and all the arcs joined to it.
2. Find the weight of the minimum spanning tree of the remaining vertices.
3. Add the weights of the two shortest arcs joined to the deleted vertex. Any tour contains a path through the remaining vertices (which is a spanning tree, so it weighs at least the minimum) plus two arcs at the deleted vertex, so the shortest tour cannot be less than this total. You can delete any vertex. The best lower bound is the largest value found, so deleting different vertices may give a higher bound.

Let the shortest tour have length L. If the lower bound is 64 and the best upper bound is 66, then 64 ≤ L ≤ 66. When you find a better upper bound, use it. When the lower bound equals the upper bound, you have found the optimal tour. Worked example: the nearest neighbour tour from A is 66. Deleting A gives MST 31 and arcs 15 and 18, so the lower bound is 64. Therefore the shortest route is between 64 and 66 km. In the exam, state the tour, the method and the interval, and write bounds with the correct units.