INTRODUCTION

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:

1. Urban travel distances and travel times when travel is restricted to take place along the links of a transportation network.
   
2. Vehicle-routing and collection and distribution problems such as those that arise in mail delivery, street sweeping, solid waste collection, demand-responsive bus services, snowplowing, parcel delivery, or telephone-booth repairing.
   
3. Problems of site selection for the location of facilities for emergency and nonemergency services such as fire houses and transportation terminals.

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.¹ 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:

1. Algorithms motivated by graph-theoretic considerations are generally much more efficient than the more traditional mathematical programming algorithms (even in cases where simplex-type LP algorithms can be applied). Thus, problems of much larger size than can be handled by standard mathematical programming algorithms can often be investigated using graph-theoretic techniques.
   
2. Perhaps most important, the graph-theoretic approach, based as it is on the pictorial representation of problems in a network context, lends itself in an excellent way to an intuition-based presentation of algorithms and to the discovery of simple, ad hoc procedures for obtaining good approximate solutions to difficult and mathematically complex problems. We shall present several such ad hoc procedures, known as heuristic algorithms, later in this chapter.
   
3. For applications in urban service systems, the graph-theoretic approach is a most natural one since an urban transportation grid can readily be translated into a network (graph) model in the manner that was outlined above. Indeed, any good map of an urban area can serve as a handy workbench for studying network-based models of urban services.

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:

1. That the algorithm make good intuitive sense with reference to the physical problem at hand.
   
2. That the most efficient algorithms currently in use be but simple variations or extensions of the algorithms described here.

¹ Graphs (and other related terms) will be defined in the next section.