Transcript Network Analysis

Network Analysis, Routing
Dawn Wright and Jim Graham
Networks
• Systems of connected lines
• Weights along edges
Junctions
Or Nodes
Edges or Links
Spatial Examples
• Electrical Grid
– Power lines and transfer stations
• Roadways (highways, freeways)
– Roads and intersections
•
•
•
•
•
Pipelines
Canals, streams, rivers
Shipping lanes
Migration paths
Social networks (non-spatial?)
Example: Freeways
Network Rules
• Edge-Junction:
– Which edges can connect to a junction
– Examples:
• Three-phase 240 volt vs. high voltage
• Freeway to overpass
• Edge-Edge:
– Freeway to Freeway: overpass with clover
leaf
– Freeway to Highway: overpass with lights
– Highway to Highway: lights
– Road to Road: stop signs
Weights
• Edge
– Type of surface, speed limit -> Travel time
• Junction
– Type of intersection -> stop time
• Barrier
– Stops travel, can be temporal
– Examples:
• Construction
• Raising bridges
• Can be directional (i.e. fish move
downstream easier than upstream)
Sources & Sinks
• Sources
– Add to the network
– Examples:
• Downtown at 5:00pm
• Spawning areas
• Sinks
– Terminate a network
– Examples:
• Suburbs at 5:00pm
• The ocean
Network Problems
• Shortest path: Route
• Minimizing total distance traveled
• Minimizing the largest distance traveled by any
customer
• Maximizing profit
• Minimizing a combination of travel distance and
facility operating cost
Network Analyst
• Finding Optimal Routes
– Route Solver Properties
– Service Area Solver Properties
– Closest Facility Solver Properties
– OD Cost Matrix Solver Properties
– Vehicle Routing Problem Solver Properties
– Location Allocation Solver Properties
Shortest Path - Route
• Stops
• Time windows for deliveries
• Etc.
Closest facility analysis
• Multiple origins, destinations, facilities
along the route
Optimization & Routing for
Emergency/Disaster Response
• Kim et al. 2006 – PARs, Protective
Action Recs
d= interpolated, shortest-distance of wildfire to community
d1 = shortest distance before PAR
d2 = shortest distance after PAR
t = time PAR was issued
t1 = time last known fire perimeter at d1
t2 = time last known fire perimeter at d2
Fire Origin to Communities:
Estimate Avg. Speed of Fire
Between Known Perimeters
Kim et al. 2006
Additional Slides
Origin-Destination (OD)
Cost Matrix
Routing service technicians for Schindler Elevator. Every day this company’s
service crews must visit a different set of locations in Los Angeles. GIS is used to
partition the day’s workload among the crews and trucks (color coding) and to
optimize the route to minimize time and cost.
Gateway to the Literature
• Cova, T. and Johnson, J.P., 2002. Microsimulation of
neighborhood evacuations in the urban-wildland
interface. Environment and Planning A, 34: 2211-2229.
• Cova, T. J., P. E. Dennison, et al. 2005. Setting wildfire
evacuation trigger points using fire spread modeling and
GIS. Transactions GIS, 9(4): 603-617.
• Kim, T.H., Cova, T.J., and Brunelle, A., 2006.
Exploratory map animation for post-event analysis of
wildfire protective action recommendations. Natural
Hazards Review, 7(1): 1-11.
• Monteiro, C., Ramirez-Rosado, I., Zorzano-Santamaria,
P. and Fernandez-Jimenez, L.A., 2005. GIS spatial
analysis applied to electric line optimization. IEEE
Transactions on Power Delivery, 20(2): 934-942.