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 twodimensional 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 examinedquestions 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 networkbased 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:
 Urban travel distances and travel times when travel is restricted to
take place along the links of a transportation network.
 Vehiclerouting and collection and distribution problems such as
those that arise in mail delivery, street sweeping, solid waste
collection, demandresponsive bus services, snowplowing, parcel
delivery, or telephonebooth repairing.
 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.^{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 graphtheoretic 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:
 Algorithms motivated by graphtheoretic considerations are generally
much more efficient than the more traditional mathematical programming
algorithms (even in cases where simplextype 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 graphtheoretic techniques.
 Perhaps most important, the graphtheoretic approach, based as it is
on the pictorial representation of problems in a network context, lends
itself in an excellent way to an intuitionbased 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.
 For applications in urban service systems, the graphtheoretic
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 networkbased 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:
 That the algorithm make good intuitive sense with reference to the
physical problem at hand.
 That the most efficient algorithms currently in use be but simple
variations or extensions of the algorithms described here.
^{1} Graphs (and other related terms) will be defined in the
next section.
