TransWikia.com

How to limit the search for facilities to only 1 unit with PG Routing? ... Closest Facility in PostGIS?

Geographic Information Systems Asked by isidrop on April 25, 2021

I’m working in PGROUTING – POSTGIS
I have my road network and two sets of points -firestation and the entire cityblocks from town (in diferent tables, 1 for origin, and 1 for destination).

The plan is to calculate the optimal routes from the fire station to the blocks. Later it would filter for maximum time. I have already achieved this first point just explained using algorithm pgr_dijkstra (many-to-many).

DO 
$$DECLARE 
mzn_o integer[] = (SELECT ARRAY (select origen from origin_table));
mzn_d integer[] = (SELECT ARRAY (select destino from destination_table));

BEGIN
create table my_routes_table as
SELECT seq::integer, path_seq::integer, start_vid::integer, end_vid::integer, concat(start_vid::integer, end_vid::integer) as id, node::integer,edge::integer, a.cost::double precision, agg_cost::double precision, b.class_id::integer, b.the_geomx::geometry 
    FROM pgr_dijkstra(
    'SELECT id, source, target, traveltime as cost, traveltime_rev as reverse_cost FROM my_network_table', mzn_o, mzn_d1,directed := false) a left join my_network_table b on a.edge=b.id;
END$$;

I would like to improve this operation, because in the above code you get all possible routes from all sources to all destinations. I would like that when a block finds its nearest fire station, it stops searching. In other words, each station is assigned only the closest station and not all of them. In this way, achieve a higher calculation performance and with less cost, since the combinations would be significantly limited. That’s the idea, something similar or identical to what is achieved with the Network Analyst Closest Facility tool in ArcMap, where it seems that you can enter the maximum number of facilities to calculate the route.https://desktop.arcgis.com/en/arcmap/latest/extensions/network-analyst/closest-facility.htm

Maybe a picture for understanding:

enter image description here

My purpose is not to insert a filter after main operation, but to integrate that idea so that it results in an improvement in the performance of the operation that causes a considerable decrease in the amount of operation and can work with large networks and improve the capacity of the computer.

I think I have already tried everything within my reach and my technical level, and my eyes are bleeding from looking at possibilities on the internet. In Postgis or PG Routing I have not been able to find anything related to Closest Facilities (if to calculate with service area and pgr_drivingtime algorithm), something that limited the calculation to find only the closest route.
I thought that with the pgr_astar algorithm it could be achieved since its concept is to find the best route and reduce possibilities but it also returns the same as with Dijkstra in my tests. I have also tried to make a cost matrix and try filtering with the minimum cost min (cost), I thought that this way I would filter out the final nodes not needed, as explained in this example https://www.qgistutorials.com/en/docs/3/origin_destination_matrix.html. But it’s not working for me.

SELECT * FROM pgr_dijkstraCost(
    'select id, source, target, cost from my_network_table',
    (SELECT ARRAY (select source from origin_table)), (SELECT ARRAY (select target from destination_table)));

select source, min(cost) as shortest_path from costs_table group by source; 

One Answer

Well, finally I found a solution, more than a week ago, that works fine for me.. So, I want to share it, if someone else has encountered the same problem. I'm aplying this to cities from Chile...also a big city like Santiago with more than 300k geometry rows in its ways table (OSM), and working for more than 40k destinations and 300 origins. You can imagine all the combinations that can be given. I work in a powerful PC with 32G RAM, and it takes 9-10 hours. The code can be improve for sure.

--- create a cost matrix

DO 
$$DECLARE 

o integer[] = (SELECT ARRAY (select id_origin from mytable_origins));
d integer[] = (SELECT ARRAY (select id_destination from mytable_destinations));

BEGIN
  create table mytable_costmatrix AS
    SELECT start_vid::integer as init, end_vid::integer as final, agg_cost::integer  FROM 
    pgr_dijkstracost(
        'SELECT id, source, target, cost, reverse_cost FROM mytable_ways',
        o, d, directed := false);

END$$;


--- filter costmatrix and keed for us the shortest path from each destination

create table mytable_filtermatrix as
   select a.init, b.final, b.shortest_path from mytable_costmatrix a, 
        (select final, min(agg_cost) as shortest_path from mytable_costmatrix group by 
        final) as b 
        where a.agg_cost=b.shortest_path and a.final=b.final order by init asc;



 --- Creation of routes through a 'FOR' loop with DIJKSTRA algorithm 'one to one' to iterate over the matrix 
--- table with the route start and end IDs, and thus ensure the calculation of only the route closest to the CLOSEST FACILITY

DO 
$$DECLARE 
row record;

BEGIN 

    CREATE TABLE mytable_routing(
        seq integer, 
        path_seq integer, 
        start_vid integer,
        end_vid integer,
        id varchar,
        node integer,
        edge integer, 
        cost double precision,
        agg_cost double precision,
        class_id integer,
        the_geom geometry
    );

    FOR row IN
        SELECT init, final from mytable_filtermatrix 

    LOOP
        insert into mytable_routing(seq, path_seq, start_vid, end_vid, id, node, edge, 
            cost, agg_cost, class_id, the_geom)
            SELECT seq::integer, path_seq::integer, row.init::integer as start_vid, 
            row.final::integer as end_vid, concat(row.init::integer, row.final::integer) 
            as id,
            node::integer,edge::integer, a.cost::double precision, a.agg_cost::double 
            precision, b.class_id::integer, b.the_geom::geometry 
            FROM pgr_dijkstra(
            'SELECT id, source, target, cost, reverse_cost FROM mytable_ways',
            row.init, row.final,directed := false) a left join mytable_ways b on 
            a.edge=b.id;

        RAISE NOTICE  'Running at % source id',row.init;
        END LOOP;
END$$;

----END

And map result:

enter image description here

Greetings!

Answered by isidrop on April 25, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP