Optimizing Petroleum Allocations with Solver

Part 1: single-stage allocation problem

Suppose there are three oil refineries--Amoco, BP and Chevron-- supplying gasoline to seven cities--Tic, Urp, Vat, Wag, Xyz, Yeti and Zed. This table includes the cities' and refineries' X-Y locations, the cities' monthly gasoline demands, and the refineries' monthly capacities.  Copy and paste these data into a blank worksheet.


You can create a bubble-plot "map" of the cities sized by demand, another bubble-plot of the refineries sized by capacity, and then copy and paste the refineries plot into the cities plot.  (I used a third-party Excel add-in to label the bubbles.)

Your objective is to determine the set of gasoline allocations from refineries to cities that minimizes aggregate straight-line delivery costs (assuming constant cost per mile per barrel).  The figure below shows how to set up the worksheet to accomplish this.

First, you need to calculate the straight-line distances between the cities and refineries.  (Use the Pythagorean theorem: square the difference in the X's and the difference in the Y's, add them, and take the square root; the illustration doesn't show the entire formula, but you get the idea!) 

Then, initialize the allocation table (which I highlighted in yellow) with zeroes, and enter the row and column sum formulas in the adjacent column and row.  Next, use the SUMPRODUCT function to sum the products of barrels allocated from each refinery i to city j multiplied by the distance between refinery i and city j.  This calculates the aggregate transportation cost of the allocation pattern.

Now use Solver to find the least-cost set of allocations from refineries to cities that satisfies two constraint sets: 
(1) the total deliveries from the refineries to each city equal (EQ) that city's demand; and
(2) the refineries' total deliveries are less than or equal to (LE) their respective processing capacities.

Specify the SUMPRODUCT cell (green) as the value to be minimized by adjusting the allocation cells (yellow), and specify the constraints: cities' deliveries = demands, and refineries' deliveries ≤ refinery capacities.

Check the "Make Unconstrained Variables Non-Negative" box.  Choose the "Simplex LP" solving method.  Solve.

When you get the Solver solution, select the Sensitivity Report so it's saved along with the solution.  Examine the shadow prices in the Sensitivity Report, and summarize the solution: 

  1. Which refineries have slack capacity and zero shadow prices? 

  2. Which refinery has a negative shadow price reflecting the cost reduction that would occur if that refinery had another barrel of capacity? (Additional capacity here would idle higher-cost capacity at one of the other refineries.)

  3. Which cities have the highest and lowest shadow prices for oil?  (You could interpolate a gasoline price surface from these points.)

  4. Now suppose BP builds a pipeline to Urp that reduces its effective cost distance by half.  Change the BP-to-Urp distance in the distances table and re-solve the problem.  How would the new pipeline affect the allocations and shadow prices?

Part 2: two-stage allocation problem

Now let's include the oil fields that supply these refineries.  Now your objective is to determine the allocations of crude from oil fields to refineries, and the allocations of refined petroleum to cities, that minimize the total cost of satisfying all the cities' demands.

This table includes the X-Y locations and monthly pumping capacities of ten fields.  Copy and paste these data into a new worksheet, and create the combined matrix of straight-line distances of both oil fields and cities from the three refineries:

Set up an expanded allocation table to solve the combined problem: find the least-cost set of allocations from oilfields to refineries and from refineries to cities that satisfies four constraint sets:
(1) total deliveries to the cities equal the cities' demands;
(2) each refinery's total deliveries are less than or equal to its processing capacity;
(4) each oilfield's monthly production is less than or equal to its pumping capacity; and
(3) the total each refinery receives from oilfields equals the total it delivers to cities.

Your setup should look something like this:

Analyze the allocations and the Sensitivity Report shadow prices:

  1. Which oil fields are unused or only partially used?

  2. Which refineries have unused capacities?

  3. Which cities get the cheapest gasoline?

  4. Suppose a pipeline between the city with the highest gasoline cost and the nearest refinery with unused capacity reduces their effective distance by half.  Adjust the appropriate distance table value and re-solve the model to see how this will affect oilfield demands, refinery production and cities' gasoline prices.

(If you get totally stuck, here are the solvable setups for both problems.)