The Classical & Practical Travelling Salesman Problem
What is the Travelling Salesman Problem?
- In the Travelling Salesman Problem, the objective is to find the tour of least weight in a given network
- A tour is a walk that starts at one vertex and visits every other vertex in the network before returning to the start vertex
- The classical travelling salesman problem requires that each vertex is visited exactly once before returning to the start vertex
- The practical travelling salesman problem requires that each vertex must be visited at least once before returning to the start vertex
- There isn't an algorithm that will definitely provide an optimal solution to the travelling salesman problem
- However the methods used will provide a lower and upper bound for the tour of least weight
- If the lower and upper bound happen to be equal, an optimal solution has been found
What is a table of least distances?
- A table of least distances shows the shortest distance between any two vertices in a graph
- In some cases, the direct route between two vertices may not be the shortest
- The table of least distances creates a complete network and so it will contain a Hamiltonian cycle
- The table of least distances turns a practical travelling salesman problem into a classical travelling salesman problem
How do I find the table of least distances?
- In practice, for smaller networks, the values in the table of least distances can usually be found by inspection of the network
- The shortest route between two vertices may not be the most direct route
- A more robust method of finding the shortest routes between pairs of vertices would be to use Dijkstra's or Floyd's algorithm
- An exam question will be clear if this is required but given time constraints this is uncommon
- Mathematically, a table of least distances is created by ensuring every entry satisfies the triangle inequality
- the longest side of a triangle ≤ the sum of the lengths of the other two sides
- ('Sides of the triangle' could be made from one or more edges in a network - there would be lots of them, even in small networks!)
- the longest side of a triangle ≤ the sum of the lengths of the other two sides
- To construct a table of least distances follow the steps below
- STEP 1
Put a line through each cell along the leading diagonal- there will be no loops!
- STEP 2
Fill in the information for a particular vertex in the graph with the distance between that vertex and each vertex that is adjacent to it in the network (i.e. vertices that are directly connected to it) -
-
- At this stage check (by inspection) if the direct connections are actually the shortest distances and change as necessary
-
- STEP 3
Complete the rest of the connections between that particular vertex and the remaining (non-adjacent) vertices in the network by finding the shortest route that can be travelled between each pair
- STEP 4
Copy the values in the completed row down the corresponding column- a complete network is undirected so the table of least distances will have symmetry
- STEP 5
If the table is not complete, return to STEP 2 and continue with the another vertex, otherwise STOP
Exam Tip
- Remember that the table of least values has a line of symmetry along the leading diagonal for an undirected network, so complete one half carefully first, then map over to the second half
Worked example
The network below contains six vertices representing villages and the edges (roads) that connect them. The weighting of the edges represents the time, in minutes, that it takes to walk along a particular road between two villages.
a)
Explain why the network in the diagram is not a complete network.
It is not a complete network as each vertex is not connected to every other vertex by a single edge
e.g., there is no single edge that connects vertices B and D
e.g., there is no single edge that connects vertices B and D
b)
Complete the table of least distances for the network below.
A | B | C | D | E | F | |
A | ||||||
B | ||||||
C | ||||||
D | ||||||
E | ||||||
F |
- STEP 1
Put a line through each cell on the leading diagonal
- STEP 2
Fill in the table with the direct connections from the graph, starting from vertex A- Check that the direct connection is the shortest route in all cases
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | ||
B | - | |||||
C | - | |||||
D | - | |||||
E | - | |||||
F | - |
- STEP 3
Find the shortest routes between vertices A and E, and A and F, then fill these values in the table
AE: ACE = 13
AF: ACEF = 21
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | - | |||||
C | - | |||||
D | - | |||||
E | - | |||||
F | - |
- STEP 4
Complete column A with the values recorded in row A.
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | ||||
C | 7 | - | ||||
D | 11 | - | ||||
E | 13 | - | ||||
F | 21 | - |
- STEP 5
The table is not complete so return to Step 2
- STEP 2
Fill in the table with the direct connections from vertex B
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 13 | 9 | |
C | 7 | - | ||||
D | 11 | - | ||||
E | 13 | - | ||||
F | 21 | - |
- STEP 3
Complete the table with the shortest route between the non-adjacent vertices B and D
BD: BCD = 18
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 18 | 13 | 9 |
C | 7 | - | ||||
D | 11 | - | ||||
E | 13 | - | ||||
F | 21 | - |
- STEP 4
Complete column B with the values recorded in row B
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 18 | 13 | 9 |
C | 7 | 13 | - | |||
D | 11 | 18 | - | |||
E | 13 | 13 | - | |||
F | 21 | 9 | - |
- STEP 5
The table is not complete so return to Step 2
- STEP 2
Fill in the table with the direct connections from vertex C
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 18 | 13 | 9 |
C | 7 | 13 | - | 5 | 6 | |
D | 11 | 18 | - | |||
E | 13 | 13 | - | |||
F | 21 | 9 | - |
- STEP 3
Complete the table with the shortest route between the non-adjacent vertices C and F
CF: CEF = 14
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 18 | 13 | 9 |
C | 7 | 13 | - | 5 | 6 | 14 |
D | 11 | 18 | - | |||
E | 13 | 13 | - | |||
F | 21 | 9 | - |
- STEP 4
Complete column C with the values recorded in row C
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 18 | 13 | 9 |
C | 7 | 13 | - | 5 | 6 | 14 |
D | 11 | 18 | 5 | - | ||
E | 13 | 13 | 6 | - | ||
F | 21 | 9 | 14 | - |
- STEP 5
The table is not complete so return to Step 2
- STEP 2
Fill in the table with the direct connections from vertex D
The direct route between D and F is not the shortest route
DF = 20
DEF = 18
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 18 | 13 | 9 |
C | 7 | 13 | - | 5 | 6 | 14 |
D | 11 | 18 | 5 | - | 10 | 18 |
E | 13 | 13 | 6 | - | ||
F | 21 | 9 | 14 | - |
- STEP 3
There are no non-adjacent vertices for D left to complete
- STEP 4
Complete column D with the values recorded in row D
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 18 | 13 | 9 |
C | 7 | 13 | - | 5 | 6 | 14 |
D | 11 | 18 | 5 | - | 10 | 18 |
E | 13 | 13 | 6 | 10 | - | |
F | 21 | 9 | 14 | 18 | - |
- STEP 5
The table is not complete so return to Step 2
- STEP 2
Fill in the table with the direct connections from vertex E
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 18 | 13 | 9 |
C | 7 | 13 | - | 5 | 6 | 14 |
D | 11 | 18 | 5 | - | 10 | 18 |
E | 13 | 13 | 6 | 10 | - | 8 |
F | 21 | 9 | 14 | 18 | - |
- STEP 3
There are no other connections for vertex E
- STEP 4
Complete column E with the values recorded in row E
- STEP 5
The table is complete so stop
A | B | C | D | E | F | |
A | - | 14 | 7 | 11 | 13 | 21 |
B | 14 | - | 13 | 18 | 13 | 9 |
C | 7 | 13 | - | 5 | 6 | 14 |
D | 11 | 18 | 5 | - | 10 | 18 |
E | 13 | 13 | 6 | 10 | - | 8 |
F | 21 | 9 | 14 | 18 | 8 | - |