What is the fastest route to drop off weight when time is proportional to weight x distance?

Question

You have a lorry at the starting point which is carrying all the parcels for the day.

$$\rm Time\ taken = Total\ Lorry\ Weight \times Distance\ travelled $$

After visiting each zone you have to return to the starting point.

Lorry's weight is $30$. You must take all undelivered parcels with you on every trip. Your fuel has no weight, your fuel is everlasting and you lose no time when dropping off packages.

What is the optimal route to delivering all the packages and returning to the starting point?

---

My initial thoughts for solving this was to work backwards and work out which delivery would add the smallest amount of total time across the whole journey. Then repeat this until I got to the first stop.

I have been told that isn't the correct way to work this out so not sure what would make the route I got for that more optimal.

Answer 1

This is not an answer as I can't prove it, but perhaps others can (or show the error of my ways).

If all parcels weighed the same, the optimal strategy would be to unload the nearest parcels first. This means we could rank the zones to visit first by ranking them by their distance $d$, i.e. rank $r=d$.

If all distances were the same, the optimal strategy would be to unload the heaviest parcels first. This means we could rank the zones to visit first by ranking them inversely by their weight $w$, i.e. $r=\frac{1}{w}$.

Putting these two observations together, it would seem a good first approximation would be to rank zones according to $r=\frac{d}{w}$. If I do this, then computer simulation shows this gives exactly the optimal route for the first $2$ zones, the first $3$ zones, etc up to the first $6$ zones (after which my recursive algorithm encountered overflow).

It seems to me then that a simple ranking of the zones by $r=\frac{d}{w}$ will give the optimal route.

EDIT

Changed my simulation from recursive to non-recursive and found the answer holds up to at least $8$ zones.

EDIT2

Improved simulation shows it works for $11$ zones. I'm convinced. :) It only remains to prove it will always work.

Answer 2

The answer by @Jens is correct: it is sufficient to rank the zones by means of $\frac dw$ from lowest to highest and follow this order.

Let us compare two different orders of delivery that differ just by a swap in two consecutive destinations. So suppose that in the first case at a certain point you serve zone A at distance $d$ and weight $w$, and immediately after you serve zone B at distance $d'$ and weight $w'$. In the second case you reverse the order of these two destinations. The cost for the other zones is the same in the two cases, so it is sufficient to compare the costs of these two. Say that before serving zone A you have weight W. Then the cost in the first case is $$C_1=Wd+(W-w) (d+d') +(W-w-w')d'.$$ In the second case the cost is $$C_2=Wd'+(W-w')(d+d')+(W-w-w')d.$$ Then $$C_1\leq C_2\iff -2wd'\leq - 2w'd\iff \frac{d}{w} \leq \frac{d'} {w'}. $$ Since through consecutive swapping we can reach any permutation then we can lower the cost until we reach the desired increasing order, when we can not decrease anymore.