This unit is part of the NCGIA Core Curriculum in Geographic Information Science. These materials may be used for study, research, and education, but please credit the author, Peter H. Schut, and the project, NCGIA Core Curriculum in GIScience. All commercial rights reserved. Copyright 1998 by Val Noronha..

Your comments on these materials are welcome. A link to an evaluation form is provided at the end of this document.

Advanced Organizer

Topics covered in this unit

• Introduction to transportation networks
• Basic data structures, some analytical operations
• Appreciation of data quality issues

Learning Outcomes

• With appropriate follow-up exercises, running demonstration programs (e.g. shortest path calculation), the student could compare routes produced using different attribute sets, and study the effect of closing a route.

Full Table of Contents

Instructors' Notes

Metadata and Revision History

1. Introduction

• Networks as schematics (Figure 1)
• Early interest in transportation networks was predominantly in mathematics: operations research and topology (e.g. Hillier and Lieberman 1971).
• Mathematical interest in networks focused on the origin and destination, not any of the points in between.  The network is constructed of links and nodes.  Coordinates may be associated with nodes, or they may not, or they may be present but deliberately distorted for convenience/esthetics (e.g. diagrams of London Underground or other urban rail networks)
• Attributes (e.g. street name, number of lanes, travel time) can be associated with schematic representations.
• Geographers' interest in macro-scale transportation still takes this approach.
• Networks as geographic databases (Figure 2)
• Geometric path of the link is of geographic interest (e.g. road, railroad); this requires shape point coordinates on a link.
• Allows us to study interaction with other geography, e.g. economic effects of the transportation link on surrounding communities, ecological impacts.
• Geometry may still be generalized, depending on the mapping scale, e.g. a freeway may be represented by a single line rather than dual carriageways, and ramps may or may not be shown.
• Analytical operations usually associated with schematics can also be performed on geometrically true databases, assuming the database is topologically structured.
• Networks are abstracted into centrelines
• Represented as centrelines even at larger scales (e.g. 1:10,000) where kerb-line representation would appear to be more appropriate.
• Because centrelines lend themselves to analytical processing of transportation activity, while kerb lines do not.
• In the case of air and sea routes, the vehicle follows a slightly different path on each trip, but an idealized centreline is still a useful and stable representation.

2. Applications

2.1. Intelligent Transportation Systems (ITS)

• In-vehicle computer
• street map on in-vehicle computer — currently available in Japan, Europe, and high-end rental cars in the U.S.
• finds addresses (234 Main Street) and landmarks
• finds best route (assuming average conditions)
• tracks vehicle using GPS, and updates best route if necessary
• basic system, runs on laptop computer: $300
• ITS Infrastructure (currently on major freeways/arteries only)
• highway traffic/speed sensors: inductive loop detectors sense presence of metal, can tell what type of vehicle is passing, at what speed
• traffic cameras looking for first stages of incidents: accidents, vehicle breakdowns
• Traffic Management Centre (TMC) monitors all this input
• overhead advisory signs to distribute traffic more evenly
• traffic calming (e.g. speed breakers, sharp bends) to control traffic volumes and speeds on side streets
• future: broadcast congestion data directly to vehicles; in-vehicle computer re-calculates best route
• vehicle sensors detect accidents (using air bag deployment sensors), automatically make emergency calls with location reading from GPS
• raises new questions about data accuracy, and the consequences of error in a database
• current systems integrated into dashboard: $2000

2.2. Network Optimization Techniques

• Shortest Path Problem.  The same basic algorithm can minimize driving time, find a scenic route, or ensure that no section of the route exceeds a maximum gradient (for heavy trucks), or crosses light bridges ... assuming that appropriate data on gradients and bridges are available.
• Travelling Salesman Problem: visit a set of points: in what order, using what routes.  Examples: pizza or other delivery.  Sears saves several million dollars each year on delivery trucking by optimizing routes.
• School Bus Routing
• fleet management: reduce number of vehicles required
• avoid peak traffic times on key arteries so as not to hold up commuting traffic
• pick up kids on appropriate side of the street to keep them from having to cross the road
• Chinese Postman Problem: visit each link while minimizing total distance travelled.  Street cleaning, newspaper delivery, police patrolling.
• Other network modeling/optimization: load balancing, capacity maximizing algorithms

2.3. Marketing

• geocoding of customer street addresses from point of sale (POS) scanners, credit card records
• create maps of customer distribution, spending
• enable “trade area analysis,” neighbourhood-specific advertising, retail location strategies

2.4. Transportation Analysis

• origin-destination flow matrices (O-D matrices)
• journey-to-work tables (from census questions: where do you live, where do you work) can be used to calculate expected commuter traffic flows
• truck origin-destination tables (from weighing records) used to work out likely truck routes
• spatial interaction modeling — predict O-D flows such as telephone calls, air traffic, to anticipate future infrastructure requirements
• macro-economics — input-output analysis

3. Attributes of Interest

• Attributes that can be attached to a network:

• origin, destination coordinates
• shape point coordinates
• street name/highway number
• direction prefix (North)
• type prefix (Via del, Highway #)
• proper name (Main, 154)
• type suffix (Avenue)
• direction suffix (NorthWest) — typically used to distinguish the region of the city in which the road lies, as distinct from the direction of traffic flow (see below).  In “Take Hwy 15 North,” North is a direction of flow (below), not a direction suffix.
• direction of flow, for separated roads only (Northbound)
• ramps: special naming requirements
• aliases on street name: not necessarily over the entire length of segment street
• addresses
• left and right address ranges
• point addresses: every address
• point addresses: significant addresses with linear interpolation in between
• directionality: one way traffic?
• classification: freeway, arterial, collector, residential
• speed limit, congestion (impedance) or travel time
• traffic volume
• length: driven length vs digitized length
• scenic value
• connectivity
• turn tables

• Comments:
• Geometry of a network is relatively easy to build, using aerial photography or digital topographical map base.  Populating the database with accurate attributes (starting with street names and addresses) is difficult and expensive.
• Computing best routes at the continental scale is easy, because small variations in distance measures are relatively unimportant.  At the intra-city level, the optimization criterion is travel time, which depends on legal restrictions (stop signs, traffic signals, one ways) and congestion (which varies by the minute), hence the margin of uncertainty in routing is far greater.

4. Data Models and Structures

• Basic link-node structure (examples with reference to Figure 1)

• Table of Nodes
• (note that geometry fields — x and y — are optional, or may be distorted, in the schematic representation of a network)

 

NODE	x (optional in schematic)	y (optional in schematic)
1	58	100
2	0	87
3	56	96

• Table of Links

 

LINK	FROM-NODE	TO-NODE	SHAPE POINT COORDINATES (optional in schematic)
a	2	3
b	1	3
c	4	5

• A link has an implicit but arbitrary direction, defined by the ordering of the nodes defining it.  Link a is defined as going from node 2 to node 3; i.e. 2 is the low end, 3 is the high end.  For the reverse link (3 to 2) we could use the notation –a.  Direction of link is important for the specification of addresses (below) and other attributes.

• Node Attribute Table:
• valency, incident links (or nodes) forming intersections.  This table may be inferred from the above, to facilitate network analysis.  It is not absolutely necessary to specify directionality (+ or –) when populating the List of Links column, because directionality can be inferred by looking up the Table of Links above.

 

NODE	VALENCY	LIST OF NODES	LIST OF LINKS
3	3	1,2,5	–b, –a, d
5	5	3,4,6,10,11	–d, –c, e, f, g
12	4	7,11,13,18	–h, –m, n, s

• Link Attribute Table: record key is Link ID or pair of nodes (dyad)

 

LINK	STREET NAME	ADDRESSES (L)	ADDRESSES (R)	CLASS	LENGTH (km)	LANES	SPEED LIMIT (km/h)
c	El Camino Real=Hwy101	—	—	Freeway	1.42	3	100
–c	El Camino Real=Hwy101	—	—	Freeway	1.44	3	100
m	Hollister Ave	1201-1299	1200-1298	Arterial	0.23	2	80
t	Walnut Lane	598-200	599-201	Residential	0.68	1	45

• Associated turn table: record keys are From-Link and To-Link

 

FROM-LINK	TO-LINK	IMPEDANCE
a	–b	2.8
b	–a	1.5
c	f	99999*

 *Large impedance indicates turn not possible (e.g. grade separation) or illegal.  A close look at Figure 2 will show that the turn from c to f is physically impossible.
• Composite link-node structure (e.g. DIME, TIGER)
• Simultaneously store street geometry, addresses and administrative polygons

• Problem with these structures:
• link must be broken each time any attribute changes (e.g. speed limit, number of lanes)
• Size of database increases (small problem)
• Maintenance (big problem):
• becomes difficult to share data with others
• multiple references to the same object ... multiplies chances of data corruption and inconsistency

• Solution: dynamic segmentation (dyseg):
• store events/attributes in association with offsets as measured from a defined starting point

LINK	LANES	FROM OFFSET (km)	TO OFFSET (km)
c	3	0.0	0.6
c	2	0.6	1.8
c	3	1.8	3.4

• link segmented at the time of analysis, but stored as a coherent unit otherwise
• limited support in current (1998) GIS: requires complete overhaul of internal data models
• “route and offset” approach is the basis of linear referencing method of location description in GIS for Transportation (GIS-T), the language used by highway maintenance professionals

• Planarity
• Many current GIS insist on a planar model (overpasses treated the same way as navigable intersections), so that polygons can be built from network geometry
• No distinction between overpasses and 4-way street intersections
• Current solution: use turn-table with large impedance to disallow turns at overpass
• Ideal solution: data model should not enforce planarity; streets should be stored as continuous entities, with explicit intersection details where they exist

• Hierarchical structures
• At continental scale, the intersection of two freeways is a point
• At a local scale, the same intersection is a basketweave of ramps
• How to model a network so that user applies either interpretation depending on need?  Answer may lie in hierarchical object oriented structures.
• GDF model: cooperative European effort between major transportation players

5. Examples of Databases

5.1. Government Databases

• These products were developed to help census enumerators determine their areas of responsibility.
• The products have subsequently found a large market in all street network applications, from retail consumer tracking to navigation, even though data quality may not be appropriate for those applications.

• USA: US Bureau of the Census:
• 1980 Census: DIME
• 1990 Census: TIGER
• Canada: Statistics Canada:
• 1981 Census: Area Master File
• 1991 Census: Street Network File

5.2. Commercial Databases

• USA: Etak, GDT, Navigation Technologies (Navtech) and Thomas Brothers (western U.S. only), among others.
• Quality varies:
• lower end products are useful for marketing applications, where consequences of error are relatively unimportant
• others used primarily as base maps for traffic control (e.g. traffic signals)
• demands of in-vehicle navigation are the most stringent.

6. Data Quality

• Types of error
• inclusion/exclusion inconsistencies (particularly ramps, private roads and driveways)
• coordinate errors: up to 200m
• street naming
• street addressing
• topological errors: streets shown to intersect when they don't
• classification
• Positional error in ITS
• vehicle rarely drives exactly down centreline, usually off by a lane or two: say 10m
• error in street centreline coordinates: typically 0-30m, sometimes 200m
• error in GPS coordinate: usually 100m
• coordinate snapped to nearest centreline: may not be the right centreline
• to reduce errors, look for turns/elbows in GPS stream, match them to centreline database: map matching
• application requirements vary: road construction (0.03m), maintenance (10m)
• Address matching.
• Success rate usually 60-80%
• non-standard spellings and representations:
• Main Av vs Main Ave
• Route 101 vs Hwy 101
• North Main Street vs Main Street vs Main St N
• Ward Memorial Blvd vs Clarence Ward Memorial Blvd
• typographical errors in one or other database
• additional problems if verbally communicated (e.g. emergency call centres): Marquette St vs Market St.  Requires phonetic processing.
• impacts
• ITS/EMS: emergency vehicles sent to wrong place
• marketing: random errors insignificant; systematic errors (e.g. whole new neighbourhood omitted) are more serious
• Location referencing:
• communicating a location (e.g. reporting vehicle location) with respect to a network
• due to database differences, interoperability is a problem: a vehicle located on one road with respect to one map may appear in a different position relative to another map
• therefore coordinates are not sufficient
• may also use
• road name
• cross street names
• street address
• linear reference (distance from a reference point)

---

7. References

• Databases
• Statistics Canada http://www.statcan.ca/
• U.S. Bureau of Transportation Statistics http://www.bts.gov/
• U.S. Bureau of the Census (TIGER page) http://www.census.gov/geo/www/tiger/

• Data Models and Structures
• ESRI http://www.esri.com
• Ontario Standard Labelled Road Network http://www.dgrc.ca/slrn/slrn.htm

• Database Error and Accuracy
• VITAL http://www.ncgia.ucsb.edu/vital

• ITS Industry
• ITS America http://www.itsa.org

8. Review and Study Questions

• suggestions invited!

Evaluation

Citation

Noronha, Val (1998) Transportation Networks, NCGIA Core Curriculum in GIScience, http://www.ncgia.ucsb.edu/giscc/units/u183/u183.html, posted December 23, 1998