Difference between revisions of "Network Analysis: Finding shortest path in QGIS"

Latest revision as of 13:06, 30 September 2021

Purpose

This project aims to introduce the various capabilities of open source softwares and their ability to solve spatial problems. The idea of open software was introduced during the GEOM 4008 course at Carleton University, and the finalized work of this course is this tutorial which was originally published in 2014, edited in 2017 and 2021. It will attempt to explain a helpful tool in Quantum GIS (QGIS), an open source software, that can identify the shortest path between two points in a network based on either distance or time. We have to use the Network Analysis tool in the processing toolbar for this tutorial and I will go step-by-step on how we can do that. QGIS is widely used in previous tutorials of the GEOM 4008 course.

Introduction

Calculating the shortest distance between two points is a very common spatial problem that appears in our daily life quite often. In ArcGIS software (not open source), this problem can be solved using the Network Analysis tool. We use an identically named tool on QGIS and it is an ideal open source alternative. This tutorial will explore that QGIS tool as a solution for finding the shortest path distance or time by calculating cumulative cost between two points in a network. Installing, activating and configuring the tool in the latest version of QGIS 3.20.3 are the most important steps to start this project. The use of the tool is to measure a cumulative cost based on length between two nodes of a network. Measurements take in consideration either the first case, when the speed limit is the same for all the roads (edges of our network) or the second case, when the speed limit differs for some selected roads.

Data

The data are provided by City of Ottawa Open Data Catalog. In order to create the network, a few files are required. Download the "Roads Centrelines" shapefile, the "Outdoor Rinks" shapefile, the "Water" shapefile and lastly the "Wards 2010" shapefile, in addition of to the "Basketball courts" , "Tennis courts", "Outdoor Wading Pools", "Cycling Network", "O-Train" "O-Train Stage 1" and their corresponding station shapefiles.

The shapefiles should be located in the same folder, within which we are going to store our work. Create a folder in your desired directory called "NetworkAnalysis" or something similar in order to store the downloaded shapefiles as well as any outputs that are generated.

Acquiring QGIS (version 3.20.3)

You need to install the newest version of Quantum GIS (version 3.20.3 at the time of editing this tutorial) in order to activate the road graph plugin.

You may go to this link : QGIS Download in order to download the QGIS version that is suitable to the operating system you are working on.

After the software is downloaded and ready to execute, double click the QGIS shortcut icon on your Desktop or search for it in the Start Menu. The QGIS window opens, and we are ready to begin.

Set up the Environment

The type of the data that we are going to work are vector data. The first step is importing the data into QGIS.

Add vector data

In Layer menu, select Add layer and choose Add Vector Layer. Another option is click the Add Vector Layer button of the toolbar..

Add each of the layers(in .shp format) individually.

Projection

All the layers are to be projected under EPSG:2951 - NAD83(CSRS) / MTM zone 9 projection. Right click on the layer, select Properties, you then go into Source, search and select the appropriate projection. Click apply to see your changes and repeat with your 4 layers. This process can done for all the layers that we are working with, however they should all have the same CRS automatically.

.

Area of Interest (AOI)

The project is focused on determining the shortest path between the outdoor rink at Brewer Park and one at Jack Purcell Park in downtown Ottawa. By creating an area of interest, or AOI, we can effectively reduce the amount of useless data in the output. In larger data sets, creating an AOI may also reduce processing times.

In Layer menu, choose Create Layer, then New Shapefile layer and the New Vector Layer window will show up. The AOI should be a polygon.
Click the AOI layer.
Click the Toggle on button to start editing the layer. Alternatively, right click on your new layer in the Layers Panel on the left hand side and toggle editing "On"
Zoom to the scale that meets your needs by holding the CTRL button and using the scroll wheel on your mouse. To create the polygon, find the polygon create tool begin by clicking in each of the four corners of your current zoom extent. This ensures that your AOI has 90 degree angles and crisp lines. On the last point of the polygon, right click to finish creating it.

Union tool

The data for the trains in Ottawa divided by old O-Train and the new LRT so if we want to be able to find the path with a train, we need to join those two together

Go on the vector menu, scroll over Geoprocessing tools and select "Union"

You will find page like the one in the figure below where you will select the input and overlay layer which can be "O-Train" and "O-Train Stage 1"

Select Run and you should have you Ottawa train network

Clip tool

Now we will clip all of our layers to match the extent of the AOI. Navigate to the Vector menu at the top of the QGIS user interface, put the cursor on Geoprocessing tools and select Clip. You select "Run as a Batch Process". This allows us to clip all of our desired layers at once using one tool (Please note that the Batch Processing Tool requires at least 3 input layers to function).

Input vector is the layer we want to clip: Roads
Clip layer is the AOI that we just created
Output shapefile is specified by us. Refer to the file folder you created to hold all shapefiles and outputs earlier in the tutorial.

Symbology

To improve the visual appeal and usability of the map that we create, we should symbolize the different layers to meet our needs instead of staying with the defaults. Firstly, we will symbolize roads based on their type (Street, Boulevard, Parkway, Highway etc.)

To that on QGIS, you need to do a rule based classification:

Right click on the clipped roads layer
Select Properties
Choose Symbology and in the scroll down menu selected "Rule Based"
You will then set a rule using an expression such as "SUBCLASS" IN ('HIGHWAY', 'FREEWAY') to combine those two classes of roads
This is necessary if you have over 10 road types that you cannot sort otherwise.
Classify to as many road names as you want

The train data can be symbolized with the rail symbol available on QGIS.

Any other added features that we added can also be customized so the map: tennis court(green dot), wading pool(blue dot), etc...

We can also label the clipped rinks file in order to see the names of the rinks.

Right click on the clipped rinks layer
Select Properties
Choose "Labels" and at the top of the Labels window, select "Show labels for this layer", using "PARKNAME" as the label field.

I do not however recommend doing it for the tennis, basketball and wading pools as they share locations in many cases and it could be a cause for clutter.

The results should look similar to the screenshot below.

Network Analysis

The Network Analysis tool for QGIS calculates the shortest path between two points on any polyline layer and plots this path over the road network.

Main features:

   - Calculates path, as well as the cost(length or time).
   - Optimizes by length or by travel time.
   - Exports path to a vector layer.

Using the Tool

Go to the Processing menu
Select the "Toolbar" menu, the processing toolbar should now appear on the right of your workspace
Select the Network Analysis drop down menu, you will then find "Shortest path(point to point)" which you then select

You should see an image like the one on the figure below

To start, you will need to choose a vector layer which will represent the network. This is where you have to choose your mode of transport, if you want to use the bike, choose the cycling network; the train, choose the union train shapefile; and for the cars, pick the roads.

You will then have the option for the shortest or fastest path, I will give the instructions for both:

Shortest:

Select the shortest option in the menu

Suppose you are playing hockey at Brewer Park after class, but your friend wants to meet at Jack Purcell rink downtown. We need to calculate the shortest possible route in length from Brewer Park to Jack Purcell Park

For the Start field, click the 3 dots and select a point to start on the map, Brewer Park for our example

For the end point, do the same but select Jack Purcell for our example

For the direction field, are able to use the FLOW field in the attribute table.

For Forward direction, specify "FT", and use "TF" for backward direction. These abbreviations mean "From - To" and "To - From" respectively, meaning From a specified point to an edge (in this case, a road polyline) and vice-versa for TF. Leave the value for two-way direction blank. This allows the tool to factor one-way roads into its calculations, instead of sending you on an impossible route through the city.

Choose the speed limit value under the Default Settings tab. For this example the speed was chosen 50 km/h as shown in Figure below.

The results should look like the figure on the right

Setting Speed Criteria

To be able to do the fastest route we need to set the speed criteria What happens when different streets in the network road have different speed limits?

The idea is to set different speed limits for some of the selected streets by us. In this case we had to add a new field in the roads layer and call it Speed.

Create New Field

Right click on the roads layer.

Open attribute table and select the Pencil to set on the edit mode .

After that click the New Column icon.

Call this new column SPEED, and give it the type Whole number (integer) with a width of 3.

Queries

Now we run a Field Calculator expression within the road layer that will specify the speed limit 60 km/h for the Streets, 50 for Avenues, 80 for Roads and 40 km/h for the rest of the road types.

Open up the attribute table for the clipped roads file and select the Pencil in the top left corner. Then, open up the Field Calculator.(figure below)

From here, we can write a simple expression that will populate the SPEED field created earlier with our desired values. Enter the expression into the Field Calculator as is shown below, or specify your own values for different road types. The speeds defined here are totally arbitrary, and are simply meant to show the functionality of the field calculator to remove the need for individually defining each street's speed limit.

After assigning the speed limits for each selection we save the edits by clicking the save button and then click the toggle button again to turn off the edit mode.

Fastest:

Go back to the Network Analysis tool like you did earlier

Select "Fastest" in the path to calculate
Select your start and end point it could be the same two again
Enter the same direction information for the shortest path
Now under the speed field, select the "SPEED" field
You can keep the average speed from earlier and the topographic tolerance as well

If you run this, you should get the fastest path(results shown on the right)

You can switch back and forth between these criteria, recalculating each shortest and fastest paths, and note the changes in cost taken. In this particular example, the only difference between the shortest and fastest route is a single right turn.

The last operation is to export the output as a shapefile, by clicking the Export button on the Shortest path panel.

Let's look at the differences between the paths, the fastest in red and the shortest in black(below)

Conclusion

The Network Analysis tool for QGIS is a useful utility for solving any cost-distance query that one might have. The tool itself is very user-friendly and intuitive and can really help in finding the best route using whichever criteria designated. One could verify that they set up the tool properly by checking if the outputs for the the fastest and shortest path are the same, indicating that the SPEED field wasn't created properly. This tool is slightly limited in the sense that if we would like to calculate the distance between two points in miles or the speed field is in miles/hour, the tool will not give us solution, because by default it supports only kilometers and meters. One way to solve this would be to convert miles to meters or km through another field calculator expression.

Future work

This solution could be further improved when we can combine modes of transport, for example, wanting to bike to the train. It can also be improved if we can find a way to incorporate traffic using some indices and the inclusion of real time data would really benefit such a model, however maybe more in a web map than QGIS. Having the data to update construction sites, road closures and other separated incidents that would affect the model would be great but mostly the responsibility of the data supplier. Also for the delivery companies such as UPS, Canada Post could calculate the most cost effective road which a software like this would permit, the possibility to add multiple points would also be pretty good.

References

7.3. lesson: Network Analysis¶. QGIS Documentation. (2020, June 5). Retrieved September 30, 2021, from https://docs.qgis.org/3.4/en/docs/training_manual/vector_analysis/network_analysis.html.
ArcGIS. (2014) Service Area Analysis. Retrieved Dec 15, 2014 http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//004700000048000000
QGIS. (2021) Download QGIS for your Platform. Retrieved on September 30, 2021 from http://www.qgis.org/en/site/forusers/download.html
City of Ottawa Open Data Catalog (2013).Roadways Retrieved on December. 15, 2014 http://data.ottawa.ca/dataset/roadways
City of Ottawa Open Data CatalogMuseums (2013). Museums Retrieved on December. 15, 2014 http://data.ottawa.ca/dataset/museums