pgRouting

pgRouting extends the PostGIS / PostgreSQL geospatial database to provide routing and other network analysis functionality.

What you need

• PostgreSQL database

• PostGIS spatial extension

• pgAdmin4 (or any other database explorer)

• QGIS (optional – see note below)

Introduction to graph data and routing

A graph data structure is made up of nodes and edges. With OS MRN, these are represented by the mrn_ntwk_transportnode and mrn_ntwk_transportlink layers.

Nodes are points that represent junctions connecting one or more paths on a network. This is where a decision is made on where to turn next (or stop if you are at the end of the route). All nodes must connect to an edge.

Edges connect two or more nodes, and represent the distance between them. They can be directed (for example, one-way restrictions) or undirected (any direction allowed). Their default direction will be in the direction the edge was digitised, from startpoint to endpoint.

The distance is a reflection of the cost to travel along that edge. At the base level, this would be the length of the edge (in metres), but can be extended with maths to incorporate things like the speed of travel along the edge.

Using other data you may have, cost can be extended even further, for example, to take into account factors that might make a traveller use a particular route more (such as scenery, traffic, points of interest and gradient).

With pgRouting, these costs can be applied to each edge in a particular direction, that is, in direction (the direction of digitising) and in reverse direction. This enables the user to have more control on what the routing algorithms look for.

Routing algorithms

Routing algorithms are a set of rules used to determine the best path between two or more points. Some of the common ones used are:

• pgr_dijkstra – The classic shortest path algorithm, from one node to another, using a directed or non-directed graph.

• pgr_drivingdistance – Using Dijkstra, finds all nodes that are reachable within a set distance using a directed or non-directed graph. Produces results that can then be visualised as an isochrone polygon.

• pgr_trsp (turn restriction shortest path) – Runs similar to Dijkstra, with the addition of using restriction information. With OS MRN, this restriction data is available in the mrn_ntwk_turnrestriction layer. These turn restrictions reference the edges from the network layer and are used as a lookup as the algorithm works.

Checking that PostGIS and pgRouting are enabled

In more recent versions of PostgreSQL, both PostGIS and pgRouting are enabled as standard, ready to be used.

To check this:

1. Load pgAdmin4 (or your chosen database explorer).

2. Highlight your database.

3. Open a SQL window and run:

CREATE EXTENSION postgis;

ERROR: extension "postgis" already exists
SQL state: 42710

In the example above, PostGIS was already enabled. However, in the example below, pgRouting wasn't enabled, but is now ready to be used within the selected database:

CREATE EXTENSION pgrouting;

Query returned successfully in 151 msec.

Loading the GeoPackage

The easiest way to load the GeoPackage (GPKG) into PostgreSQL via ogr2ogr is to use the OSGeo4W Shell that is provided with the QGIS install package:

1. Before loading the GPKG, check that environment variables have been set up so that PostgreSQL will be recognised by the command prompt. Admin permissions are required to edit these variables.

2. Add the folder location of your PostgreSQL install to the User->Path and System->Path variables.

3. Once you have done this, open the OSGeo4W Shell (as shown above), and type in ogr2ogr. If everything is setup correctly, you should see:

1. To then load the OS MRN GPKG into your PostgreSQL database, navigate to the location of the file, and type the following:

ogr2ogr -f PostgreSQL -progress -gt 65000 -a_srs EPSG:4326 -lco SCHEMA=<schema> -lco GEOMETRY_NAME=geometry PG:"dbname=<dbname> host=<host> port=<port> user=<user> password=<password>" OSMulti-modalRoutingNetwork.gpkg

You could alternatively use the following command (where /vsizip/ is a file handler that allows reading ZIP archives on-the-fly without decompressing them beforehand):

ogr2ogr -f PostgreSQL -progress -gt 65000 -a_srs EPSG:4326 -lco SCHEMA=<schema> -lco GEOMETRY_NAME=geometry PG:"dbname=<dbname> host=<host> port=<port> user=<user> password=<password>" /vsizip/OSMulti-modalRoutingNetwork.zip/OSMulti-modalRoutingNetwork.gpkg

This will load the three layers of the OS MRN GPKG into the defined database schema, and create the relevant spatial indexes.

1. You can now add some further attribute indexes for the unique identifiers:

CREATE INDEX mrn_ntwk_turnrestriction_wayid_idx ON <schema>.mrn_ntwk_transportlink USING btree (wayid);
CREATE INDEX mrn_ntwk_turnrestriction_nodeid_idx ON <schema>.mrn_ntwk_transportnode USING btree (nodeid);
CREATE INDEX mrn_ntwk_turnrestriction_relationid_idx ON <schema>.mrn_ntwk_turnrestriction USING btree (relationid);

1. With all the indexes added, you can create a basic edge table on which to start routing:

CREATE TABLE <schema>.edge_table AS
SELECT
  wayid AS id,
  name,
  foot,
  highway,
  railway,
  rail,
  ferry,
  toll,
  junction,
  route,
  ford,
  bridge,
  tunnel,
  service,
  oneway,
  ST_Length(geometry::geography) AS length,
  (STRING_TO_ARRAY(nodes, ',')::int[])[1] AS source, -- converts the nodes string to an array and extracts the first index item
  (STRING_TO_ARRAY(nodes, ',')::int[])[array_upper((STRING_TO_ARRAY(nodes, ',')::int[]), 1)] AS target, -- converts the nodes string to an array and extracts the last index item
  CASE
    WHEN oneway = '-1' THEN -1
    ELSE ST_Length(geometry::geography) -- returns the geometry length in metres
  END AS cost,
  CASE
    WHEN oneway = 'yes' THEN -1
    ELSE ST_Length(geometry::geography) -- returns the geometry length in metres
  END AS reverse_cost,
  geometry
FROM <schema>.mrn_ntwk_transportlink;

CREATE UNIQUE INDEX edge_table_id_idx ON <schema>.edge_table (id);
CREATE INDEX edge_table_source_idx ON <schema>.edge_table (source);
CREATE INDEX edge_table_target_idx ON <schema>.edge_table (target);

CREATE INDEX edge_table_geometry_idx
  ON <schema>.edge_table
  USING gist
  (geometry);

Loading the Protocolbuffer Binary Format

osm2po is a cross platform tool written in Java that can be used to parse OS MRN PBF data and make it routable in pgRouting.

1. To find out if you have Java installed, open PowerShell / Command Prompt (Windows) or Shell (Linux) and type:

java -version

1. Press Enter. If Java is installed, you should see a few lines of text detailing which version you have installed. If you get something along the lines of "java is not recognized ...", please download JVM [or OpenJDK] from https://adoptium.net/en-GB/.

2. Once osm2po is downloaded and extracted, open and edit the config file to satisfy your usage requirements (for example, change the wtr.finalMask = car line (use Ctrl+F to search the file) to car,foot,bike travel types).

3. Uncomment the following line (this helps with getting the topology into a format pgRouting likes):

postp.0.class = de.cm.osm2po.plugins.postp.PgRoutingWriter

1. When this is done, and assuming Java is installed and accessible, open a command prompt and navigate to the location of the .pbf file, and then run the following:

java -jar osm2po-core-5.5.11-signed.jar cmd=c prefix=osm2po OSMulti-modalRoutingNetwork.pbf

This will create the .sql file version of the .pbf file.

1. Import the .sql file version of the .pbf file to the PostgreSQL database using the following:

psql -h <host name> -U <username> -d <database name> -q -f <filename>.sql

In this newly created table, each record should have a source and target node, and an integer classification. Cost and reverse cost columns are also applied. Cost in this case is worked out using distance (in km) and speed (kmh) defined in the config file.

Running a test route with pgRouting (Dijkstra)

The mandatory things pgRouting needs to be able to route with are a routing table, start node and end node. Once the routing table is created, pgRouting can be run straight away.

For the following example, OS MRN sample data has been used, with the GPKG data being loaded into PostgreSQL via ogr2ogr (with the SQL run to create basic edge table). A couple of waypoints have been selected in Exeter, and a sample Dijkstra route query can look like the one below:

WITH start AS (
  SELECT source
    FROM <schema>.edge_table
    ORDER BY geometry <-> ST_SetSRID(
      ST_GeomFromText('POINT (-3.53532 50.72046)'), 4326)
    LIMIT 1
),
destination AS (
  SELECT source
    FROM <schema>.edge_table
    ORDER BY geometry <-> ST_SetSRID(
      ST_GeomFromText('POINT (-3.52133 50.72294)'), 4326)
    LIMIT 1
)
SELECT ST_Union(geometry) AS route
  FROM pgr_dijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM <schema>.edge_table',
    ARRAY(SELECT source FROM start),
    ARRAY(SELECT source FROM destination)
  ) AS di
  JOIN <schema>.edge_table AS pt
  ON di.edge = pt.id;

This route query is made up of three parts:

• First, the 'start' section finds the start node to use from the network that is closest to the point given. This could be fed in to the query in multiple ways, such as clicking on a web map, or using a plugin.

• Second, the 'destination' section finds the start node closest to the destination point given.

• The final part includes the pgr_dijkstra function, reading in the start and destination ids, and returns a merged geometry of links that form the route.

When visualised in QGIS, the result should look similar to this:

It should be noted that the above route query does not take any of the additional OS MRN attribution into account. This means that every edge will be considered when calculating the shortest path. We can therefore apply some additional logic in the SELECT statement to facilitate either vehicular or pedestrian routing:

• Vehicular routing – Determines the best vehicular route where the edges are deemed to be roads.

'SELECT id, source, target, cost, reverse_cost
  FROM <schema>.edge_table
  WHERE "rail" = ''no''
    AND "highway" IN (
      ''motorway'',
      ''motorway_link'',
      ''trunk'',
      ''trunk_link'',
      ''primary'',
      ''primary_link'',
      ''secondary'',
      ''secondary_link'',
      ''tertiary'',
      ''tertiary_link'',
      ''unclassified'',
      ''residential''
    )'

• Pedestrian routing – Determines where the edges can be traversed by foot and whether there is designated infrastructure for walking.

'SELECT id, source, target, cost, reverse_cost
  FROM <schema>.edge_table
  WHERE "foot" != ''no''
    AND "rail" = ''no''
    AND "highway" IS NOT NULL'