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]


8

Chapter J

Variations on the Single-Facility Model

This chapter introduces several of the many variations of the basic single-facility model treated in the preceding chapter. The objective remains the minimization of the sum of weighted distances. We begin with location on the surface of a sphere. Using a plane as a location surface assumes that if the location region is actually a segment of the surface of the world spheroid, this segment is small enough for the assumption to provide an adequate approximation. This assumption becomes less tenable as the scale of the location problem approaches the global. The model presented in this chapter uses exact shortest arc distances on the surface of a sphere; such distances can be used as good approximations to actual global travel distances.

The model of the preceding chapter idealized the existing facility locations as discrete points on a plane. Yet problems arise that are difficult to model by this approach. Consider, for example, the location of some facility in a large city. If each member of the population served by that facility is considered to be a separate "existing facility," then the number of existing facilities would likely be prohibitively large. (The term "existing facility" becomes inappropriate, so let us instead substitute the term "destination" in this context.)

A new facility location need not necessarily be modeled as a point in space, either. If, for example, an access way or conveyor belt is to be located, we may well describe its location as a line under the assumption that the facility is reached once the nearest point on it is reached.

In another application, a "point facility" may be called on to serve for many periods of time; during that time the parameters of the problem may change. It may be necessary to plan for the relocation of the new facility one or more times during the planning horizon.



It has also been assumed in the preceding chapter that the costs and other parameters in the model are known; an alternative often closer to the truth is that these parameters are stochastic variables. The case is analyzed wherein locations of the demand points are known only in probability.

The following sections introduce these variations to the basic single-facility location model in their simplest form. They can, of course, be adapted to the more complex models of the succeeding chapters; this has been, and is being done, in the location literature.

3.1 LOCATING A FACILITY ON A SPHERE

Suppose the existing facilities lie on a sphere. Assume that this sphere has a radius of 1.0 to simplify expressions; as will be evident, there is no loss of generality in doing this. Problem (2.1) becomes

minimize W{X) = WjA{X,a X

(3.1)

where X = {x,x, and x, and Xj are the latitude and longitude coordinates of the facility that is to be located. A{X,a]) is the shortest distance, measured (in radians) on the surface of the sphere, between the facility at X and existing facility j at Qj = { ,). Some observations will now be made about the properties of distances, sets, and functions on the surface of the sphere.

Distances, Sets, and Functions

A plane cutting through the center of a sphere will trace a circle on the surface; this is known as a great circle. Examples are the equator and the Greenwich meridian. The shortest distance between any two points on a sphere must be measured along the great circle passing through them and is the shorter of the two arcs between the points. For this reason, this distance is known as the great circle distance or shortest (minor) arc distance. It is evident that the greatest possible distance between two points on the unit radius sphere is . In this case the points are on opposite ends of a line passing through the center of the sphere and are said to be antipodes. As is easily visualized, when angles are measured in radians, the antipode of point X may be written X = (-x,,X2 + ).

The shortest distance between the new facility and existing facility j on a sphere with unit radius is:

(A,aj)=cos-[cos x.cos a,,cos(x2 - a,2) + sin x.sin a,,] (3.2)

where a,, and ,2 are the latitude and longitude, respectively, of the existing facility.

3.1 LOCATING A FACILITY ON A SPHERE

It will be necessary to estabhsh the concepts of spherical circles, convex sets, and convex functions on the surface of the sphere in order to carry out the optimization required by problem (3.1). A spherical circle is the locus of all points with a fixed shortest arc distance from the point that is its center. Note that a spherical circle with radius is actually the antipode of the center of the circle. A spherical disk is the set formed by a spherical circle and its interior.

A convex set on the sphere is such that every two points in the set have at least one shortest arc joining them that lies entirely within the set. For example, a hemisphere is a convex set and so is any great circle. However, a spherical disk with radius greater than /2 is not a convex set.

Let be a point on the shortest arc between two other points Y = Cv„>2) and Z = (Z,Z2) in some subset D of the sphere; X is such that the distance between and Fis A times the distance between and Z. Any function /is convex on D if:

/(F) < \f{Y) + (1 - X)/(Z), where 0 < X < 1. (3.3)

Property 3.1 [Convexity of shortest arc distance]. The distance A(X,aj) is a convex function of X on a spherical disk with radius n/2 centered on point aj.

A proof is given in the Appendix, mathematical note 3.1. This convexity property will be important in determining when the methodology to be described can be expected to produce a global minimizer for W(X). This is true because of Property 3.2.

Property 3.2 [ Unique minimum value for a convex function on a sphere]. A local minimizer of a convex function on a convex subset of a sphere is also a global minimizer.

A proof is given in the Appendix, mathematical note 3.2. The following corollary is definitive (see Exercise 3.5) for problem (3.1).

Property 3.3 [Problems for which a local minimizer is a global minimizer]. If all uj, j ~ l,...,n can be covered by a spherical disk of radius n/4, thfn a local minimizer of W(X) is also a global minirhizer.

Minimizing W(,X)

We first investigate the extremal conditions for W{X). Differentiating, we obtain:

)

)

--2 H-X-sin X, cos cos ( - aj2)

f cos X, sin a„)/sin ( , ),

(3.4a)

dX2 sin (X2 - aj2)/sin A(X,a,Y (3.



These derivatives are not defined at the existing facility locations (or their antipodes) because sin A{X,aj) = 0 at X = a,. However, as was done in Section 2.1 of Chapter 2, we can derive a check to see if there is a minimum at the point a,. The difference here is that unless Property 3.3 is met, this may only be a local minimum.

Property 3.4 [Local minimum at an existing facility location]. W(X) has a local minimum at a, if and only if

(3.5)

where:

CF, = {F + F,)/2

Fn = S vXsin a,, cos a, cos (a,2 - 02) + cos a,i sin a,i)/sin A{a„a)

P,2 = Y.j COS « sin {aj2 - a.2)/sin A{a,,a,).

The proof is given in the Appendix, mathematical note 3.3.

To find a local minimum at other than an existing facility location, set the derivatives in equation (3.4) to zero and solve to obtain:

tan X2 =

2 Wj cos a„ sin flyj/sin A(X,a}

i-\ , .

X w, cos ay cos fljj/sin A(X,a

(3.6a)

tan X sin X2

w, sin Oji/sin A(X,a)

j-i -

Wj cos sin aj2/sin A{X,a

(3.6b)

This is not an explicit solution for x, and Xj because these variables appear on both sides of the equations. However, as was the case for equation (2.5) of the previous chapter, these equations may be solved iteratively by a version of the Weiszfeld procedure. Essentially, if some values of X, and X2 are entered on the right-hand side of equations (3.6), new and better (it is hoped) values are produced. Note that any new X2 thus created by equation (3.6a) could also be X2 + -w.li is the value of the right-hand side in (3.6b), then x, = tan- (K sin Xj). Because sin (Xj + ) =

-sin X2 and tan {-y)--tan y, the antipodes (x„X2) and (-x„X2 -I- )

are actually produced by equations (3.6). This iterative process for some arbitrarily small positive constant £ can be summarized as follows.

Weiszfeld Procedure on the Sphere

Step 0 Choose a starting point ( / ")- Set 11=0.

Step 1 Compute X > by equations (3.6) using to calculate s\nA(,X,a;).

Step 2 If x<,*+) - x\« + +> - xS« > ˆ, go to Step 1.

Step 3 Check {xff , +") and its antipode.

Convergence of this algorithm has not been proved, but has been achieved in all computational studies so far. Unfortunately the stopping criterion stated as Property 2.4 in Chapter 2 cannot, in general, be used here because W{X) is not necessarily convex. The characteristics of this procedure are very similar to those of the Weiszfeld procedure of Section 2.1. For instance, the procedure, as a rule, accomplishes the substantial part of its improvement in the objective function in the first few steps, regardless of the choice of starting point. There is one important contrast. Now convergence may be to a local maximizer and not to a minimizer. However, this need be of no practical concern because of the following easily proved property.

Property 3.5 [Local optima at antipodes]. A point is a local minimizer of W(X) if and only if its antipode is a local maximizer.

Because we can easily keep track of the antipode at each step of the procedure, we can, in effect, always assure that convergence is to a local minimizer. Incidentally, the sum of the objective function values at an-

tipodes is always Wj, and this can be used to shorten calculations.

The following general strategy is recommended. First, condition (3.5) is used to check for local minima at the existing facility locations. Property 3.3 is then used to check if a local minimum must also be a global minimum. Of course, if some point a, is a local minimizer and Property 3.3 indicates that it is a global minimizer, then we are done. Otherwise we must choose a starting point and an "accuracy level" e and carry out the iterations.

Starting points may be chosen in a variety of ways. One should choose several points if a global optimum cannot be guaranteed; they may be chosen at random or, alternatively, uniformly distributed over the surface of the sphere. Sometimes Wendells starting point is used. It is obtained by setting sin A{X,aj) = I in equations (3.6), and it is analogous to the



[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]