Table 8.6 First Proposed Aggregation (Optimal Solution Indicated; Optimal Value = $116,445).

to the expected magnitude of total transportation costs, another aggregation must be sought. Table 8.7 characterizes an alternative. Setting Ll = {NY,BOS) and using c« =

NY/BOS max fc= 1,2,3

+ max A;= 1,2,3

Dnv BOS

£>NV

= 15,000 max{(2.879-2.815),(2.856-2.786),(1.686-1.608)! + 10,000 maxi(2.879-2.976),(2.856-2.960),(1.686-1.804)!

upon factoring ZJny and ZJbos out of the respective braces. Thus, «ny/bos = 15,000(0.078) -b 10,000(-0.097) = $200 for this aggregation. For the two proposed aggregations. Property 8.1 is exemplified by the following:

v[full problem] < v[PIT/NY/BOS aggregation] < v[full problem] + *p,t/n

ie, 116,005 < 116,445 < 116,505, and

v[full problem] < v[NY/BOS aggregation] < v[full problem] + fNv/Bos, ie, 116,005 < 116,170 < 116,205.

Table 8.7 Second Proposed Aggregation (Optimal Solution Indicated;

IY/BOS>

Demands

Owing to the nature of the pro rata demand aggregation scheme, an optimal solution of an aggregated model can be disaggregated into a feasible solution to the full problem with the same cost as the optimal value of the aggregated problem. In the second aggregation the SEA-»NY/ BOS flow of 5000 cwt has an associated cost of 5000(2.879) = 5000[(15/ 25)2.815 + (10/25)2.976]. This flow would be disaggregated into (15/ 25)5000 cwt to New York and (10/25)5000 cwt to Boston with the identical cost in the full problem. Similar results hold for disaggregating the remaining flows to NY/BOS. The value of the disaggregated solution is guaranteed to be within $200 of optimality. Indeed, the suboptimality is actually only $116,170 - $116,005 = $165.

Considering H sequential applications of Property 8.1 leads to its extension given below.

Property 8.2 [Extended customer aggregation error bound]. Let Li,L2,...,Lf,, be disjoint subsets of demand point indices such that each subset Ll, individually satisfies qualification (8.28). Then:

if for A = 1,..., and all k, the js are identical

over all etLi,

(8.30)

v[CPLP] =¸ v[CPLP; (8.30)1 =¸ v[CPLP]

IModeling Philosophy

Solving the linear programming relaxation of problem (CPLP) augmented by the constraints 0 < z < 1, for all k, will generally produce fractional values for the variables if any throughput constraints are binding. The convenience of using linear programming directly as a solution approach is lost. However, Kuehn and Hamburger (1963) issued an early caveat: "Care must also be taken to avoid the chase for optimal solutions to simple problems and thereby miss the actual problem of business-the solution of,large-scale problems containing many customers buying various mixes of a full product line, many potential warehouse sites, alternate warehouse types with different cost structures, several factories and, perhaps, a number of potential factory sites." The foUowing section presents a computationally practicable approach for treating the complex problem described in the caveat.

8.3 TWO-STAGE, MULTI-COMMODITY DISTRIBUTION SYSTEM DESIGN

A large food products company is engaged in distribution planning [Geoffrion and Graves (1974)], and a computer-based model is adopted to plan

the configuration and flow aspects of the distribution system design for the next five years. Hundreds of products must be aggregated into several product groups or "standard commodity bundles." Examples of groupings are bottled cooking oil, packaged shortenings, and catsup. These commodity bundles, hereafter called commodities, are produced at several existent plants with known production capacities (cwt/year). Not every plant can produce every group. There is a known demand for each of the commodities at each of several demand zones (customer aggregations). Commodities may be shipped through distribution centers (DCs). Each demand zone is to be assigned uniquely to a DC. This feature has accounting, marketing, and transportation advantages. There may be upper and lower bounds on the throughput of the DCs. There is a list of candidate sites for DCs developed from current locations, competitor DC locations, major demand centers, hub cities, or sites generated fi-om continuous models. There is a fixed cost of establishing and operating a DC as well as a variable throughput cost. The transportation system is characterized by transportation costs that are linear in the amount shipped.

The primary design questions are: which DC sites to use, what throughput to plan for at each DC, what demand zones to assign to each DC, and what pattern of flows should there be for each commodity. The distribution system is to be designed to satisfy customer demand at minimum total cost while honoring plant capacity constraints, DC throughput bounds, and any additional constraints on the system configuration. The model presumes that all plants are previously established. However, the potential exists for including additional zero-one variables to select among alternative plant sites for some or all plants as well as among plant capacity expansion projects. The reader is encouraged to consider these possibilities as the narrative unfolds. The following symbols are used throughout this section:

S., =

index for commodities,

index for plants (or, more generally, procurement zones), index for DC candidate sites, index for demand zones,

supply (production capacity) of commodity / at plant j (cwt/ year),

deinand for commodity i in demand zone H (cwt/year), minimum, maximum allowed total annual throughput for a DC at site (cwt/year),

fixed cost of establishing a DC at site (dollars/year), average variable unit cost of throughput for a DC at site (dollars/cwt),

average unit cost of producing and shipping commodity i from plant j through a DC at site to demand zone £ (dollars/cwt),

Xijki = amount of commodity i shipped from plant j through a DC at

site to demand zone (cwt), 1,1 = a zero-one variable equal to 1 if a DC at site serves demand

zone £ and equal to 0 otherwise, Zl, = a zero-one variable equal to 1 if a DC is established at site k, and equal to 0 otherwise.

The distribution design model denoted problem (DD) is given by:

minimize 2 2 S Z Cuki/X.ki + E (/ + S S ) (8-31) x,y,z J l i I

subject to

Summations are understood to extend only over practicable combinations of indices, ie, certain ij links will be omitted if plant j doesnt produce commodity / and certain jk and k£ links will be clearly uneconomical. There may only be a small subset of potential DC sites for supplying any given demand zone. The omitted subscript combinations reduce the number of variables actually present in the model. The quadruple subscripting scheme used for the flow variables preserves the identity of the origin of commodities. This permits imposition of restrictions on certain Jk£ routes for perishable commodities by omitting the associated variables. The quadruple subscripting scheme is also useful when a commodity price depends on the originating plant or when some transportation costs are determined on the basis of direct plant-to-customer shipments even though a stopover is made at the assigned DC, a "storage-in-transit" privilege. If certain demand zones are actually to be supplied directly from plants, a dummy DC site, say, k„, can be included. The associated z and ,/s would be set to 1 and the c,jtjs would be specified appropriately.

The linear configuration constraints (8.36) can be used as a technical device to select among projects for expansion or contraction of capacity at existing DCs, or to ensure that, at most, one version of a DC will be

opened at a given site. Discussions with management uncovered the need to include service level constraints such as )/! Da <

Ti, where t,i,e is the average time to deliver an order for commodity / to demand zone 2 from a DC at site k, and , is an upper bound on average delivery time for commodity i. The latter concern can also be addressed by assigning p a comparatively large objective function coefficient whenever site is unacceptably distant from demand zone £

Data Considerations

The unit production cost (dollars/cwt) component of Cijfcif measures the real cash flow change for changing the output rate of commodity i at plant j. The directly assignable portion of production cost can be derived from an existing standard cost accounting system. Actual, rather than standard, raw material costs should be used to measure the influence of regional raw material prices on location. The overhead portion requires estimation of variable components of indirect cost accounts (such as energy, indirect labor, management, maintenance, etc.) and the allocation of the variable component to the given commodity.

The distribution cost (dollars/cwt) component of %-f has two parts. For inbound J->k transportation links, the transportation rate may adequately be modeled as a weighted average reflecting the mix of modes and shipment sizes judged most likely to be used. (Pipeline inventory costs might be included.) For k-J2 links to large volume demand zones, unit transportation rates are developed by dividing estimated total annual freight cost by the volume that must flow on the link. This flow is known because Dm is known and demand zones must be supplied entirely from a single DC. If shipment is by truck delivering to smaU volume demand zones on a dehvery tour, distribution cost for k-*( hnks must be approximated. The following has been applied by Mairs, Wakefield, Johnson, and Spielberg (1978) to give quick and reasonably accurate estimates:

(constant) X X m,, X Oie X r,,g

tiki ~ -----, where

sX UgX Pi

dke = travel distance from site to demand zone £,

nil, = freight cost per mile from site k. Si, = factor for trailer size, depending on site k, Ue = factor for trailer utilization, depending on the destination, Pi = density factor in cwt/cubic feet,

of = one-way trip factor-normally is 2 to reflect two-way trip; otherwise, less than 2 if the trip includes pickup of supplies from plant at an interchange point,

r„ = circuit cost factor, approximated by 2.38-0.18 loge(u?«), which reflects the fact that demand zone (is supplied on delivery route.

Solution by Benders Decomposition

The distribution design problem is a large-scale mixed-integer programming problem for this application. There are 17 product groups (commodities), 14 plants, 45 DC sites, and 121 demand zones. The solution approach to be presented decomposes the problem. The approach capi-I talizes on the property that when the zero-one variables and z are held fixed at feasible values, the flow partition of the problem separates into independent classical transportation problems, one for each commodity. To see this, consider the flow partition of the problem that involves all the transportation variables and the temporarily held fixed variables, say yig. The problem becomes:

minimize 2 S E S

X I j Q

subject to (8.38)

Xiike S,j for all i,}

e

1 Xij.g = D.gyl/g for all i,k,ll

Xijke 0 for all i,j,k,Q.

I Define as the index value such that > = 1 for a particular value I of the H index. In words, T<i£) is the DC that serves demand zone £ Since U£) is unique by constraint (8.34), x,,;,, = 0 for all ijM with (£). These facts provide the basis for stating the transportation problem for I the commodity as:

minimize X S , , « , ,.

subject to

(8.39)

2 -Mw S,j for all j

E XijUife = Dig for all £

X,jk(e)P s= 0 for all /,£

The DC variable cost (dollars/cwt) includes handling, inventory costs, and other variable operating expenses. The DC fixed cost (dollars/year) captures amortized capital costs and fixed components of operating costs. However, as in Figure 8.6, f may function only to provide a straight-line approximation of DC throughput cost over a range of interest.