The travelling salesman problem
Studying this course? Keep your progress in one place.
Key facts
- The travelling salesman problem asks for the shortest tour: a route that visits every vertex and returns to the start.
- In the classical problem each vertex is visited exactly once; in the practical problem vertices may be revisited.
- A complete network with vertices has different tours, so only small networks can be solved by listing.
- The triangle inequality holds when the longest side of every triangle is no longer than the sum of the other two.
- If a vertex has only one arc, no classical tour exists.
The problem and tours
The problem asks for a route of minimum length that visits every vertex and returns to the start. Such a closed walk is called a tour.
The travelling salesman problem (TSP) asks for a route of minimum length that visits every vertex of an undirected network. A walk that visits every vertex and returns to its starting vertex is a tour.
Examples are a delivery driver visiting customers or a drilling machine moving between holes.
No quick method always gives the best tour for a large network, so for exam networks we list tours or find bounds.
- 1
Start
at the depot or first vertex
- 2
Visit every vertex
using the arcs of the network
- 3
Return
to the start vertex to complete the tour
Then back to step 1
What makes a walk a tour?
The classical problem
In the classical problem each vertex is visited exactly once, normally on a complete graph. A complete network with vertices has different tours.
In the classical TSP each vertex is visited exactly once, apart from the start, which is also the finish. A tour that does this is a cycle through all the vertices.
It is normally set on a complete graph, where every pair of vertices is joined by an arc.
A tour and its reverse count as the same tour. For there are 3 tours and for there are 12.
If a vertex has only one arc, no classical tour exists: the tour would have to enter and leave by the same arc.
How many different tours are there in a complete network with 5 vertices?
The practical problem
In the practical problem a vertex may be revisited, which is needed when the network is not complete or a vertex can only be reached through another.
In the practical TSP a vertex may be revisited. A van delivering to shops along a one-road spur must go in and come out again.
If the network is a tree, every arc must be travelled twice, so the shortest tour has length twice the total weight of the arcs.
In general, list sensible tours, add up each total and compare. If a vertex is joined only to by an arc of weight , that arc adds to the tour.
| Classical | Practical | |
|---|---|---|
| Each vertex visited | Exactly once | May be revisited |
| Network | Complete graph | Any connected network |
| Tour is | A cycle through every vertex | Dead ends are allowed |
Classical
- Each vertex visited:
- Exactly once
- Network:
- Complete graph
- Tour is:
- A cycle through every vertex
Practical
- Each vertex visited:
- May be revisited
- Network:
- Any connected network
- Tour is:
- Dead ends are allowed
A network is a tree with total arc weight . What is the length of the shortest tour that visits every vertex and returns to the start?
The triangle inequality
A complete network satisfies the triangle inequality if, in every triangle, the longest side is no longer than the sum of the other two.
This says that going directly between two vertices is never longer than going through a third. Straight-line distances satisfy it.
If a network does not satisfy it, some direct arc is longer than a route through another vertex, so the practical and classical problems can have different answers.
To show it fails, find one triangle where the longest side is greater than the sum of the other two, such as .
- Triangle inequalitylongest side ≤ sum of the other two
A triangle in a network has sides , and . Does it satisfy the triangle inequality?
Finding the shortest tour
List every tour systematically, give each its length as a sum, and choose the shortest.
A complete network with four vertices , , , has three tours starting at : ----, ---- and ----.
For five vertices list the 12 tours by fixing the start, listing orders of the other four vertices and dropping reversals. Always show every tour you considered.
Worked example
Find the shortest tour in the network above.
- 1
----: .
- 2
----: .
- 3
----: .
Which tour in the example has length 95?
Exam skills
State whether the problem is classical or practical, give each tour as a list of vertices ending at the start, and show its length as a sum.
To explain why no classical tour exists, name a vertex that is joined to only one other vertex.
When a new arc is added, find a tour that uses it, write its length with the unknown, and compare with the previous best tour to form an inequality.
- 1
State the problem type
classical (visit each vertex once) or practical (revisits allowed)
- 2
List each tour
as vertices, ending at the start
- 3
Show its length
as a sum of arc weights
- Length of a toursum of its arcs, back to the start
Why does no classical tour exist if a vertex is joined to just one other vertex?
Try an exam question
A complete network has vertices A, B, C and D with AB = 12, AC = 9, AD = 15, BC = 7, BD = 11 and CD = 8. List all the different tours that start and finish at A, give the length of each, and state the shortest.
[4 marks]
- [1]Three tours: ABCDA, ABDCA and ACBDA (a reversed tour is not counted again).
- [1]ABCDA = 12 + 7 + 8 + 15 = 42 and ACBDA = 9 + 7 + 11 + 15 = 42.
- [1]ABDCA = 12 + 11 + 8 + 9 = 40.
- [1]The shortest tour is ABDCA with length 40.
That's the notes covered.
Carry on to the next subtopic.
Try a question
How many different tours are there, starting and finishing at , if a tour and its reverse are counted as the same?
1 mark, marked against the mark scheme
How many different tours are there, starting and finishing at , if a tour and its reverse are counted as the same?
1 mark, marked against the mark scheme