ImpOsm2pgRouting: Route planning on OpenStreetMap road network with the benefit of updates

Approach for importing and maintaining an up-to-date road graph of OpenStreetMap data and using it to calculate routes with pgRouting.

This article is an English translation of my own French article from Makina Corpus Blog.

Constantin Litvak, CC By Sa

OpenStreetMap

Route calculation

Among the recurring main functionalities there is also the matrix calculation. This is a “distance calculator” (in cost units) that can give for example the travel time between a set of cities.

Route planners with OpenStreetMap

Some of these software are designed to respond quickly even on large scale requests:

  • OSRM: implementing the Dijkstra Multi-Level (MLD) and Contraction of Hierarchy (CH) algorithms,
  • Graphhopper implementing the Dijkstra and Contraction of Hierarchy (CH) algorithms,
  • Valhala: implementing the Dijkstra Multi-Level (MLD) algorithm.

In fact, it is not the Dijkstra algorithm that is really implemented, but improvements, typically a bidirectional A-star.

Generic route planner

With the exception of importing the data and putting it into a routable network, pgRouting does not use pre-calculation. The preparation time is brief but the time to calculate a route is therefore longer. Consequently the calculations use simple algorithms derived from Dijkstra. This approach allows much more flexibility: the cost function as well as the graph to be routed can be dynamic according to the request (“I want to take moderate slopes by bike with my trailer, but I do not want to go through the city centre”).

Import OpenStreetMap data for pgRouting

Generic OpenStreetMap data importers

The database schema depends on the tool and the configuration. But in all cases these generic tools do not directly import a road network ready to use in pgRouting.

pgRouting requires as input for its calculation a list of segments described by a start identifier, an arrival identifier and the cost of crossing the segment. The calculation goes from segment to segment using the arrival identifier of a segment as the departure identifier of potential next segments. pgRouting does not require the geometry.

The next logical step after import is to build the graph of segments from the imported OpenStreetMap data.

osm2pgRouting

This solution is softly maintained and in particular does not have the ability to use the new OpenStreetMap extract binary file format (.pbf), nor able to load large volumes of data and finally it does not allow updates from OpenStreetMap.

Set up a generic importer and create the graph of segments

To achieve this goal it is necessary to use pgRouting, as it does not require a pre-calculation step. It will also be necessary to make quick updates from OpenStreetMap data with a generic data importer. Because of the use of a generic data importer, we will also have to create the segment graph ourselves.

Import with Imposm

OpenStreetMap data consists of nodes, points, ways, relationships (object groups) described by free attributes (tags). We are interested here in a road network that is made up of ways annotated with certain tags (the road is described by ways with key tags highway). We will use an Imposm mapping file to describe the OpenStreetMap data to import.

tables:
ways:
type: linestring
mapping:
highway: [__any__]
columns:
- name: osm_id
type: id
- name: geometry
type: geometry
- name: tags
type: hstore_tags

Configure of Imposm to load the linestring with tags highway=* into a table (ways automatically prefixed by osm, so osm_ways) containing the OpenStreetMap identifier, geometry and the set of tags.

Create a navigable network

Topology of the data in OpenStreetMap and after cutting at intersections.

So the first step is to extract all the intersections. These are not the geometric intersections of polygonal paths, but the intersections in the topological meaning of the OpenStreetMap road network. That is, when polygonal paths are explicitly connected to each other by a node. These intersections are numbered and are called “vertices” of the graph. In particular, we does not want to be able to jump from a bridge to a way passing below vertically at the point where they intersect spatially.

SELECT
(ST_DumpPoints(geometry)).geom AS point
FROM
import.osm_ways
GROUP BY
point
HAVING
count(*) >= 2

Collecting intersections.

The second step is to cut the OpenStreetMap polygonal paths along these same intersections. We do not use the ST_Segmentize() function of PostGIS for this purpose, because it cut using a length. The appropriate function for our case is ST_Split() which cuts one geometry by another.

SELECT
osm_id,
(ST_Dump(ST_Split(
geometry,
ST_Collect(osm_ways_junctions.point))
)).geom AS geometry,
tags
FROM
import.osm_ways
JOIN imposm2pgr.osm_ways_junctions ON
osm_ways_junctions.point && osm_ways.geometry
GROUP BY
osm_id,
geometry,
tags

Cutting of polygonal paths on topological intersections that spatially intersect its geometry.

The ends of each segment must then be reconciliated to the intersection numbers.

For each segment, all that remains is to gather the elements as the network on which we wishes to calculate routes. This means store it, and extract the desired OpenStreetMap tags and optionally calculate the cost to cross the segment (if the cost is not on request).

To do this we can use the following database table definition.

CREATE TABLE network (
id serial PRIMARY KEY,
osm_id bigint NOT NULL, -- required field, for update
source_vertex_id int, --required field, for routing
target_vertex_id int, -- required field, for routing
geometry geometry(LineString,3857) NOT NULL, -- Advised, for display
cost float,
highway varchar,
name varchar
)

For example, if you want to make a shortest route planner, the cost may simply be the length of the segment: ST_Length(geometry). The road name will be extracted from the OpenStreetMap tags if it is available with tags->'name' (using the syntax of the Postgres hstore extension).

Update

To do this, a database trigger collects the modifications made on the polygonal paths table by Imposm. At the end of the transaction, it deletes all the impacted segments and recalculates a new version of them by going through the steps of extracting the intersections and cutting into segments. This update procedure is minimal in the sense that it only modifies the segments of the graph that have actually been modified in OpenStreetMap and is therefore fast.

Compute a route with pgRouting

SELECT
ST_Collect(network.geometry) AS geometry,
sum(path.cost) AS total_cost
FROM
pgr_dijkstra('SELECT * FROM selected_network', 1480, 1503, true) AS path
JOIN network ON
network.id = path.edge

Calculating the geometry of a route.

Visualizing the route on the graph.

ImpOsm2pgRouting

This project allows you to load and keep the data up to date. It does not force how the network graph should be stored, nor how it should be used. This remains the responsibility of the user.

It can be used as an external tool to manage the network data on a new or existing project, for example by using it as a Docker container.

https://github.com/makinacorpus/ImpOsm2pgRouting

The project is available on Github and open for contribution.

OpenStreetMap contributor, Osmose-QA maintainer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store