Route inspection and travelling salesperson

Route inspection and travelling salesperson

Spec DB3–DB4 · AQA A-Level Further Maths: Revision notes

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.
ABCD
A network in which every node has degree 3, so all four nodes are odd (drawn without weights). 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. 1

    Total weight

    add every arc; list the odd nodes

  2. 2

    Pair the odd nodes

    every possible pairing

  3. 3

    Shortest paths

    for each pair, then add up

  4. 4

    Choose the least

    those paths are repeated

  5. 5

    Length

    total weight + least pairing

Route inspection

Worked example

A network has total weight 53 and exactly two odd nodes, BB and EE. The shortest path from BB to EE is B,C,EB,C,E with length 12. Find the length of the shortest closed route that uses every arc.

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. 1

    A to C

    5

  2. 2

    C to B

    11

  3. 3

    B to E

    4

  4. 4

    E to D

    15

  5. 5

    D back to A

    6

Nearest neighbour from AA: total 41

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 AA to EE have the distances in the table. Use nearest neighbour from AA.

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:

  1. Delete one vertex and its arcs.
  2. Find the minimum spanning tree of the remaining vertices.
  3. 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.

34353637383940414243lower 36upper 41

Worked example

Use the deleted vertex method, deleting BB, with the depots AA to EE from before.

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.

wt 4wt 3wt 5wt 6wt 9ABCD
Roads in km, as labelled (wt = weight, not to scale).

Worked example

Roads ABAB 4, BCBC 3, CDCD 5, DADA 6, BDBD 9 (km). Find the shortest tour.

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. 1

    Build the network model

    nodes, arcs and weights

  2. 2

    Solve it

    apply the algorithm

  3. 3

    Interpret in context

    does the answer make sense?

  4. 4

    Evaluate the assumptions

    weights, direction, constraints

  5. 5

    Refine the model

    change what fails and repeat

Then back to step 1

Modelling is a loop: keep refining until the answer makes sense in context.

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 8080 and four odd nodes AA, BB, CC and DD. The shortest distances between them are ABAB 7, ACAC 9, ADAD 12, BCBC 11, BDBD 8, CDCD 6. Find the length of the shortest closed route that uses every arc at least once.

[4 marks]

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

Revision notes