Routing/Shortest Path Analysis in Python and QGIS
As the name suggests, this is simply looking at how can I get from A to B in the shortest possible distance or time? Routing has many applications- from underpinning the maps we use regularly (think Google Maps) to game development, neuroscience, and artificial intelligence.
But why not just measure the distance from A to B? Well, the Euclidean distance (or the as-the-crow-flies distance) does not reflect real world movement- it doesn’t incorporate the network that you would take in real life to get from one place to another.
There are multiple variations of Shortest Path Analysis. You can measure the shortest path based on distance or time. And you can calculate both between two points, from multiple to start points to one end point, or from multiple end points to one start point.
In this article, I’ll set out some of the more common routing techniques in Python and QGIS.
Getting started
If you follow along with this article, you’ll want an up-to-date version of Python and QGIS installed. I use Python 3.9.12 and QGIS 3.26.1.
The examples in this article are going to look at applying routing/shortest path analysis to a dataset consisting of the Leeds road network and the locations of dental practices in Leeds (found here). The examples assume that you have knowledge of loading data into QGIS, projections, and clipping.
Sourcing data
Before you can start any analysis, you need a network. This could be roads, train lines, pedestrian movement- any network you can think of. For the sake of ease, you’ll want this data in a format such as a ShapeFile (.shp), GeoJSON (.geojson), Geopackage (.gpkg), or in a tabular format such as a CSV or xlsx file.
We will use the OSMnx Python package to source our road network data:
# pip install osmnx
import osmnx as ox
G = ox.graph_from_place('Leeds, UK', network_type = 'drive')Having done so, we can project the network to WGS84 and plot it:
Gp = ox.project_graph(G)
ox.plot_graph(Gp)
For routing in Python, we can immediately use this network. If we wanted to work in QGIS or another GIS software, however, we must export the network to a useable format. Here, I export it as a Geopackage:
ox.save_graph_geopackage(Gp, filepath="/filepath/leeds_driving_network.gpkg")Python
Say I have two points and I want to get from Point A to Point B, and I have the Lat/Long coordinates for each. We can calculate the route of shortest distance between these two points.
Our projected network (Gp) from above consists of thousands of nodes, or points. We can see these by looking at the list:
list(Gp)But we don’t know which node is closest to Point A or Point B. So, we can take the coordinates we do have and use the nearest_nodes function of OSMnx to identify the nodes closest to each point.
X0 = 51.76022, -1.80555 # Point A
X1 = 53.89806, -1.51252 # Point B
node = ox.nearest_nodes(Gp, X0, X1)
X0_node = [i for i, x in enumerate(list(Gp)) if x == node[0]]
X1_node = [i for i, x in enumerate(list(Gp)) if x == node[1]]
print(X0_node, X1_node)We can then use these nodes to calculate and plot the shortest path between the two points based on distance:
Note: the calculation is weighted by road length else all edges (roads) are considered equal distance.
orig = list(Gp)[X0_node[0]]
dest = list(Gp)[X1_node[0]]
shortest_distance_route = ox.shortest_path(Gp, orig, dest, weight="length")
fig, ax = ox.plot_graph_route(Gp, shortest_distance_route, route_color="r",
route_linewidth=6, node_size=0)
We can also calculate the k shortest routes- e.g. the 2 shortest distance routes from Point A to B.
mutliple_routes = ox.k_shortest_paths(Gp, orig, dest, k=2, weight="length")
fig, ax = ox.plot_graph_routes(Gp, list(mutliple_routes), route_colors="y",
route_linewidth=4, node_size=0)
We first need to know the speed of each edge or road along our route:
Gp = ox.add_edge_speeds(Gp)Note: Some edges may not have speeds associated with them due to the nature of OpenStreetMap (which underlies OSMnx)- these can be added using the hwy_speeds argument described here and shown below:
# 32 kmh (20mph); 48 kmh (30mph); 96 kmh (60mph)
hwy_speeds = {"residential": 32, "secondary": 48, "tertiary": 96}
Gp = ox.add_edge_speeds(Gp, hwy_speeds)
Gp = ox.add_edge_travel_times(Gp)Now we have speeds for all edges in our network, we can calculate the travel time (in seconds) that it’s likely to take to travel along each edge:
Gp = ox.add_edge_travel_times(Gp)We can then plot the route of shortest time (i.e. the fastest route) between Point A and B as above. This time, we weight by travel_time rather than by length as we’re interested in the time it will take.
shortest_time_route = ox.shortest_path(Gp, orig, dest, weight="travel_time")
fig, ax = ox.plot_graph_route(Gp, shortest_time_route, route_color="r",
route_linewidth=6, node_size=0)
To better visualise the optimal routes based on distance or time, we can plot them together:
fig, ax = ox.plot_graph_routes(Gp, routes=[shortest_distance_route,
shortest_time_route], route_colors=["b", "r"], route_linewidth=6, node_size=0)
Above, we can see how the shortest route between Point A and B differs depending on whether you’re interested in distance (blue line) or time (red line).
QGIS
Things are a little different when conducting routing in QGIS. I’m first going to import the GeoPackage of the Leeds road network saved earlier, as well as the shapefile of dental surgeries in Leeds:
To begin, I’ve chosen a house (Point A) and a specific dental surgery (Point B). I want to know how I can get from Point A (the red dot) to Point B (the blue dot) in the shortest possible distance using the road network.
I’m going to use the Shortest Path (point to point) tool (found under ‘Network Analysis’ on the Toolbox icon) to do this. This is going to calculate, for every possible route combination, the distance (in km) from A to B, and return the shortest.
For the start and end points, I’ve taken the XY coordinates of Points A and B. In distance based routing, we don’t particularly need to worry about the ‘Advanced Parameters’.
Once run, we get an output like that below, which shows the shortest route of all possible network combinations between Point A and Point B.
To find the distance of the shortest route, we can go to the Attribute Table (right-click on the ‘Shortest Path’ layer) where we can see the ‘cost’ column. Cost refers to Travel Cost, a measure of the distance or time expended travelling along a network. In my example, the cost is 18,164, or 18.164 km.
In addition to calculating the shortest path between two points based on distance, we can also calculate the shortest path based on time- i.e., which route will get me there fastest?
It’s very similar to the above, using the same Shortest Path (point to point) tool, except here we will change the ‘Path type to calculate’ field to ‘Fastest’, and we will look at some of the ‘Advanced Parameters’. Based on your need, alter the direction values to identify different edge types, and change the ‘Default speed (km/h)’ field to an appropriate value. If you have a network dataset containing the speed limits of each road, input this into the ‘Speed field’ to account for variable speed limits.
I’ve left most of the parameters as default, only changing the speed to 32 kmh to reflect a 20 mph speed limit.
Running this gives an output like below:
The fastest route is the same as the shortest distance route above. This is convenient but is not always the case depending on the road network and path dynamics. Looking again at the Attribute Table, we can see the travel cost of this route- in my example it’s 0.5644. Time units in QGIS are measured in hours, meaning that this journey would take roughly 34 minutes (0.5644 * 60) if travelling at a constant speed of 20mph.
So now we’ve looked at how we can calculate the paths of shortest distance and time between points A and B. But what if I want to know the shortest route from a single start point to multiple end points? This is where the ‘Shortest path (point to layer)’ tool comes in handy.
Shortest path (point to layer)
For this, I’ve added back in the shapefile of all dental surgeries in Leeds, and I will calculate the shortest routes (based on distance) from the house (Point A) to each of the other dental surgeries. As above, we can leave many of the parameters alone when measuring distance.
Running this yields an output like below, showing the shortest distance route from the house to each of the other dental surgeries.
Looking at the Attribute Table, we can see which dental surgery is closest to the house based on the lowest travel cost. In real life, we would likely choose the route with the lowest travel cost as it means shorter distances to the dentist.
The same process can be repeated to understand the fastest route that will take the least amount of time. Just follow the steps used previously.
We can also reverse this by looking at the shortest routes from multiple start points to one end point using the ‘Shortest path (layer to point tool). This is the exact same process as above and can be used for either distance or time measurements. In our example, we would be interested in knowing the shortest or fastest routes from any of the dental surgeries to the house (Point A).
Summary
In this article we’ve looked at how to conduct routing/shortest path analysis in both Python and QGIS, using a road network sourced from OSMnx. In future articles, we will look at service areas, isochrones, and distance matrixes.
