back start next


[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [ 16 ] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]


16

Example 4.2 In the following problem, two new facilities are to be located among four existing facilities. Table 4.2 gives the existing facihty locations («,1,0,2); the new-to-existing facility weights, w,,,; and the new-to-new facility weight, 212. We will concentrate on minimizing WM,(x,„X2,). According to equation (4.3), we can write:

IFAr,(x,„X2,) = lxn - 3j + 2„ - 2 + - 1 + 1„ - 5 + 02, - 3 + 121 - 2 + 32, - 1 + 22, - 5 + 2x,, - X2,.

We know that WM,(Xn,X2,) describes a surface in three dimensions. We make the following important observation: In a region of the x, iXj, plane, the surface WM, itself is a plane-as long as none of the terms inside the absolute value brackets changes sign in that region. This is because within a given region absolute value brackets can be replaced unambiguously by parentheses to yield a linear function. Changes of sign can occur only across the lines: x,, = 3, x,, = 2, x„ = 5, X2, = 2, X2i = 1, X21 = 5, and X,, = X2,. These lines must therefore define edges of the surface WM,. The surface WM, and its edges projected on the x„X2, plane are shown in Figure 4.2.

To illustrate the technique of edge travel, we need a starting point. A point at the intersection of at least two of the edge-defining lines will suffice. Let us arbitrarily choose the point (5,5) that is at the intersection of three of the lines and let us attempt downward travel along the edge defined by X2, - 5. In other words, we set X2, = 5 and minimize WM, with respect to x,,. Then:

WM,{x„,5) = \\x„ - 3\ + 2\x„ -2\+ l\x„ - 5 + 2\x„ - 5 + 15.

The constant 15 can be ignored in the optimization. When we apply the median weight approach of Example 2.5 in Section 2.2, we find that the best x„ is the range [3,5]. Setting jc,, = 5, we minimize WM, with respect to X21, where:

WM,(5,X2,) = 12. - 2 + 32, - 1 + 22, - 5

+ 25 - JC21I + a constant.

Table 4.2 Problem Parameters for Example 4.2.

W2,2 - 2

Figure 4.2 The Surface IFM,(a:,„x,,) and the Projections of the Edges on the x„X2, Plane.

The best X2, is the range [2,5]. If we did not know better, we might conclude that the point (5,5) minimizes WM,. However, let us investigate the edge x„ = X2, that goes through the point (5,5). We have:

WM,(x„,x„) = l\x,, - 3 + 2\x„ - 2 + 1,1 - 5

+ l\x„ - 2\ + 3\xn - 1 + 2,, - 5.

The minimum along this edge occurs atx,, = X2, = 2. We then find that X,, = 2 minimizes WM,{x,„2), and 2, = 2 minimizes WM,{2,X2,y, thus the procedure terminates at this point with WM,(2,2) = 13.

There are, of cotirse, alternative "rules of the road" that we could have followed. However, as long as we move downward and investigate all the edges going through a point before declaring it the optimum, we cannot go wrong. For three or more facilities, the surface WM,, is a bit



more difficult to visualize. However, the edges are easy enough to determine. These (their projections) are:

, = for i=l,...,m; j=l,...,n, and = x,A. for 1 =e r < / < m.

The following algorithm, essentially a modified edge descent procedure, formalizes a strategy for exploiting this convex edge structure inherent in WMf,. The algorithm is applied once for each dimension (k = 1,2) of the location problem. It achieves edge descent by optimizing the locations of all single new facilities, all clusters and all subsets of all clusters of new facilities.

Juel-Love Algorithm

Step 0 Find an initial solution. (The initial solution may be found by solving m single-facility problems and ignoring the weights between pairs of new facilities).

Step 1 Improve the current solution by optimizing the location of single new facilities one at a time, until no further improvements are possible.

Step 2 Improve the current solution by optimizing the location of sets of coinciding new facilities, one set at a time, until no further improvements are possible.

Step 3 Check all subsets of each set of coinciding new facilities. If moving some subset improves the current solution, optimize the location of that subset and return to Step 1.

The algorithm continues cycling through steps 1 to 3. It terminates when a full cycle has been completed and no improvements have been made.

4.2 THE DISTANCE MODEL

The general case of WM in problem (4.1) lacks the structure for linearization when 1 < p < oo, and so we must rely on nonlinear optimization methods. However, some useful structure remains.

negative, WM{X) is convex. However, for w > 1, the derivatives of WM(X) may be undefined anywhere on the two-dimensional plane. This is in contrast to the single-faciHty Hp distances problem, where the derivatives are discontinuous only at the existing facility locations a. This derivative discontinuity arises because two or more of the new facilities may occupy the same location anywhere.

Property 4.2 [Discontinuities in the derivatives of the Sp distance function]. The derivatives ofilp(X„X,} and, hence, WM(X) may be undefined anywhere on the two-dimensional plane.

A proof is given in the Appendix, mathematical note 4.2. To eUminate the problem of discontinuities in the derivatives, we will generalize problem (2.19) and approximate WM{X) by:

m n

WMHiX) = 2 S w,,[{{x,-a,,Y+eY + {{x,-a,2y+eYY

+ S i W.Mx.,-X,,Y + ey + {{Xa-X,,y + trYl, /-1 /-/+1

where e > 0.

All orders of derivatives of WMH are continuous everywhere. WMH{X) is a strictly convex function when each new facility is chained to at least one existing facility.

Chained Facilities

New fadlities / and r are said to have an exchange if vvj,, > 0 or W2,, > 0. New facihty i is said to be chained to existing facility j if there exists a sequence of distinct new facilities i, such that there is an exchange

between / and /„ and /, and /2,-,,, and iv,, > 0. We will not consider problem (41) to be well stated unless each new facility is chained to at least one existing facility.

Property 4.3 [Maximum difference between WMH(X) and WM(X)].

Property 4.1 [Convexity ofthe Hp distance function]. Thefunction £(X„ XJ is convex.

A proof is given in the Appendix, mathematical note 4.1. As WM(X) is a sum of weighted convex functions where the weights are all non-

max {WMH(X) ~ WM{X)\ < ) = ltY. Z uj X -ij-i

m- \ m



The proof follows analogously the proof of Property 2.8. By taking aWMH{X)/dx,i„ equating to zero, and "isolating" Xrk on the left-hand side, the Weiszfeld procedure given by equation (2.6) generalizes to the multi-facility case as:

where:

4 " =

+ SA[

for r= l,2,...,m; and fe= 1,2,

= 2

, - a,,y + e]"/ + [(4? - a,2)

0)/2

5,< = 2

-siS- = 2

rt/2

(4.6)

Analogous arguments to those preceding Property 2.4 and succeeding Property 2.8 can be used to justify:

Property 4.4 \Lower bounds on WMH(X**) and WM(X*)].

IVMH(X**) LBMH" = IVMHiX") - \\VWMH(X>)\\<7jX>), and WMiX*) LBM = LBMm - „(<).

Example 4.3 Tables 4.3 through 4.6 give the parameters and numerical results for a problem with m = 3, n = 5, p = 1.8, and e = 0.001.

For problems in which one or more of the new facilities are constrained to lie in some subset of the plane (or three-dimensional space if the problem is three-dimensional in nature), it is usually necessary to employ a nonlinear programming algorithm. In this case, it is advisable to replace WM(X) by IVMH{X) in order to ensure convergence of most nonlinear programming algorithms.

Table 4.3 Existing Facility Locations.

(2,3)

(4,2)

(5,4)

(3,5)

(6.7)

It is important to note that 2„ must be evaluated as Wj, whenever r > /. The sequence is relatively simple to program, relatively efficient, and requires very little computer memory space.

A stopping criterion for procedure (4.6) must consider the suboptimality of the current iterate X with respect to minimizing WMH, as well as the error of approximating WM by WMH. The following property defines such a criterion. Let X* and X** minimize WM and WMH, respectively. Let

= = (X„A-2,...,XJ I X, e fi, /= l,...,m],

where fi is the convex hull of the existing facility locations, and let

aJX) = max )]. X

Table 4.4 New-to-Existing Facility Weights w„j.

1 2

3 4 5

* 3

1 1 4 1

1 1

10 1 6 1 1 1 1 1 1

Table 4.5

New-to-New Facility Weights Wj,,.

2 3

1 1 - 1



[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [ 16 ] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]