Jean-Paul Rodrigue (2017), New York:
Routledge, 440 pages.
Author: Dr. Jean-Paul Rodrigue
theory developed a topological and mathematical representation of
the nature and structure of transportation networks. However, graph
theory can be expanded for the analysis of real-world transport networks
by encoding them in an information system. In the process, a digital
representation of the network is created, which can then be used for
a variety of purposes such as managing deliveries or planning the construction
of transport infrastructure. This digital representation is highly complex,
since transportation data is often multi-modal, can span several local,
national and international jurisdictions and has different logical views
depending on the particular user. In addition,
while transport infrastructures are relatively stable components, vehicles
are very dynamic elements.
It is thus becoming increasingly relevant to use a data model where
a transportation network can be encoded, stored, retrieved, modified,
analyzed and displayed. Obviously, Geographic Information Systems have
received a lot of attention over this issue since they are among the
best tools to store and use network data models. Network data models
are an implicit part of many GIS, if not an entire GIS package of its
own. There are four basic application areas of network data models:
Constructing the geometry of a network depends on the mode and the
scale being investigated. For urban road networks, information can be
extracted from aerial photographs or topographic maps. Air transport
networks are derived from airport locations (nodes) and scheduled flights
between them (links). Two fundamental tables are required in the
basic representation of a network data model that can be stored
in a database:
Topology. The core purpose of a network data model is to provide
an accurate representation of a network as a set of links and nodes.
Topology is the arrangement of nodes and links in a network. Of
particular relevance are the representations of location, direction
and connectivity. Even if graph theory aims at the abstraction of
transportation networks, the topology of a network data model should
be as close as possible to the real world structure it represents.
This is especially true for the usage of network data models in
Cartography. Allows the visualization of a transport network
for the purpose of reckoning and simple navigation and serves to
indicate the existence of a network. Different elements of the network
can have a symbolism defined by some their attributes. For instance,
a highway link may be symbolized as a thick line with a label such
as its number, while a street may be symbolized as an unlabeled
simple line. The symbolized network can also be combined with other
features such as landmarks to provide a better level of orientation
to the user. This is commonly the case for road maps used by the
Geocoding. Transportation network models can be used to derive
a precise location, notably through a linear referencing system.
For instance, the great majority of addresses are defined according
to a number and a street. If address information in imbedded in
the attributes of a network data model, it becomes possible to use
this network for geocoding and pinpoint the location of an address,
or any location along the network, with reasonable accuracy.
Routing and assignment. Network data models may be used
to find optimal paths and assign flows with capacity constraints
in a network. While routing is concerned by the specific behavior
of a limited number of vehicles, traffic assignment is mainly concerned
by the system-wide behavior of traffic in a transport network. This
requires a topology in which the relationship of each link with
other intersecting segments is explicitly specified. Impedance measures
(e.g. distance) are also attributed to each link and will have an
impact on the chosen path or on how flows are assigned in the network.
Routing and traffic assignment at the continental level is generally
simple since small variations in impedance are of limited consequences.
Routing and traffic assignment in an urban area is much more complex
as it must consider stop signs, traffic lights and congestion, in
determining the impedance of a route.
Once those two tables are relationally linked, a basic network topology
can be constructed and all the indexes and measures of graph theory
can be calculated. Attributes such as the
connectivity and the shimbel matrix can also easily be derived from
the link table. This basic representation enables to define the topology
of networks as structured by graph theory. Many efforts have been made
to create comprehensive transportation network databases to address
a wide variety of transportation problems ranging from public transit
to package distribution. Initially, these efforts were undertaken within
transportation network optimization packages (e.g. EMME, TransCAD)
which created topologically sound representations. Many of these representations
were however geographically inaccurate and had limited visual and geocoding
capabilities. Using a network data model for the purposes of cartography,
geocoding and routing requires further developments.
Most conventional GIS data models separate information in layers,
each representing a different class of geographical elements symbolized
as points, lines and polygons in the majority of cases. As such, a network
data model must be constructed with the limitation of having points
and lines in two separate layers; thus the layer-based approach. Further,
an important requirement is that the geometry of the network matches
the reality as closely as possible since these networks are often part
of a geographic information system where an accurate location and
visualization is a requisite. This has commonly resulted in the
fragmentation of each logical link into a multitude of segments, with
most of the nodes of these segments mere intermediate cosmetic elements.
The topology of such network data models is not well defined, and has
to be inferred. However, these network data models benefit from the
attribute linking capabilities of the spatial database models they are
derived from. Among the most significant attributes that can be attached
to network layers are:
- Node table. This table contains at least three fields;
one to store a unique identifier and the others to store the node's
X and Y coordinates. Although these coordinates can be defined by
any Cartesian reference system, longitudes and latitudes would insure
an easy portability to a GIS.
- Link table. This table also contains at least three fields;
one to store an unique identifier, one to store the node of origin
and one to store the node of destination. A fourth field can be
used to state if the link is unidirectional or not.
The Topologically Integrated Geographic Encoding and
Referencing (TIGER) model is a notable example of a layer-based structure which
has been widely accepted. TIGER was developed by the US Census Bureau
to store street information constructed for the 1990 census and was
continuously updated since then. It contains
complete geographic coordinates and in a line-based structure. The most
important attributes include street name and address information, offering
an efficient linear referencing system for geocoding. The layer-based
approach is consequently good to solve the cartography and geocoding
issues. However, it is ill-suited to comprehensively address routing
and assignment transport problems.
4. Object-Oriented Approach
The object-oriented approach represents the latest development in
spatial data models. It assumes that each geographical feature is an
object having a set of properties and a set of relationships with other
objects. As such, a transportation network is an object composed of
other objects, namely nodes and links. Since topology is one of the
core concepts defining transportation networks, relationships expressing
it are imbedded in object-oriented representations. The basic elements
object-oriented transportation network data model are:
- Classification and labeling. Each segment can be classified
into categories such as its function (street, highway, railway,
etc.), importance (number of lanes) and type (paved, non-paved).
Also, a complex labeling structure can be established with prefixes,
proper names and suffixes.
- Linear referencing system. Several systems to locate
elements along a segment have been established. One of the most
common is the address system where each segment is provided with
an address range. Through linear interpolation, a specific location
can be derived (geocoding).
- Segment travel costs. Can consider a vast array of impedance
measures. Among the most common is the length of the segment, a
typical travel time or a speed limit. Congestion can also be assessed,
either as a specific value of impedance or as a mathematical function.
- Direction. To avoid unnecessary, and often unrealistic
duplication of links, especially at the street level, a directional
attribute can be included in the attribute table.
- Overcrossing and undercrossing. Since the great majority
of layer-based network models are planar, they are ill designed
to deal with non-planar representations. A provision must be made
in the attribute table to identify segments that are overcrossing
or undercrossing a segment they are intersecting with.
Turn penalties. An important attribute to insure accurate routing
within a network. Each intersection has different turn constraints
and possibilities. Conventionally in road transportation, a right
turn is assumed to have a lesser penalty than a left turn. The
opposite applies for countries where driving is on the left
By their structure, especially with their embedded topology, an object-oriented
transport network data model would be effective to solve the routing
issue in transport. However, object-oriented data models are still in
the design phase with proposals such as UNETRANS (Unified NEtwork-TRANSportation
data model) hoping to become accepted standards. The potential of the
object-oriented approach for GIS remains to be seen as well as the amount
of effort required to convert or adapt existing transport network databases,
which are mainly layer-based, into the new representational structure.
- Classes. They categorize objects in a specific taxonomy,
which has a proper set of properties and relationships. The two
basic classes of a network are obviously nodes and links, but each
of these classes can be subdivided into subclasses. For instance,
a link can be subdivided as a road link, a rail link, a walkway,
- Properties. They refer to a set of measurable characteristics
that are associated with a specific class. For instance, the properties
of a road class could be its length, number of lanes, name, surface,
speed limit, etc.
- Relationships. They describe the type of logical relations
objects have with one another. Instance (is-a) and membership (is-in)
are among the most common relations. For example, a street is an
instance of the road class, which itself is an instance of a transport
infrastructure. A specific road segment can be considered part of
a specific transport system through a membership relation. From
these relations inheritance can be derived, where the characteristics
of one object can be passed to another. Using the previous example,
it is logical to derive that a street is a transport infrastructure,
thus the object street inherits the properties of the object transport