is to model distances rather than obtain locations, the unweighted bi metric will likely be inappropriate. Arbitrarily setting = 1 in could result in a serious understatement of total distance.

10.3 THE WEIGHTED ONE-INFINITY NORM

A norm in is a function, \ -\: R \ having the following properties: positivity: v > 0 for v 0; identity: v = 0 if and only if v = 0; triangle inequality: \u + v < + v; homogeneity: avj = ajv for every real number a. We observe that £Jiq,r) is actually vp where v = -r and v,, is defined as [v," + IvjI]", p s= 1.

A hybrid norm based on the extreme norms given by p = \ and p = oo has interesting properties. In particular, letting p , vp becomes max {V,v2l, denoted by v. This limiting process is portrayed in Figure 10.1 for the case p = \00. Letting A:, and be non-negative numbers, not both of which are zero, the hybrid distance predicting function to be studied is:

d,{q,r, ki,k,) = kA{4,r) + k.M Sq,r).

The function d is convex because it is a non-negative Unear combination of convex functions. The reason for the v2 factor is that /2 can be viewed as a rectangular metric defined on a 45° rotated coordinate system (see Exercise 10.9). This can be motivated using Figure 10.1. The unit distance contour for v2 ¸„ would be a contraction of the 2 contour. The contracted contour is simply a 45° rotation of the jP, contour.

Figure 10.2 shows unit distance contours oi df„ which are piecewise-linear approximations of 2 contours when 1 <: p < . The function db can be viewed as characterizing distance in the following way. Let v = q - r. Then the vector v can be considered as representing a trip between the points q and r. Write d as:

(A:, + + \, + v2 KMA:, + . (10.2)

As v2 2J,q,r) measures 2 distances in a 45° rotated coordinate system, these are distances for rectangular paths in the rotated system. Back in the original system these are diagonal paths, ie, 45° rotations of rectangular paths. Therefore, expression (10.2) views kjik + k) of the trip between points q and r as being along rectangular roads, and kJik + k) of the trip as being along diagonal roads. The factor [k + k,) outside the bracket is analogous to the inflation factor in functions , through d. The ratio kjki can be idealized as the relative proportion of a trip using rectangular roads to the relative proportion using diagonal roads.

To test d(, as an empirical distance function the parameters A;, and k were determined by Ward and Wendell (1980) as those minimizing SDf, for the intercity data sets. The SD values and {ki,k: values are 24.225

slope = -fci/(/fi + 42k2)

slope = -(/f, + /2/ 2) ,

*1 = 1, /f2 = 0

fc, = 0, /f2 = 1/\/2

Figure 10.2 Contours for d (g,0; ki,k2) = 1.

(Reprinted with permission from OPERATIONS RESEARCH, 28, 3, 1980, part , Copyright (1980), Operations Research Society of America. No further reproduction permitted without the consent of the copyright owner.)

for (0.62884,0.27320) and 125.249 for (0.53316,0.39251), respectively, for the Wisconsin and U.S. samples. We see that d outperforms d2,the Euclidean distance function for the Wisconsin sample. There is a clear advantage over «i„ which is a special case of df,.

For the Wisconsin sample, / = 2.30, implying a dominant use of rectangular paths. This is borne out by the relatively low value of p (1.57 versus 1.78) for d,, indicating more rectangular bias than in the U.S. sample. Not unexpectedly then, d fares better in the Wisconsin sample.

A practical benefit of df, is that location problems have linear forms. To see this, consider the minimum sum problem:

minimize ) = wd,iX,a/, k

(10.3)

which is:

minimize ,(- \ + j-a.zD + k max{,-a,,, xr-aJ]. X

Using the fact that max !«, = i/2(« + /3 -I- a - 0) we can write max

\>c-a,\, [xj-all as

/2( , + x2- a„ - a,2\ + \c,-x2- aj, + a and using the approach of Section 4.1 for removing absolute values, problem (10.3) can be written as the linear program:

minimize kKid+dji+d + dj) + (dl,+dy, + d], + d-i)] X,d*,d v2

subject to

X, + X2

X, - - rf.S + = - flp

(10.4)

X,, X2, rfjvt.

= \,...,n, j = /: = 1,2,3,4.

The analogous minimax problem is to:

minimize { ) = max{w,u?6(,aj; Kk);] = !,...,«! (10.5) X

which can be written as the hnear program:

mmimize Xo

Xo,d,d~

subject to

(10.6)

x„ > w,[t+aT+at+a2) + (at+3 + a+fi?,4)] J = 1,-,",

together with the constraints of problem (10.4).

Clearly Xo = 0, and so this condition can be added to the non-negativity conditions. The problems are assumed to be posed in the first quadrant in order that the conditions x„X2 > 0 included in problems (10.4) and (10.6) will not affect the optimal solution. Linear constraints on the coordinates X and X2 can be added to restrict location. Extension to the multi-facility cases is straightforward.

It is useful to summarize the trade-offs between using d(, and using d. Both u?6 and d, are two-parameter functions. In comparative studies reported thus far, d has given more accurate fits to geographical data than d(,. Yet u?6 allows for linear formulations of location problems (with a considerable number of variables and constraints), whereas d for 1 < p < 00 yields intrinsically nonlinear location problems.

10.4 EMPIRICAL "METRICS," CONVEXITY, AND OPTIMAL LOCATION

All of the empirical functions except d are metrics; d is not guaranteed to satisfy the triangle inequality. To see this, let d4,Q,r) be written k[£p{q,r)Y, where = p/s \, and lei = \. Consider the points a, = (-1,0), = (0,0), and a, = (1,0). Then d{a„a) = 2 whereas diaa) +

?4((22,(2 ) = 1* + = 2. This means the triangle inequality d(ai,a -\-diaa = daa is violated for A: > 1. However, for 0 < A: < 1, the triangle inequality is preserved (see the Appendix, mathematical note 10.2). For A" = 1, reverts to d, which is a metric. Define:

d\iq,r; k,p,K) = { , )¥ = Ak.-nh + \ 1- \]

where k> 0,p 1,0 < < l.afisa metric. Perhaps not surprisingly, the empirical studies described above typically produced d\ rather than df This is because p/s{ = K) was typically less than unity.

In application using cost terms given by w[d(X,aj)Y, AT > 0, rather than wdiX,a, provides for more general forms of proportionality. Example cost structures are portrayed in Figure 10.3, where w = \. Evidently, d models diseconomies-of-scale and d models a cost function characterized by economies-of-scale. In the case of expression (10.1) travel time may be modeled by af; (as = Vi) for short distances.

Minimum sum and minimax problems involving rf, through d are convex minimization problems. The standard myopic strategy of finding a local optimum, when successful, finds a global optimum. However, typical nonlinear minimization techniques use derivatives to guide the search for optimahty. Because u?(x,a) is not differentiable at X = Uj, J = l,...,n, when given by d„ dj, d, d or d\, something must be done. As described in Chapter 2, distance functions can be smoothed by introducing a constant e > 0. While dlX,aj) is differentiable at X = when > 1 (see the Appendix, mathematical note 10.3), the formula for the derivative yields an indeterminate form there. A computational expedient is to introduce e > 0 and use problem (2.19) to yield:

WH{X) = X w,[((x,-a„) + 6)-/ + ((x2-a,2) + tY\

\Klp

Figure 10.3 Cost Terms as Powers of the Distance Variable.

= V2

WH{X) approximates WiX) when distance is estimated either by or by u?;. For 1 p 2and0 < <i p, A(ˆ) of equation (2.20) becomes:

(«) = 2"e w,.

Modeling with d!, is computationally inconvenient. The following results indicate why, in the context of minimizing W{X).

Property 10.1 [Inconvenience of d4]. W(X) is neither convex nor concave when d4 models distance.

Property 10.1 can be justified graphically. Let = 1 and w, = \/k. Then W(X) reduces to «i(X,i2,; \,p,K) and in the one-dimensional case this becomes :, 0 < : < 1, after shifting the origin to the point a,. The graph of this function would have the shape of the = curve in Figure 10.3 for positive values of Xy together with the mirror image of this curve (with respect to the vertical axis) for negative values of x.

Property 10.2 [Local minima at existing facility locations using d4]. When d4 models distance, W(X) has local minima at Uj, j = l,...,n.

The Weiszfeld algorithm has been proved to converge to a stationary point for W(X) using d or d, when \ p 2 and 0 < A: < p. Limited computational experience with d suggests the convergence point is usually a global minimizer of W{X), although this tendency appears to weaken as Nonetheless, it is prudent to use the algorithm with more than

one starting point. Of course, if d is used, a stationary point must be a global minimizer.

A question naturally arises from this discussion: Can differing parameter values lead to significantly different optimal locations? To see that this can happen, let a, = (0,0), aj = (1,0), and a = (0,1) with tv, =

= w,= 1. The minimizer of W{X) = [(x, - a,,) + (- aj2j»2

is (0,0) when = , (0.2113,0.2113) when \, and (1/3,1/3) when =2.

10.5 LARGE REGION METRICS

Large region location problems arise when the difference between the Euclidean and great circle metrics is considerable. Location of international headquarters, distribution centers, or military bases are examples. As an illustration consider the plight of Jack Smooth (introduced in Exercise 2.10) who is in charge of planning a sales meeting for sales representatives of Globetrotter Business Machines. The company wants Jack

to concentrate on minimizing total round-trip airfare costs for 100 representatives. Departure cities are given in Table 10.8. To generate candidate sites. Jack assumes airfares are proportional to distance and independent of destination. The objective then is to find a point that minimizes the weighted sum of flight distances from the cities. As discussed in Section 3.1, if the point falls in an ocean, some form of sensitivity analysis using objective function contour curves can be used to guide location. This section treats metrics pertinent to such large regional locational analysis.

We vrill approximate great circle distances by converting latitude and longitude to coordinates on a Mercator projection, and then compute rhumb Une* map distances. Specifically, conjure up a Mercator map whose width is 21,600 miles at the equator. Let = (,,2), where is stated in degrees of latitude (north positive, south negative) and q is stated in degrees of longitude (west positive, east negative). Then q is converted to the Mercator coordinate 1 using:

Qi = 7915.704468 log.ocot (45° - 0.5,)-

The map coordinate corresponding to 2 is:

Qi = 602-

The rhumb line map distance between points q and r is calculated according to the Euclidean formula:

d"{q,r) = [{q, - f,y + (q, - , -]".

Table 10.8 Departure Cities for Sales Representatives.

City

Latitude (degrees)

Longitude (degrees)

Number of Representatives

London Paris Zurich Rome

Copenhagen

Berlin

Stockholm

Athens

Ankara

Tel Aviv

Moscow

Teheran

Bombay

Manila

Tokyo

51.5 48.9 47.4 41.9 55.7 52.5 59.3 38.0 39.9 32.1 55.7 35.4 18.9 14.6 35.6

- 0.4

- 2.3

- 8.5

- 12.5

- 12.6

- 13.4

- 18.9

- 23.7

- 32.8

- 34.8

- 37.7

- 51.4

- 72.8 -121.0 -139.7

7 6 7 5 5 5 7 3 5

*Rhumb lines are straight lines on a Mercator projection.