10 9 8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8 Figure 3.4 Three Area Destinations and Two Point Destinations.

the X-axis first. Figure 3.7 shows the areas and weights "dropped" on the X-axis. The rectangles can be thought of as being made of a material that has unit weight per unit volume; the thickness of each is then Uj.

Table 3.6 Calculation of WA,{x,) and Its Derivative WA\{x,).

600 550 500 450 400-350-300 -250

Figure 3.5 WA,(x,).

1 2 Figure 3.6 WAix,).

10 -

4 -

2 --

• w, = 6

2 4 6 8

-lU-*

-114-

weight

Figure 3.7 Finding the Median Weight.

We must find a point on the x,-axis such that the weights are equal on either side. The total weight of points and areas is calculated as follows.

Area 1: (4, - cM - = (4)(3)(5) = 60

Area 2: (4, - cdid. - ) = (5)(3)(7) = 105

Area 3: (4, - - ,,) = (2)(3)(2) = 12

Point 1: w, = 45

Point 2: w, = 6

Total weight 228

We have found that the point of median weight has a total weight of

228/2 = 114 to either side. We now do a bit of trial and error. The total weight in [2,4] is (2)(3)(5) + (2)(3)(7) + (2)(3)(2) = 84, whereas the weight in [2,6) is 84 + (2)(3)(5) -f- (2)(3)(7) = 156. The point of median weight therefore falls in [4,6). Solving the equation

84 + (jc* - 4)(3)(5 + 7) = 114

produces = 4.83. The reader will find that a similar procedure yields ? = 6.

3.3 THE LOCATION OF A LINEAR FACILITY

In some appHcations, it may make sense to describe the new facihty location by a line, rather than a point. In the design of some transportation networks, access roads or throughways may be treated as linear facilities that connect populations or industrial installations to a major transportation system. For example, MacKinnon and Barber (1972) presented the problem of designing a transportation network consisting of trunk lines (represented by line segments) and feeder routes (represented by least-distance line segments from the demand points to the lines). The cost of transportation along the trunk lines was assumed to be negligible compared with the transportation costs on the feeder routes. Another example would be a conveyor line that serves a plant floor by transporting materials produced at several different points.

Suppose there are n existing facilities each with an associated (positive) weight. The problem is to locate a line X2 = A* + 5*x„ such that the sum of weighted perpendicular distances to the line (the total cost of the

Figure Perpendicular Distances.

*( 2,, )

system) is minimized. Figure 3.8 illustrates a line X2 = A + Sx, and the resulting perpendicular distances from three points.

The perpendicular distance from a point ( ) to the line can be shown (see Exercise 3.10) to be:

- {a,2 - Sa,d

which implies the location problem:

w}A - (g,, - 54,)

minimize PiA,S) A,S

(52 . 1)1/2

(3.13)

(3.14)

Unfortunately, P(A,S) is not convex and is, as we shall see, multimodal as a rule. However, given any 5, the problem reduces to locating a point on a line. We can see this by comparing equation (3.14) to problem (2.12) for any fixed S. We can therefore easily find P*(S) where:

P*(S) = min P{A,S).

(3.15)

Minimizing P*(S) is more difficult because P*{S) is multimodal in S, the derivatives are discontinuous, and the range in S to be searched is awkward (S approaches as the line becomes vertical). As a result, we will reformulate the problem using not S but , the angle of the line with the

Figure 3.9 Rotation of Axes.

X-axis (see Figure 3.9). We will also find it expedient to rotate the coordinate axes by degrees to produce x", and xi. The new coordinates of point Qj are therefore:

«„ay = (Ojicos + ajjsin , - asin + a,,cos 0). (3.16)

Figure 3.9 shows that the line X2 = A + Sx, becomes x = A cose = Ge after rotation.

The problem of minimizing the sum of weighted perpendiculars to the line now becomes:

minimize = „{ ,) = wjGe - a%\.

(3.17)

We must investigate 0 in the range [0,180°). Fortunately, only a finite set of values of in the range will be candidates. We will show how to identify these candidates by eliminating portions of the range from consideration. After a somewhat lengthy development the readers patience will be rewarded by two examples intended to clarify matters.

Problem (3.17) is easily solved using methods developed in Section 2.2. Recall that a value of Ge is optimal if it is a median weight point. That is, if we place the weight w, on some line marked off with their locations, al2, then (7? is a median weight location. For example, if afj = 3, a22 = 1, 32 = 2, and w, = 2 = vVj = 2, then the point of median weight is at a,2 and G* = 2. However, if Wi = 1, = 2, and W3 = 1, then any point between aj and inclusive is a median weight location.

The essential idea in what follows is that or [al2,a%] may still define the median even if changes. The median changes from index j or from the pair of index values (i.f) only if the order of the a/ljs, = l,...,n changes Sufficiently to upset the "balance" of weights. As changes, so do the values of ajs- However, it should be evident that it is often possible to rotate the line through some angle 6 without changing the value J or at which G* is equal to a% or {aa,a%]. Figure 3.10 illustrates this.

A Hne drawn through point a, with either angle 6, or 62 in Figure 3.10 minimizes the sum of weighted perpendiculars; in either case a, is the location of the median weight. However, it can also be verified that a line through a, is optimal for any angle in the range [ ,,62]. Note that at = a line through a is optimal, and that for = 2 a line through is optimal. We will now show that any line with an angle in the open interval (6,,2) cannot be optimal with respect to . In other words, the best in the closed interval [efij] must occur at an endpoint.

Let , = (01,90 be an open interval of angles for which = aa and