Optimal refueling strategy

Question

On the way home from work, I want to refuel my car. There are 5 petrol stations along the way that all have a different price for petrol. I know that the prices will be in the range [A, B], chosen uniformly at random. As I approach a petrol station I see the price of its fuel. At this point, I can either go in and refuel some percentage of my tank, or I can keep driving. Once I've passed a petrol station I cannot go back to it. What should be my strategy to refuel as cheaply as possible in expectation?

This is a real-life puzzle that has been bugging me for years and I would love to know the answer to it. I will accept solutions that refuel at multiple petrol stations as long as the total petrol added is 100%. For example, you could refuel 20% at the first station, 50% at the third station, and 30% at the fourth station. You could of course refuel all 100% at the first station. Note you can assume that the stations are close to each other and the amount of fuel needed to travel between them is insignificant.

Answer 1

Scale [A,B] to [0,1], and buy 100% of your tank from the first station if its price is below 0.2583, then repeat for the remaining stations with limits 0.3047, 0.375, 0.5, and 1.

Solution explanation:

Here is a solution for strategies of a certain form: Before departing, declare a threshold price $T_i$ for each gas station $i \in \{1,2,3,4,5\}$. Upon arriving at station $i$, fill up 100% of the tank if the station's price is less than or equal to $T_i$. What are the optimal thresholds?

I conjecture that a strategy of this form is optimal, as the total cost we are optimizing is linear with respect to the price you end up paying. As such, I don't see any reason why you would ever do a partial fillup. If we were optimizing a nonlinear function, like the utility of your money, or the probability that you would spend less than some bound, then I could see reasons for a partial fill.

Assume each station's price $P_i$ is uniformly distributed on $[0,1]$ (for simplicity, this will be the price to fill up the entire tank, and can be scaled to $[A,B]$ at the end). We also must enforce $T_5 = 1$ to ensure that the tank is eventually full. Then, the expected cost of the fillup is

$E[Cost] = \sum_{i=1}^5E[P_i$ assuming $P_i \leq T_i]*Prob(P_i \leq T_i)*Prob(P_j > T_j$ for all $j < i)$.

Given that all prices are uniformly distributed (and assuming all thresholds are in $[0,1]$), we can write $Prob(P_i \leq T_i) = T_i$ and $E[P_i$ assuming $P_i \leq T_i]=\frac{T_i}{2}$. Then, the expected cost is

$E[Cost] = \left[T_1^2 + T_2^2(1-T_1)+T_3^2(1-T_1)(1-T_2)+T_4^2(1-T_1)(1-T_2)(1-T_3)+(1-T_1)(1-T_2)(1-T_3)(1-T_4)\right]*\frac{1}{2}.$

This is a function of four variables, and I used Wolfram Alpha to compute the local minimum. It returned

min{T_1^2 + T_2^2 (1 - T_1) + T_3^2 (1 - T_1) (1 - T_2) + T_4^2 (1 - T_1) (1 - T_2) (1 - T_3) + (1 - T_1) (1 - T_2) (1 - T_3) (1 - T_4)} = 483008799/1073741824 at (T_1, T_2, T_3, T_4) = (8463/32768, 39/128, 3/8, 1/2)

Therefore, you would expect to pay $\frac{483008799}{1073741824}*\frac{1}{2} \approx 0.2249$ on average using thresholds $(\frac{8463}{32768}, \frac{39}{128}, \frac{3}{8}, \frac{1}{2}, 1) \approx (0.2583, 0.3047, 0.375, 0.5, 1).$

To scale prices to $[A,B]$, multiply each value by $(B-A)$ and add $A$.

Answer 2

I think this is more of a Mathematical problem than a puzzle, and one possible solution (for a single refuel) is:

viewing it as an instance of the Secretary Problem, which suggests that the best strategy would be: always reject the first 2 stations, and then refuel in the next one that is the cheapest so far, resulting in a 43,3% chance of getting the cheapest gas in your route.

More about the solution:

The original problem is about an administrator who needs to hire the best secretary of n applicants, but they need to decide right after the interview if they will or will not hire the person, without the possibility to call an earlier applicant. There is a nice video from Numberphile about that problem, if you want a better and more visual explanation.

Answer 3

For simplicity, assume that [A,B] = [0,1] and that the price of a full tank is 1. It is easy to rescale at the end.

1. Assume there is only one station. The expected price is $\int_0^1 x dx = {^1/_2}$.

2. Assume there are 2 stations. The price in the first is $x$ and you fill $p$. The expected price is $px + (1-p){^1/_2} = {^1/_2} + p(x-{^1/_2})$. If $x \le {^1/_2}$ this is minimized by $p = 1$, and if $x > {^1/_2}$ by $p = 0$. Therefore the expected price is ${^1/_2} {^1/_4} + {^1/_2} {^1/_2} = {^3/_8}$ (the first halves are the probabilities of x being below/above half, the other term is the expected price on this event.)

3. Similarly, if the expected price for n stations is $Z_n$ then the expected price for $n+1$ stations is $Z_{n+1} = Z_n \times {^{Z_n}/_2} + (1-Z_n) \times Z_n = \frac{Z_n (2-Z_n)}{2}$

This simple formula gives $\frac{39}{128}, \frac{8463}{32768}, \frac{483008799}{2147483648}$ for 3, 4 and 5 stations, and one can easily extend to any number of stations.