5.4 HYPERCUBE QUEUEING MODEL

One would have a powerful planning tool if the N = 2 server results of Section 5.3 could be extended to arbitrary N. Such a tool would be particularly useful if it included the true complexities of a city's geography and dispatch policies rather than assumptions of uniformity and the like needed for an analytically tractable model. These are the goals of the hypercube queueing model. Implemented on a computer, the "solution" to the model-rather than being a closed form expression-is the set of numerical values of the state probabilities and associated system performance measures (e.g., travel times, workloads, interarea dispatch frequencies).

The city's geography is modeled by partitioning the city into a set of geographical atoms or reporting areas, each representing an independent point source of requests for service. As we will see in Chapter 6, this same notion of a point source of demands, is called a node or vertex of a transportation network. A unit's primary response area consists of those atoms to which it would be dispatched, if available, even if all other units were available. With this approach, primary response areas can assume any geometric shape; they need not even be comprised of contiguous atoms. A fixed-position unit, when available, would be prepositioned in one specific atom; a mobile position unit (e.g., a patrolling police car) would be probabilistically located in one of several atoms comprising its patrol area. Patrol areas need not coincide with primary response areas. Precise statements regarding all definitions and assumptions are given in Section 5.4.2.

The model user need not concern himself with either the solution of the system equilibrium equations or even their specification; this is all done algorithmically.

The model's name derives from the state space describing the availabilities of servers. Just as in the previous section, each server can be in one of two states: busy or free. A particular state of the system is given by the entire listing of servers that are busy and free. For instance, the state 110 corresponds to a three-server system in which unit 1 is free and units 2 and 3 are busy. The state space for a three-server system is given by the vertices of a threedimensional cube (Figure 5. 10). As the number of servers grows beyond 3, the notion of a cube is carried over into N-dimensional space, called hyperspace, and thus the name hypercube. Unlike the two-server model of Section 5.3, the hypercube model allows the option of a queue of unserviced requests to form; if this option is employed, the state space must be augmented by an "infinite tail."

The mathematics of the hypercube model and its various descendants, while not particularly complicated, requires considerable notation and-to include all the descendants-considerable space. Thus, our purpose here is not to cover all the details of the hypercube model. Our restricted attention here is focused on four points:

1. To illustrate the use of the model in practical decision-making settings. We do this by providing thumbnail sketches of plausible (and sometimes actual) applications of the model.

2. To illustrate for one particular version of the hypercube model how one relates the city's spatial structure to parameters of a queueing model and how one constructs such a model for numerical solution by a computer.

3. To demonstrate for that same version of the model why one might desire a computationally faster approximate procedure and to develop the rudiments of the approximation procedure.

4. To gain proficiency in modeling analytically simple N-server spatially distributed systems (N > 2). This is done primarily with homework examples that build on concepts of the hypercube model but apply them in analytically tractable settings.