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

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.


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.

Tags:

Graph Theory

Combinatorics

Optimal Transport

Related

$\operatorname{Aut} (G)$ is isomorphic to $\operatorname{Aut} (H)$ then is it necessary that $G$ is isomorphic to $H$? Inverse Limit of Dense Subsets is Dense Find locus of points by finding eigenvalues Does a family of linearly independent injective maps have a vector with linearly independent images? Why my process is wrong:-How many ways are there to choose $5$ questions from three sets of $4$, with at least one from each set? Probability that random walk will reach state $k$ for the first time on step $n$ Continuous bijection between compact and Hausdorff spaces is a homeomorphism Given a trapezoid with base $AD$ larger than side $CD$. The bisector of $\angle D$ meets $AB$ at $K$. Prove $AK > KB$ Seeking Methods to solve $\int_{0}^{\infty} \frac{e^{-x^n}}{x^n + 1}\:dx $ $\int_{0}^{\infty} \frac{1}{1 + x^r}\:dx = \frac{1}{r}\Gamma\left( \frac{r - 1}{r}\right)\Gamma\left( \frac{1}{r}\right)$ Methods to solve $\int_{0}^{\infty} \frac{e^{-x^2}}{x^2 + 1}\:dx$ What are the foundations of probability and how are they dependent upon a $\sigma$-field?

Recent Posts