5.3.4 Optimal Partitioning

Carter, Chaiken, and Ignall have generalized the ideas illustrated in the foregoing example. They have derived the optimal partitioning of any twoserver region, allowing a general spatial distribution of service requests and an arbitrary travel time function. Optimality implies minimizing overall system mean travel time. The optimal partition consists of the set ofpoints within the region for which the travel times from facility 2 and facility 1 differ by a constant.² The constant, denoted by s_o, is the amount by which facility 1 is closer (in a travel time sense) than facility 2 to any point on the boundary. For example, if the constant is 30 seconds, the partitioning "boundary" is the set of points in the region for which travel from facility 1 to a point in the boundary set consumes 30 fewer seconds than travel from facility 2 to that point. Suppose that travel time varies linearly with travel distance, as in most of our examples. Then s₀/2 is the travel time amount by which the optimal boundary is shifted from the equaltravel-time boundary. The factor of 2 (or 1/2) occurs because movement of the boundary 1 second of travel time closer to facility 1 causes the boundary to be 1 second farther away from facility 2; thus, a 1-second movement creates a 2second difference in travel times. In the above two-server example, any point on the optimal boundary line (located at x = 0.25 + 10/25) is s₀ = 2(1/2 - 53/126) = 20/126 = 10/63 0.1587 mile closer to facility 1 than to facility 2.

Carter, Chaiken, and Ignall prove that the optimal value for s_o is obtained from the simple formula

where , T₁(B), and T₂(B) are defined as in the foregoing example [CART 721. We emphasize that this result is completely general: it applies to nonhomogeneous, arbitrarily shaped regions in which travel time can occur according to the Euclidean or Manhattan distance metric or travel can be more complicated, perhaps involving discontinuities due to barriers and one-way streets (see Problem 5.3).

²In certain rare circumstances, this set of points has positive area. In such cases, the optimal partition is not unique, and any partition fully contained on this set is optimal.