The Fareham agentMost urgent first, or nearest first?
Thirty post boxes, thirty collection times, and an agent on foot that can only be in one place at once.
One OpenStreetMap query returns 87 post boxes in a rectangle around Fareham, together with the road network, 410.5 km in its largest connected part. Volunteers have tagged 67 of the boxes with a weekday collection time: 37 at 09:00 and 30 in the afternoon, between 16:00 and 18:30. The other 20 have no time recorded. The project uses the 30 afternoon boxes as a list of errands with deadlines, and invents an agent to do them: it sets off from the middle of West Street, walks along roads at 4.5 km/h and spends a minute at each box. The boxes are real and so are the times on the map; the agent and its walk are a simulation, and footpaths are not in the network, so real walks could be shorter.
Earliest deadline first, EDF, always heads for the box whose collection is soonest. Liu and Layland showed in 1973 that this is an optimal rule for scheduling jobs on one processor, where switching between jobs is free. Nearest-first ignores deadlines entirely and walks to the closest unvisited box. Two more careful versions look before they leap: each one only considers boxes it can still reach before their collection, then chooses either the nearest or the most urgent of those. As a yardstick the learner also runs 20,000 randomised versions of the careful agent and keeps the highest score, which is not proven to be the true maximum.
Post boxes reached before collection, out of 30 (late arrivals in brackets), our simulation| Setting off at | Nearest first | Earliest deadline first | Nearest still reachable | Most urgent still reachable | Top score in 20,000 tries |
|---|
| 14:00 | 15 (4 late) | 2 (5 late) | 16 | 10 | 17 |
| 15:00 | 10 (7 late) | 2 (3 late) | 12 | 10 | 13 |
| 16:00 | 7 (7 late) | 0 (3 late) | 9 | 9 | 10 |
Plain EDF is the worst agent on the list. The earliest deadlines belong to boxes scattered across the town, from 40 metres to more than 5 km from the start, so chasing them in order means criss-crossing Fareham and arriving late almost everywhere; setting off at 15:00 it makes 2 collections in time and walks 16.36 km. The domino effect is the lesson: once an EDF agent falls behind, every job it tries is already late, and it keeps trying. Filtering out boxes it can no longer reach fixes the lateness but not the zig-zag, which is why the reachable nearest-first agent does better than the reachable deadline-first one. The winning idea is to take deadlines seriously without letting them decide the route alone.
Ages 8 to 11
Plan a paper route to five marked points, each with a time on it, and see which order works.
Ages 11 to 15
Write the nearest-first and deadline-first rules in Python on a small made-up map.
Ages 15 and up
Run all four agents on the Fareham network, then design a fifth that beats them.
Sources and caveats
Post box positions, collection time tags and roads are from OpenStreetMap contributors under the Open Database Licence, read with one Overpass query on 1 October 2026. We did not check the tags against the plates on the boxes, so some may be out of date. The walking agent, its speed and the one-minute stops are our assumptions, and every count comes from our own Python.
