Table 3.1 Locations, Weights, and CF/s of Four Cities.

center-of-gravity starting point in the planar version of the problem. A discussion of this topic is found in Wesolowsky (1982).

Example 3.1 Table 3.1 gives the locations of four cities, their weights, and their CF, values. Table 3.2 gives the interfacility distances divided by the radius of the sphere. Figure 3.1 shows the locations of these cities on the sphere.

As no CFr is less than w„ no citys location is a local minimizer. Also, because the Manila-London distance is 1.68040 > ir/2 = 1.57080, Prop-

Figure 3.1 Locations of Four Cities.

erty 3.3 will not be able to guarantee a global minimum. Table 3.3 shows sample iterations; it is the antipode that is the minimizer in this example. Incidentally, Wendells starting point is (-50.925,-82.694). If were to fall in an ocean, contour curves of W(X) could be investigated (possibly using computer graphics) to obtain a constrained minimizer.

3.2 POINT AND AREA DESTINATIONS WITH RECTANGULAR DISTANCE

Suppose it is desired to locate a facility in a large U.S. city, and demand data are readily available in the form of estimates by census tracts. Demand is then only "known" to within the resolution provided by these areal units. A plausible heuristic is to treat the center of an "area destination" (one or more contiguous tracts) as a point destination weighted by the dejnand of that area. The weakness of this approach is that an error is introduced by the implicit assumption that the distance traveled from the facility to each destination in the area is the same as the distance from the facility to the center of the area. This error decreases as the area in question is decreased, but in the limit this decrease leads to the measurement andi computation difficulties of having as many destinations as there are demand points.

To resolve this dilemma, we subdivide large populations of destinations into areas having roughly uniform demand densities per unit area. The use of point destinations along with such area destinations enables us to accurately depict even complex demand configurations.

We will consider only a rectangular distance model. General Cp distances are treated by Drezner and Wesolowsky (1980a, 1980b), but the problem becomes considerably more complex to analyze. Also, for convenience, we assume uniform distribution of destinations over rectan-

gular areas. The latter assumption is not overly restrictive because the Rectangular components can be used to build up more complex shapes. In both model and mode of analysis, the concept of uniformly distributed destinations is closely allied to the assumption that locations of destinations are unknown, but distributed with a uniform probability distribution over a rectangular area. This interpretation is treated later in this chapter.

Assume now that the destinations can be divided into points and into rectangular areas (with sides parallel to the coordinate axes) that have uniform distributions of destinations. Let there be t destination areas. Figure 3.2 shows rectangular area j bounded by the corners ( ,1, ;2), {dj„Ci2), (dj„d/2), and (Cj,,dj2). Within the area is an infinitesimally small square area, and within that is the point (z,,Z2). The distance between the facility at (x,,X2) and the point (zi.Zj) is measured along only rectangular distance paths such as that depicted. Let , be the weighting constant (per unit area) that transforms distance and the area of the infinitesimally small square into cost. For example, suppose 400 people were "uniformly distributed" over two square kilometers and each demanded 30 units where each unit cost $0.50 per kilometer to transport. The uniform distribution assumption would give us u, = (30)(400)(0.5)/2 = $3000 per kilometer of distance per square kilometer of area.

The transportation cost to area j is:

r,{x„X2) = f j (k.-il + \X2-Z2\)dz,dz2. (3.7)

The problem of optimally locating a new facility among / area destinations and n point destinations can now be written:

Figure 3.2 Area Destination /

(>i . )

minimize WA(X) = 4xX2) + X ,- ,, + x2-aj. (3.8)

The function WA(X) has two very useful properties. It is separable in X, and 2 and it is convex. These two properties are basic to finding Jf*, an optimal location.

The cost term / ,) can be simplified by integration. Write:

rXx„X2) = r„(x,) + 7:2(X2), (3.9)

where:

r,i(x,) = u,{d/2 - c,2) j x, - z,\dz,

Tj2(X2) = Uidj, - C„) I X2 - Z2\dZ2.

For convenience, let:

Uj, = Ujidj2 - Cj2) and w,, = u,{dj, - c,,), so we can write:

„( ) = j - zlz, (3.10)

and in turn:

WA{X) = X ,) + r,2(x2) + ,( ,) + 2( 2) (3.11)

where:

If we now let:

WA,{x,) = X ,) + W,(x,), 7-1

(3.12)

It IS clear that we can find (xt,xf) by minimizing first WA,{x,) to obtain xT, then minimizing WA2(X2) to obtain xf. To proceed, it is necessary to obtain ,( ) in another form.

Table 3.4 The Algebraic Breakdown of T,iix).

X, < c,.

t> < Xj < dj

Xt > dj

Table 3.4 summarizes the resuks of integration and Figure 3.3 plots the function and its derivative. As is evident by inspection of Figure 3.3 (or formally, Exercise 3.6), ( is convex. As all terms IFAa,) are also convex, 4 ( ) is convex.

There is an easy way to find an optimum location. Recall that in the rectangular distance location problem with destination points (existing facility locations), we could find x by locating the median weight on the A,-axis and xf by locating the median weight on the Xi-axis (see Example 2.5). We can think of the areas as being composed of a very large number of points. The representation of an area by points can be made as accurate as desired by increasing the number of points. It would seem to follow that we again need only locate the medians of weights on the respective

Figure 3.3 T„(xJ and Its Derivative ;( ).

axes to find the optimal facility locations. The total weight of an area j is simply the constant (which is a weight per unit area) multiplied by the size of the area. This intuition is indeed correct as can be shown using the derivatives in Figure 3.3. Exercise 3.7 requests the proof for this.

Example 3.2 Table 3.5 and Figure 3.4 present a location problem with three area destinations and two point destinations.

The calculation of WAXxi,) and its derivatives at selected points x* is summarized in Tables 3.6 and 3.7.

As sample calculations, we find WA,ix,) and 4;( ) at x, = 2. Using equation (3.12) we calculate:

WA,{2) = 2 ,( ,( „ - 4) + (4 - 4)) + X / .-2)

1 ;= 1

= 15 [2(2 - 6) + (6 - 22)/2] + 21 [2(2 - 7) + (72 - 2)/2] + 6 [2(2 - 4) + (4 - 22)/2] + 45 (6 - 2) + 6(7 - 2) = 604.5. Using Table 3.4 we calculate:

WA\{2) = 2 - 4,) + 2 (-Wj)

y= 1 /- 1

= 15(2 - 6) + 21(2 - 7) + 6(2 - 4) + (-45) + (-6) V = -228.

Graphs of WAXXi) and WA2[X2) appear in Figures 3.5 and 3.6.

The figures (if accurate enough) show that xf =4.83 and x? = 6. These coordinates can be obtained as the locations of median weights. Consider

Table 3.5 Points, Areas, and Weights.