PG routing – shortest path algorithms

Once a routable network has been set up we can start to find the shortest path (using Dijkstra’s algorithm) between two points. From here on, I will be using the OSM data for the London road network.

The query use’s a ‘cost’ column – which could be anything thing you like – to calculate the shortest cost from one node to another. In this example I decided to use travel time (rather than distance).

First, I changed the distance of each vertex (the way table) from km to miles, and then calculated the time it would take to traverse each vertex whether walking, cycling or driving. To make this more accurate, I updated the max speed (forward and backward) along each vertex dependent on its class (as listed in the class table).

 

 
alter table ways_osm add column len_miles double precision;

alter table ways_osm add column len_miles double precision, add column travel_time_cars double precision, add column travel_time_walking double precision, add column travel_time_cycling double precision;

update ways_osm set len_miles = length*0.6214;

update ways_osm set maxspeed_forward = case when class_id = 101 then 70 
      when class_id = 102 then 70
      when class_id = 103 then 70
      when class_id = 106 then 60
      when class_id = 107 then 60
      when class_id = 108 or class_id = 109 then 60
      when class_id = 110 or class_id = 11 then 30
      else 50 end;

update ways_osm set travel_time_cars = ((60/maxspeed_forward::double precision)*len_miles);

--average walking speed = 3m/h

update ways_osm set travel_time_walking = ((60/3::double precision)*len_miles);

--average cycling speed = 15 km/hr

update ways_osm set travel_time_cycling = ((60/9.32::double precision)*len_miles);

This should produce a ‘ways’ table similar to this:

Now we can run the following query to find the shortest distance between 2 nodes.

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
  FROM pgr_dijkstra(
    'SELECT gid as id, source, target, len_miles as cost FROM "ways_osm"',
   1924, 72515, false, false
  )

This produces a list of vertices, with the cost as ‘len miles’ for each, which tracks a route from node 1924 to 72515. To put this into qgis we need to join this to the ways table which contains the geom for each vertex.

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
  FROM pgr_dijkstra(
    'SELECT gid as id, source, target, len_miles as cost FROM "ways_osm"',
   1924, 72515, false, false
  ) as di
  JOIN "ways_osm" wy
  ON di.id2 = wy.gid;

Loaded into QGIS, we arrive at the following layer:

As we can see, this does not differ much from google maps:

 

Comparing the overall times and length for the route between osm, OS open roads and google maps highlights the accuracy of the pg routing algorithm:

NETWORKWALKING TIME (MINS)CYCLING TIME (MINS)LENGTH (MILES)
Google 485 145 24.3
OSM 480 153 23.8
OS open roads 486 156 24.3

A nice additional ability is to find the nodes nearest to a start and end point which you have the lat long coordinates for. To find these nodes use the following:

select source from "ways_osm" order by st_distance(the_geom, 
st_setsrid(st_makepoint(51.415996, -0.212311), 4326)) limit 1;

select target from "ways_osm" order by st_distance(the_geom, 
st_setsrid(st_makepoint(51.460254, -0.087616), 4326)) limit 1;

These can then be placed in the Djkstra query!

Groundwork - Geospatial & Data services

Groundwork GDS is part of Groundwork London

Visit us
18-21 Morley Street, London SE1 7QZ
Get in touch