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 s₀, s₁, s₂, …, s_n on this fixed route, and the route starts from the stop s₀ in city A with a full tank of gas and ends in stop s_n in city B. All the intermediate stops s₁, s₂, …, s_n-1 can provide gas. Since this is a long trip, the truck need to refuel somehow in some of these intermediate stops s₁, s₂, …, s_n-1. Let P_i be the price of gas per at stops s_i. Let G_i be the number of gallons of gas needed to go from stops s_i to s_i+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?