problem to be solved, ie, of maximizing the signal strength of the weakest signal to be received at X, may be formulated as . . .

maximize min\IJ{ll2{X,a)f,j = 1,

where F is the feasible region. This maximin problem is equivalent to the minimization over XtF of

M{X) = max{w,je2(X,a,),; = \,...,n].

(6.1)

with (positive) weights given by w, = 1/ . This, in turn, is an example of a minimax criterion applied to a location problem.

Let C/Xo) = {X\ wMX,a) o), and let C(Xo) denote the intersection of all the circular sets Qxo),; = 1,Then = M{X*) is the smallest value of Xo such that the intersection of C(Xa) and Fxs not empty. These concepts have direct graphic expressions.

Example 6.1 Let there be five radio transmitters located at (3,2), (6,2), (4,4), (8,1), and (5,7) with intensities 1, 1/4, 1/4, 1, and 1, respectively. The weights are therefore 1, 2, 2, 1, and 1, respectively. Figure 6.1

Figure 6.1 Graphic Analysis of Example 6.1.

illustrates construction of the intersection set C(Xo) for Xq = 4. The circular region CiiXo), for example, is the "listening area" enclosed by the circle centered at Uj with radius Xo/w. A receiver located therein with sensitivity Xo can monitor the signal sent by the transmitter at location «22. Then C(Xo) represents the region within which to place the receiver to monitor the signals of all n transmitters. The feasible region here is the entire plane (no forbidden zones). As Xo is reduced to 3.474, X* = (5.689,3.595) emerges as the single member of C(Xo), and therefore is the optimal location of the receiver. If F implied location along a road or outside a body of water, the analysis would include a graphic display of F in order to consider the intersection of C(Xo)and F.

The minimax criterion might be adopted when the facilities to be located provide goods or services under conditions of urgency, or when system response depends on the "weakest locational link." Examples of applications include locating industrial services (rapid delivery, troubleshooting); locating public facilities (fire alarm boxes, ambulance bases); or designing detection or signaling systems (radar systems, early warning sirens).

There are two important observations that can be made upon careful consideration of Figure 6.1. First, there will exist a subset of two or three existing points a, such that C(x?) is the intersection of the circular regions for these points. In the example, transmitters at a, a, and determine X*. If W4 were changed to 1/2, then «2 and «25 would determine X* = (5.664,3.666). The second observation is that the minimax criterion is a "grease-the-squeaky-wheel" criterion, because only the extreme existing facility locations determine X*. No account is taken of the average distances. Whether this sensitivity to outliers is problematic must be determined within the context of the application. Minimax formulations imply "fequity" considerations since the poorest service is made to be as good as possible.

Further lessons can be gained from graphic analysis. Suppose a helicopter ambulance base is to be located and the population to be served is spread oyer a convex polygon (H) with a finite number (n) of corner points. (Convert any nonconvex polygon to a convex polygon by joining the vertices.) Figure 6.2, which is based on a similar figure in Nair and Chandrasekaran (1971), illustrates that a minimax location will be at the center of the smallest circle that encloses H. The circle in Figure 6.2(b) is not a minimum covering circle and so X is not the minimax location. Figure 6.2(a) illustrates that a minimum covering circle will pass through at least two corner points. Only corner points vrill determine the extreme distances to the facility. Thus, letting the a/s correspond to the corner points and the w/s = 1, the helicopter base location problem may be solved by minimizing M(X) in equation (6.1).

Figure 6.2 Covering Points and Covering Circles.

A formal definition of the (unconstrained) distance multi-facility problem is to find X* that minimizes MMX), given by:

( ) = max {> „ , ,), / = l,...,m, j =

wJiXM, i = \,...,m-\; r = i+\,...,m] (6.2) where X = (X„...,X,„), AT, = ( ,,, ,2), and the weights are non-negative. We shall assume that each new facility is chained (Section 4.2) to at least one existing facility. The single-facihty case is given by omitting the elements W2jp(X,,X,) from the set that determines MM(X). Otherwise these terms reflect interaction between the new facilities themselves.

It is appropriate to consider whether MM{X) indeed takes on a minimum value. Because wjeiXa) and W2,MX,,Xr) are continuous functions, MM(X) is continuous. For any X, say, with an X, outside the smallest rectangle enclosing all existing facility locations a,, there is an X" with all X, inside the rectangle such that MM{X") < MM(X). The existence of a minimizer X*, say, for MM(X) is thus guaranteed by the extreme value theorem.

A mathematical programming formulation that facilitates subsequent discussion of solution procedures and derives from the intuition gained from Figure 6.1 is:

minimize Xo

Xo,X

subject to

Xo » WiijCpiXaj), i = l,...,m;J = l,...,n

Xo > W2jpiX„XX i = l,...,m-l; r = i+\,...,m.

(6.3a)

During the course of minimization the value of Xo will be reduced. The effect is to reduce the largest of the weighted distances. When Xo is minimized, the binding constraints correspond to the weighted distances that are equal to the minimax weighted distance.

Let Zq = X6, then formulation (6.3a) can be put into a computationally convenient form. Upon raising both sides of the constraints to the power p, we obtain:

minimize Zq

Zo,X

subject to (6.3b)

Zq > wujl\xn-aj\" + \xa-aj2], i = \,...,m;j = l,...,n

Zo > vv?,.[ki-4ip + \x,2-x44 i = l,...,w-l; r = i+l,...,m.

As well as avoiding p" root operations, formulation (6.3b) is differentiable for p > 1, ie, the constraint functions are now differentiable everywhere. Discussion of the p = 1 case is deferred to Section 6.2.

As noted, the minimax criterion is insensitive to the magnitude of weighted distances that are less than MM(X*). Remedies include mandatory closeness constraints such as j?,,(X„a,) = b, feasibility constraints such as giX,i + g2Xi2 < b, or the embedding of formulation (6.3) in a multi-objective framework. The first two remedies are considered after the ensuing discussions of solution approaches for Euclidean and rectangular distance problems.

6.1 EUCLIDEAN DISTANCES Unweighted Single-Facility Problems

A convenient quadratic program is an immediate consequence of formulation (6.3b) for the unweighted (all w, = 1) single-facility Euclidean distance problem. Using the substitution = Zo - (x? + x reduces formulation (6.3b) to the following:

minimize xf -f xi + Xj

Xi,X2,X3

subject to (6.4)

2x,a,, + 2 2 ,2 + Xj » aj + aji,] = 1,

This formulation gains access to finite quadratic programming algorithms.

Graphic methods also have natural appeal here. These are motivated by the following property from Nair and Chandrasekaran (1971), which was observed in Figure 6.2.

Property 6.1 [Minimum covering circles and corner points]. The minimum covering circle of a convex polygon will pass through two or more of its corner points, and all such corner points cannot be on less than half the perimeter of the circle.

An example of the use of these observations is contained in the following algorithm. When reduced to algebraic terms and implemented on a computer, the algorithm is very efficient.

Elzinga-Hearn Algorithm

Step 1 Plot the existing facility locations as points on a graph. Construct the convex hull H of the points. Choose the two corner points of H that are farthest apart. Construct the minimum covering circle for the two points. If this is also a minimum covering circle for H, terminate. Otherwise, choose a (likely) corner point outside the circle, and proceed to Step 2.

Step 2 If the three points define a right triangle or an obtuse triangle, exclude the point at the angle greater than or equal to 90°, and return to Step 1 with the remaining two comer points. Otherwise, proceed to Step 3.

Step 3 Construct the minimum covering circle for the three defining points. If this is also a minimum covering circle for H, terminate. Otherwise, choose a (likely) corner point outside, call it D, and label as a point from among the three defining points that is farthest from D. Extend the diameter of the current circle through point A to divide the plane into two half-planes. Label as the defining point in the same half-plane with D, and label the remaining point as C. Return to Step 2 with points A, C, and D.

If in Step 2 the three points are on a straight line, consider this a degenerate triangle with a 180° angle at the intermediate point. To construct a circle through the three points in Step 3, construct perpendicular bisectors of any two sides of the (acute) triangle; the intersection of the two bisectors is the center of the circle. Convergence of the algorithm derives from the increasing radii of the circles created and the finite number of possible two-point and three-point circles. The users visual inspection of the problem (using interactive computer graphics) will produce "likely" candidates in Steps 2 and 3.

Weighted Single-Facility Problems-Interactive Computer Graphics

The strategy of the Elzinga-Hearn algorithm can be extended to weighted problems. However, we will describe an approach that represents a dis-

tinct departure from the mathematical programming orientation of most techniques in this text. Here we require a person at a computer graphics terminal to test visually for intersection of circular regions. This idea is attractive because human pattern recognition can be used to detect whether C(Xo), for a given Xq, intersects with a feasible region F of irregular (perhaps nonconvex) shape possibly dictated by the inclusion of forbidden regions (also of irregular shape).

Let Xo denote the constrained minimum value of M{X) in equation (6.1), for which X is constrained to be in F. Then observe that C(xo) and F do not intersect if Xo < Xo whereas there is an intersection if Xq > x„. This dichotomy enables the following iterative bisection search for Xq.

Brady-Rosenthal Interactive Graphics Minimax Algorithm

Step 0 Choose e > 0, and set LB = 0, UB = M where M is a finite number sure to exceed Xq.

Step 1 Set Xo = (UB+LB)/2. If UB-LB <. t, terminate; Xq = Xq.

Step 2 Otherwise, display F and Qxq), = 1graphically. The user observes whether or not C(Xo) intersects F. If so, set UB = x; otherwise set LB = Xq. Return to Step 1.

It is envisioned that the algorithm would be implemented in two phases using color graphics. The circular sets C,<Xo) might be shaded blue, whereas the background might be white. Once easily discernible, the set C(Xo) might be red. In the first phase the user would apply the approach to find the unconstrained minimum xf,, say, where F is temporarily the entire plane. The second phase would begin with UB = M and LB = x and require the user only to determine if C(xo) and (the original) F intersect. The regfbn F might conveniently be drawn by the user with a light pen.

The more complicated first phase might necessitate a verification procedure in Step 2 to avoid human error. If the user indicates C(Xo) = , the user would be required to identify j,, and J2 such that C„(Xo) and Cjlxo) do n,ot intersect. If C(Xo) is indicated, a light pen would be used to indicate a point in C(xo). Alternatively, a mathematical algorithm, such as that described in the next section, could be used in the first phase to find xS without human intervention. This avoids a possibly difficult recognition task in the first phase.

Addenda

Suppose an ambulance base is to be located. If a trip is made from a base located at X to the /" response zone, centered at a„ a trip must then be made to the hospital nearest to a,. Let g, measure the expected trip time