Network Analysis: Finding shortest path in QGIS

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 in Carleton University, and the finalized work of this course is this tutorial which was originally published in 2014 and edited in 2017. 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. The Road graph plugin is the essential tool used for this task, and will be explained with a step-by-step walk-through in this tutorial. QGIS is widely used in previous tutorials of the GEOM 4008 course. Referring to previous tutorials done before on this course you may find more information regarding the QGIS software. Check: Georeferencing Raster Imagery in QGIS using Vector Data.

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. However, not everyone has access to these expensive software, so an open-source alternative would be ideal. This tutorial will explore the Road Graph plugin of QGIS 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 2.18.13 are the most important steps to start this project. The use of the plug in 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" shapefile, the "Outdoor Rinks" shapefile, the "Water Bodies" shapefile and lastly the "Wards 2014" shapefile.

The shapefiles should be located in the same folder, in which we are going to work within. 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 2.18.13)

• You need to install the newest version of Quantum GIS (version 2.18.13 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 GQIS 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 shapefiles 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

Projection

All the layers were projected under EPSG:2951 - NAD83(CSRS) / MTM zone 9 projection. Right click on the layer, select Project Properties, from which we choose CRS. Then we select the appropriate projection for our case. This process can done for all the layers that we are working with, however they should all have the same CRS automatically.

Area of Ineterest (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, 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.

Batch Clip tool

Now we will clip all of our layers to match the extent of the AOI. Navigate to the Processing menu at the top of the QGIS user interface and select Toolbox. This opens a window on the right of the screen. From there, navigate to QGIS Geoalgorithms, Vector Overlay Tools, right click on the Clip tool and select "Execute as 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.)

• Right click on the clipped roads layer
• Select Properties
• Choose Style and at the top of the Styles window where it currently says Single Line, select Categorized and Column: ROAD_TYPE
• Double click on the symbols of each roads type to edit them further if you would like. In the example screenshot below, I increased the thickness of the Highways and changed to color to a deep red to make them, stand out from other roads.

We can also label the ClippedRinks 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.

The results should look similar to the screenshot below.

Road Graph Plugin

The Road Graph Plugin is a C++ plugin for QGIS that 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 length and travel time.
   - Optimizes by length or by travel time.
   - Exports path to a vector layer.
   - Highlights roads directions (not used in this tutorial).

Activate the Tool

---

To activate the Road Graph plugin:

---

• Start the Plugin Manager by clicking on the QGIS main window’s menu item Plugins ‣ Manage and Install Plugins.
• A dialog window appears. Write road on the search tab
• It will automatically appear the road graph plugin and check it on. (this plugin is already installed in the repository, when we installed the software in our computers )
• Go back to your work window
• This panel will appear in your interface

• If the plugin doesn't show automatically in your interface, go to View ‣ Panels and ensure that Shortest path has a check mark next to it.

Configure the Tool

• Go to Vector menu
• Select Road graph
• Select Settings

Time Unit and Distance Unit we leave as default in hour and kilometer. Topology tolerance: In the case of a gap between two lines that should be treated as continuous, a topology tolerance may be applied, for example 10m. In our case we left as default 0 because it can be assumed that a municipal dataset should be almost entirely topology error-free.

For the Transportation Layer, we choose the ClippedRoads layer created earlier.

For the direction field, are able to use the FLOW field in the attribute table. For Forward direction, specify "FT", and use "TF" for reverse 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 60 km/h as shown in Figure below.

Use the Tool

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 . In the plugin panel, click on the Capture Point button next to the Start field:

• Click point that represents Brewer Park as the start point.
• Use the Capture Point button next to the Stop field and capture the point representing Jack Purcell Park.

• Click on the Calculate button to see the solution:

The result for the shortest path is shown below. This is a simple case, where the speed mode is the same for all the streets, 60 km/h.

Using 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 Toggler button 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 had to run some selection attribute query over the road layer, in order to specify the speed limit 50 km/h for the private roads,60 for public roads with the name BRONSON, 45 km/h for the public roads with name GLOUCSTER and 30 km/h for the rest of the roads.

• On the bottom left corner of the Attribute Table, there is a Show All Features button. Click on the arrow and select Column Filter *Then choose for example TYPE, because we want to select the private roads.
• As you write rt_private automatically will appear the Advanced Filter expression.

• Select private roads and assign the speed limit 50 by using Advanced Filter expression. (Click on under the speed field, and add the value of speed for each record).

Hint: It is not found how to change automatically the value for a range of records with field calculator. After the selection was done, I had to enter manually the values for each selected record. This needs to be improved, because imagine you have a set of 300 records selected and for all of them should be assigned the same speed limit value. Entering manually it is not a solution

• Select public roads with name BRONSON and assign the speed limit 60 by using Advanced Filter expression

• Select public roads with name GLOUCESTER and assign the speed limit 45 by using Advanced Filter expression

• Select the rest of the public roads and assign the speed limit 30 by using Advanced Filter expression

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.

Use the tool after criteria is done

• Check the Vector ‣ Road graph ‣ Road graph settings to ensure that it’s set up as explained previously in this tutorial, but with the Speed value set to the SPEED field you just created.
• In the Shortest path panel, click the Start point button.
• Set the starting point to where the point of Museum of Nature is located.
• Set the end point to the Museum of War location.

• In the Criterion drop-down list in the Shortest path panel, select Length.
• Click Calculate. The route will be calculated for the shortest distance:

Notice the values of Length and Time in the Shortest Path panel.

And this is the result graphically of the shortest path in distance

• Set the Criterion to Time.
• Click Calculate again. The route will be calculated for the shortest time:

• You can switch back and forth between these criteria, recalculating each time, and note the changes in the Length and Time taken.

The Shortest Time path result as shown below

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

Conclusion

Road graph plugin used in QGIS, helped defining the shortest and the fastest way to get from Canadian Museum of Nature to Canadian Museum of War, based on the cost length. It is easy to work with this tool. It is important to verify the settings. You could verify from the output that if the speed limit is the same in all the roads, the shortest distance would be the same route for the length and time cost. While if we apply different speed limits for different segments of roads, than there is difference between the shortest path way for length cost, compare to shortest path way for time cost. This tool is limited, in the sense that if we would like to calculate the distance between two points and we have speed limit in miles/hour, the tool will not give us solution, because by default it has only kilometers or meters measurement. So one way to solve it is to convert miles to meters or km by re-editing the attribute table. According to QGIS field calculator I found difficulties in assigning the speed values automatically once a time for a specific selected amount of records. I had to enter them manually, which takes time. This step needs to be improved for this tutorial.

Future work

Future work might be creating Drive Time isochrones in QGIS. Site analyses can benefit greatly from using “drive-time” isochrones to define the study area. In ArcGIS this is called Sercive Area. It might be helpful pgRouting open source software to create the nodes network, which each of them would define a start and an end point for different segments that create the network. Check in for more details: Drving time isochrones.

References

• ArcGIS. (2014) Sercive Area Analysis. Retrieved Dec 15, 2014 http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//004700000048000000
• QGIS. (2014) Download QGIS for your Platform. Retrieved on December 15, 2014 from http://www.qgis.org/en/site/forusers/download.html
• QGIS. (2014) Road Graph plugin. Retrieved Dec 15, 2014 http://docs.qgis.org/2.6/en/docs/user_manual/plugins/plugins_road_graph.html
• QGIS Blog. Anita Gracer (2011).Drive Time Isochrones – An Example Using Finnish Airports. Retrieved on December 16, 2014 from http://planet.qgis.org/planet/tag/drive%20time%20isochrones/
• 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