So far in this book we have concentrated on models that view urban services as spatially distributed systems operating in planar areas. We have thus disregarded the fact that the two-dimensional urban space is not really a continuum but rather a largely "discretized" space in which travel is restricted to take place along the highways, avenues, streets, and other transportation arteries (rail links, waterways, etc.) that compose a typical urban transportation grid. Our strategy has actually been that of considering such departures from the continuum model as "perturbations" (cf. Section 3.2) and thus accounting for their effects by computing the perturbation terms that arise from their presence.
This approach is an entirely justifiable one for the types of questions that we have examined--questions which for the most part explored the spatial relationships within urban areas and the resultant characteristics of service requirements in these areas. There are, however, many other types of questions for which it is more appropriate or more convenient to recognize explicitly the presence of a transportation network and, in fact, to use that network as the "space" in which urban services operate. In these cases, we should use networkbased models and analysis. The purpose of this chapter is to present such network-based models and their applications.
We shall again be concerned mostly with questions that arise from the spatial distribution of demands for urban services. Specifically, we shall consider:
Throughout the discussion of these topics our representation of the urban environment will remain basically unchanged: the transportation grid in the area of interest will be our network; intersections of transportation arteries will be the network's nodes and artery segments between intersections its links. While at times it will be assumed that demand for urban services is distributed (in some way) along the whole length of the network, at other times it will be assumed that demand is concentrated at specific points on the network. The latter points will also be denoted as nodes of the network. Which of the two assumptions will be used will depend on which one is more appropriate for the application at hand.
The methodology that will be developed and used in the following sections is that of graph theory, the study of graphs and their properties.1 This is still a rapidly developing area of applied mathematics that has attracted a great deal of attention during the last 15 years. The stimulus for this attention has been provided by the opportunities that the digital computer has opened for solving computationally difficult problems through the use of powerful algorithms. Indeed, graph theory is very much oriented toward the development of algorithmic approaches, and thus major parts of this chapter will be devoted to the presentation of several such algorithms.
We feel it is important, at the outset, to justify briefly for the reader the adoption of a graph-theoretic approach for presentation of this material. For it is true that most of the models that will be developed and solved here can also be formulated as linear programming (LP) or integer programming (IP) problems (and, indeed, this is how, in historical terms, many of these problems were initially formulated and investigated). However, the graphtheoretic approach has three advantages:
In concluding this introduction, we note that some of the algorithms presented below are not necessarily the most computationally efficient among those available for the problem they solve or are not as readily translatable into computer code as other algorithms that can be used for the same purpose. The criteria that have been used here for algorithm selection have been: