Bounds for the travelling salesman problem

Bounds for the travelling salesman problem

Spec 3.3–4 · Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • An upper bound is the length of a tour that exists; a lower bound is a value the shortest tour cannot be below.
  • The shortest tour lies between them; if the bounds are equal the tour is optimal.
  • The nearest neighbour algorithm gives an upper bound: start with the smallest arc each time; try every start vertex.
  • Going round a minimum spanning tree gives an upper bound of twice its weight, improved by shortcuts.
  • For a lower bound, delete a vertex, add the MST of the rest and the two shortest arcs at the deleted vertex; take the largest.

Why we use bounds

For a large network we find an upper bound (a tour that exists) and a lower bound (a value the shortest tour is not below), so the shortest tour is trapped between them.

For a large network there is no quick method that always finds the shortest tour. Instead we find an upper bound, the length of a tour that exists, and a lower bound, a value the shortest tour is no shorter than.

The smaller the gap, the better we know the answer. If the two bounds are equal, the tour found is optimal.

363738394041424344lower bound 38upper bound 41
The shortest tour lies between 38 and 41

A tour of length 4141 exists, and the lower bound is 3838. What can you say about the shortest tour?

A complete network of shortest distances

The bound methods need a complete network. Where a pair is not joined by a road, create an arc of the shortest distance between them.

The bound methods need a complete network, where every pair of vertices is joined by an arc. For pairs not joined by a road, create an arc whose length is the shortest distance along the original network.

After finding a tour, replace each new arc by the shortest path it stands for. The route may revisit vertices, which is allowed in the practical problem.

w=7w=5w=6w=4w=9ABCDE
Roads AB, BC, CD, DE and BE

Worked example

Find the shortest distance for each pair of vertices not joined by a road.

Why does every new arc in the complete network satisfy the triangle inequality?

Nearest neighbour algorithm

From a start vertex, always go along the shortest arc to an unvisited vertex, then return to the start; the length of this tour is an upper bound.

The nearest neighbour algorithm builds a tour step by step.

Different starting vertices can give different tours. Start from each vertex in turn and take the smallest tour length as the best upper bound.

  1. 1

    Start

    choose a starting vertex

  2. 2

    Move

    go along the shortest arc to a vertex not yet visited

  3. 3

    Repeat

    until all vertices are visited

  4. 4

    Return

    go back to the start vertex

Nearest neighbour algorithm

Worked example

A complete network has PQ=14PQ=14, PR=10PR=10, PS=17PS=17, PT=9PT=9, QR=11QR=11, QS=8QS=8, QT=15QT=15, RS=12RS=12, RT=13RT=13, ST=16ST=16. Find the tour from PP by nearest neighbour.

Nearest neighbour from AA gives a tour of length 5252, and from BB gives 4949. Which is the better upper bound?

Minimum spanning trees and shortcuts

A walk round a minimum spanning tree uses every arc twice, so its length is 2×2\times the weight of the tree. Shortcuts then reduce it.

A walk that goes all the way round a minimum spanning tree, out along each arc and back, visits every vertex and returns to the start. It gives an upper bound.

Use shortcuts to improve it: whenever the walk would revisit a vertex, go straight to the next new vertex. In a complete network satisfying the triangle inequality a shortcut is never longer than the route it replaces.

Shortcuts can also improve a nearest neighbour tour.

w=8w=9w=7w=6w=11BCAED
Minimum spanning tree B-C-A-E-D (solid, weight 30) and the shortcut D to B (dashed): tour length 8 + 9 + 7 + 6 + 11 = 41.
  • Walk round a minimum spanning tree2×2\times weight of the tree

Worked example

A minimum spanning tree is the path BB-CC-AA-EE-DD with arcs 88, 99, 77, 66, and BD=11BD=11. Find an upper bound.

A minimum spanning tree has weight 2525. What is the length of the walk that goes round it, before any shortcuts?

Lower bound: deleting a vertex

Delete one vertex, find a minimum spanning tree of the rest and add the two shortest arcs at the deleted vertex; repeat and take the largest.

To find a lower bound, delete one vertex XX with all its arcs, find a minimum spanning tree of the remaining vertices, and add the two shortest arcs at XX.

This works because every tour has two arcs at XX, each at least as long as the two shortest, and the rest of the tour is a path joining the other vertices, at least as long as their minimum spanning tree.

Deleting a different vertex can give a different bound. Take the largest, the best lower bound.

w=9w=7w=6w=8w=11BCAED
Delete B. The tree on A, C, D, E (solid) weighs 9 + 7 + 6 = 22; add the two shortest arcs at B (dashed, 8 and 11): lower bound 41.
  • Lower boundMST of the rest + two shortest arcs at the deleted vertex

Worked example

In the same network, BC=8BC=8 and BD=11BD=11 are the two shortest arcs at BB. Find the lower bound by deleting BB.

Deleting vertex A gives a lower bound of 38 and deleting vertex B gives 41. Which should you quote?

Using the bounds

Give the best bounds as an inequality. If they are equal the tour is optimal; otherwise the shortest tour lies in between.

State the bounds as an inequality such as 38≤shortest tour≤4138\leq\text{shortest tour}\leq41. You can say how close the upper bound is, for example within 3 of the lower bound.

In the practical problem, convert the tour back to the original network by replacing each arc of the complete network by its shortest path. State the final route as a list of vertices, and check its length equals the upper bound.

3636.53737.53838.53939.54040.54141.54242.543lower bound 38upper bound 41
Bounds 38 ≤ shortest tour ≤ 41: the shortest tour lies in the shaded gap.

Bounds equal

  • The tour is optimal

Bounds differ

  • Shortest tour lies between them
Reading the bounds

Upper bound 41 and lower bound 41. What does this tell you?

Try an exam question

A complete network has vertices A, B, C, D and E with AB = 10, AC = 7, AD = 12, AE = 9, BC = 8, BD = 6, BE = 11, CD = 9, CE = 5 and DE = 13. (a) Use the nearest neighbour algorithm, starting at A, to find an upper bound. (b) By deleting A, find a lower bound.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

The nearest neighbour algorithm is applied starting at QQ. Which tour is produced?

1 mark, marked against the mark scheme

Revision notes