Calculating many shortest paths with pgRouting

Question

I 145013 Danish addresses, and 10 big cities in Denmark as points in QGIS. Furthermore, I have four vector layers that connect all the points. They are small roads, main roads, freeways and ferry routes. See the screen dump from QGIS below for an illustration:

Now I would like to calculate the shortest distance from each address to each of the 10 big cities. I will use pgRouting for this, and I have followed the nice tutorial on finding 1 shortest path here http://anitagraser.com/2013/07/06/pgrouting-2-0-for-windows-quick-guide/

However, I can't figure out how to extend the problem from 1 path to (145013 * 10 =) 1450130 paths.

• What method should I use in pgRouting, and how do I incorporate all the 1450130 paths?

I use:

• QGIS 2.1.0
• postgres 9.2
• postgis 2.0
• pgRouting 2.0
• OS: Win 7 64bit

I have shared my data here: https://www.dropbox.com/sh/rn8gdxr1bki4q4x/fFRd0PerkP

It's in in a QGIS project file.

I appreciate all comments and answers!

Answer 1

You can use a new algorithm of pgRouting 2.0 nammed pgr_kDijkstra. It will allow you to request "1-n" shortest paths with a single query.

There are two variations: one returns the full path of all routes and one only returns the total cost for each route.

The documentation should explain how to use it: http://docs.pgrouting.org/2.0/en/src/kdijkstra/doc/index.html#pgr-kdijkstra

Answer 2

First load data into postgis and convert all data to same projection. Create one table from all data and follow PgRouting tutorial to create edges and vertexes. I really hope that that data is topologically correct already and you dont need to fix those issues. ( Have you considered just using osm2po data for your network ? )

If you have already done it, then see pgrouting dijkstra example and do:

This works but is slow. i used Finnish osm2po data for testing

CREATE OR REPLACE FUNCTION get_all_routes(target int) RETURNS VOID  AS
$BODY$
DECLARE
    r record; 

BEGIN

    CREATE TABLE route_res as  SELECT  0 , route.* 
        FROM (SELECT  seq, id1 AS node, id2 AS edge, cost FROM pgr_dijkstra('
                SELECT gid AS id,
                         source::integer,
                         target::integer,
                         length::double precision AS cost
                        FROM vw_finland_routing',
               10 , 60, false, false) ) as route  ; 



    FOR r IN
        SELECT source from vw_finland_routing
    LOOP

      INSERT INTO route_res  SELECT  r.source , route.* 
        FROM (SELECT  seq, id1 AS node, id2 AS edge, cost FROM pgr_dijkstra('
                SELECT gid AS id,
                         source::integer,
                         target::integer,
                         length::double precision AS cost
                        FROM vw_finland_routing',
               r.source  , target, false, false) ) as route ; 

        RAISE NOTICE  ' Running at % source id' ,r.source ;
    END LOOP;

END
$BODY$
LANGUAGE plpgsql;

AND

SELECT get_all_routes(10) -- where 10 is target from city 

Solution is slow and badly written. CREATE table needs to be taken out from function or needs to be in if exist block. to get some performance out of this you need to run N queries to target or if you can change it so that source is city and target is in for loop. My other ideas for problem are using pgr_kDijkstra. Or you can create city wide polygon and use it to overwrite that area source/target id's so function needs only find an area (takes 1000-> or more edges from route table)