Route inspection and travelling salesperson
Studying this course? Keep your progress in one place.
Key facts
- Route inspection: traverse every arc and return to the start with least length; repeat arcs only between odd nodes.
- Length of the shortest closed route = total weight + the least pairing of odd nodes.
- The travelling salesperson problem asks for the shortest tour visiting every node once.
- Nearest neighbour gives an upper bound; the deleted vertex method gives a lower bound.
- The practical problem allows nodes to be revisited, using shortest distances.
Route inspection: the problem
The number of odd nodes decides: none or two means each arc can be used once, otherwise some arcs must be repeated.
In a route inspection problem (the Chinese postman problem) every arc must be traversed at least once, and the route returns to its start, with least total length.
The degree of a node is the number of arcs meeting it, and the number of odd nodes is always even.
- If all nodes are even the network is Eulerian.
- If exactly two nodes are odd it is semi-Eulerian: the route starts at one odd node and finishes at the other.
- Otherwise some arcs must be repeated.
| 0 odd nodes | 2 odd nodes | 4 or more odd nodes | |
|---|---|---|---|
| Type | Eulerian | Semi-Eulerian | Neither |
| Route using each arc once | Closed, so length is the total weight | From one odd node to the other | Some arcs must be repeated |
0 odd nodes
- Type:
- Eulerian
- Route using each arc once:
- Closed, so length is the total weight
2 odd nodes
- Type:
- Semi-Eulerian
- Route using each arc once:
- From one odd node to the other
4 or more odd nodes
- Type:
- Neither
- Route using each arc once:
- Some arcs must be repeated
A network has five nodes of degree 3, 4, 3, 2 and 2. How is it classified?
Solving route inspection problems
Pair up the odd nodes, repeat the shortest paths in the cheapest pairing, and add them to the total weight.
Find the total weight of all arcs and the odd nodes. Pair up the odd nodes in every possible way: 2 odd nodes have 1 pairing, 4 have 3, 6 have 15.
For each pairing, find the shortest path between the nodes in each pair, and add them. Choose the least total. These paths are the repeated paths.
- 1
Total weight
add every arc; list the odd nodes
- 2
Pair the odd nodes
every possible pairing
- 3
Shortest paths
for each pair, then add up
- 4
Choose the least
those paths are repeated
- 5
Length
total weight + least pairing
Worked example
A network has total weight 53 and exactly two odd nodes, and . The shortest path from to is with length 12. Find the length of the shortest closed route that uses every arc.
- 1
Only one pairing exists: with .
- 2
Its shortest path is , so these arcs are repeated.
- 3
Length = total weight + repeated path .
Start and finish at different nodes: the start and finish must be two odd nodes, and only the shortest path between the other odd nodes is repeated. With four odd nodes, repeat the smallest shortest distance between a pair of odd nodes and start and finish at the other two.
A network has 6 odd nodes. How many ways are there to pair them up?
Travelling salesperson and upper bounds
The problem seeks the shortest tour through every node; any tour, such as one from nearest neighbour, is an upper bound.
The travelling salesperson problem (TSP) asks for the shortest route that visits every node and returns to the start.
In the classical problem each node is visited exactly once and the network is complete (every pair joined). Any tour gives an upper bound for the shortest tour.
The nearest neighbour algorithm: start at a node, repeatedly go to the nearest unvisited node, then return to the start.
- 1
A to C
5
- 2
C to B
11
- 3
B to E
4
- 4
E to D
15
- 5
D back to A
6
| From A | From B | From C | From D | |
|---|---|---|---|---|
| to B | 8 | – | – | – |
| to C | 5 | 11 | – | – |
| to D | 6 | 9 | 12 | – |
| to E | 13 | 4 | 13 | 15 |
From A
- to B:
- 8
- to C:
- 5
- to D:
- 6
- to E:
- 13
From B
- to B:
- –
- to C:
- 11
- to D:
- 9
- to E:
- 4
From C
- to B:
- –
- to C:
- –
- to D:
- 12
- to E:
- 13
From D
- to B:
- –
- to C:
- –
- to D:
- –
- to E:
- 15
Worked example
Depots to have the distances in the table. Use nearest neighbour from .
- 1
From the nearest unvisited depot is : 5.
- 2
Then : 11.
- 3
Then : 4.
- 4
Then : 15.
- 5
Return to : 6.
The nearest neighbour algorithm gives a tour of length 41. What can you say about the shortest tour?
Lower bounds: deleted vertex method
Delete a vertex, find the MST of the rest, then add the two shortest arcs at the deleted vertex.
For a lower bound:
- Delete one vertex and its arcs.
- Find the minimum spanning tree of the remaining vertices.
- Add the two shortest arcs from the deleted vertex.
This works because the optimal tour minus the deleted vertex is a path, at least as heavy as the MST, and the tour uses two arcs at the deleted vertex, each at least as long as the two shortest. Different deleted vertices give different bounds; the largest is the best.
Worked example
Use the deleted vertex method, deleting , with the depots to from before.
- 1
Delete . The MST of has weight .
- 2
The two shortest arcs at are .
- 3
Lower bound .
Several vertices are deleted in turn, giving lower bounds of 34, 36 and 35. Which do you quote?
The practical travelling salesperson problem
Replace each arc by the shortest distance between its nodes, solve the classical problem, then interpret back in the real network.
In the practical problem the network need not be complete and nodes may be visited more than once.
To convert it to the classical problem, replace each arc by the shortest distance between the nodes (using other nodes if needed) to form a complete network, solve it, then interpret the result in the original network.
Worked example
Roads 4, 3, 5, 6, 9 (km). Find the shortest tour.
- 1
Shortest distances: via (shorter than the direct 9), and via .
- 2
Tour : .
- 3
Other tours are longer: and .
In the practical problem, why do we replace each arc by the shortest distance between its nodes?
Evaluating and refining network models
A network model simplifies reality, so check its assumptions and change the model where they fail.
You may be asked to evaluate, modify and refine a model. Ask:
- Are the weights realistic? Use times or costs if speeds differ, or add stopping times.
- Are arcs two-way? One-way streets need a directed network.
- Does the answer meet real constraints (time windows, vehicle capacity, finishing point)?
- In route inspection, repeated arcs are driven but not inspected, and the inspector may not need to return to the start.
- Is the solution optimal or only a bound?
Always check the final answer makes sense in context.
- 1
Build the network model
nodes, arcs and weights
- 2
Solve it
apply the algorithm
- 3
Interpret in context
does the answer make sense?
- 4
Evaluate the assumptions
weights, direction, constraints
- 5
Refine the model
change what fails and repeat
Then back to step 1
If the model assumes
- Distance is time
- Arcs are two-way
- One vehicle
- Return to the start
Refine by
- Using times or costs
- Using a directed network
- Splitting the job between vehicles
- Dropping the repeated path
A delivery network uses distances, but one road is much slower than the others. How would you refine the model?
Try an exam question
A network has total weight and four odd nodes , , and . The shortest distances between them are 7, 9, 12, 11, 8, 6. Find the length of the shortest closed route that uses every arc at least once.
[4 marks]
- [1]The three pairings are and , and , and .
- [1]Totals: , , .
- [1]The least is , so and are repeated.
- [1]Length .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which nodes have odd degree?
1 mark, marked against the mark scheme
Which nodes have odd degree?
1 mark, marked against the mark scheme