The Travelling Salesman problem
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.
| Classical | Practical | |
|---|---|---|
| Each vertex visited | Exactly once | At least once |
| Network | Complete, triangle inequality | Need not be complete |
| Arcs and vertices repeated | No repeats | Repeats if needed |
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.
Worked example
Roads , and . What weight is used for arc in the complete network?
- 1
Direct road to : 11.
- 2
Route through : .
- 3
The smaller value is the least distance.
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 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
Choose a start vertex
mark it as visited
- 2
Go to the nearest unvisited vertex
add the arc to the tour
- 3
Repeat
until every vertex is visited
- 4
Return to the start
add the final arc; the total is an upper bound
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:
- Delete one vertex and all arcs joined to it.
- Find the weight of the minimum spanning tree of the remaining vertices.
- 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
Delete a vertex
remove it and its arcs
- 2
Minimum spanning tree
of the remaining vertices
- 3
Add two shortest arcs
the two shortest at the deleted vertex
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 . If the lower bound is 64 and the best upper bound is 66, then .
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.
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?
- 1
Upper bound from the tour: 66.
- 2
Lower bound: .
- 3
Combine them as an interval.
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 has length 56 km. Deleting leaves a minimum spanning tree of weight 38 km, and the two shortest arcs at 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]
- [1]Adds the minimum spanning tree weight and the two shortest arcs at : .
- [1]Lower bound is 54 km.
- [1] (km).
- [1]The shortest tour cannot be longer than a tour that has been found.
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
Using the nearest neighbour algorithm starting at A, which town is visited immediately after E?
1 mark, marked against the mark scheme