MULTI-FACILITY LOCATION

The condition on the sum describing the cost of distances between pairs of the new facihties indicates that each distance is to be considered only once. m = I, the problem reverts in form to problem (2.1), the single-facility problem.

Example 4.1 To motivate the multi-facility model, we describe an actual appUcation reported by Love and Yerex (1976). The Coastal Construction Company* is to introduce a new product, transmission poles for electrical utilities, and the location of two new production facilities is to be determined. Figure 4.1 shows a section of the yard area and the three relevant existing facilities. The concrete batching plant supplies the premixed concrete used in pole construction. The steel manufacturing area supplies the steel hardware used in pole production, about half of which is embedded in the concrete and forms part of the finished pole. All completed

Figure 4.1 Layout of Existing Facilities.

(Reprinted by permission, "Application of a Facilities Location Model in the Prestressed Concrete Industry," Love and Yerex, Interfaces. Vol. 6, No. 4, August 1976. Copyright 1976. The Institute of Management Sciences, 290 Westminster Street, Providence, RI 02903.)

20-18 16

14 4-12 10 -

Concrete Batching Plant

Existing Building A

Steel Area Manutacturlng

Existing Building

Shipping Gate

8 10 12 14

*This is a fictitious name.

MULTI-FACILITY LOCATION

production moves through the shipping gate, where it is checked and weighed before leaving the yard.

The two new facilities are a concrete casting area, where the poles are cast, and an assembly and storage area, where the remainder of the steel hardware is added. To develop numerical data, a sales estimate of 40 poles per day is used as a production norm. These 40 poles require approximately 10 cubic yards of concrete and 8400 pounds of manufactured steel. The required handling equipment is as follows:

Concrete (3 cubic-yard buckets)-flatbed trucks Steel (in drums)-front-end loader Poles-hft crane and flatbed trailer

A field accountant supplied historical costs for each piece of handling equipment based on studies of existing operations. The following cost-distance values were then computed:

Table 4.1 Cost Estimates for the Coastal Construction Problem.

Based on these estimates, the following daily costs in dollars per 100 feet betyeen all pairs of facilities were computed:

Forbidden regions for location are shaded in Figure 4.1; the coordinates are m units of 100 feet. Locations are denoted as follows: concrete casting area, , = ( :„, ,2); assembly and storage area, = ( :); concrete batching plant, a, = (10,20); steel manufacturing area, a, = (7,6); and shipping gate, «3 = (13,0). Temporarily ignoring the effect of the forbidden

regions, the location problem is to determine the values of and that minimize:

WMiX) = 0.80 + 0.80 S,{X,,a2) + 0.80 SlX2,ai)

+ 0.40 , ) + 4.0 (.{ ) Methods for solving problem (4.1) are generalized from those for solving problem (2.1). We will first discuss the rectangular distance case, of which the Coastal Construction Company problem is an example.

4.1 THE RECTANGULAR DISTANCE MODEL

For rectangular distances, WM{X) in problem (4.1) becomes:

Itl

WMiX) =22 uAn - aj + \x,2 - a.J) 1=1 /-1

«1-1 III

+ 22 2iXK - + \x-2 - x.i). (4.2)

As in the case of the single-facility problem, WM(X) is separable (into two functions). In particular:

where:

WM(X) = WM,iX,u..;X„n) + WM2iX,2,-,Xn,2)

m n

WM,{x,„...,x,„,) =22 >"J,* -

+ 22 2„]jf,* -

(4.3)

/-I r-i+\

The minimization of WM{X) can therefore be accomplished in two separate steps: minimizing WM, with respect to ,1,..., 1, and minimizing WM2 with respect to 2,..., ,„2- We already know that the terms - AjaI are convex, and the convexity of the terms W;,,] - Xri\ is the subject of Exercise 4.1. Because the sum of convex functions is convex, WM, is a convex function, as is WM itself.

A Linear Programming Approach

We will now show how to minimize WMt, by transforming the problem to linear form and using linear programming. To develop an appropriate formulation, new variables representing absolute deviations are first in-

troduced. These deviational variables are intended to behave in the following way:

dtik = Ka " if ujk and is 0 otherwise; d7jk = \Xik - a,k\ if J,*. = ciji, and is 0 otherwise.

Similarly:

= \Xik - Xri\ if x,i, x,i, and is 0 otherwise; h-k = x,!\ if Xik Xrk and is 0 otherwise. The function WM given by equation (4.3) can now be linearized as:

2 2 >io(«i+<„t) +22 w2,v(+*+e-,t).

(4.4)

/-1 J-1

However, we must ensure that the new variables behave as intended. This is accomplished by appending constraints to equation (4.4) to obtain the following linear programming problem for dimension k.

minimize Z, = 22 i/Xi + «7*) +22 iXtrk + e,>A)

/- I I /-I r~i+ I

subject to:

(4.5)

Xik - uoA + = * for i=\,...,m and J=l,...,n,

x,k - x,A - + e,H = 0 for =1,..., -1; r=/+l,...,m,

and all d7ik, < et, e-, 0.

The formulation includes non-negativity constraints on the ,%. This is innocuous if the origin of the coordinate system is chosen so that all of the existing facility locations fall in the first quadrant.

Now we claim that dfjk and djj cannot both be positive in an optimal solution. For example, let us say dtjk = 3 and </,7a = 1 in a given feasible solution. The; relevant constraint specifies that x,vt + 3 - 1 = a, and the associated cost w,,/3+1) is registered in the objective function. However, this solution can be improved upon by setting dfjk = 2 and rf = 0 because the associated cost then drops to w,y<2 + 0) while the difference of 2 between :, and is preserved. In this way it can be shown that from each pair of dtik and d variables, at least one variable must be zero in an optimal solution. (This assumes „ > 0. However, if w,,y = 0, the pair of variables is extraneous and is to be omitted from the formulation-together with the associated constraint.) Similar reflection will show that elt, and ej, cannot both be positive in an optimal solution. This implies the deviational variables behave as intended.

Assuming rectangular travel distances, we can solve the Coastal Construction Company location problem by solving the foUowmg pair of linear programming problems:

minimize Z, = 0.8Q(dn,+dn,)

+ . .+ .) + 0.80¹,+22,) + 0.40¹ 1 + 4- ,)

subject to:

- din + 41, = 10

X,, - 4"2, + 421 = 7

, + dr,, = 13

dtn + dTn = 10

dL + 2-2, = 7

, + 2-3, = 13 X,, - Xi, -21 + 21 = 0

minimize Zj = OMidtn+dm)

+ 0M(dt22 + dT22) + 0M(dt22 + d222) + 0.40(432 + 2 ) + 4.00( 22+ 22)

subject to:

X21 X2,

X,2 X,2 X,2 X22 X22 X22

dn2 + dn2

dt22 + 122

i32 + ? 32

4"l2 + 2i2

?22 + 422

4 2 + 232

- X22 -fi22 + e\

20 6 0

20 6

0

0

and all variables are non-negative.

The dijk variables may be interpreted intuitively in a given application. The first subscript refers to the new facility number and the second refers to the existing facility number. The third subscript indicates whether 4*; corresponds to distance along the horizontal {k = 1 problem) or the vertical (Jc = 2 problem) direction in Figure 4.1. At optimality, ni + dn I measures the horizontal distance between existing facility 1 (concrete batching plant) and new facility 1 (concrete casting area). If the location of the casting facility is to the left of the concrete batching plant, dfy, is zero and dn\ measures the horizontal distance between these facilities. Otherwise, d is zero and dtn measures this horizontal distance. In the same way, 4*12 + 112 measures the vertical distance between the concrete batching plant and the concrete casting area; d\2 measures the distance when the casting area is below the batching plant, whereas dt\2 measures this distance when the casting area is above the batching plant. Each new-to-exisling facility pair has associated with it four of the 4y/t variables; two for the horizontal problem and two for the vertical problem. Similarly, the sum et2\ + e2\ measures the horizontal distance between the two new facilities, whereas et22 + eui measures the vertical distance.

The optimal solutions to the linear programs for the Coastal Construction Company application are x*,, = x*2, = 7 and x*i2 = x*22 = 6, respectively, with a total daily cost of ZT + Z? = $18.40. This indicates

that the two new facilities are to be located together adjacent to the (forbidden) steel manufacturing area for maximum materials handling cost savings. This solution was implemented by the company.

Management did not recognize the existence of a location problem in this form. The location study had not been specifically requested, but was suggested by a production analyst who was enrolled in a facilities location course! It is not possible to state with certainty the exact savings that were achieved by using the model, as management had not reached an earlier decision regarding the location of the new facilities. However, one possible set of sites that had been considered located the concrete casting area at location (10,18) and the assembly and storage area at location (13,10), with an associated daily cost of $69.60.

But what if the 40-poles-per-day sales forecast is not accurate? Conveniently, the optimal locations of the new facilities would not be different with a different sales volume, because all material flows between facilities are proportional to the flow of finished poles fi-om the yard. For example, with a sales volume of 80 poles per day, all coefficients in the objective functions of the linear programs would be doubled. Because the constraints remain unchanged, the same facility placements would be optimal.

The linear programming approach allows for linear constraints on the locations of the new facilities. Had it been desirable to locate the concrete casting area below x, = 6 and to the right of .v, = 10, the constraints x,i 10 and x,2 < 6 could have been added to the respective formulations. Several computer runs testing out various combinations of constraints may be necessary before the best locations are found when forbidden regions are present. If a constraint involves x,, together with x,2, such as .v,i + X2 10, the linear programming problems cannot be solved separately. A combined formulation is then required.

Traveling Along Edges

We now describe an approach to minimizing WM that is computationally more efficient, but which (unless specially adapted) precludes constraints on the locations of the new facilities. The basic idea is this: The convex surface HWt(x,,, -, ) is made up of plane segments. In two variables the three-dimensional surface may be visualized as the bottom of a diamond-sometimes of unorthodox cut (see Figure 4.2). We may imagine "travel" to a lowest level (minimum) along the edges. Because of convexity we are guaranteed that as long as we keep travehng downward, we will eventually reach the minimum. Fortunately, "edge travel" is straightforward and, in fact, is based on techniques developed in Section 2.2. The preceding, admittedly vague, description is illustrated with an example.