Understanding an algorithm for the gas station problem

Question

In the gas station problem we are given $n$ cities $\{ 0, \ldots, n-1 \}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. Our goal is to go from a source to a destination in the cheapest possible way. Our tank is limited by some value.

I try to understand the algorithm, so I manually wrote down steps to calculate the solution. Unfortunately I got stuck - at some point there are no edges to consider, I don't know why, maybe I'm missing something.

Example:
road:
0 ----------- 1 ------------ 2 -------------- 3
(it doesn't have to be that simple, it could be any graph i.e. there could be roads between 0->2, 0->3, 1->3 etc.)

Source: 0, Destination: 3, Tank: 10 units
Fuel prices: 0: 10 units, 1: 10 units, 2: 20 units, 3: 12 units
Lengths: 0->1: 9 units, 1->2: 1 unit, 2->3: 7 units
Optimal solution: fill 9 units at 0 and 8 units at 1. Total cost then is 170 units (9 * 10 + 8 * 10).

So I tried to calculate it as shown here (paragraph 2.2)

GV[u] is defined as:
GV[u] = { TankCapacity - length[w][u] | w in Cities and fuelPrice[w] < fuelPrice[v] and length[w][u] <= TankCapacity } U {0}

so in my case:
GV[0] = {0}
GV[1] = {0}
GV[2] = {0, 3, 9}
GV[3] = {0}

D(u,g) - minimum cost to get from u to t starting with g units of fuel in tank:
D(t,0) = 0, otherwise:
D(u,g) = min (foreach length[u][v] <= TankCapacity)
         { 
           D(v,0) + (length[u][v] - g) * fuelPrice[u]                             : if  fuelPrice[v] <= fuelPrice[u] and g <= length[u][v]
           D(v, TankCapacity - length[u][v]) + (TankCapacity - g) * fuelPrice[u]  : if  fuelPrice[v] > fuelPrice[u]
         }

so in my case:
D(0,0) = min { D(1,0) + 9*10 }  - D(0,0) should contain minimum cost from 0->3
D(1,0) = min { D(2,9) + 10*10 } - in OPT we should tank here only 8 units :(
D(2,9) = min { ??? - no edges which follows the condition from the reccurence 

Nevertheless D(0,0) = 90 + 100 + smth, so it's already too much.

To achieve the optimal solution algorithm should calculate D(2,7) because the optimal route is:   
(0,0) -> (1,0) -> (2, 7) -> (3, 0) [(v, g): v - city, g - fuel in tank]. 
If we look at G[2] there is no "7", so algorithm doesn't even assume to calculate D(2,7), 
so how can it return optimal solutions?

Recurrence from the document doesn't seem to work or what's more likely I do something wrong.

Could anybody help me with this?

Answer 1

The problem is in the condition for the first argument to min() in Equation (4) on p. 7. It's currently

c(v) <= c(u) and g < d[u][v]

but it should be

(c(v) <= c(u) or v = t) and g < d[u][v]

to force arrival at t to have no gas left. (Just as with my explanation below for the bug in Fill-Row(u, q), we are never interested in the cost of gas at t. And as with there, another way to fix the problem would be to overwrite c(t) with 0 at the start of the algorithm.)

Fixing this mistake (in the published algorithm), combined with adding in the missing edges as I describe below (your mistake :-P), should be enough to get everything working.

---

One thing you're missing is that the graph G must be complete (first sentence of section 2, p. 4) -- and if it's not complete, any missing edges must be added, with the weights found by taking minimum path lengths in the graph. So e.g. in your example graph, there should be (among others) an edge from 1 to 3 with weight 8 (corresponding to the path via 2), so that in fact GV[3] = { 0, 2 }.

I'm not sure whether that will completely solve the problem for you, but it should help.

Separately, I think there's a bug in the Fill-Row(u, q) algorithm on p. 6: this algorithm should treat the case q=1 specially, but it doesn't. I believe it could be fixed by changing

if c(v) <= c(u)

on line 3 to

if c(v) <= c(u) or q = 1

to force any final leg to arrive at the destination empty. (Intuitively, we should always disregard the price of gas at the final destination, t.) Another way around this would be to overwrite c(t) with 0 at the outset.

Answer 2

Using @j_random_hacker solution we need to transform our graph to a complete graph and change the condition from equation (4) to:

(c(v) <= c(u) or v = t) and g < d[u][v]     

Complete graph should look like this:

and final calculations:

GV[0] = {0}, GV[1] = {0}, GV[2] = {0, 3, 9}, GV[3] = {0, 2}

D(0,0) = min { D(1,0) + 9 * 10 }
D(1,0) = min { D(2,9) + 10 * 10, D(3,0) + 8*10 }
D(3,0) = 0
... etc

so D(0,0) = 170

Path through 0 -> 1 -> 3 [total cost 170$] is the solution. That's what we expected :-). If we need a route, then we should be able to transform those extra edges from the solution to the given edges at the beginning (it shouldn't be very difficulty).

I only wonder how we should avoid deadloops in this recurrence. For example there can be deadloop between 0 <-> 1 , because c(0) <= c(1) and c(1) <= c(0).

Answer 3

The idea is to get the fuel as required in cheapest rate wherever you get (greedy algorithm paradigm)

Take some examples. in your example

Source: 0, Destination: 3, Tank: 10 units Fuel prices: 0: 10 units, 1: 10 units, 2: 20 units, 3: 12 units Lengths: 0->1: 9 units, 1->2: 1 unit, 2->3: 7 units

I have to travel 9 units at first, so I need to fill up my tank at 0 with >= 9 units (capacity >= 9). Now, I can see at 1,2,3 the fuel rate is >= fuel rate at 0. As, I want to buy my needed fuel in cheapest rate I'll try to fill up 9+1+7=17 units at city 0 only. But, the capacity of tank might be < 17, say 10. So, I will fill up till 10. Then at 1 I have 1 units fuel left and I have to traverse 8 units more, so at 1 I'll fill up 7 units more. I can't fill up at 2 because the rate would be higher. My, total cost = 10*10+7*10 =170.

The greedy algorithm follows the idea mentioned above. $C_i$ fuel cost at city i. $d_{ij}$ distance between two cities $i$ and $j$. "full" is unit of fuel with which tank is filled up. "capacity" is max tank capacity.

i) full = 0

ii) for $i=0$ to $n-1$, let $l$ be the first city after $i$ such that $C_i > C_l$ (if no such $l$ exists then $l=n-1$). $d_l$= more_distance_need_to_travel_till_city_$l$ = $\sum_{k=i+1}^l d_{k,k+1}$. Buy $\min${$d_l - $ full, capacity} unit fuel at city $i$. full = $\min${$d_l - $ full, capacity}. Set $i=l$.