Bounds for the travelling salesman problem
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.
A tour of length exists, and the lower bound is . 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.
Worked example
Find the shortest distance for each pair of vertices not joined by a road.
- 1
, via .
- 2
, via and .
- 3
, via .
- 4
, via .
- 5
, via .
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
Start
choose a starting vertex
- 2
Move
go along the shortest arc to a vertex not yet visited
- 3
Repeat
until all vertices are visited
- 4
Return
go back to the start vertex
Worked example
A complete network has , , , , , , , , , . Find the tour from by nearest neighbour.
- 1
From , the nearest vertex is ().
- 2
From , the nearest unvisited vertex is ().
- 3
From , the nearest unvisited vertex is ().
- 4
From , go to (), then return to ().
Nearest neighbour from gives a tour of length , and from gives . 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 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.
- Walk round a minimum spanning tree weight of the tree
Worked example
A minimum spanning tree is the path ---- with arcs , , , , and . Find an upper bound.
- 1
The tree has weight , so going round it gives a walk of length .
- 2
Going out along the path ends at . Instead of retracing the path back to , take a shortcut straight from to ().
- 3
The tour is -----.
A minimum spanning tree has weight . 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 with all its arcs, find a minimum spanning tree of the remaining vertices, and add the two shortest arcs at .
This works because every tour has two arcs at , 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.
- Lower boundMST of the rest + two shortest arcs at the deleted vertex
Worked example
In the same network, and are the two shortest arcs at . Find the lower bound by deleting .
- 1
Delete and all its arcs.
- 2
The minimum spanning tree on , , , has arcs , and , with weight .
- 3
Add the two shortest arcs at : and .
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 . 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.
Bounds equal
- The tour is optimal
Bounds differ
- Shortest tour lies between them
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]
- [1]Nearest neighbour gives the tour A-C-E-B-D-A.
- [1]Length 7 + 5 + 11 + 6 + 12 = 41, so an upper bound is 41.
- [1]Minimum spanning tree of B, C, D and E: CE 5, BD 6 and BC 8, total 19.
- [1]Add the two shortest arcs at A (7 and 9): lower bound 19 + 16 = 35.
That's the notes covered.
Carry on to the next subtopic.
Try a question
The nearest neighbour algorithm is applied starting at . Which tour is produced?
1 mark, marked against the mark scheme
The nearest neighbour algorithm is applied starting at . Which tour is produced?
1 mark, marked against the mark scheme