[GIS] driving time to the nearest facility using pgrouting

distance matrixpgroutingpostgispostgresqlproximity

I'm using pgrouting 2.0 and postgis in postgresql.
My problem is to calculate the driving time to the closest facility for each node of my OSM derived network.
These are the steps to be implemented (if I'm not mistaken..):
1. Find the closest node of the network for each facility (let't call them "nodes_fac");
2. Calculate iteratively the driving distance to all nodes (or within a given distance) from each of the previous nodes_fac writing the results in a table;
3. Filter the results using the minimum operator to select the driving time to the closest facility (the result should be a table including the nodes geometries with the minimum values);

Step 1: I think that this code can work (posts is the table of facilities):

SELECT posts.id AS post_id, 
  (SELECT nodes.id AS node_id 
   FROM  ways_vertices_pgr as nodes
   ORDER BY posts.geom <#> nodes.the_geom LIMIT 1)
FROM post_offices as posts
ORDER BY post_id;

Step 2: The following code could be used, but I don't know how to loop it to produce a table with the driving distance for each node_fac:

SELECT ways_vertices_pgr.id,
    ways_vertices_pgr.the_geom,
    basin.cost
   FROM ways_vertices_pgr
     JOIN ( SELECT pgr_drivingdistance.id1,
            pgr_drivingdistance.cost
           FROM pgr_drivingdistance('
      SELECT gid AS id,
          source::integer,
          target::integer,
          avg_cost_min::double precision AS cost
          FROM ways'::text, 22938, 10::double precision, false, false)) basin ON ways_vertices_pgr.id = basin.id1;

avg_cost_min is a calculated column with the driving time for each network segment, 22938 is one of the node_fac, 10 is the maximum driving time.

Best Answer

Here is my solution (it can be improved for sure!). I wrote this function:

RETURNS TABLE(node integer, cost double precision) AS
$BODY$
DECLARE
    node integer;
BEGIN
FOR node IN SELECT DISTINCT (temp.node_id) FROM temp 
-- WHERE node_id = 6626 (temporary filter to speed up testing)
LOOP
RETURN QUERY EXECUTE
'SELECT pgr_drivingdistance.id1, pgr_drivingdistance.cost AS cost
 FROM pgr_drivingdistance(''
      SELECT gid AS id,
          source::integer,
          target::integer,
          avg_cost_min::double precision AS cost
      FROM ways'',
      ' || node || ' ,
      60,
      false,
      false)';
END LOOP;
RETURN;
END;
$BODY$

and this script to be run for minimum driving distance calculation:

-- create table (temp) with closest network node to points included in facilities table (facs)
DROP TABLE IF EXISTS temp;
CREATE temp TABLE temp AS (SELECT facs.id AS fac_id, 
  (SELECT nodes.id AS node_id 
   FROM  ways_vertices_pgr as nodes
   ORDER BY facs.geom <#> nodes.the_geom LIMIT 1)
FROM facs
-- WHERE fac_type = --use this line as filter on facility types
ORDER BY fac_id)
;
-- use isochrones_fac function to calculate driving time from nodes in temp table
-- aggregate by node returning minimum value and join geometry from the node table

CREATE TABLE posts_mincost -- modify output table name
AS (SELECT output.id,
    output.min_cost,
    vertices.the_geom
   FROM (SELECT isochrones_fac.node AS id,
            min(isochrones_fac.cost) AS min_cost
           FROM isochrones_fac() isochrones_fac(node, cost)
          GROUP BY isochrones_fac.node
          ORDER BY isochrones_fac.node) output,
    nodes_gbe AS vertices
  WHERE output.id = vertices.id);

It seems working good (about 15 seconds for 100 facilities, 58000 nodes, max 60 min of driving distance). I'm quite happy considering my sql programming level!! ;)

This is a snapshot of an output of a spline interpolation:

Any further suggestion is welcome,of course!!

Related Solutions

[GIS] Nearest facility with pgRouting

Firstly few questions:
1. what do you mean by converting roads to nodes? Maybe you meant network graph?
2. Are you able to find at least one way and the trouble is with many ways?
3. Nearest school euclidean or by the roads?
4. What was the work-flow of this conversion form roads to nodes?
5. What are the names of tables and column names in this tables?
6. How big are your tables with students and schools?
7. Is it OK to select nearest school euclidean

Please add information to your question so maybe there will be simplest to help you.

But back to the point:

PG_Routing is not a resolution out of the box since it provides a kind of 'low level' stored procedures. You can't write query like 'select pg_CountMeTheWay(student, scholl), but it can find shortest way if you'll give it source edge id, target edge id and set of edges as graph with cost.

Also function st_DrivingDistance is not finding route, but it's creating set of edges reachable in specified time (e.g. how far you can go in 15 minutes).

Also 2 you need distance from student to nearest school but which is nearest if you don't know the distance? Do you have some kind of relation between schools and students? If not you have to count distance from one student to every school to know which is nearest. In most cases nearest euclidean (in straight line) will be also nearest by the roads, but if you have some special cases in your graph such as river with one bridge you cant be sure.

There are many resolutions of your problem even without this questions to your question, so please try to be more specific.

EDIT

Ok, so hope you have a lot of time :)

Firstly - to know the driving distance you have to (one way or another) find shortest path - there is no smoke without fire...
1. Driving distance is not doing anything different then this, but under another conditions. It's like space-time in military meaning - you have to dig ditch from here to everywhere till 4:00pm.
2. Also as far as I know driving_distance is working like window functions (e.g. row_number() over()) so it's designating cost during calculations, so you can't make him to do calculations for all edges, but designate cost only to few. Of course you can do select from select but this means that distance to every edge will be calculated anyway.
3. pgr_Driving_distance is much more slower then pgr_dijkstra - finding one route between points spaced about 15km is taking on my dataset (all Poland) about 1s (0,5-2,5), driving distance with the same condition will be about 15s

Basing upon this times counting:
1. Shortest paths between all students and scholls (100000x50x2) will last 115 days
2. Shortest paths between all students and scholls with minimal time will last about 46 days
3. Mixed version - Shortest paths between all students and 10 euclidean nearest to them scholls will last about 10 days
4. driving_distance for all students till 15km will last 17 days
5. Short version - Shortest paths between all students and 1 euclidean nearest to them scholl will last about 1 day.
6. Performance depends on numer of rows in edges table (network graph) so less records less time you'll need.

Possible resolution (1):

Write stored procedure with your pgr_djikstra() with id_source, id_target as input and cost as output (there are many exapmples on network)
create table with id_student, id_source, id_school, id_target, cost
Fill it with Id's and nearest edges of network graph
update it with cost of shortest path using your function
select for every student record with the lowest cost

Possible resolution (2):

Write stored procedure with driving_distance with source_id as input and retorn output of driving_distance
Write stored procedure with geometry as input and nearest edge id as output.
create tables with students and their nearest edges using above procedure, the same for schools
create table a as select *, your_proc(nearest_edge_id) as dist from students_nearest.
create another table b as select * from a where exists id of nearest student and school id
Select from this table records with student_id, school_id, min(cost) group by student_id, school_id

IMO the best resolution as compromise of time and quality is to find 3 euclidean nearest schools for every student and count for them shortest paths, then choose one - the shortest. With some tuning and only absolutely necessary edges in network graph you can feet in few hours.

pgRouting – How to Get the Closest Point from a Table in PostGIS

I found this link: http://www.sqlexamples.info/SPAT/postgis_nearest_point.htm

based on which, I created the following function:

CREATE OR REPLACE FUNCTION get_nearest_node
(IN x_long double precision, IN y_lat double precision) -- input parameters
RETURNS TABLE -- structure of output
(
  node_id bigint ,
  dist integer -- distance to the nearest station
) AS $$

BEGIN

RETURN QUERY

  SELECT id as node_id,
     CAST
     (st_distance_sphere(the_geom, st_setsrid(st_makepoint(x_long,y_lat),4326)) AS INT)
     AS d
  FROM ways_vertices_pgr
  ORDER BY the_geom <-> st_setsrid(st_makepoint(x_long, y_lat), 4326)
  LIMIT 1;

  -- geometric operator <-> means "distance between"

END;
$$ LANGUAGE plpgsql;

This function gives me the node id & the distance

Best Answer

Related Solutions

[GIS] Nearest facility with pgRouting

pgRouting – How to Get the Closest Point from a Table in PostGIS

Related Question