Figure 1. A logistics network; unit transportation costs are given on each connecting link.[Example 3-2 from Designing and Managing the Supply Chain by D. Simchi-Levi et al]
Goal: Find a plan of distribution to minimize total transportation cost, while satisfying the demand at each customer location and the plant capacity limitations.
Heuristic #1: Customer chooses warehouse based on outbound unit costs.Step 1: Each customer chooses warehouse with the cheapest outbound-to-customer unit cost.Step 2: Route entire demand for each customer through warehouse identified in Step 1.
What is the distribution plan, and what is the total cost?
Heuristic #2:Customer chooses warehouse based on inbound and outbound unit costs.Step 1: For each customer, choose warehouse with cheapest inbound-from-plant plus outbound-to-customer unit costs. Step 2: Route entire demand for customer through warehouse found in Step 1.
What is the distribution plan, and what is the total cost?
Exact solution of the Logistics Network Configuration Model
The problem of determining the optimal logistics distribution in Figure 1is an example of what is known as a linear program, and specifically in this context the “transhipment problem.”
The problem described earlier can be framed as the following linear programming problem.We have the following decision variables:
- x(p1,w1), x(p1,w2), x(p2,w1) and x(p2,w2) will be the flows from the plants to the warehouses;
- x(w1,c1), x(w1,c2), x(w1,c3) will be the flows from the warehouse w1 to customer zones c1, c2 and c3.
- x(w2,c1), x(w2,c2), x(w2,c3) will be the flows from warehouse w2 to customer zones c1, c2 and c3
The problem we want to solve is:
minimize 0x(p1,w1) + 5x(p1,w2) + 4x(p2,w1)+ 2x(p2,w2) + 3x(w1,c1) + 4x(w1,c2) + 5x(w1,c3) + 2x(w2,c1) + 1x(w2,c2) + 2x(w2,c3)
subject to the following constraints:
x(p2,w1) + x(p2,w2) 60000capacity, plant 2
x(p1,w1) + x(p2,w1) = x(w1,c1) + x(w1,c2) + x(w1,c3)conservation of flow, w1
x(p1,w2) + x(p2,w2) = x(w2,c1) + x(w2,c2) + x(w2,c3)conservation of flow, w2
x(w1,c1) + x(w2,c1) = 50000demand, customer 1
x(w1,c2) + x(w2,c2) = 100000demand, customer 2
x(w1,c3) + x(w2,c3) = 50000demand, customer 3
all flows greater than or equal to zero.
To solve such a modelto optimality,we can turn to an exact algorithm that is guaranteed to find an optimal solution. It is not difficult to use EXCEL to represent this problem within a spreadsheet (LPexample36.xls) and solve it using EXCEL’s Solver add-in.
First of all, we arrange the problem’s data: plant capacity, unit transportation costs, and customer demands, in appropriate cells in a spreadsheet. In Figure 2, these data and their labelling information appear in columns B through K and rows 5 through 9.
Note that some of the terminology used by Solver is idiosyncratic. For instance, variables, the unknowns in a model, are stored in cells designated as changing cells. In Figure 2, the cells highlighted yellow contain the decision variables representing shipments from plants to warehouses, while those highlighted in rose represent shipments from warehouses to customers. The initial values of zero in each of these cells can later be changed by the Solver.
The objective function to be minimized, total transportation cost, is stored in a “target cell” highlighted blue. The location of the target cell, along with those of the changing cells, must be input to the Solver via the Dialog box shown in Figure 3.
You can access the Solver Dialog box by going to “Tools” and selecting “Solver.” (If Solver does not appear when you click Tools, go to ADD-INS and select Solver.)
Along with references to the target cell and the changing cells, input to the Solver Dialog box must include the constraints. The first line in the constraint section of the box, B15 <= B8, indicates that the function contained in cell B15, SUM(D15:E15) must not exceed in value the contents of cell B8. In other words, the total amount shipped out of plant 2 cannot exceed its capacity, 60,000 units.
The second line indicates that the function contained in cell D16 must equal in value the function contained in G14 and that in E15 must equal that in G15. Those constraints ensure flow conservation:i.e., that the amount shipped into each warehouse exactly balances the amount shipped out of it. Finally the third line contains three constraints, each of which ensure that the correct amount is shipped to each customer.
Go to the spreadsheet now and investigate this model by clicking on the appropriate cells!
Now go to Tools invoke the Solver Dialog box, and click on “solve”. You should next see the following screen:
Figure 4 displays an optimal solution to the transhipment problem that calls for production of 140,000 units at plant p1 and 60,000 (the specified limit) at plant p2. These quantities appear in the yellow cells. As we see in the rose cells, customer c1 receives 50,000 units from warehouse w1, customer c2 receives 40,000 from warehouse w1 and 60,000 from w2, and customer c3 receives a shipment of 50,000 units from w1. The total transportation cost of this solution is $740,000, as seen in the blue cell.
Note that the target cell utilizes EXCEL’s built-in function SUMPRODUCT, which, as the name suggests, multiplies together corresponding elements in an array, and then sums them up. For more information about SUMPRODUCT, Solver, or other features, use EXCEL’s Help function.
The Sensitivity Report from EXCEL is shown in Table 1.
Adjustable CellsFinal / Reduced / Objective / Allowable / Allowable
Cell / Name / Value / Cost / Coefficient / Increase / Decrease
$D$14 / p1 w1 / 140000 / 0 / 0 / 2 / 1
$E$14 / p1 w2 / 0 / 2 / 5 / 1E+30 / 2
$D$15 / p2 w1 / 0 / 5 / 4 / 1E+30 / 5
$E$15 / p2 w2 / 60000 / 0 / 2 / 1 / 1E+30
$I$14 / w1 c1 / 50000 / 0 / 3 / 2 / 1E+30
$J$14 / w1 c2 / 40000 / 0 / 4 / 2 / 0
$K$14 / w1 c3 / 50000 / 0 / 5 / 0 / 1E+30
$I$15 / w2 c1 / 0 / 2 / 2 / 1E+30 / 2
$J$15 / w2 c2 / 60000 / 0 / 1 / 0 / 2
$K$15 / w2 c3 / 0 / 0 / 2 / 1E+30 / 0
Constraints
Final / Shadow / Constraint / Allowable / Allowable
Cell / Name / Value / Price / R.H. Side / Increase / Decrease
$B$15 / changing cells shipped out / 60000 / -1 / 60000 / 40000 / 60000
$D$16 / highlighted in yellow w1 / 140000 / 0 / 0 / 1E+30 / 140000
$E$16 / highlighted in yellow w2 / 60000 / 3 / 0 / 60000 / 40000
$I$16 / amt received c1 / 50000 / 3 / 50000 / 1E+30 / 50000
$J$16 / amt received c2 / 100000 / 4 / 100000 / 1E+30 / 40000
$K$16 / amt received c3 / 50000 / 5 / 50000 / 1E+30 / 50000
Table 1. Sensitivity Report from EXCEL, Logistics Network Configuration problem.
A sensitivity report can help a manager answer “what if” questions. For example, what if plant 1 could produce 1 additional unit of the product: how would that change our total transportation cost? The “shadow price” of -1 reported in Table 1 tells us that for every additional unit of capacity at plant 1, total cost would change by -1; i.e., decrease by $1. This rate of decrease would hold for up an “allowable increase” of 60000 additional units of capacity, according to Table 1.
We can answer a similar question: what if customer 2 demanded 1 additional unit of the product? What would that do to total transportation cost? The shadow price of 4 means that the total transportation cost would increase by $4, and this $4 per unit rate would hold for up to 100000 additional units of demand.
Design of a Logistics Network
An Integer Linear Model in EXCEL
An optimal solution to the transshipment (LPexample36.xls) linear programming model specified the shipments from plants to warehouses and from warehouses to customers. Though very valuable information, shipments are more properly considered operational decisions rather than design decisions. True design decisions represent long term commitments, such as choosing locations for plants and warehouses.
Can we build our own design decision support system? The answer has both good news and bad news for us. Let’s save the bad news for later. The good news is that we can indeed design networks using EXCEL! In fact, not only can we decide warehouse locations, but plant locations as well. (We’ll assume that customer locations are beyond our control.)
To illustrate, let’s consider Figure 1, augment the data, and run with it a bit. First we consider p1 and p2 to be candidate plant locations, and add a third, p3 as well. That is, these are potential locations for plants in a “clean paper” design from scratch – the actual locations will be determined by solving an optimization model. Recall that there is only one product in this scenario. Were there multiple products, we would consider “product sourcing” decisions, that is, choosing a candidate location for each. We also consider candidate warehouse locations w1, w2, and w3. We’ll assume that the firm wishes to have no more than 2 plants and no more than 2 warehouses, although these kinds of restrictions are not hard to remove. The following figure illustrates the new problem.
Figure 5. Graphical representation of the Network Design Example. Each candidate plant would have a capacity of 100,000 units.
Besides unit transportation costs between all the candidate locations, we need some more pieces of data. Specifically, we need to know the annual fixed cost of opening, operating and maintaining a facility, plant or warehouse, at each candidate location. This cost must be on an annual basis to be consistent with the units of the original data. It would include, for example, rent or amortized construction costs. These costs appear in the cells beneath the heading “fixed cost” in the EXCEL spreadsheet (MIP1.xls) in Figure 6.
We also need an unknown to represent each plant location decision, and each warehouse location decision. These are found beneath the heading “Selection” in changing cells B4 through B6, and changing cells B21 through B24, respectively. These changing cells are of a special type known as binary valued, since a location decision is yes/no, with no in-betweens. A “yes” for a candidate location indicates the location should be included in the final solution, while “no” means the location should be excluded. In our formulation, “yes” is represented by the value 1, and a “no” by 0.
Recall that the target cell, H33 (highlighted in blue), contains a formula for the total cost, which is to be minimized. Now not only does this include the costs of transporting all shipments, but the sum of fixed costs associated with the plants and warehouses chosen. This total cost is contained in the EXCEL formula =SUMPRODUCT(G4:I6,E12:G14)+SUMPRODUCT(E21:G23,E28:G30)+SUMPRODUCT(C4:C6,B4:B6)+SUMPRODUCT(C21:C23,B21:B23)
The first two SUMPRODUCTS contain transportation costs, while the second two contain the fixed costs of plants and warehouses, respectively.
The constraint system is more complicated than that of the transshipment problem as well. The 20 constraints in the model are displayed and annotated in Table 2.
Constraint / Comment1 / $E$15=$C$28 / amount received from all plants at w1 equals amount shipped out from w1 to all customers
2 / $F$15=$C$29 / amount received from all plants at w2 equals amount shipped out from w2 to all customers
3 / $G$15=$C$30 / amount received from all plants at w3 equals amount shipped out from w3 to all customers
4 / $E$31=$E$24 / amount received from all warehouses
by customer c1 equals demand at c1
5 / $F$31=$F$24 / amount received from all warehouses
by customer c2 equals demand at c2
6 / $G$31=$G$24 / amount received from all warehouses
by customer c3 equals demand at c3
7 / $C$12<=$E$4 / forcing constraint: can’t ship product out of plant p1 in any amount, unless location 1 is selected
8 / $C$13<=$E$5 / forcing constraint: can’t ship product out of plant p2 in any amount, unless location 2 is selected
9 / $C$14<=$E$6 / forcing constraint: can’t ship product out of plant p3 in any amount, unless location 3 is selected
10 / $B$7<=$B$8 / no more than 2 plants can be chosen
11 / $E$15<=$A$21 / forcing constraint: can’t receive product into warehouse w1 in any amount, unless location 1 is selected
12 / $F$15<=$A$22 / forcing constraint: can’t receive product into warehouse w2 in any amount, unless location 2 is selected
13 / $G$15<=$A$23 / forcing constraint: can’t receive product into warehouse w3 in any amount, unless location 3 is selected
14 / $B$24<=$B$25 / no more than 2 warehouses can be chosen
15 / $B$4=binary / location selection is a binary (0,1) variable
16 / $B$5=binary / location selection is a binary (0,1) variable
17 / $B$6=binary / location selection is a binary (0,1) variable
18 / $B$21=binary / location selection is a binary (0,1) variable
19 / $B$22=binary / location selection is a binary (0,1) variable
20 / $B$23=binary / location selection is a binary (0,1) variable
Table 2. Constraints for the network design model in Figure 6.
Constraints 1-6 correspond to those we encountered in the transshipment model. The other constraints are necessitated by the location decisions for both plants and warehouses. The logical forcing constraints 7-10 ensure that no shipment is promised from a location without a plant! Likewise 11-13 are logical forcing constraints that ensure that no shipment goes to a location without a warehouse. Constraints 10 and 14 place limits on the number of plants and warehouses to be selected, respectively. Finally, constraints 15-20 tell the Solver that the changing cells in the specified locations can only take on the values of 0 and 1.
Once again we go to the Solver dialog box and click “solve” resulting in the optimal solution seen in Figure 7.
Figure 8. Graphical representation of the optimal network design found by EXCEL. Plants are located at p2 and p3, warehouses at w2 and w3. Shipments are shown by thick red arrows. The total cost is $675,000.
Now for the bad news: this design model, known as a mixed integer program, is a much harder problem in terms of the amount of computation required, than the transshipment linear program. In fact, there is no guarantee that any optimization software would not have to solve as many linear programs as there are combinations of plant and warehouse locations. This is not of much consequence when there are only 3 candidate locations for each, as in our illustration. However, suppose we were tackling a larger design instance with 15 candidate warehouse locations, and we wished to select exactly than 7 of them. There are 6435 different ways of selecting 7 of 15 locations, and we might have to solve virtually as many linear programming models, if we were “unlucky.” Were we to select 15 of 30 candidate locations, the number of combinations would jump beyond 15,000,000, a phenomenon known as the “combinatorial explosion”! In these cases, decision makers often must turn to heuristic methods. Such methods attempt to provide good answers with a reasonable level of computation, but the answers are not guaranteed to be optimal.
1