The Truck Refueling Problem

 

 

A truck company runs its business on a fixed route from city A to city B. There are n+1 stops s0, s1, s2, Ö, sn on this fixed route, and the route starts from the stop s0 in city A with a full tank of gas and ends in stop sn in city B. All the intermediate stops s1, s2, Ö, sn-1 can provide gas. Since this is a long trip, the truck need to refuel somehow in some of these intermediate stops s1, s2, Ö, sn-1. Let Pi be the price of gas per at stops si. Let Gi be the number of gallons of gas needed to go from stops si to si+1. Let the maximum capacity of the truckís gas tank be c gallons.Consider the following refueling problems:

 

1.     Letís try to minimize the number of refueling stops. (i) Devise a polynomial-time algorithm (if possible) to determine in which intermediate stops the truck should get refueled to full tank to minimize the total number of stops for refueling along the route. (ii) What is the complexity of your algorithm? (iii) Can you prove that your algorithm does always find a solution that minimizes the total number of stops for refueling along the route?

 

2.     Letís try to minimize the total refueling cost. (i) Devise a polynomial-time algorithm (if possible) to determine in which intermediate stops the truck should get refueled and the numbers of gallons refueled respectively (in other words, you donít have to fill the tank entirely every time) to minimize the total amount of refueling cost on the route. (ii) What is the complexity of your algorithm? (iii) Can you prove that your algorithm does always find a solution that minimizes the total amount of refueling cost?

 

 

Examples:

1.     Samples: Case 1 and Case 2 (solved)

2.     Test case: What is the optimal solution you get?