The Paper Round: A Real World Exercise in Computational Thinking

Paper bag While doing my stepson’s paper round for him this morning, I couldn’t help but think the end part of the round seemed a bit inefficient.

Surely we can shave some time off the round by delivering these papers in a different order I thought. A little computational thinking (graph theory in this case) will reveal a shorter route is possible…

…so I drew a map (graph) of the current route, labelling the road junctions and mid points (called nodes or vertices in graph theory) A to J and marking the houses where papers are delivered with an X.

Paper round graph

The route must start at node A (there are papers to deliver just before we reach A) and finish at node H (the closest point to home).

The current route (blue arrows) A – B – E – B – C – F – J – I – H – D -H  has a total distance of 10 units, assuming the distance between each node is the same, which give or take a few metres it is. But I can’t beat 10 units!!! There is no shorter route.

But is there a marginal advantage to be gained by delivering the papers in a different order?

Given that newspapers are very heavy these days (especially on a Saturday and Sunday) which route minimises the number of papers in the bag and allows me (or my stepson) to cycle that bit faster? Can you prove which route is best? We always start with 8 papers at node A.


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>