Author: Dr. Jean-Paul Rodrigue
Network data models offer a digital representation of transportation networks that can be used for planning, operational and simulation purposes.
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 and complex 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. Besides, 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 (GIS) are among the best tools to create, store and use network data models, which are an implicit part of many GIS. 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 and their relationships. Of particular relevance are the representations of location, direction and connectivity since different features can share a point such as a street intersection being connected to several lines. 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 (annotations). 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. Networks as Layers
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. In the 1990s, ESRI (a major GIS software provider) developed the shapefile data model, which became the most common format and standard to store vector information, including points, polylines (a continuous line composed of several segments) and polygons. This format became extensively used to create, store and analyze network information. 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).
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 from an operational standpoint. 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 opposite applies for countries where driving is on the left (e.g. UK).
The layer-based approach is consequently good to perform an effective cartography of transportation network and to perform geocoding. However, it is ill-suited to comprehensively address routing and assignment transport problems.
3. Topological Representation
Two fundamental tables are required in the topological 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 insure 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 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.
The Topologically Integrated Geographic Encoding and Referencing (TIGER) model is a notable example of a topological structure which has been widely accepted. TIGER was developed by the US Census Bureau to store street information constructed for the 1990 census and has been 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, which has been very useful for the GIS industry in general and for transportation in particular. It does not contain census or any other socioeconomic data, but this data can be merged with the geodataset for spatial analysis.
4. Object-Oriented Approach
The object-oriented approach represents a more recent development in spatial data models, often known as geodatabases. 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 embedded 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 are effective to solve routing issues in transport. Object-oriented data models were in design phase in the 2000s with proposals such as UNETRANS (Unified NEtwork-TRANSportation data model). By the 2010s, transport data models became common within geodatabases that can include a wide array of geographic datasets such as features (points, polylines, polygons), attribute tables, raster datasets, topologies and network datasets. More specifically, network datasets within a geodatabase include the standard structural elements, mainly links and nodes and their topology.
The object-oriented approach for GIS is becoming the standard, but requires effort to convert or adapt existing transport network databases, which are mainly layer-based, into the new representational structure. However, once implemented, they offer a wider set of tools to analyse transportation systems.
- The Geography of Transportation Networks
- Geographic Information Systems for Transportation (GIS-T)
- Graph Theory: Definition and Properties
- Graph Theory: Measures and Indices
- Traffic Assignment
- Adams, T.M., N.A. Koncz, and A.P. Vonderohe (2001) Guidelines for the Implementation of Multimodal Transportation Location Referencing Systems. NCHRP Report 460, Transportation Research Board, National Research Council. Washington, DC: National Academy Press.
- Butler, J.A. (2008) Designing Geodatabases for Transportation, Redlands, CA: ESRI Press.
- Guimera, R. and L. Amaral (2005) “Cartography of complex networks: modules and universal roles”, Journal of Statistical Mechanics, No. 2.
- Zeiler, M. (1999) Modeling our World: The ESRI Guide to Geodatabase Design, Redlands, CA: ESRI Press.