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

For those who does not still know it, OpenStreetMap is a collaborative mapping project under a free license. The primary goal was to map the streets of the world, but it now goes far beyond that. The OpenStreetMap database contains a network of roads annotated with attributes such as name, type (“street”, “motorway”…) or speed limits. Unlike other map data “providers”, modifications are made available immediately: no prior validation and continuous broadcast of modifications.

Route calculation

A route planner is a software program that will use a road network (graph) to determine the most appropriate route. This path is rarely the shortest in distance. For example by car, you want to use the fastest route and in fact use longer but faster roads, as well as respecting constraints such as one-ways. We will therefore try to calculate the route with the lowest “cost”. Each segment of the graph has a cost associated with it. It is calculated according to the length and attributes such as the type of way, but this can include for example the fact that you have to climb when the calculation is made for bicycles.

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

The OpenStreetMap ecosystem contains several software dedicated to this task. They are optimized to reduce the time to calculate a point-to-point route, this is the nominal use case. The corollary of this speed of execution is the pre-calculation, which is time-consuming and reduces the flexibility of the possible calculation on requests. As these solutions are only able to process OpenStreetMap data, they provide “profiles”. These profiles describe which OpenStreetMap data should be selected among the available data and how to calculate the “cost” of each segment.

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

In addition to these specialized software, other solutions using generic data sources exist. The most common is pgRouting. Because of its genericity, it does not come with a data importer, profiles or cost functions, or even with its own storage system. pgRouting is a module for the Postgres database. It is necessary to import at first step the data in the database, then to prepare the graph. On request, we must provide the graph with the cost of the segments to pgRouting, then it does the calculation.

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

Several tools exist to read an OpenStreetMap extract file (.pbf), filter and import into a database and then apply post-processing. They can also import update files that are available every minute or daily.

• osmosis
• osm2pgrouting
• imposm

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

The osm2pgRouting solution is an OpenStreetMap data importer for pgRouting. It reads the old XML data format and understands the OpenStreetMap data ontology. However, it does not contain a data interpretation profile for segment cost.

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

We would like to be able to do short distance route calculations on an OpenStreetMap road network over large areas. The data must be kept up to date very regularly so that if the result of a route calculation is not satisfactory, the data can be corrected in OpenStreetMap and the correction in the route planner can be used almost immediately (maximum delay of 1 minute).

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

Imposm is the latest tool to read data from OpenStreetMap and import it into a database. As osm2pgsql it is oriented for map production but can be used for other tasks.

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

Then it is required to convert this set of polygonal paths into segments. There is a difference in topology between the imported data and the data needed for route calculations. For calculations we need segments from one intersection to the next. However, the polygonal paths in OpenStreetMap do not impose this structure. A polygonal path can pass through an intersection without ending there and can also end between two intersections.

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

Imposm allows you to wait for OpenStreetMap data updates and apply them when they are available. It will download and apply to the database according to the mapping defined during the import. Modifications are made on the OpenStreetMap polygonal paths table. It is necessary to report them on the graph segments.

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

Then it is possible to use the loaded and continuously updated graph to calculate routes using only conventionally pgRouting usage.

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 new approach described here is implemented in the “ImpOsm2pgRouting” project. It is intended as an alternative to load large volumes of OpenStreetMap data into a database and use them with pgRouting while keeping the database up to date from OpenStreetMap. This synchronization can be done with a maximum delay of one minute and thus allow to correct the road in OpenStreetMap and to benefit from it almost immediately for the route calculation.

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.