5.3.3 Nonhomogeneous Rectangular City Example

We consider as an example the rectangular city shown in Figure 5.2. This city runs 2 miles east-west and 1 mile north-south with an x-y coordinate system centered at the city center. Travel time is assumed to be proportional to travel distance; the travel distance between any two points (x_i, y_i) and (x_j, y_j) is given by the Manhattan metric,

The home location for unit 1 is x₁ = +0.75, y₁ = 0.0 and for unit 2 is x₂ = -0.25, y₂ = 0.0. Requests for service are unevenly distributed, with fully 50 percent of the requests distributed uniformly over the region east of facility 1 (x > 0.75). The remaining half of the requests for service are distributed uniformly over the rest of the city (x 0.75). Since the high-demand region is {0.75 x 1.0), the system planner located facility 1 at x = 0.75, since (s)he desired response unit 1 to be near the high-demand region while not sacrificing too greatly system-wide travel time. The city-wide arrival rate of requests for service is = 5/4 per service time unit; since we are measuring time in service time units, we set = 1.

It is decided that the primary response areas for the two units will be determined by a boundary line located a distance w west of facility 1 (and 1 - w east of facility 2). We assume that 0 w 1. Requests occurring west of the boundary line will be assigned to unit 2, if available, and requests occurring east of the line will be assigned to unit 1, if available. Thus, the set A corresponds to {(x, y) B: x 0.75 - w} and B - A corresponds to {(x, y) B: x < 0.75 - w}. In measuring travel times, we will only consider east-west travel, since north-south travel (which averages 1/4 mi per response) is not dependent on w. For the convenience of working directly with Figure 5.2, and not having to divide by travel speed, we deal directly with travel distances rather than travel times. This is perfectly appropriate since in this example the two are linearly related (we assume, of course, that response speed is sufficiently great so that total service time is dominated by on-scene time).

Using the general formulas given above, we arrive at expressions as functions of w for _n, T_n(B), T₁(A), and T₂(B) - A) (see Table 5-3). As just indicated, the travel time formulas are providing mean travel distances in this case. These functions behave as we expect. For instance, ₁ = ₁, grows linearly with w, whereas ₂ = ₂, decreases linearly with w. The mean intraresponse area travel times are nonlinear functions of w, with the two limiting conditions (w = 0 and w = 1) checking with our intuition. As we might expect, T₂(B) = 11/14 is greater than T₁(B) = 1/2 since facility 2 is located relatively far from the high-demand region, 0.75 x 1.0.

Equal-travel-time boundary line. A most sensible partitioning of the city into the two primary response areas would entail setting w = 1/2, equidistant from facilities 1 and 2, yielding response areas A_{w = 1/2} and B - A_{w = 1/2}. With such a partitioning, requests are always assigned to the closest available unit, thereby minimizing the "immediate cost of response," where cost is measured by mean travel time. One might think that such a policy would minimize overall system mean travel time. Substituting all the numerical values describing this problem into (5.17), we obtain the system mean travel time,

(A_{w = 1/2}) = 0.46246

₁ = 0.49010
₂ = 0.43773

yielding a workload imbalance

|₁ - ₂| = 0.05236

Alternative boundary line. If we believe that w = 1/2 yields minimum system-wide mean travel time, we should be able to verify that by differentiation of with respect to w. That is, solving the equation d/dw = 0 in terms of w should yield the optimal value for w, implying minimum mean travel time. (Of course, we must be careful to assure that 0 < w < 1 and that d²/dw² > 0, implying that a minimum rather than a maximum is obtained.)

The differentiation is straightforward since w appears in T only additively in the forms k₁w and k₂w². Substituting the equations in Table 5-3 into (5.17), we obtain

d/dw = 0 = w - 53/126

implying that the optimal value for w, denoted w^*, is

Response area 1, now denoted A_w^*, has its western boundary shifted to the right of the equal-travel-time boundary line by 10/126 = 0.0794 mile. In the "shifted" region, corresponding to 1/2 w 53/126, the result states that if unit 1 were to respond instead of unit 2, the immediate savings gained by assigning the closest unit (unit 1) are not sufficiently large to compensate for the likelihood of another request causing unit 2 to be dispatched on a distant request (perhaps into unit 1's high-demand zone) because of unit 1's unavailability. This means that minimal system-wide travel time is obtained by occasionally incurring a travel time slightly greater than the immediate minimum possible in order to leave the system in a state that best anticipates future requests for service. This is a fundamental property of many stochastic systems: In selecting a decision alternative at any given time, it is often optimal to select an alternative that does not yield the minimum possible immediate cost (or the maximum possible immediate reward) in order to facilitate the most javorable future system states and decision alternatives.

The interested student may well wonder what savings in mean travel time are obtained in this example by following an optimal boundary-line policy. The result is

(A_w^*) = 0.46166

or only 0.173 percent less than the equal-travel-time boundary line. This result is consistent with other analysis of spatially distributed probabilistic systems, which show that mean travel time is rather insensitive to slight changes in system boundaries. What is surprising about the boundary line that minimizes mean travel time is its effect on workload imbalance. With w = w^* = 53/126.

₁ = 0.44189
₂ = 0.48594

yielding a workload imbalance of 0.04405, compared to the earlier value of 0.05236, or a 15.87 percent improvement in this measure. Thus, by designing the system to minimize one performance measure, we obtain an improvement in another performance measure. This is unusual in operations research, where one usually must confront trade-offs requiring degradation in one measure of performance to achieve improvement in another. In applications, Carter, Chaiken, and Ignall, who originally analyzed the two-server model, and later Jarvis, who extended the ideas to N servers, have used the developed procedures for minimizing mean travel time primarily to achieve reductions in workload imbalance. So, here we have a rather strange situation in which algorithms and procedures developed for optimizing one system of performance measure are used in practice to achieve improvements in another performance measure.