The Travelling Salesman problem

The Travelling Salesman problem

Spec 3.2 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • The classical problem visits every vertex exactly once and returns to the start (a Hamiltonian cycle).
  • The practical problem visits every vertex at least once, so arcs and vertices may repeat.
  • To use classical methods on an incomplete network, build a complete network of least distances.
  • Any tour gives an upper bound: nearest neighbour, or twice a minimum spanning tree.
  • A lower bound is a minimum spanning tree of the remaining vertices plus the two shortest arcs at the deleted vertex.

Practical and classical

The classical problem visits each vertex exactly once; the practical problem visits each at least once and may repeat.

The Travelling Salesman problem asks for the shortest closed route that visits every vertex.

The classical problem asks for a Hamiltonian cycle on a complete graph whose weights obey the triangle inequality: the direct distance between two vertices is no more than the distance by way of a third.

The practical problem needs each vertex visited at least once, on a network that need not be complete.

No efficient algorithm is certain to find the shortest tour, so we find an upper and a lower bound.

434355ABCD
A complete graph on four vertices, weights from straight-line distances (they obey the triangle inequality). The tour ABCDA has length 4 + 3 + 4 + 3 = 14.

Classical

Each vertex visited:
Exactly once
Network:
Complete, triangle inequality
Arcs and vertices repeated:
No repeats

Practical

Each vertex visited:
At least once
Network:
Need not be complete
Arcs and vertices repeated:
Repeats if needed

A route may visit a vertex twice and use the same arc twice. Which problem is this?

A complete network of least distances

Replace each arc with the least distance between its two vertices. These distances satisfy the triangle inequality.

If the network is not complete, build a complete network in which each arc has the least distance between its two vertices in the original network.

Use inspection or a shortest path algorithm and record the answers in a table. 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.

BD 11BC 4CD 5BCD
The direct road BD is longer than the route through C.

Worked example

Roads BD=11BD=11, BC=4BC=4 and CD=5CD=5. What weight is used for arc BDBD in the complete network?

Why do least distances satisfy the triangle inequality?

Upper bounds

Any tour is an upper bound. Use nearest neighbour or twice a minimum spanning tree, then shorten with shortcuts.

The shortest tour cannot be longer than any tour you find, so every tour is an upper bound.

Nearest neighbour: from the start, go to the nearest unvisited vertex, repeat, then return to the start. Try different starts for a smaller bound.

Minimum spanning tree method: walking round a minimum spanning tree twice visits every vertex, giving 2×2\times the tree weight.

Shortcuts: skip a revisited vertex by going straight to the next unvisited one. By the triangle inequality this is no longer, so the bound improves.

  1. 1

    Choose a start vertex

    mark it as visited

  2. 2

    Go to the nearest unvisited vertex

    add the arc to the tour

  3. 3

    Repeat

    until every vertex is visited

  4. 4

    Return to the start

    add the final arc; the total is an upper bound

Nearest neighbour algorithm

A minimum spanning tree has weight 20. What upper bound does the minimum spanning tree method give?

The lower bound

Delete a vertex, find a minimum spanning tree of the rest, then add the two shortest arcs at the deleted vertex.

To find a lower bound:

  1. Delete one vertex and all arcs joined to it.
  2. Find the weight of the minimum spanning tree of the remaining vertices.
  3. Add the two shortest arcs at the deleted vertex.

Any tour contains a path through the other vertices (a spanning tree, so at least the minimum) plus two arcs at the deleted vertex.

You can delete any vertex. The best lower bound is the largest value found.

  1. 1

    Delete a vertex

    remove it and its arcs

  2. 2

    Minimum spanning tree

    of the remaining vertices

  3. 3

    Add two shortest arcs

    the two shortest at the deleted vertex

Finding a lower bound

After deleting a vertex, the minimum spanning tree has weight 31 and the two shortest arcs at that vertex are 15 and 18. What is the lower bound?

Using the bounds

The shortest tour length lies between the best lower bound and the best upper bound. If they are equal, the tour is optimal.

Let the shortest tour have length LL. If the lower bound is 64 and the best upper bound is 66, then 64≤L≤6664\le L\le66.

When you find a better upper bound, use it. When the lower bound equals the upper bound, you have found the optimal tour.

In the exam, state the tour, the method and the interval, with the correct units.

60616263646566676869706466

Worked example

The nearest neighbour tour from A has length 66 km. Deleting A gives a minimum spanning tree of weight 31, and the two shortest arcs at A are 15 and 18. What can you say about the shortest route?

The lower bound is 64 and the best upper bound is 64. What do you conclude?

Try an exam question

A tour found by the nearest neighbour algorithm from AA has length 56 km. Deleting AA leaves a minimum spanning tree of weight 38 km, and the two shortest arcs at AA are 7 km and 9 km. (a) Find a lower bound for the shortest tour. (b) State the interval in which the shortest tour lies. (c) Explain why the length of any tour is an upper bound.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Using the nearest neighbour algorithm starting at A, which town is visited immediately after E?

1 mark, marked against the mark scheme

Revision notes