1. Nature and Utility
Graph 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 [Miller
and Shaw, 2001]. 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:
-
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 a GIS.
-
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 general public.
-
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.
2. Basic Representation
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:
- 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.
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/2, 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.
3. Layer-Based Approach
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:
- 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 TIGER (Topologically Integrated Geographic Encoding and
Referencing) 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. 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 of an
object-oriented transportation network data model are:
- 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, etc.
- 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 infrastructure.
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.
Copyright © 1998-2008, Dr. Jean-Paul Rodrigue, Dept. of Economics & Geography,
Hofstra University. For personal or classroom use ONLY. This material (including
graphics) is not public domain and cannot be published, in whole or in part,
in ANY form (printed or electronic) and on any media without consent. Permission
MUST be requested prior to use.