Route Planning with OpenStreetMap

last updated 2018-01-22

This blog post gives an overview of how to perform route planning :running: :bike: :car: with OpenStreetMap (OSM) data. In beginning, some basics about route planning will be explained. Afterwards, the routing engines GraphHopper, pgRouting and the routing web service OpenRouteService will be described in more detail.

OpenStreetMap is perfectly suited for route planning applications because the data quality of the street network is usually very satisfying. This has two reasons: Streets can easily be mapped from satellite imagery and GPS-tracks. Moreover, errors can be discovered quickly because they cause unrealistic routing results.

Programs which can compute routes are called routing engines. All routing engines work similarly: they parse an OSM file, extract the streets and convert them into a local graph consisting of nodes (junctions) and edges (street segments). Every edge gets a weighting. Mostly this is the distance, but can also be travel duration or something else. Then algorithms like Dijkstra or A* find the shortest path by minimizing the sum of the weightings.

Adjusting the weighting of the edges makes it possible to create profiles for different means of transportations (vehicles) e.g. car, bike or pedestrian. First of all, every vehicle can only move on some types of streets. For example, a car can not move on a footpath and a pedestrian may not walk on a highway. Hence for each profile, a subset of all edges is excluded. Additionally, a vehicle dependent weighting is assigned to each edge e.g. a car takes less time for a specific street segment than a bike.

Edges can also have different weightings for each direction. In case of a hill, it obviously takes longer going up than going down. The weighting of the edges can be pretty much anything such as CO2 emission, the beauty of the landscape or noise. These examples would respectively return eco-friendly, beautiful or silent routes.

There are a couple of routing engines that can be hosted locally: GraphHopper, OSRM, Valhalla, pgRouting, OpenTripPlanner. There is a great presentation in German language by Frederick Ramm which gives a summary of most of the existing routing engines (video, slides). This post describes GraphHopper and pgRouting in more detail.

GraphHopper

GraphHopper is a Java library that also can be run as an independent program. It is relatively easy to install by following this quickstart guide. The default settings only compute the graph for cars. However more profiles and many other settings can be activated in the .properties-file. Once GraphHopper is running, it starts a local routing server on port 8989. It can be tested with a locally running web application similar to this one.

But routes can also be computed in an automated way by using a local API. The arguments are passed inside the URL like this example shows:

localhost:8989/route?
  point=53.525615%2C15.514755&
  point=53.540307%2C15.46875&
  vehicle=car&
  weighting=fastest&
  elevation=true

The description of the API can be found here. The response of the API is a JSON with the requested information. Requesting the API can be done with basically any programming language. There are already some prepared templates. It is also possible to edit existing profiles or to create new ones. However, this requires some time to get into it.

All in all, GraphHopper is a great tool for setting up a local routing server with little effort. It is built for handling a high load of requests, is super fast and has a user-friendly API. If you have enough RAM it is even possible to offer a routing service for the whole planet.

pgRouting

pgRouting has a different use case compared to GraphHopper. It is an extension of the PostgreSQL database and requires the PostGIS extension. This means that you should know some SQL. There is a great workshop that helps to get into pgRouting. The Linux distribution OSGeoLive already comes installed with pgRouting and some test data.

The philosophy behind pgRouting is that you have to set up everything by yourself. It comes with some basic functions for routing. pgRouting does not contain any vehicle profiles. This means that you have to know what you want and then you can build your own specialized routing application.

pgRouting also offers some advanced routing algorithms like isochrones. Loosely speaking isochrones return all nodes which are reachable within a specific cost limit. Isochrones help to answer questions like: Which supermarkets are within 25 min walking distance?

The underlying street network of pgRouting is stored in the Postgres database and can be changed dynamically. Consequently, the weighting for each edge (street segment) can be changed dynamically as well. This can be useful if you want to build a vehicle profile that is dependent on dynamic data like traffic or weather.

Example query (source) :

SELECT * FROM pgr_dijkstra(
    'SELECT gid AS id,
         source,
         target,
         length AS cost
        FROM ways',
    9411, -- source id
    3986, -- target id
    directed := false);

The query above shows a basic routing function. It uses the length of the street segments as cost, but this could be changed to anything else (noise of the street, CO2 emission, …). The result is a list of all traversed nodes and edges. This gives you the possibility to study every detail of the computed result. If you want to receive the geometry of the route you have to write an additional function that joins the geometry to the nodes.

The pgRouting workshop already provides some templates for useful functions. The QGIS plugin pgRoutingLayer offers a GUI (graphical user interface) for pgRouting. The settings for routes and isochrones can be chosen in a menu. The resulting geometries are displayed in QGIS and can be exported.

pgRouting works perfectly with OpenStreetMap data: osm2pgrouting is a dedicated command line program for importing OSM data. However it also possible to import any other spatial data source. This post describes how to import a shapefile. pgRouting is not limited to routing on roads, it can also be used for more exotic purposes like routing on railways or river networks.

All in all, pgRouting is a nice solution if you want to create a very specialized routing application. You can pretty much manipulate everything and study every detail of the result. The downside is that pgRouting is relatively slow (compared to GraphHopper) and is more challenging to set up. Typical use cases are street network analysis, visualizations or specialized routing services with not too many requests.

OpenRouteService

If you do not want to install anything you can use a public API by one of these routing providers: GraphHopper API, Mapbox or OpenRouteService. Some of them offer a free basic plan. However, for a higher amount of requests they require to pay.

OpenRouteService is operated by the University of Heidelberg and offers a lot of vehicle profiles. Additionally, it offers a free isochrone service. You can use OpenRouteService directly in the web browser via maps.openrouteservice.org, via the API or with the QGIS plugin ORStools (which also accesses the API). The plugin displays the results in QGIS and gives the possibility to further export the data.

Using a web service like OpenRouteService is comparably simple and has the advantage that the underlying street network is regularly updated by the providers. Hence your routing results are always based on the latest data. If you run your own routing service you have to update the street network by yourself. The disadvantage is that you are dependent on an internet connection and, unless you are paying for a plan, you cannot query a high load of routes.

Additional links

Some additional links to websites with related content:

• Topi Tjukanov did many routing projects with GraphHopper and pgRouting
• Anita Graser has some posts about routing - mostly with pgRouting
• Digital Geography has various post about routing
• the OSM-Wiki page about routing