Speed up pgr_dijkstraCost

Question

I have a pgRouting network graph of ~ 1 mio edges and ~ 0.4 mio vertices. I want to find out something like "nearest facility" for bigger subsets.

E.g. i have a bigger number of source vertices and a bigger number of target vertices. I need to know the cost (!) of the shortest path from every source vertex to the closest (lowest cost) target (and it's id). Nothing more. The graph itself won't be changed anymore.

At the moment I use pgr_dijkstraCost which takes ~ 0.05 s per source vertex. This is fast, but I need to run thee whole query (with up to 20.000 sources and up to 100 targets) within < 15 s.

Is it realistic to reach this goal just by optimizing the graph?

Answer 1

As you mentioned, your current response is quite fast already, but you could try to run all computations in one query with pgr_dijkstraCostMatrix if you need a full matrix, or recently the shortest path functions also allow so called "combinations" as input,for example https://docs.pgrouting.org/latest/en/pgr_dijkstraCost.html#combinations. This way your network graph is only loaded once.

Answer 2

This is probably too late for author, but for anyone with the same goal - as mentioned by @dkastl, it can be wise to use 'combinations' table, which is basically a predefined table with exact combinations of origin and destination points (vertices) for your goals.

So instead of running cost matrix on all origins to all destinations, which pgr_dijkstraCost will originally do:

origin	dest
1	10
2	20
3	30
4	40

in this case meaning origin 1 -> destinations 10,20,30, origin 2 -> 10,20,30 etc, resulting in 1->10, 1->20, 1->30 etc,

with 'combinations' table you have predefined ODs, meaning the same table will result in: 1->10, 2->20, 3->30, 4->40, saving you loads of time especially on your scale of calculations.

Now, to craft the combinations table that will speed things up I suggest you can run a ST_DWithin from all of your start points, in certain radius that will make sense in your case - 100m, 1000m, even more maybe. This way you will get a table where from each start point you have a number of vertices that are potentially closest to your origin vertice.

The code for looking at vertices within 100m from origins will be something like this:

    CREATE TABLE tablename AS (
    
    SELECT v.node_id as source, vc.node_id as target
    FROM network_name_vertices_pgr v
    JOIN network_name_vertices_pgr vc
    ON ST_DWithin(v.geometry, vc.geometry, 100)

ST_DWithin uses spatial indexes that you added to your network, so it should be very fast.

In this way, instead of calculating pgr_dijkstraCost on 0.4mio x 0.4mio matrix - which is essentially 160bn OD rows, you will calculate on 0.4 mio x 10-20 closest per each, which is somewhere between 4 and 8 mio OD rows. I imagine the speed boost will be quite big.