13
$\begingroup$

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?

$\endgroup$
0

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Besides being careful about what happens for $q = 1$, you also need to take care to fill out the table with meaningful values when the inner loop runs out of elements. Moreover, if I'm reading it correctly,, the algorithm appears to completely ignore the case $c(v) > c(u)$ (cf. this CS SE question), so something needs to be done there as well. $\endgroup$
    – fuglede
    Oct 17, 2019 at 8:56
2
$\begingroup$

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:

enter image description here

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).

$\endgroup$
1
1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer! Unfortunately I didn't specified myself clearly enough. You assumed, that graph will be as simple as my example, but it can be any graph i.e. there can be also roads 0->2, 1->3 etc. $\endgroup$ May 20, 2014 at 1:14
  • $\begingroup$ Ya,as you didn't mention that before I assumed all the cities are connected in a linear fashion (the graph is a simple path). $\endgroup$ May 20, 2014 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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