Instructor: Hi, and welcome to module four
of Advanced GIS.
This is the first of two modules we'll spend focused
on moving things around the landscape using GIS.
In this module, it's people.
Next week, it's water.
I thought I'd change things up a bit this week
by starting with a story about bridges.
Really old bridges, in fact.
And while we're starting with a story about bridges,
we'll end with an approach to network analysis
that relies heavily on a branch of theoretical mathematics
known as graph theory.
We'll explore how to apply network analysis techniques
to solve transportation problems.
Graph theory is a branch of mathematics
that uses structures or graphs
to model pairwise relationships.
In this case, we're interested in modeling
the spatial relationship between discrete
locations on a map.
So what does that have to do with the image on the right?
Well, this is where it gets interesting.
Back in the 1730s, Leonard Euler was wondering
about the seven bridges of Konigsberg.
Specifically, he was wondering if he could cross
all seven bridges one time without having to travel
across the same bridge twice.
He correctly concluded that the answer was no,
but never proved as much.
More than 100 years later, Carl Hierholzer came up
with the proof known as Euler's Theorem.
This eventually laid the groundwork for graph theory.
If we reduce each landmass to a point
and convert each bridge into a line
representing the connections between the landmasses,
we are able to abstract a physical landscape
into a graphical representation using points and lines.
A graph of, for example, a road network
lends itself readily to point
and line vector representations,
where the points represent junctions in the network
and the lines represent the edges of the network
to traverse in order to travel
from one location to another.
So what we see on the right should look familiar.
These points and lines, or junctions and edges,
comprise what is known as a network dataset,
and we'll talk about what differentiates it
from the more traditional vector data
we've worked with previously.
Graph theory provides the foundation
for transportation analysis of many types,
from simple paths to service area polygons
to origin destination matrices.
You could even identify weak links in the network,
the loss of which would cause severe travel disruptions.
Routing, logistics, and even site selection
can benefit from knowledge gleaned from network analysis.
Let's look at a few example graphs
and consider some routing alternatives.
We want to travel from point one to point nine
along the available edges,
without traversing the same edge more than once.
There are four possible routes available to us.
For example, we can travel from point one
to point two to point seven to point nine.
What if we add direction information to the edges?
Those could be used to manage the flow of traffic.
All the same conditions hold from before.
We still want to travel from point one to point nine,
and we still don't want to traverse
an edge more than once.
In addition, we need to respect the direction arrows.
As a result, we go from four possible routes down to two.
Let's take it one step further and add a weight,
or a cost, associated with traversing each edge.
In the last two examples,
it was about traveling from point one to point nine.
Now, let's figure out the best route
between these two locations.
I've assigned a cost for each edge,
and to determine the best route,
we need to sum the cost of all edges traversed
on the route between point one and point nine.
We see that route one costs 17 units,
while route two costs 13 units.
As a result, we declare that route two,
the path from point one to point two to point six
to point nine, is the least cost path
among all the available options.
Least cost path is fancy speak
for shortest route in this case.
Note again that cost is not always measured in distance.
Okay, so that was pretty easy,
but what about something like this?
There's no way I'm going to do all that math
on the back of an envelope.
It's time to turn the heavy lifting
over to the computers.
Remember that seven bridges problem?
Well, fast forward 75 years,
and Edsger Dijkstra developed an algorithm
which computed the shortest path between nodes in a graph.
This discovery had significant implications
for any number of routing applications,
including transportation modeling, utilities analysis,
and computer science among other topics.
Now let's look at the network analysis toolkit in ArcGIS.
Just a quick diversion though before we get started.
I mentioned earlier that a network data set
is different than the vector data
we've worked with previously.
Think of a network data set
as a special kind of vector data set.
Special because there's quite a bit
of additional information baked into the network data set
to enable analysis.
We'll talk about this in the context
of the road network,
but all the same concepts would apply to sidewalks,
hiking trails, bike lanes, and so on.
So the network data set includes the roads,
the intersections or junctions,
and some notion of connectivity.
The roads are straightforward, intersections too,
but what about connectivity?
The easiest example here is to think
of an interstate overpass
and the road that runs underneath it.
You can't turn from one to the other
unless there's a ramp.
There's a vertical offset that restricts
the connectivity of the two roads.
You can also apply specific restrictions
like one-way streets or turn limits
at particular intersections.
Maybe you're not allowed to turn right or left.
That affects everything from individual route decisions
to cumulative traffic flows.
The last piece of information embedded
in the network data set is the travel cost.
We typically think of travel cost and time units,
but we could also consider fuel consumption
or calories or total distance instead.
Calculating the time with no congestion is easy.
Divide the length of the segment by the speed limit.
Total distance isn't hard either,
but if you're interested in other cost alternatives,
you may need to develop your own cost model
to calculate those values based on other factors,
just like you would for time or distance.
One last thing before we move on
to the network analyst toolkit.
A network analysis requires a network data set.
This data set can be hosted either locally,
a data set on your local computer or network,
or can be accessed through cloud-based resources.
One thing to note here is that ArcGIS credits
are consumed if you use the cloud-based approach.
We don't assign you many credits for this course,
and those that we do are used for publishing data,
web maps, and web apps.
If you want to perform a network analysis
somewhere outside of Chittenden County, Vermont,
you will need to develop a network data set
of your own for that region.
A network analysis workflow typically follows
a minimum three-step procedure.
First, create an analysis layer.
We'll talk about the different types
of analysis you can perform.
Each one requires a slightly different version
of an analysis layer.
Once you select the type of analysis to perform,
in this case, we'll compute the shortest path
between two points, ArcGIS creates a feature data set
to contain all the inputs and outputs of the analysis.
Next, you'll add analysis objects
to the feature data set you just created.
These are things like stops or facilities
or incidents or origins and destinations.
You could also include point, line, or polygon barriers,
network elements that restrict the flow of travel.
The image on the right illustrates
four different types of network analysis.
Note that each requires slightly
different input information.
We'll look at examples of each in the coming slides
and in lecture two of this learning module.
Then, once you're happy with the parameters,
all that's left is to click run.
This solves for the equation you just built.
ArcGIS will lock the features of the analysis layer
and write the output information to the data set.
Depending on the kind of analysis you're doing,
the output will be represented
as a line, polygon, or matrix.
We'll look at examples of these in a few slides.
Well, now what?
That's up to you.
Maybe that's the end point of your analysis.
You just wanted to know the travel cost
from point A to point B.
If that's the case,
open the attribute table and find the answer.
Or maybe this is just the first step
in a much longer geoprocessing workflow.
The only limit here, as I've said before,
is your imagination.
I'd like to round out the lecture
with a brief review of four types of network analysis
you can perform with ArcGIS.
We'll start with the easiest,
but most fundamental of all network analysis operations.
This is the algorithm that makes all the others possible.
Let's compute a route between two point locations
based on a specified travel cost.
In this case, time measured in minutes.
Remember, this information is baked into
the network data set
and is used by ArcGIS to determine
the most efficient route between two points.
On the right, we see the output from the analysis.
It's a line connecting my two point locations.
If we open the attribute table
for the routes feature class,
we see that there is a single record
defining my travel between stops one and two.
The record includes information on the total distance
measured in meters,
and the total cost measured in minutes.
Remember, both of those unit definitions
can be found in the network data set properties.
Let's up the difficulty just a bit.
In this case, we'll perform a closest facility analysis.
This type of analysis identifies
the closest facility to an incident.
Note that it's possible to have
both more than one incident
and more than one closest facility identified.
We see the simplest case on the right,
where I've identified the single closest facility
to a single incident.
Consider you're an emergency services operator.
There's a fire.
You would like to know which fire station
is closest to the incident.
We see that the route delineated
as a purple line connecting a circle,
the location of a fire station,
with a square, the location of the fire.
That information is written to the routes feature class
within the closest facility feature data set.
If I open my route attribute table,
I once again see a single record
describing travel between locations one and three.
The total distance is just under 4,800 meters,
and the total travel time
from the closest fire station is just under six minutes.
Next up is what's known
as an origin destination cost matrix.
In this case, we're computing the travel time
between every origin and every destination
in our data sets.
This information is written out as a cost matrix.
The image on the right illustrates the connections
from each origin to each destination.
If we open the lines attribute table,
we see the details of each route.
This information could be used to identify
the closest origin to each destination,
or more frequently is used as a primary input data set
into more formalized travel demand models.
One other thing about the attribute table.
Notice that the total meters attribute
is full of null values.
In this case, only the travel cost is measured.
Although the shape length attribute
in the previous examples match the total meters attribute,
in this case, the shape length refers
to the length of the straight line.
Not really useful for the level of detail you'd need
for network analysis.
Otherwise, you could just use the near tool
if you weren't interested in travel across a network.
The last of the examples looks at a service area analysis.
This type of analysis defines polygon boundaries
that represent the area you could travel to
within a given amount of time
from a given point of origin.
In the example here, we've got two facilities,
the purple dots and polygons representing
the area of travel
within one and three minute cutoff times.
If we look at the attribute table,
we can see the facility ID,
the from and to breaks representing the cutoff times
you specify, and the typical system fields
like shape length and shape area.
There are four records,
two polygons for each facility representing
their one and three minute cutoff boundaries.
Service areas are useful for locating gaps in coverage.
Consider our first responder example from before.
Want to locate service gaps or gaps in coverage?
A service area analysis would be a good place to start.
Maybe you want to open a gas station
or a coffee shop or a hotel.
A service area could identify priority locations
if you want to be close to
or far away from your competitors.
Two other analyses I'll mention
without covering in any depth
are location allocation analysis
and vehicle routing problems.
These are both good skills for working
with vehicle fleets, delivery scheduling,
and the transport of goods.
Two more elements of note though,
before I offer a short demonstration
of the Network Analysis Toolkit.
The first of these is that you can compute directions
for route, closest facility,
and vehicle routing analyses.
Simply specify the output type as XML, HTML, or text.
Determine whether to include travel cost,
and if so, specify the time attribute.
That, of course, comes directly
from the network dataset specification.
Expect output here that is similar
to what you would see from Google Maps.
The second tool I want to mention
is the copy traversed source features.
This is a great way to export the results
of a particular network analysis.
The network analysis layer naming scheme
in the geodatabase is a bit difficult to parse.
Use this tool to export your results
while having control over the naming conventions.
The output of this operation is two feature classes,
the edges and the junctions, and a table for turns.
This data offers a much more detailed documentation
of each of the routes that were identified
in the analysis, broken down by individual segment
within an overall route.
There's the route ID attribute,
plus the from and to junctions
for each of those segments,
along with cost and distance calculations.
That's a lot of information.
Okay, I think that's enough
to whet your network analysis appetites.
In the next lecture, I'll run through
a short demonstration of a few of these techniques.
See you in a minute.