Archive

Tag Archives: Routing

Wrong navigation instructions can be annoying and sometimes even dangerous, but they happen. No dataset is free of errors. That’s why it’s important to assess the quality of datasets. One specific use case I previously presented at FOSS4G 2013 is the quality assessment of turn restrictions in OSM, which influence vehicle routing results.

The main idea is to compare OSM to another data source. For this example, I used turn restriction data from the City of Toronto. Of the more than 70,000 features in this dataset, I extracted a sample of about 500 turn restrictions around Ryerson University, which I had the pleasure of visiting in 2014.

As you can see from the following screenshot, OSM and the city’s dataset agree on 420 of 504 restrictions (83%), while 36 cases (7%) are in clear disagreement. The remaining cases require further visual inspection.

toronto_turns_overview

The following two examples show one case where the turn restriction is modelled in both datasets (on the left) and one case where OSM does not agree with the city data (on the right).
In the first case, the turn restriction (short green arrow) tells us that cars are not allowed to turn right at this location. An OSM-based router (here I used OpenRouteService.org) therefore finds a route (blue dashed arrow) which avoids the forbidden turn. In the second case, the router does not avoid the forbidden turn. We have to conclude that one of the two datasets is wrong.

If you want to learn more about the methodology, please check Graser, A., Straub, M., & Dragaschnig, M. (2014). Towards an open source analysis toolbox for street network comparison: indicators, tools and results of a comparison of OSM and the official Austrian reference graph. Transactions in GIS, 18(4), 510-526. doi:10.1111/tgis.12061.

Interestingly, the disagreement in the second example has been fixed by a recent edit (only 14 hours ago). We can see this in the OSM way history, which reveals that the line direction has been switched, but this change hasn’t made it into the routing databases yet:

This leads to the funny situation that the oneway is correctly displayed on the map but seemingly ignored by the routers:

toronto_okeefe_osrm

To evaluate the results of the automatic analysis, I wrote a QGIS script, which allows me to step through the results and visually compare turn restrictions and routing results. It provides a function called next() which updates a project variable called myvar. This project variable controls which features (i.e. turn restriction and associated route) are rendered. Finally, the script zooms to the route feature:

def next():
    f = features.next()
    id = f['TURN_ID']
    print "Going to %s" % (id)
    QgsExpressionContextUtils.setProjectVariable('myvar',id)
    iface.mapCanvas().zoomToFeatureExtent(f.geometry().boundingBox())
    if iface.mapCanvas().scale() < 500:
        iface.mapCanvas().zoomScale(500)

layer = iface.activeLayer()
features = layer.getFeatures()
next()

You can see it in action here:

I’d love to see this as an interactive web map where users can have a look at all results, compare with other routing services – or ideally the real world – and finally fix OSM where necessary.

This work has been in the making for a while. I’d like to thank the team of OpenRouteService.org who’s routing service I used (and who recently added support for North America) as well as my colleagues at Ryerson University in Toronto, who pointed me towards Toronto’s open data.

Advertisements

As announced in Salzburg a few days ago, I’m happy to present the lastest enhancement to my IDF router for QGIS: travel time routing and catchment computation.

Travel times for pedestrians and cyclists are computed using constant average speeds, while car travel times depend on the speed values provided by the road network data.

Catchment computations return the links that can be traversed completely within the given time (or distance limit). The current implementation does not deal with links at the edge of the catchment area, which can only be traversed partially.

Loading the whole network (2.7GB unzipped IDF) currently requires around 10GB of memory. One of the next plans therefore is to add a way to only load features within a specified bounding box.

Plans to turn this into a full-blown plugin will most likely have to wait for QGIS 3, which will ship with Python 3 and other updated libraries.

Screenshot 2016-07-17 22.04.54

Monday, January 4th 2016, was the open data release date of the official Austrian street network dataset called GIP.at. As far as I know, the dataset is not totally complete yet but it should be in the upcoming months. I’ve blogged about GIP.at before in Open source IDF parser for QGIS and Open source IDF router for QGIS where I was implementing tools based on the data samples that were available then. Naturally, I was very curious if my parser and particularly the router could handle the whole country release …

Some code tweaking, patience for loading, and 9GB of RAM later, QGIS happily routes through Austria, for example from my work place to Salzburg – maybe for some skiing:

Screenshot 2016-01-06 17.11.27

The routing request itself takes something between 1 and 2 seconds. (I should still add a timer to it.)

So far, I’ve implemented shortest distance routing for pedestrians, bikes, and cars. Since the data also contains travel speeds, it should be quite straight-forward to also add shortest travel time routing.

The code is available on Github for you to try. I’d appreciate any feedback!

This is a follow-up on my previous post introducing an Open source IDF parser for QGIS. Today’s post takes the code further and adds routing functionality for foot, bike, and car routes including oneway streets and turn restrictions.

You can find the script in my QGIS-resources repository on Github. It creates an IDFRouter object based on an IDF file which you can use to compute routes.

The following screenshot shows an example car route in Vienna which gets quite complex due to driving restrictions. The dark blue line is computed by my script on GIP data while the light blue line is the route from OpenRouteService.org (via the OSM route plugin) on OSM data. Minor route geometry differences are due to slight differences in the network link geometries.

Screenshot 2015-08-01 16.29.57

It’s my pleasure to report back from this year’s AGIT and GI_Forum conference (German and English speaking respectively). It was great to meet the gathered GIS crowd! If you missed it, don’t despair: I’ve compiled a personal summary on Storify, and papers (German, English) and posters are available online. Here’s a pick of my favorite posters:

I also had the pleasure to be involved in multiple presentations this year:

QGIS at the OSGeo Day

As part of the OSGeo Day, I had the chance to present the latest and greatest QGIS features for map design in front of a full house:

Routing with OSM

On a slightly different note, my colleague Markus Straub and I presented an introduction to routing with OpenStreetMap covering which kind of routing-related information is available in OSM as well as a selection of different tools to perform routing on OSM.

Solving the “unnamed link” problem

In this talk, I presented approaches to solving issues with route descriptions that contain unnamed pedestrian or cycle paths.

Here you can find the full open access paper: Graser, A., & Straub, M. (2015). Improving Navigation: Automated Name Extraction for Separately Mapped Pedestrian and Cycle Links. GI_Forum ‒ Journal for Geographic Information Science, 1-2015, 546-556, doi:10.1553/giscience2015s546.

Inferring road popularity from GPS trajectories

In this talk, my colleague Markus Straub presented our new approach to computing how popular a certain road is. The resulting popularity value can be used for planning as well as routing.

Here you can find the full open access paper: Straub, M., & Graser, A. (2015). Learning from Experts: Inferring Road Popularity from GPS Trajectories. GI_Forum ‒ Journal for Geographic Information Science, 1-2015, 41-50, doi:10.1553/giscience2015s41.

A few weeks ago, the city of Vienna released a great dataset: the so-called “Flächen-Mehrzweckkarte” (FMZK) is a polygon vector layer with an amazing level of detail which contains roads, buildings, sidewalk, parking lots and much more detail:

preview of the Flächen-Mehrzweckkarte

preview of the Flächen-Mehrzweckkarte

Now, of course we can use this dataset to create gorgeous maps but wouldn’t it be great to use it for analysis? One thing that has been bugging me for a while is routing for pedestrians and how it’s still pretty bad in many situations. For example, if I’d be looking for a route from the northern to the southern side of the square in the previous screenshot, the suggestions would look something like this:

Pedestrian routing in Google Maps

Pedestrian routing in Google Maps

… Great! Google wants me to walk around it …

Pedestrian routing on openstreetmap.org

Pedestrian routing on openstreetmap.org

… Openstreetmap too – but on the other side :P

Wouldn’t it be nice if we could just cross the square? There’s no reason not to. The routing graphs of OSM and Google just don’t contain a connection. Polygon datasets like the FMZK could be a solution to the issue of routing pedestrians over squares. Here’s my first attempt using GRASS r.walk:

Routing with GRASS r.walk

Routing with GRASS r.walk (Green areas are walk-friendly, yellow/orange areas are harder to cross, and red buildings are basically impassable.)

… The route crosses the square – like any sane pedestrian would.

The key steps are:

  1. Assigning pedestrian costs to different polygon classes
  2. Rasterizing the polygons
  3. Computing a cost raster for moving using r.walk
  4. Computing the route using r.drain

I’ve been using GRASS 7 for this example. GRASS 7 is not yet compatible with QGIS but it would certainly be great to have access to this functionality from within QGIS. You can help make this happen by supporting the crowdfunding initiative for the GRASS plugin update.

Correct turn restriction information is essential for the vehicle routing quality of any street network dataset – open or commercial. One of the challenges of this kind of information is that these restrictions are typically not directly visible on each map.

This post is inspired by a share on G+ which resurfaced in my notifications. In a post on the Mapbox blog, John Firebaugh presents the OSM iD editor which should make editing turn restrictions straight-forward: clicking on the source link turns the associated turn information visible. By clicking on the turn arrows, the user can easily toggle between allowed and forbidden.

iD, the web editor for OpenStreetMap, makes it even simpler to add turn restrictions to OpenStreetMap.

editing turn restrictions in iD, the web editor for OpenStreetMap. source: “Simple Editing for Turn Restrictions in OpenStreetMap” by John Firebaugh on June 06 2014

But the issue of identifying wrong turn restrictions remains. One approach to solving this issue is to compare restriction information in OSM with the information in a reference data set.

This is possible by comparing routes computed on OSM and the reference data using a method I presented at FOSS4G (video): a turn restriction basically is a forbidden combination of links. If we compute the route from the start link of the forbidden combination to the end link, we can check if the resulting route geometry violates the restriction or uses an appropriate detour:

read more about this method and results:

illustrative slide from my LBS2014 presentation on OSM vehicle routing quality – read more about this method and results for Vienna in our TGIS paper or the open pre-print version

It would be great to have an automated system comparing OSM and open government street network data to detect these differences. The quality of both data sets could benefit enormously by bundling their QA efforts. Unfortunately, the open government street network data sets I’m aware of don’t contain turn information.

%d bloggers like this: