Network Data Models

Author: Dr. Jean-Paul Rodrigue

---

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.