6.6 PROBABILISTIC NETWORKS

In all the network models of urban and other areas that we have seen so far, we have not considered the possibly probabilistic nature of at least some of the networks' parameters. Yet, in many instances this probabilistic nature is sufficiently important to merit separate attention.

For instance, at no point in the discussion above was explicit recognition given to the fact that demand for urban services constitutes, in most cases, a Poisson (or some other probabilistic) process. A consequence of this is that these services undergo periods of intensive activity, as well as other periods of relative inactivity. During high activity periods, any given facility or, more specifically, the servers associated with that facility may be unable to keep up with the many demands for service. In such instances, either some demands will have to queue up and wait for a server to become available or assistance may be sought from other service facilities elsewhere. In either event, we have a violation of some of the unstated premises under which all the facility location problems described earlier were examined. For, in the k-center, the k-median, and the set-covering problems, we have implicitly assumed that:
1. No queueing ever occurs (i.e., whenever a demand arises at a point assigned to a given facility, that facility will immediately respond to that demand).
2. Facilities do not interact (i.e., once a demand generation point is assigned to a given facility that point is served forever and exclusively by that facility with no assistance from servers locatedat other facilities).

When violation of these assumptions is an infrequent occurrence, as it usually is in service systems that are utilized at a relatively low rate, the results obtained in Section 6.5 with regard to optimality of locations can still be considered valid. If, however, as it happens with highly utilized urban service systems, the foregoing assumptions are violated with high probability, then these results must be accordingly modified and revised. To do this, we need the tools provided by queueing theory--and especially the methodology of the hypercube queueing model--which we covered in Chapters 4 and 5. Much recent work [JARV 75b, BERM 78] has focused on the problem of selecting facility locations on networks in the presence of significant queueing (see also Problems 6.13 and, especially, 6.17 for some important concepts in this respect).

Rather than examine the implications of the probabilistic aspects of demand our emphasis in this section will be on another important network parameter, "link length." In our earlier material we have always assumed that the lengths of the links are known constants. In practice, however, this is often not so, especially when these lengths represent travel time rather than distance between adjacent nodes. As we all know from experience, there is usually considerable uncertainty about how long it will take to travel between any two points x and y in a city. This is especially true under peak traffic conditions, when actual travel times can vary widely from day to day over any given travel path.

It may thus be much more realistic to represent link lengths as random variables (hopefully, with known probability distributions) under these circumstances. We shall use the term probabilistic network to refer to all networks for which one or more link lengths are explicitly defined to be random variables.21

21 Our earlier, deterministic models can of course be viewed as only special cases of probabilistic networks.