Network Models
Objectives
Network Models Find connected paths through the network(s)
SIE 510 Estimate costs of moving through the network
Spring 2005
Manage/analyze parts of the network or assets
From Miller, H. and S. Shaw. 2001. Geographic Information associated with the network
Systems for Transportation. Oxford:Oxford University Press.
Requires representation of topology and geometry of
February 1, 2005 the network
Network Model Topics Network Models and Graph Theory
Graph theory as underlying mathematical model Graph theory supplies the mathematical framework for networks
A graph is a set of vertices and relations between vertices
Network representation applied to transportation
systems Graph components
Vertices – uniquely identified, represent members of a set
Linear referencing systems
Edges – represent relationships among members of the set
edges are ordered pairs of vertices
Dynamic segmentation
directed edge – relation applies in one direction
undirected edge – relation applies in both directions
1
Network Models and Graph Theory Network Models
Planar graph Non-planar graph
Directed Link: a topological straight line
connection between two ordered nodes
Embedded in a Euclidean plane, Does not required vertices
NodeID #1 NodeID #2
requires a vertex at edge crossings at edge crossings
Networks – graph for explicitly representing interaction - Directed chain – a directed link with intermediate shape
connected set of nodes and links points between two ordered nodes
Nodes – vertices representing origin, termini or relays,
uniquely identified
NodeID #1 NodeID #2
Links – edges representing conduits for flow between nodes,
identified by labeled node pairs, for a directed graph the node
order is significant
Network representation of Road network representation
transportation systems
Transportation systems typically represented as directed
networks
Transportation system often partitioned into modal
specific sub-networks
Roadway, subway, air, rail, bus,
Links correspond to streets or roads
Often stored as separate networks with transfer links to
represent connections Nodes correspond to street intersections
Generalized cost function represents the unit cost to traverse a
link
2
Transit network representation Node-link model 32
31
8
7
23
Line haul links 6 Link ID From Node To Node Length
Transfer stop
6 20 23 22
20
7 23 31 86
stops
8 31 32 69
Node ID X Y Relational model
20 235.00 420.00 for node-link
23 250.11 436.00 consists of link and
31 324.05 460.35 node relations
32 410.65 472.80
Weaknesses of Planar Network Link Table
2 Link-ID From-Node To-Node
Most GIS require planar embedding of the node-link model 10 1
1 10 30
30
2 30 40
Planar embedding forces nodes at all intersections 4 40 5 50
3 3 30 20
Does not account for overpasses, underpasses or ramps 4 30 40
20 5 40 50
Assumes links are homogenous – an attribute is constant over
a link Turn Table Node Table
Limited support for one to many and many to many relations Node-ID From-link To-Link Impedance Node-ID attributes
30 1 3 5 10
Relations of many physical and logical transportation 30 1 4 10 20
entities are complex 30 1 2 -1 30
Route 202
30 1 1 -1
Route 202 Route 9 40
40 4 2 -1
50
Route 9
40 4 5 5
50 5 5 5 Addition of a turn table
relation addresses planar
embedding limitation
3
Turn Table Representation Spatial Referencing Systems
21 A spatial reference system defines the parameters
Over pass – under pass situation
and rules to situate a measurement in space.
20 23
The essential parameters for any spatial reference
Node ID From Arc To Arc Impedance system are an origin and units.
31
2 20 21 -1
2 20 23 0 These are the required parameters for a linear
2 20 31 -1 spatial referencing system.
Spatial Referencing Systems Linear Referencing Systems
155 miles 210, 398 Components
Datum – set of objects with directly measured locations
Z Axis
Y Axis Network - digital spatial representation of nodes and links
feet
Y Axis
35,107 Linear referencing method – method to determine a
0,0,0
0 0,0 X Axis position within the network using a defined path and an
X Axis
offset distance along the path
feet
Linear 2-D 3-D
4
Linear Referencing Methods Linear Referencing Systems
Support the association of “events” with positions within a
Road name - Mile point transportation network
9 Point events
Route 2 30
u te Accident event coded as:
5.0 10.0 Linear event Ro
Referenced as Route 2 MP 5.5 Route 22, Milepost 147.5
Control Sections Point events
2
Linear events
Route 2
Control section 1 Control section 2 Control section 3
Linear event Passing zone coded as
Route 22, Milepost 126.125
Link and Node
Link 43 to Milepost 134.25
Node 30 Referenced along link 43 Node 40
from node 30
Linear Referencing Systems Maintaining relationships
Widely used by Departments of Transportation since distances Physical roadway Æ Network
along roads were easier to collect than 2D positions and most
Physical marker
assets are assumed to be on the road. ( anchor point)
Often collected on-road by Distance Measuring Instrument
1 Physical measurement
(DMI)
Physical marker
Easy to report on-road attributes (e.g. accident ½ One physical roadway
Multiple spatial representations
mile south of Milepost 153 on I-95) (network links)
Anchor Point Anchor Section
Can be easily understood by users (e.g. ambulance driver) Identifier Identifier
Location description From anchor point
To anchor point
Changing with the growing use of GPS Measured distance
Linear Datum
5
Dynamic segmentation Spatial object for each attribute
Linkage of linearly referenced events (discrete or interval) Route 9
to a set of network spatial objects at run time. Route 101
Allows multiple sets of attributes to be associated RM102 RM105 RM108.5
with any portion of a linear feature RM108
RM1 RM9 RM11 RM17
Removes the need for a set of spatial objects for
Multiple sets of linearly referenced events
each attribute.
Without dynamic segmentation each event requires a node
Creates attribute based objects as needed.
on the segment to indicate beginning and end of an
attribute value
Dynamic segmentation example
Assume a set of pavement condition events referenced
using the LRM Road Name - mile-point
Route 101
RM 0 RM 22 RM 57 RM 177
Pav cond Route ID Start End Pavement
event# Marker Marker cond
10 101 RM0 RM22 Fair
11 101 RM22 RM57 Poor
12 101 RM57 RM177 Good
How do we place these events on the network?
6
Measured attribute –
Pavement condition
Maintaining relations
RM 0 RM 22 RM 57 RM 177
Datum to Network
101
Route
5
Sections 5 5
2 3
10 2 3
Links-nodes
6 7 8 One to one
Datum Node 23 Link 13 Node 24
Anchor section
Maintains precisely
Anchor points
measured distances
Anchor point 10 Anchor section 2 Anchor point 11
One to many
Real world Node 23 Link 13 Node 24
road section
Anchor section 2 Anchor section 3 Anchor section 4
Maintaining relations Links, Routes and
8
Network to LRM components
Sections 7
3
Many to many 2 Route # 5
6 Route # Route ID
Node 23 Link 13 Node 24
1 5 101
Route A Sect Link From To From To Pos Route
ID ID Measure Measure Pos #
Route B
1 6 0 22 0 100 5
2 7 22 108 0 100 5
Sections
3 8 108 177 0 50 5
7
Dynamic Segmentation for Multi-modal
Routing ITS data models
Virtual network database design based on route systems Improve use of existing capacity of systems
that capture functional dependencies in multi-modal
networks Suite of roadway sensor devices contribute to dynamic
model of the network system and its load
Topological network stored independently
For auto-routes as
direction of travel Goal is to provide real time information to travelers, to
Node 23 Node 24 traffic control devices, variable message signs
Link 13
Bus stop Bus route
Attributes maintained as routes systems and events
Need for 3D data models For complex overpass,
Adding complex lane and turn underpass, multi-ramp
configurations to the data model systems
Need model to represent
multiple lanes, lane change
constraints, lane splits and
merges, temporary lane
modifications, lane-lane
turns at intersections
Dynamic segmentation
approach assigns route to
each lane
8
Network Update Issues Address Geocoding
22 North Main
A B C
90 Node 65
10
0 100
11 Chain 159 89
Node 63
Chain From To From To From To
ID Node Node LADD LADD RADD RADD
159 63 65 10 90 11 89
AB/AC
100 * .15 = 15
12/80 = .15
