Using Solver to solve transportation or distribution problems

Applies to
Microsoft Office Excel 2003

Book cover


This article was adapted from Microsoft Excel Data Analysis and Business Modeling by Wayne L. Winston. Visit Microsoft Learning to learn more about this book.

This classroom-style book was developed from a series of presentations by Wayne Winston, a well known statistician and business professor who specializes in creative, practical applications of Excel. So be prepared — you may need to put your thinking cap on.

Sample files You can download the sample files that relate to excerpts from Microsoft Excel Data Analysis and Business Modeling from Microsoft Office Online. This article uses the file Transport.xls.

Many companies manufacture products at locations (often called supply points) and ship their products to customers (often called demand points). A natural question is "What is the least expensive way to produce and ship products to customers and meet customer demand?" This type of problem is called a transportation problem. A transportation problem can be set up as a linear Solver model with the following specifications:

  • Target cell     Minimize total production and shipping cost.
  • Changing cells     The amount produced at each supply point that is shipped to each demand point.
  • Constraints     The amount shipped from each supply point can’t exceed plant capacity. Each demand point must receive its required demand. Also, each changing cell must be nonnegative.

How can a drug company determine the locations at which they should produce drugs and from which they should ship drugs to customers?

You can follow along with this problem by looking at the file Transport.xls. Let’s suppose a drug company produces a drug in Los Angeles, Atlanta, and New York City. The Los Angeles plant can produce up to 10,000 pounds of the drug per month. Atlanta can produce up to 12,000 pounds of the drug per month, and New York City can produce up to 14,000 pounds per month. Each month, the company must ship to the four regions of the United States — East, Midwest, South, and West — the number of pounds listed in cells B2:E2, as shown in the following figure. For example, the West region must receive at least 13,000 pounds of the drug each month. The cost per pound of producing a drug at each plant and shipping the drug to each region of the country are given in cells B4:E6. For example, it costs $3.50 to produce a pound of the drug in Los Angeles and ship it to the Midwest region. What is the cheapest way to get each region the quantity of the drug they need?

Spreadsheet with data for transportation problem

To express our target cell, we need to track total shipping cost. After entering in the cell range B10:E12 trial values for our shipments from each supply point to each region, we can compute total shipping cost as the following:

(Amount sent from LA to East) *
(Cost per pound of sending drug from LA to East) +
(Amount sent from LA to Midwest) *
(Cost per pound of sending drug from LA to Midwest) +
(Amount sent from LA to South) *
(Cost per pound of sending drug from LA to South) +
(Amount sent from LA to West) *
(Cost per pound of sending drug from LA to West) +

(Amount sent from New York City to West) *
(Cost per pound of sending drug from New York City to West)

The SUMPRODUCT function can multiply corresponding elements in two separate rectangles (as long as the rectangles are the same size) and add together the products. I’ve named the cell range B4:E6 as costs and the changing-cells range (B10:E12) as shipped. Therefore, our total shipping and production cost is computed in cell B18 with the formula SUMPRODUCT(costs,shipped).

To express our constraints, we first compute the total shipped from each supply point. By entering the formula SUM(B10:E10) in cell F10, we compute the total number of pounds shipped from Los Angeles as (LA shipped to East) + (LA shipped to Midwest) + (LA shipped to South) + (LA shipped to West). Copying this formula to F11:F12 computes the total shipped from Atlanta and New York City. Later I’ll add constraints (called supply constraints) that ensure the amount shipped from each location does not exceed the plant’s capacity.

Next I compute the total received by each demand point. I begin by entering in cell B13 the formula SUM(B10:B12). This formula computes the total number of pounds received in the East as (Pounds shipped from LA to East) + (Pounds shipped from Atlanta to East) + (Pounds shipped from New York City to East). By copying this formula from B13 to C13:E13, I compute the pounds of the drug received by the Midwest, South, and West regions. Later, I’ll add constraints (called demand constraints) that ensure that each region receives the amount of the drug it requires.

We now open the Solver Parameters dialog box (click Solver on the Tools menu), and then fill it in as shown in the following figure.

Solver set up to solve transportation problem

We want to minimize total shipping cost (computed in cell B18). Our changing cells are the number of pounds shipped from each plant to each region of the country. (These amounts are listed in the range named shipped, consisting of cells B10:E12.) The constraint F10:F12<=H10:H12 (the supply constraint) ensures that the amount sent from each plant does not exceed its capacity. The constraint B13:E13>=B15:E15 (the demand constraint) ensures that each region receives at least the amount of the drug it needs.

Our model is a linear Solver model because our target cell is created by adding together terms of the form (changing cell)*(constant), and both our supply and demand constraints are created by comparing the sum of changing cells to a constant.

I now click Options in the Solver Parameters dialog box and select the Assume Linear Model and Assume Non-Negative options. After clicking Solve in the Solver Parameters dialog box, we’re presented with the optimal solution. The minimum cost of meeting customer demand is $86,800. This minimum cost can be achieved if the company uses the following production and shipping schedule:

  • Ship 10,000 pounds from Los Angeles to the West region.
  • Ship 3,000 pounds from Atlanta to the West region and from Atlanta to the Midwest region. Ship 6,000 pounds from Atlanta to the South region.
  • Ship 9,000 pounds from New York City to the East region and 3,000 pounds from New York City to the Midwest region.

Problems

  1. The distances between Boston, Chicago, Dallas, Los Angeles, and Miami are given in the following table. Each city needs 40,000 kilowatt hours (kwh) of power, and Chicago, Dallas, and Miami are capable of producing 70,000 kwh. Assume that shipping 1,000 kwh over 100 miles costs $4.00. From where should power be sent to minimize the cost of meeting each city’s demand?
Boston Chicago Dallas LA Miami
Chicago 983 0 1,205 2,112 1,390
Dallas 1,815 1,205 0 801 1,332
Miami 1,539 1,390 1,332 2,757 0
  1. What would be the optimal solution to our drug company example if New York City’s capacity were 5,000 pounds?
  2. We produce drugs at several locations and sell them in several areas. The decision of where to produce drugs for each sales location can have a huge impact on profitability. Our model is similar to the model used in this article to determine where drugs should be produced. We’re using the following assumptions:
    • We produce drugs at six different locations and sell to customers in six different areas.
    • Tax rate and variable production cost depend on the location where the drug is produced. For example, any units produced at Location 3 cost $6.00 per unit to produce, and profits from these products are taxed at 20 percent.
    • The sales price of each product depends on the place where the product is sold. For example, each product sold in Location 2 is sold for $40.00.
Production Location 1 2 3 4 5 6
Sales price $45 $40 $38 $36 $39 $34
Tax rate 30% 40% 20% 40% 35% 18%
Variable production cost $8 $7 $6 $9 $7 $7
  • Each of our six plants can produce up to 6,000,000 units per year.
  • The annual demand (in millions) for our product in each location is as follows:
Sales Location 1 2 3 4 5 6
Demand 1 2 3 4 5 6
  • The unit shipping cost depends on the plant where the product is produced and the location where the product is sold.
Sold 1 Sold 2 Sold 3 Sold 4 Sold 5 Sold 6
Made 1 $3 $4 $5 $6 $7 $8
Made 2 $5 $2 $6 $9 $10 $11
Made 3 $4 $3 $1 $6 $8 $6
Made 4 $5 $5 $7 $2 $5 $5
Made 5 $6 $9 $6 $5 $3 $7
Made 6 $7 $7 $8 $9 $10 $4
  • For example, if we produce a unit at Plant 1 and sell it in Location 3, it costs $5 to ship it.
  • How can we maximize after-tax profit with our limited production capacity?
  1. Suppose that each day, northern, central, and southern California each use 100 billion gallons of water. Also assume that northern California and central California have available 120 billion gallons of water, while southern California has 40 billion gallons of water available. The cost of shipping one billion gallons of water between the three regions is as follows:
Northern Central Southern
Northern $5,000 $7,000 $10,000
Central $7,000 $5,000 $6,000
Southern $10,0000 $6,000 $5,000
  1. We will not be able to meet all demand for water, so we assume that each billion gallons of unmet demand incurs the following shortage costs:
Northern Central Southern
Shortage cost/billion gallons short $6,000 $5,500 $9,000
  1. How should California’s water be distributed to minimize the sum of shipping and shortage costs?
 
 
Applies to:
Excel 2003