In the subsequent three sections, W(X) is minimized for straight-line, rectangular, and general (£„) distances. What follows is a hypothetical example, created out of whole cloth, of a typical location problem.

Example 2.1 Bulk shipments of an industrial chemical arrive in 10-ton modules at a railway depot. The users of the chemical are clustered some distance from the depot and order the chemical in relatively small lots to avoid storage and inventory expenses. The supplier of the chemical is therefore considering the best location on which to construct a warehouse that would receive modules from the depot and then distribute them to the users.

Sacrificing realism for brevity, let us assume that there are only four users. Their locations and demands per year are given in Figure 2.1. Let us further assume that the cost per module per mile is $20.00 for transportation from the depot and $8.00 per ton per mile for distribution from the warehouse to the users.

Making the colossal assumption that all relevant cost structures in the system have been specified, W{X) as given in problem (2.1), can now be constructed. There are five existing facilities, including the depot. The weights can be calculated as in Table 2.1. If we read the coordinates (a,„aj2) of the existing facilities from Figure 2.1, and assume, for example, that p = 1.7, we have:

}V{X) = 400(x, - 1 + \x2 ~ 9)"-

+ \ , - 2" -I- \X2 - 5p)/-

+ 240( ;, " 6" + \X2 - 5")"-

+ I60(x, - 7" + \X2 - 10)-

+ 220( : - 15i + \X2 - 2")

The problem is to find the location (Xt,X2) that minimizes W(X).

2.1 THE STRAIGHT-LINE DISTANCE PROBLEM

We now turn to a mathematical description of the straight-line (Euchd-ean) distance problem and to two of its very basic properties. To solve problem (2.1), a single new facility must be located among n existing facilities on the plane in accordance with the criterion that the sum of weighted distances be minimized. Because the straight-line distance (p = 2) between the new faciUty at ( „ 2) and an existing facility at (0,1,0,2) is:

je2(X,a,) = ((X, - a,,y + (X2 - 2 )

0 5 10

Figure 2.1 Schematic of a Facility Location Problem.

problem (2.1) becomes:

minimize W(X) = - > + (2

,2 . (2.2)

It is useful at this point in the discussion to introduce the concept of a convex function. A function f(X) is said to be convex if the line segment between any two points, [X\f{X<)] and [ "")], on the graph of the function never lies below the graph. Formally, this means /(X) is convex if

f[XX> + {1 - ) < /( ) + (1 - X)f(X)

for all and X and any [0,1]. The notation X and X is used to denote two distinct points in the domain of / A function f(X) is said to be strictly convex if the above inequality holds as a strict inequahty for all distinct X and X and any \e(0,l). Strict convexity of / means that the Kne segment lies strictly above the graph except at the two endpoints of the segiAent.

Table 2.1 Calculation of Weights.

Property 2.1 [Convexity of Wje/X.aJ]. w/ZX.aj) is a convex function of X.

The proof of convexity is given in the Appendix, mathematical note 2.1. Note that this property would not hold if the weight were negative. It can be shown (see Exercise 2.1) that the sum of convex functions is convex, and hence W{X) itself is convex. This means local optima are global optima for problem (2.2), and WiX) has no inflection points. With this information, we are assured that the extremal equations for W{X) can produce only global optima for problem (2.2). These equations are:

dW{X)

dXi,

for k= 1,2.

(2.3)

One difficulty immediately presents itself The derivatives in equation (2.3) are undefined if e2(X,a = 0. Therefore, if an optimal location for the new facility coincides wdth that of an existing facility, equation (2.3) cannot be used to check optimality. Fortunately, we can easily check each existing facility location for optimaUty.

Property 2.2 [Minimum ofW(X) at an existing facility location]. W(X) is minimized at the r* existing facility location (ari.aj if, and only if

CR, =

L V-1

Wj(a,x - a,S\

Il2ia,,a

Uar,a)

(2.4)

A ready explanation for Property 2.2 is provided by the analog model in Exercise 2.2. A derivation is in the Appendix, mathematical note 2.2. There now exist many different iterative methods for finding a solution to problem (2.1). One of the oldest, as well as perhaps the simplest, follows.

In addressing the problem of minimizing ), let us temporarily ignore the possibility that the new facility location will coincide with an existing facility location. A procedure for iterating to the optimum location can be obtained by rewriting equation (2.3) so that we have one equation for Xi and one for Xj:

(2.5)

Note that x is not really isolated on the left-hand side in equation (2.5) because each £2{X,aj) is a function of x. However, equation (2.5) can be used iteratively to approach (x=f,x?), the optimum new facility

location. We refer to this procedure as the Weiszfeld procedure (see Chapter 1). Let us imagine that we have just completed iteration £ and have obtained the location {Xi\X2>). We can then use equation (2.5) to find the estimate of iteration (£+1):

„ £2( > )

(2.6)

Before beginning the iterations, an initial location (x/*,X2<>) is required. An expedient choice is the solution to the squared Euclidean distance problem, which is the same as problem (2.2) except that each distance £2i-,aj) is squared. As shown in Exercise 1.2, the center-of-gravity location solves the squared Euclidean distance problem; hence, our starting point for procedure (2.6) is:

x,">

~=„- for k= 1,2.

(2.7)

The iterations will converge to an optimal location, provided that neither an iterate nor an optimal new faciUty location is at an existing facility location. References for convergence properties are given at the end of this chapter. Though we would expect convergence difficulties with the iterations when {x,x) coincides with an existing facility location, these difficulties do not generally materialize. When CR in condition (2.4) is much smaller than w,, convergence is fairly rapid; as £2{,ar) in equation (2.5) approaches zero, computational difficulties could eventually arise. Experience shows that when condition (2.4) is near equality (whether or not it is met), convergence may be slow. It is therefore helpful to check all existing facility locations using condition (2.4) first. If condition (2.4) is not met, but CR, is nearly equal to w, at some existing facility r, iterations could be started near that point. Convergence may also be slow for certain weight structures. We are compensated by the fact that in such cases the cost "bowf is usually shallow in the vicinity of the optimum solution.

The practical question of when to terminate the procedure can be answered by the use of a stopping criterion that employs a lower bound on the optimum value of IV(X). This lower bound is continually updated during the iterations. To derive this bound we need the following property.

Property 2.3 [Dominance of the convex hull]. X* an optimal solution to problem (2.1), must lie within Q, the convex hull of the existing facility locations.

The convex hull is defined as the smallest convex polygon that contains all the existing facility locations. A proof of Property 2.3 is the subject of Exercise 2.5b. It can be shown that the starting point defined by equation (2.7) is in the convex hull. Further, regardless of the starting point used for procedure (2.6), the next point will be in the convex hull (see Exercise 2.5a). We will now give a geometrical rationale for a stopping criterion for the Weiszfeld procedure.

To begin the discussion, recall that W(X) is a convex function. This means that a plane tangent to the convex bowl-shaped graph of W{X) at a given point ) underestimates W(X) for any X. In particular, if the partial derivatives given in equation (2.3) exist, this means

W{X) Wm + [dWiXydXiix, - Jti«)

for any X. The gradient VW{X-) is a vector with components given by the respective partial derivatives. Choosing A" = X* we can write:

W(X*) W{X) + VW{X).(X* - X>)

(• denotes scalar product)

W{X - \VWiX)-iX* - X>)\

W{X>) - pWi.X \\x* - «1

(since m • v < m v; Schwartz inequality)

where denotes the magnitude of a vector. But X* and **> are both in the convex hull 0 for j? 1. Hence \X* - cannot be greater than the straight-line distance a{X), say, between X<*> and the point in 0 furthest away from XK Therefore, an upper bound on the improvement in W(X) must be ( <)\< ( ). It is now possible to state the following property.

Property 2.4 [Lower bound on W(X*)].

W{X*) £5W = W{X) - p7W(Xi)\\iriX>) (2.8)

where ( ( ) = max {UX,y)\.

It is, therefore, possible to know an upper bound on further improvement in the objective function value at every iteration in the Weiszfeld procedure. A stopping criterion based on proportional suboptimality can be set using:

Table 2.2 Evaluation of CR,.

From inequality (2.8), whenever LR > 0 we have:

S> (WiX)) - iW(X*))/W(X*).

Hence,if we wish to find an iterate X with relative suboptimality bounded { >) ~ W(X*))/W{X*) < (, iterations need only be continued until < t. For example, if iterations are terminated when S < 0.001, then WiX) is within 0.1% of the minimal value W{X*). It should be mentioned that tighter lower bounds can be obtained (see the Appendix, mathematical note 2.5). This one is presented due to its geometrical simplicity.

Example 2.2 Four existing facilities are located at the points (1,1), (1,4), (2,2), and (4,5). The corresponding weights are 1, 2,2, and 4, respectively. Values of CR, are given in Table 2.2. Because CR, is always greater than Wr, the optimum location of the new facility does not coincide with any of the existing facility locations. Table 2.3 shows iterations from the center-of-gravity starting point, which in this example was quite close to the optimum location. As Exercise 2.4 shows, this is not always so.

When iterations were started at (0,1000), X was (2.557,3.669), thus demonstrating the insensitivity of the procedure to the starting point.

Table 2.3 Iterations for Example 2.2.