70 -- 88.1 (21,66)

*. 96.2 (23,64) 76.3 (43,53)

60 -50 -40 --30 -20 -10--

7 1 (20,81)

••42.5 (22.5,80)

•67.0 (82.78)

•2.5 (62.5,64) • 24.0 (66,56)

76.3 (43,42.5). «83.3 (74,47) •28.8(8,42.5) • 13.6 (65,44)

•94.3(39.36) .43.2 (79,36)

• 16.1 (13,29) .86.8(48,27) .32.7(77,26)

.47.8 (69,18)

35.1 (1,5) -1-h-

10 20 30 40 50 60 70 80 90 100 Figure 7.1 Demand Locations and Their Annual Requirements.

Let the amount supplied by the new facility to the p* existing facility be given by w,j. Then, to minimize total weighted (fp) distances:

minimize L{X, IfO = Z S w,A(X„a,) X,W

subject to

(7.1)

w„ 0, z = \,...,m;j = 1,...,«,

where X = iX„...,X,n), W = (Wu,w,2,...,w,„h,„...,w,„J.

Problem (7.1) has a nonlinear objective function that is neither concave nor convex, and generally contains many local minimizers. This means standard nonlinear programming algorithms may fail to produce a global minimizer.

We call this model the location-allocation problem. However, we do not mean to imply that all actual location-allocation problems can be adequately represented by problem (7.1). Among the prominent factors that may impair the use of the model are the following: The requirements Wj may depend on the new facility locations. Transportation costs may not be adequately expressed as weights times distances. The total cost may involve other significant components besides transportation costs.

10 20 30 40 50 60 70 80 90 100 Figure 7.2 Possible Location and Allocation for Three Distribution Centers.

There may be flows between the new facilities. Finally, it may be more appropriate to maximize profit.

We emphasize that this is a site-generating model. It is intended to give a rough cut at an optimal distribution design, perhaps for input to

Figure 7.3 Optimal Location and Allocation for Three Distribution Centers.

"2

• 67.0

H-1-1-1-1-1-1-1-

10 20 30 40 50 60 70 80 90 100

90 -80 -

the more detailed models of the following chapter. Yet there are applications for which formulation (7.1) is quite appropriate (see the Blue Water Farms problem, Exercise 7.4). As observed by Ostresh (1975), "Applications of the analysis of continuous space problems (site-generating models here) include the locating of helicopter serviced emergency medical units, in which travel time is essentially proportional to distance; and the whole realm of long range facilities location planning, in which todays costs and times are probably a less reliable estimate of future costs than measures derived from distances."

7.1 ONE-DIMENSIONAL LOCATION-ALLOCATION BY DYNAMIC PROGRAMMING

Suppose all existing facilities are situated on one route, or equivalently on a straight line given by the x-axis. This means SpiXaJ) = X, - aj because X, and uj are now one-tuples and [\x - ]"] = x - a\. One type of application is the placement of supply, storage, or processing facihties along transportation or flow arteries. An example of the location of sewage treatment plants along a river basin is given by Converse (1972). To illustrate the difficult nature of problem (7.1), even in this one-dimensional context, consider the following example where two new facilities are to be located with respect to five existing facihties. The requirements Wj and locations Uj are given as:

w, = 2, = 2, Wj = 2, W4 = 2, W5 = 1,

a, = I, = 2, a, = 3, = 6, as = 15.

An early heuristic solution approach used was to alternate between locating the new facilities and allocating the existing facilities to their nearest new facility until neither the locations nor the allocations changed. Suppose this procedure led to:

Xi = 2, w, = w, = 2, w,2 = W2 = 2, w,3 = Wj = 2, w,4 = w,5

X2 = 6, W21 = W22 = W23 = 0, W24 = W4 = 2, W25 = W5 = 1,

with { , ) = 13. Since the values of X, and X are optimal given the values of the w,„ and the values of the w„ are optimal given the values of the Xi, the procedure terminates. The following solution is optimal, however:

A*e[2,3], )vT, = w, = 2, vvfj = VV2 = 2, wTs = Wy = 2,yvf=w = 2, w*, = 0, :? = 15, vvf, = w?2 = 1 = w?4 = 0, w*5 = W5 = 1, with LiX*,W*) = 12.

A dynamic programming approach can be used to produce optimal solutions to the one-dimensional case of problem (7.1). For notational convenience, let the existing facilities be numbered so that aj < 0;+,, J = 1. As there are no capacity constraints, each existing facility

is optimally allocated to the nearest new facility (ties broken arbitrarily). This observation together with the numbering convention used for the existing facilities leads to a fundamental insight: Existing facilities will be optimally allocated to new facilities in sequence. For example, if existing facilities 1 and 4 are optimally allocated to a given new facility, so also will existing facilities 2 and 3. Let the stages of the dynamic programming formulation be the number of new facilities yet to be located. The stage number is given by i, i = l,...,w. The state is measured by s, the index of the lowest numbered unallocated existing facility. Then m - i+l =s 5 = n - i+l if / < m, and s = 1 if / = m. Let A,(s) be the set of all possibly optimal subsets of allocations of existing facilities to the i new facility, given 5. Each such subset is represented by an index t„ s t, n - i+l if i 1 and t, = n otherwise. Let IVis.t,) denote the minimum weighted-distance cost of the new facility optimally located with respect to allocated existing facihties s, s+l,...,t,. Let X*(s,t,) be an optimal location that produces W(i,0- This means X*{s,t,) is a minimizer for:

WiX,-s,ti) = X Wj\X, - a,\.

Efficient techniques have been discussed (in Section 2.2) for finding Xf(5./,).

The recursive dynamic programming relationship is:

/*(5) = min {f,{s,t)l

(7.2)

where f,(sj,) = W*{s,t,) + ft,U,+ l). Stated in words, (5) is the minimum weighted-distance cost of allocating existing facilities s, s+l,...,n, to / new facilities. The approach is probably best "explained" by an example.

Example 7.1 The location and requirements of seven demand points are given in Table 7.1. Three distribution centers are to be located. Corn-Table 7.1 Data for Example 7.1.

putations for the three dynamic programming stages are shown in Tables 7.2, 7.3, and 7.4 where tf denotes the minimizer in equation (7.2).

Wefind/3*(1) = 10.5, with ? = 4, ! = 6, and /* = 7. In the notation of problem (7.1), this means:

X*, = (1,4), w?, = w, = 2, w*,2 = W2 = 1, w*, = w, = 2.5, w*,= w,= 1.5,

= Xf{5,6), Hf 5 = W5 = 2.5, Hf, = = 4,

X* = X*(7,ll w, = w, = 3,

and all other w*if> equal zero.

We have implemented the algorithm on a computer. For simplicity the value of X*{s,t;) was determined by evaluating W{X-,s,t) at successive a/s fory = s, s+\,...,t, until a minimizer is found using conditions (2.15). The shapes of sample computing time functions are shown in Figures 7.4 and 7.5.

The shapes are not unexpected. The number of minimizations of W(X,\s,t) at each stage is of order n~m and the number of stages is m. The average computation time to do one minimization will be of order n-m because /, ranges from 5 to +1, and j ranges from w- -1 to 1- Total computation time then should be of order { - . With

Table 7.4 / = 3.

ms) x*{s,t*)

s/t.

12.5 12,5 11.5 10.5 18 10.5

Computing Time

20 40 60 80 100 120 140 160 Figure 7.4 Computing Time in Relation to n for w = 7.

n fixed and m variable, the maximum of ( - occurs at m = n/3. Figure 7.5 shows that this a good prediction for n = 1 .

Unfortunately, the dynamic programming approach doesnt generalize to two-dimensional problems. This is because the fundamental insight is no longer valid. (There are some exceptions-see Exercise 7.2.)

Determining the Number of New Facilities

When each new facility has the same constant operating cost per unit time, problem (7.1) can be extended to determine the optimal number of new facilities, as well as the optimal locations and allocations. For a warehouse location problem the fixed operating cost might correspond to the monthly fixed rental charges. The optimal weighted-distance cost is computed for increasing numbers of new facilities and added to the total fixed operating cost. Performing this analysis for Example 7.1 gives weighted-distance costs of: 43, 16.5, 10.5, 6.5, 3.5, 1.0, and 0.0, respectively, for m = 1,2,...,7. Augmenting these costs with an operating cost of 10 per unit time for each new facility gives the results depicted in Figure 7.6. The weighted-distance cost is strictly decreasing in m, whereas the operating cost increases linearly. It is best to use m* = 2 distribution centers with an optimal total cost of 16.5 + 2(10) = 36.5.

Notice that the total cost for the best configuration of m = 3 distribution centers is 40.5 which is about 11% higher than the least cost for an optimal number of centers. This is not an unusual finding in distribution studies. The total cost curve for an optimally configured distri-