A.7 – Network Data Models

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 to analyze 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, spans several local, national, and international jurisdictions, and has different logical views depending on the user. Besides, while transport infrastructures are relatively stable, vehicles are 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. The representations of location, direction, and connectivity are of particular relevance since different features can share a point, such as a street intersection 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 using network data models in a GIS.
  • Cartography (annotations). It allows the visualization of a transport network for the purpose of reckoning and simple navigation and indicates the existence of a network. Different network elements can have symbolism defined by some of 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 a simple unlabeled line. The symbolized network can also be combined with other features, such as landmarks, to give the user a better orientation level. 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 is embedded 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 with the specific behavior of a limited number of vehicles, traffic assignment is mainly concerned with the system-wide traffic behavior 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 impact the chosen path or 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 stop signs, traffic lights, and congestion must be considered in determining the impedance of a route.
Topology of a Network Data Model
Cartography of a Network Data Model
Geocoding in a Network Data Model
Routing in a Network Data Model

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 reality as closely as possible since these networks are often part of a geographic information system where an accurate location and visualization are 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 ensure 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 to countries where driving is on the left (e.g. UK).

The layer-based approach is consequently good for performing effective transportation network cartography and geocoding. However, it is ill-suited to address routing and assignment transport problems comprehensively.

The ESRI Shapefile Model
Turn Penalties at an Intersection

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 other to store the node’s X and Y coordinates. Although any Cartesian reference system can define these coordinates, longitudes and latitudes ensure portability to a GIS.
  • Link table. This table also contains at least three fields; one to store a unique identifier, one to store the node of origin, and one to store the destination node. A fourth field can be used to state whether the link is unidirectional.

Once those two tables are relationally linked, a basic network topology can be constructed, and all graph theory indexes and measures can be calculated. Attributes such as 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), creating topologically sound representations. However, many of these representations were geographically inaccurate and had limited visual and geocoding capabilities. Using a network data model for cartography, geocoding, and routing requires further developments.

Relational Database Representation of a Simple Network
Creation of a Connectivity Matrix with a Link Table
Object Oriented Network Model

The Topologically Integrated Geographic Encoding and Referencing (TIGER) model is a notable example of a topological structure that 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 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 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 with a set of properties and relationships with other objects. As such, a transportation network is an object composed of other objects, namely nodes and links. Since the 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 into a road link, a rail link, a walkway, etc.
  • Properties. They refer to a set of measurable characteristics 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 effectively solves routing issues in transport. Object-oriented data models were in the 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, including 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, they offer a wider set of tools to analyze transportation systems once implemented.

Related Topics

Bibliography

  • 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.