What is the quickest way to deliver a leaflet to every house on my estate?

Every spring my Scout group raises money by delivering leaflets for a local plant sale, and my patrol is given our own estate: 137 houses on 14 stretches of street. Last year we split up and each walked the streets we thought were nearest, and it took most of a Saturday morning, with some streets done twice and one cul-de-sac missed completely. This year I volunteered to plan the route, and I realised that the problem — walk along every street at least once and return to the start, as quickly as possible — is the Chinese postman problem we met in the graph theory topic.

But the textbook version assumes that walking a street once is enough. On a street with houses on both sides, I either have to cross the road back and forth or walk down one side and back up the other. So the real question is not only which route, but how to walk each street.

Aim. I will (1) model my estate as a weighted graph and find the shortest closed route that covers every street, justifying why it is optimal, (2) see how much an open route (ending somewhere other than home) would save, (3) compare two ways of dealing with streets that have houses on both sides, and find the best combination of them, and (4) test the predicted time against a real delivery.

I drew the estate from an online map and measured each stretch of street between junctions with the map's measuring tool, rounding to the nearest 10 m. Each junction or dead end is a vertex, and each stretch of street is an edge weighted by its length. H is the junction next to my house, where we start and finish. I also counted the houses on each stretch and noted whether they were on one side or both.

Data note: the street network and delivery data in this exemplar are illustrative, created by IB Math Revision; a student must use their own area.

The graph has 10 vertices and 14 edges with a total length of 1780 m. J and K are cul-de-sacs, so they have degree 1. I checked that every edge is the shortest way between its two ends (no street is longer than a detour around it), so the edge weights are also the shortest distances between neighbouring vertices.

Assumptions. Pavements run along every street; the walking distance along a street equals its length; walking speed is constant; every letterbox takes the same time; and there are no one-way restrictions for walkers. I test the effect of the most doubtful of these (the constant times) in Section 7.

To compare pairings I need the shortest distance between every pair of odd vertices. Many of these are not direct streets, so I used Dijkstra's algorithm. Table 2 shows it from C: at each step the unvisited vertex with the smallest temporary label is made permanent and its neighbours' labels are updated.

I repeated this from each odd vertex (and checked the results with a graph-theory package). With six odd vertices there are \(5 \times 3 \times 1 = 15\) possible pairings: A can be paired with any of the other 5, then the first remaining vertex with any of 3, and the last two together.

The best pairing is AB, CJ, GK, adding 600 m, so the shortest closed route is \(1780 + 600 = 2380\) m. My first instinct was to pair the closest odd vertices first: that gives AC, GJ, BK for 900 m, which is 300 m worse. Pairing the closest vertices first uses up the pair AC and leaves the remaining vertices far apart. This is why all 15 pairings have to be checked.

To turn this into a route I added the repeated streets to the graph (now every vertex has even degree) and built an Eulerian circuit starting at H with Hierholzer's method — follow edges until you return to the start, then splice in any unused loops. One such route, of 2380 m, is:

H–B–D–E–G–K–G–F–J–F–E–C–E–F–D–C–A–B–A–H

Checking it edge by edge, it uses every street once, except the repeated ones, which it uses twice, and its length adds up to 2380 m. With 6 odd vertices checking 15 pairings is easy, but the number grows quickly: with \(2k\) odd vertices there are \((2k-1)(2k-3)\cdots 3 \cdot 1\) pairings, which is 945 for 10 odd vertices and over 650 million for 20. A whole town would need a cleverer algorithm than listing them all.

Modelling my estate as a weighted graph with six odd vertices, the shortest closed route covering every street is 2380 m, found by pairing the odd vertices (AB, CJ, GK) using Dijkstra's shortest distances and checking all 15 pairings; pairing the nearest vertices first would have added 300 m. An open route would save only 150 m. The more important decision was how to walk streets with houses on both sides: walking each side separately adds 650 m but, with any crossing slower than about 11 s, is quicker than zig-zagging, and the best street-by-street mix improves on it by only 2.2 minutes. The real delivery took 71 minutes, longer than predicted because letterboxes took longer than I assumed, but the choice of plan did not depend on that.

The main limitations are in the inputs. Street lengths were measured from a map to the nearest 10 m, the “half the houses need a crossing” rule is an average, and the constant walking speed ignores the hill on the way to K. I tested the parameter that mattered most (the crossing time) and found the conclusion robust. The model also assumes one walker: with the whole patrol, the real problem is to split the estate into several routes of similar length that all start at H, which is a much harder problem (a version of the “multiple postmen” problem) that I could only approach by trial and error.

What surprised me most is that the shortest route was not the quickest. The textbook Chinese postman problem minimises distance, but my problem was to minimise time, and making that change is what made the mathematics mine.