Case 1

Gas tank capacity: 15 Gallons

Initially no gas in the tank

 ci: Gas price per gallon at station Si gi: Number of gallons needed to go from Si to Si+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  Si Number of gallons when arriving at Si Yi: gallon purchased at station Si Number of gallons when leaving Si 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  Si ci: Gas price per gallon at station Si gi: Number of gallons needed to go from Si to Si+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  Si Number of gallons when arriving at Si Yi: gallon purchased at station Si Number of gallons when leaving Si 1 2 3 4 5 6 Destination