Tag Archives: Paper round graph theory

The Paper Round: The Best Route for a Marginal Gain

The current route (blue) is very inefficient because it doesn’t offload papers very quickly. It takes 4 units of distance (hops) to offload just 3 papers, and we still have 3 papers in the bag at H (hop 8) just 2 hops from the finish. If we take advantage of the fact that H is a block of flats where we delivery two papers, and head straight for that delivery (via D) then we can get rid of three papers in just two hops. This is the pink route on the map below.

Paper round best routeFrom H we cycle on to I, where we have a choice of routes to deliver the remaining five papers. Neither loop offloads papers faster than the other, so the decision here should be based on which offloads the heaviest paper/s first. E has the Telegraph, and J the Daily Mail if I recall, so lets take the loop that offloads the Telegraph first.

Bye the time we get to J (hop 8) we have delivered all our papers and have the luxury of cycling the final two hops with a paper free bag.

The marginal gains of the new route are probably best illustrated in a table.

Blue route Papers in bag Pink route Papers in bag
A
B
E
B
C
F
J
I
H
D
H
8
7
6
6
5
4
3
3
1
0
0
A
D
H
I
E
B
C
F
J
I
H
8
7
5
5
4
3
2
1
0
0
0
Hops = 10 Total Papers in bAG =  43 hOPS = 10 Total pAPERS IN BAG = 35

This may not look like a huge advantage, but remember these are the sort of ‘marginal gains’ British Cycling and Team Sky search for in the pursuit of Olympic gold and Tour de France glory. Just steer clear of the TUEs, unless you wake up with a bad cold!

FacebookTwitterGoogle+Share

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.