Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following problem is about optimization. It is not a homework, but rather a natural question to ask to oneself afterwards. Here it is.

Consider a road of length $L$ between two cities $A$ and $B$. Whenever a car runs out of fuel on this road, the distance between the car and the city $A$ is uniformely distributed on the interval $[0,L]$. There are three gas stations on the road. Now the question of the exercise is to compare two different distributions of the set of gas stations along the road. The first distribution is to put a station in A, another at distance $L/2$ from $A$ and the third in $B$. The second distribution is to put the stations at distance $L/4$, $L/2$ and $3L/4$.

Clearly the second distribution is better. However, the reference (from which I took the exercise) admits that the second distribution is not optimal!

Question: Given $n$ gas stations, where to place them on the road is such a way that the expectancy of the distance from one station to the place of breakdown is minimal?

share|improve this question
    
@ Didier: 'Whenever a car runs out of fuel on this road, the distance between the car and the city A is uniformely distributed on the interval [0,L].' –  Thomas Connor May 5 '11 at 20:21
    
This appears to be the continuous, one-dimensional, Fermat-Weber problem. For lots of generalization, check out this paper: arxiv.org/abs/cs.CG/0310027 –  Matthew Conroy May 5 '11 at 22:48

4 Answers 4

up vote 3 down vote accepted

Adding on Matthew Conroy's answer (my answer was composed completely independently, and gives exactly the same result).

We consider the case $n=3$, $L=1$. So, subject to $0 \leq x_1 < x_2 < x_3 \leq 1$, we want to minimize $$ \int_0^{x_1 } {(x_1 - u)\,du} + \int_{x_1 }^{\frac{{x_1 + x_2 }}{2}} {(u - x_1 )\,du} + \int_{\frac{{x_1 + x_2 }}{2}}^{x_2 } {(x_2 - u)\,du} $$ $$ + \int_{x_2 }^{\frac{{x_2 + x_3 }}{2}} {(u - x_2 )\,du} + \int_{\frac{{x_2 + x_3 }}{2}}^{x_3 } {(x_3 - u)\,du} + \int_{x_3 }^1 {(u - x_3 )\,du} , $$ or, after obvious change of variables, $$ \int_0^{x_1 } {u\,du} + \int_0^{\frac{{x_2 - x_1 }}{2}} {u\,du} + \int_0^{\frac{{x_2 - x_1 }}{2}} {u\,du} + \int_0^{\frac{{x_3 - x_2 }}{2}} {u\,du} + \int_0^{\frac{{x_3 - x_2 }}{2}} {u\,du} + \int_0^{1 - x_3 } {u\,du}, $$ that is, $$ \frac{{x_1^2 }}{2} + \frac{{(x_2 - x_1 )^2 }}{4} + \frac{{(x_3 - x_2 )^2 }}{4} + \frac{{(1 - x_3 )^2 }}{2}. $$

share|improve this answer
    
Note that the last expression is denoted $E$ in Matthew Conroy's answer. –  Shai Covo May 5 '11 at 21:16
    
Also note that my derivation begins with an application of the law of total probability, conditioning on the location which is uniform$(0,1)$. –  Shai Covo May 5 '11 at 21:32

Here is how to solve the $n=3$ case.

I'll assume L=1.

Let $x_1 < x_2 < x_3$ be the locations of the three stations. Then there are six intervals to consider for the location of a fuel-less car: $(0,x_1),(x_1,(x_1+x_2)/2),((x_1+x_2)/2,x_2),(x_2,(x_2+x_3)/2),((x_2+x_3)/2),x_3),$ and $(x_3,1)$.

In each of these intervals, it is clear which point $x_1, x_2$ or $x_3$ is nearest, and it is easy to determine both the probability that the car is in the interval, and what the expected distance to the nearest station is. The result is that the expected distance $E$ to the nearest station can be expressed as $$ 2 E=x_1^2+\left( \frac{x_1+x_2}{2} - x_1\right)^2 +\left( x_2 - \frac{x1+x2}{2}\right)^2 + \left( \frac{x_2+x_3}{2}-x_2 \right)^2 $$ $$+ \left( x_3 - \frac{x_2+x_3}{2}\right)^2 + (1-x_3)^2$$ $$=\frac{3}{2}x_1^2-x_1 x_2 + x_2^2 - x_2 x_3 + \frac{3}{2} x_3^2 -2 x_3+1$$ Applying usual optimization techniques to this we find the minimum $E$ occurs with $x_1=\frac{1}{6}, x_2=\frac{1}{2},$ and $x_3=\frac{5}{6}$.

share|improve this answer
1  
The argument can be extended to show the stations should go at $\frac{2k+1}{2n}$ for $k \in [0,n-1]$. Basically you want to minimize the maximum distance to walk. –  Ross Millikan May 5 '11 at 20:56
1  
Obvious generalization time: for $k$ stations, I'm guessing that the optimal locations are at $1/(2k), 3/(2k), \ldots, (2k-1)/(2k)$, by this same proof but with more variables. –  Michael Lugo May 5 '11 at 20:57
    
That is, what Ross said. –  Michael Lugo May 5 '11 at 20:57

Divide the road into $n$ equal intervals, and put a petrol station at the centre of each interval. To see that this is optimal, you need two lemmas:

Lemma 1: Given three consecutive petrol stations $X,Y,Z$, if we fix the positions of $X$ and $Z$ then the unique optimal position of $Y$ is half-way between $X$ and $Z$.
Lemma 2: If we fix the position of the second petrol station $S$ (from city $A$), then the unique optimal position of the first petrol station $F$ is one-third of the way from $A$ to $S$.

You can prove these by using Matthew Conroy's method.

share|improve this answer

For the general case, you can show that:

  1. in an interval with no stations at either end, the optimal position of a single station is in the middle (you only need to know this if $n=1$);
  2. in an interval with a station at each end, the optimal position of a single station is in the middle (Matthew Conway's answer shows this for the middle station);
  3. in an interval without a station at one end but with a station at the other, the optimal position of a single station is a third of the way along from the end with no station (Matthew Conway's answer also shows this for the other two stations).

So with $n$ stations placed in an interval of length $L$ with no stations at either end, the optimal positions are at

$$\frac{1}{2n}L, \frac{3}{2n}L, \frac{5}{2n}L, \ldots , \frac{2n-1}{2n}L.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.