5.3.5 Facility Location

Larson and Stevenson, in work concurrent with that of Carter, Chaiken, and Ignall, used a particular form of the two-server model to examine certain questions of optimal facility location [LARS 72]. In particular, they considered an n x m rectangular region in which service requests are uniformly distributed and in which facility 1 is located at (x1, y1). One is free to position facility 2 at any location (x2,y2) and to construct optimal response areas. This situation might correspond to one in which an existing facility serving the region is overburdened and a second facility is about to be introduced. The problem is to locate the second facility and to partition the region so that the resulting mean travel time is minimized. A similar type of problem in a network context is related to the "p-median" problem (see Chapter 6).

Travel time is assumed to be right-angle, with directions of travel parallel to the sides of the rectangle. As one varies so a first question involves the change of the candidate boundary lines. Applying the Carter-Chaiken-lgnall result in this case, an optimal boundary consists of points (x, y) satisfying an equation of the form

| x1 - x | + | y1 - y | + so/2 = | x2 - x | + | y2 - y | - so/2

where (x1, y1 ) and (x2, y2 ) are the respective facility coordinates. Equation (5.19) generates the family of boundaries, either type 1 or type 2, illustrated in Figure 5.3. For any given (x1, y1 ) and(x2, y2 ), it turns out there will be two values for so which do not yield unique boundaries but rather regions in which all points are so closer to one facility than to another. Any line partitioning B and contained in such a region is an optimal boundary.

The system's mean travel time, while containing many terms, can be found almost by inspection by repeated application of the ideas in Sections 3.4.1 and 3.8, linking pdf's to geometric designs of service regions. For instance, for a very low utilization system, in which the frequency of interresponse area dispatches is negligibly small, the optimal boundary is the equal-travel-time boundary (i.e., so = 0). For this case, suppose that facility 2 is located north to northeast of facility 1:

x2 x1
y2 y1
y2 - y1 x2 - x1

yielding a type 1 boundary (see Figure 5.3). Then, by repeated conditioning on rectangular and triangular subregions one obtains, for the mean systemwide travel time,

For each of the other seven possibilities for the relative placement of facilities, the expressions for (Aso=0) can be obtained by a straightforward relabeling of coordinates.

For the case of = /2 0, implying that so = 0, the optimal positioning for facility 2, given a position for facility 1, can be obtained using differential calculus. For cases in which > 0, implying that so 0, the expressions for the partial derivatives of (Aso) become too difficult to solve, so a gradient search procedure is used to obtain the optimal values for (x2, y2).

To indicate the qualitative properties of the results, we discuss as an example a region for which n = 1, m = 2. We continuously vary the position of facility 1 over a closed trajectory in the southern half of the region. We then examine the locus of optimal positions of facility 2 induced by varying facility 1 over the fixed trajectory.

In Figure 5.4 we see the effect of varying the position of facility 1 over a circular trajectory centered at (0.5, 0.5) and having radius 0.45. The most striking feature of Figure 5.4 is that for large changes in the position offacility 1, the change in the position of facility 2 to maintain optimality is relatively small.

On occasion, a continuous trajectory of facility 1 locations induces a discontinuous trajectory of optimal facility 2 locations, the discontinuities occurring at points where the optimal boundary configuration changes, say, from type 1 to type 2. The mean travel time is found to be continuous, however. This effect is seen clearly in Figure 5.5, in which the position of facility 1 is varied over a square centered at (0.5, 0.5) of dimension 0.9, yielding a dis continuous trajectory of optimal facility 2 locations. We see that, for facility 1 near the top corners of the square, the optimal location of facility 2 jumps to a region in which a type 2 (rather than a type 1) boundary is required.

Corresponding to the two trajectories for facility 1 in Figure 5.4 and 5.5, we have plotted in Figure 5.6 the mean travel time when facility 2 is optimally located. The figure shows as a function of , an angle defined from the point (0.5, 0.5) to the position of facility 1.3 For the circular trajectory, varies between 0.56 ( 140o) and 0.59 ( 65o). For the square trajectory, the maximum value of is about 0.65 ( 45o), the minimum approximately 0.57 ( 0o or 180o). Considering the size of the facility 1 trajectories, is not very sensitive to the facility 1 position.

We may now be interested in how the optimal trajectory for facility 2 changes as , a measure of the system's request rate, is increased above zero. Intuitively, we would expect that as increases, the optimal server 2 trajectory would shift southward in order to be better positioned for responses into the southern half of the region (since unit 1 may be busy when a service request arrives from that region).

For = 0.2 we notice in Figure 5.7 the same discontinuity observed in Figure 5.5 in the locus of (x02, y02) as (x1, y1) follows the square trajectory. In addition, the optimal location of facility 2 is even less sensitive to the location of facility 1 than we have observed for 0.0; and the locus of optimal positions has shifted downward.

These last two observations are more pronounced for = 1.0 (Figure 5.8). We see that as increases, the optimal position of facility 2 becomes less sensitive to the location of facility 1 and converges from both the type 1 and type 2 boundary regions to the point (0.5, 1.0). This phenomenon can be understood intuitively as follows: as q increases, the probability P00 that both service units are simultaneously available goes to zero. For large , nearly all dispatch assignments are made to the one available unit, the other unit being busy on a previous assignment. Thus, the spatial distributions of service requests to which each service unit is assigned become uniform over the entire region. Clearly, the optimal position for a unit whose service requests are distributed uniformly over the region is at the center of the region (0.5, 1.0). Hence, for large , the optimal location of facility 2 is near the center of the region, irrespective of the location of facility 1. Indeed, if we had the freedom to specify the position of facility 1, its optimal position would also converge to the midpoint (0.5, 1.0).

Following the method illustrated above, we plot in Figure 5.9 the minimal mean travel time versus the angle of the position of facility 1. Three different functions are plotted, corresponding to the three values of ( = 0.0, 0.2, 1.0). When 0.0 (i.e., no interresponse area dispatching), the maximum occurs for values of near 45o and 315o corresponding to facility 1 near the top corners of the square. As q is increased, the effects of traveling long distances from (x1, y1) into response area 2 become apparent, and the maximum occurs for values of 0 near 135o and 225o corresponding to facility 1 near the bottom corners of the square. We notice that, for = 1.0, increases both as we move away from the line x = 0.5, and as we move away from the line y = 0.95. This is consistent with the notion that for large the optimal location of each facility is at the point (0.5, 1.0). Simple models such as this can be used to study the sensitivity of system performance measures to alternative management practices, involving facility location in this case. Here we have discovered a type of insensitivity that may be useful in opening additional policy options to a decision maker. In practice, he or she may be happy to sacrifice a few percentage points in response time to take into account certain nonquantifiable factors such as neighborhood characteristics, political pressures, land availability and cost, and so on.

3Because of the symmetry of facility 1 locations about x = 0.5, we have graphed only for values of up to 180o.]