Route inspection and travelling salespersonAQA A-Level Further Maths: Revision notes

In a route inspection problem (the Chinese postman problem) every arc of a network 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.

• All nodes even: the network is Eulerian; a closed route using each arc exactly once exists, so the length is the total weight.
• Exactly two odd nodes: the network is semi-Eulerian; a route using each arc once starts at one odd node and finishes at the other.
• Otherwise some arcs must be repeated.

To find the shortest closed route:

1. Find the total weight of all arcs and the odd nodes.
2. Pair up the odd nodes in every possible way: 2 odd nodes have 1 pairing, 4 have 3 pairings, 6 have 15.
3. For each pairing, find the shortest path between the nodes in each pair, and add them.
4. Choose the pairing of least total. Those paths are repeated.
5. Length = total weight + least pairing. Example: odd nodes $B$ and $E$ with shortest path $B,C,E=12$ in a network of total 53 give $53+12=65$. 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.

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 that visits each node once and returns gives an upper bound for the shortest tour. Nearest neighbour algorithm: start at a node; repeatedly go to the nearest unvisited node; finally return to the start. Example (depots $A$ to $E$): from $A$: $AC$ 5, $CB$ 11, $BE$ 4, $ED$ 15, $DA$ 6 gives an upper bound of $41$. The shortest tour may be shorter (here it is 37), so nearest neighbour only gives an upper bound.

To find a lower bound for the shortest tour:

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 (a spanning tree), 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. Example: delete $B$: MST of $A,C,D,E$ is $5+6+13=24$; two shortest arcs at $B$ are $4+8=12$; lower bound $36$. Different deleted vertices give different bounds; the largest is the best. Together with the upper bound: $36\le\text{shortest tour}\le41$. If the bounds are equal, that tour is optimal.

In the practical problem the network need not be complete and nodes may be visited more than once. To convert it to a 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 back in the original network. Example: roads $AB$ 4, $BC$ 3, $CD$ 5, $DA$ 6, $BD$ 9. Shortest distances: $BD=8$ via $C$ and $AC=7$ via $B$. The shortest tour is $A,B,C,D,A$ with length 18 km. Where a shortest distance passes through another node, that node is visited again in the practical route.

A network model is a simplification, and you may be asked to evaluate, modify and refine it. Questions to ask:

• Are the weights realistic? Replace distances with times or costs if speeds differ, or add stopping times at nodes.
• Are the arcs two-way? One-way streets need a directed network.
• Does the answer meet real constraints (time windows, vehicle capacity, finishing point)? Adjust the model, for example by splitting the job between several vehicles.
• Is the route necessary? In route inspection, repeated arcs are driven but not inspected, and the inspector may not need to return to the start, which removes a repeated path.
• Is the solution the optimum or only a bound? Nearest neighbour is not optimal, so test improvements. Always check the final answer makes sense in context.