[GIS] Calculating shortest paths from all points in one layer to any points in another via road layer in QGIS

closest-facilityNetworkqgis

I'm trying to calculate the shortest paths from all the points in a layer representing population settlements (the green points) to any of the points in another layer representing the hospitals (orange points), going through the roads in blue.

enter image description here

The idea is to see where are the gaps in terms of public service delivery (here for health facilities).
I've tried using GRASS, converted all the vector layers into graph vertexes and connected my points to the road network using the "v.net" tool but couldn't manage to go further with GRASS tools.

Having checked a number of other subjects on StackExchange, it seems to me I could be using pgRouting or Dijkstra’s algorithm, but it seems to me that those two tools only allow to find the shortest paths to definite destination. As I'm just beginning on QGIS – or Python for that matter – I could be mistaken, but I don't want to waste too much time learning a tool that wouldn't do the job in the end.

A closest facility tool apparently exists in ArcGIS, so I guess I would need something equivalent in QGIS.

Could you please guide me to the best tools to do this?

Best Answer

After these comments:

Looking at pgRouting tutorials, I thought the pgr_createTopology was enough to create source and target locations. I'm not sure to understand how to verify that the source and target locations have equivalent locations that are located on the network edges

I think my problem was that all of the crossroads where not mapped as nodes, so I used the v.split tool in GRASS to update my network, and the pgr_dijkstra request works now. Now do you know how I could assign to all of the points in my layers there corresponding number as "source" or "target" in my road network?

So after splitting your intersecting lines so that intersections are now points in your graph, the only remaining preparation task is to map your source and target points of interest to their nearest nodes in the graph so they can be routed between. The pgRouting docs have a useful but somewhat advanced example here, including this snippet of a plpgsql function:

-- Find nearest node
EXECUTE 'SELECT id::integer FROM ways_vertices_pgr 
ORDER BY the_geom <-> ST_GeometryFromText(''POINT(' 
|| x1 || ' ' || y1 || ')'',4326) LIMIT 1' INTO rec;
source := rec.id;

Then there is this example plpgsql function:

CREATE OR REPLACE FUNCTION get_nearest_station
(IN x_long double precision, IN y_lat double precision) -- input parameters
RETURNS TABLE -- structure of output
(
  station_id integer,
  city_name character varying,
  station_name character varying,
  dist integer -- distance to the nearest station
) AS $$

BEGIN

RETURN QUERY

  SELECT id, city, station,
     CAST
     (st_distance_sphere(geom, st_setsrid(st_makepoint(x_long,y_lat),4326)) AS INT)
     AS d
  FROM stations
  ORDER BY geom <-> st_setsrid(st_makepoint(x_long, y_lat), 4326)
  LIMIT 1;

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

END;
$$ LANGUAGE plpgsql;

The key part is the ORDER BY geom <-> st_setsrid(st_makepoint(x_long, y_lat), 4326) LIMIT 1, a pattern that is in both solutions.

You can use this with the following query (but you will have to adjust the above function slightly to match your schema):

SELECT get_nearest_station(ST_X(geom), ST_Y(geom)) FROM table;

Finally, you can also work with ST_ClosestPoint between two point layers.

Related Question