5
$\begingroup$

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?

enter image description here


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.

$\endgroup$
4
  • $\begingroup$ I think the weight of the lorry itself is irrelevant since it must travel a round trip to each zone independent of the order of the zones. That said, I suspect there is no straightorward algorithm. You'll need something like backtracking: en.wikipedia.org/wiki/Backtracking (I hope I am wrong and someone contributes a good answer for you.) $\endgroup$ Commented Dec 17, 2018 at 16:02
  • $\begingroup$ I understand the optimization problem, but "time" sounds like the wrong name for what you want optimize. The lorry will just creep along at the start of the day. Fuel consumption is more likely to be proportional to that product. The fuel weight will be (essentially) constant for an electric lorry. $\endgroup$ Commented Dec 17, 2018 at 16:27
  • $\begingroup$ @EthanBolker I have added the fuel to be everlasting, as the point is fuel is not a factor to be concerned with. $\endgroup$
    – Ben Franks
    Commented Dec 17, 2018 at 16:29
  • $\begingroup$ I understand that fuel is not a factor. What looks unreasonable to me is that equation for time, which (in real life) isn't close to proportional to weight. Of course the optimization question is independent of what you call that quantity. $\endgroup$ Commented Dec 17, 2018 at 16:31

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for your proof! I gave it a (+1) about a week ago, but was too distracted at the time to make a comment. Thanks again. $\endgroup$
    – Jens
    Commented Jan 28, 2019 at 2:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .