Travelling with the most efficient path

Question

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time.

The problem is: you have to travel $1000$ km. The only gas station is at the starting point. Your maximum fuel tank capacity is just enough for $50$ km traveling, you are allowed to "bury" fuels in the middle of the journey and save it for later.

For example you can travel $20$ km first, and bury $10$ km worth of fuel there, and then go back to refuel, so next time you can retrieve the $10$ km fuels you left and reach further with it.

You need to find the most efficient way to reach the destination.

What I thought of is using dynamic programming, however you have to assume the distance you travel before each time you do refueling is an integer in terms of kilometers, else you it is hard to do it with DP, I have not try linear programming yet, but I think it is possible.

Do you have any idea how to do it? Or any hints?

Most importantly what type of cs problem is it? is it NP hard? Is it solvable by machine or is it more of a mathematical problem?

Some more thoughts:

• Since it is a continuous path, asking whether if it is NP might be bit silly, but I am still very curious.
• $1000$ and $50$ might be deliberately picked to avoid complex computation.
• Is there a greedy solution? I cannot think of any just yet.
• I now think it more of a mathematical pattern finding problem, though my friend claims it is a cs problem, so I am decide to keep this post.

And if you have any scientific articles or textbooks related to this please tell me, I do not know where to start in the first place.

Answer 1

The basic idea is to make $n$ trips, returning to the start and refueling on all but the last trip. On each trip but the last, you'll leave some fuel at a new dump. You want to know how far you can go on the last trip. To make calculations easy, we'll say that a full tank contains 1 (unit) of fuel and that amount will take you a distance of 1 (other unit) of distance.

Example 1 ($n = 1$ trip). Trivial: drive until you run out of fuel. Distance covered $D(1)=1$.

Example 2 ($n=2$). On the first trip, travel $x$ distance, so you'll have $1-x$ fuel remaining. Leave just enough fuel at dump 1 to allow you to return to the start. Leaving $1-2x$ at dump 1 will do the trick. On the second trip, starting with a full tank, go to the first dump (using $x$ of your fuel), top off your tank (taking $x$ from the dump, leaving $1-3x$) and drive until you run out of fuel. To maximize the distance we'll need the dump to be empty so $1-3x=0$, so $x=1/3$. The total distance you'll cover will be $D(2)=1+1/3$.

The general case. With $n$ trips, you'll hit dump 1 $2n-1$ times, dump 2 $2n-3$ times, dump 3 $2n-5$ times, and so on. To empty the dumps on the last trip, we'll place dump 1 at a distance $1/(2n-1)$, dump 2 at a further distance $1/(2n-3)$, and so on. Then the last trip will cover $$ D(n) = 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1} $$ If we define the $m$-th harmonic number, $$ H_m=1 + \frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5} + \dotsm + \frac{1}{m} $$ then it's well known that $H_m\approx\ln m$ and we can write our distance $$\begin{align} D(n) &= 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1}\\ & = \left(1 + \frac{1}{2}+\frac{1}{3}+ \dotsm + \frac{1}{2n-1}\right)-\left(\frac{1}{2}+\frac{1}{4}+ \dotsm + \frac{1}{2n-2}\right)\\ &=H_{2n-1}-\frac{1}{2}H_{n-1} \end{align}$$ This will take an amount of trips (and fuel) that are exponential in the desired distance. For example, to go a distance of $2$, it will take $n=8$ trips and to go a distance of $5$ will take $3093$ trips.

This (and a variant) is known as the jeep problem and is covered in more detail here.