Case 1
Gas tank capacity:
15 Gallons
Initially no gas
in the tank
c_{i}: Gas price per gallon at station S_{i} 
g_{i}: Number of gallons needed to go from S_{i} to S_{i+1} 

1 
$3 
1 
2 
$1 
5 
3 
$6 
2 
4 
$2 
13 
Destination 


In this case, the optimal refueling policy is <Y1=1, Y2=15, Y3=0, Y4=5>. In other words, refill the vehicle with 1, 15, and 5 gallons in stations S1, S2, and S4 respectively, ending in a total fuel cost of $3*1 + $1*15 + $6*0 + $2*5=$28.
Station S_{i} 
Number of gallons when arriving at S_{i} 
Y_{i}: gallon purchased at station S_{i} 
Number of gallons when leaving S_{i} 
1 
0 
1 
1 
2 
0 
15 
15 
3 
10 
0 
10 
4 
8 
5 
13 
Destination 
0 

Case 2
Gas tank capacity:
15 Gallons
Initially no gas
in the tank
Station S_{i} 
c_{i}: Gas price per gallon at station S_{i} 
g_{i}: Number of gallons needed to go from S_{i} to S_{i+1} 
1 
$4 
7 
2 
$5 
5 
3 
$3 
9 
4 
$6 
13 
5 
$2 
12 
6 
$1 
3 
Destination 


In this case, what is the optimal refueling policy (i.e. how much should we refill the vehicle in each of the statins to minimize the refueling cost)? What is the minimal refueling cost?
Station S_{i} 
Number of gallons when arriving at S_{i} 
Y_{i}:
gallon purchased at station S_{i} 
Number of gallons when leaving S_{i} 
1 

2 


3 


4 


5 



6 



Destination 


