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:

QGIS screen dump illustrating my problem

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!


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

    r record; 


    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,
                         length::double precision AS cost
                        FROM vw_finland_routing',
               10 , 60, false, false) ) as route  ; 

    FOR r IN
        SELECT source from vw_finland_routing

      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,
                         length::double precision AS cost
                        FROM vw_finland_routing',
               r.source  , target, false, false) ) as route ; 

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

LANGUAGE plpgsql;


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)

| improve this answer | |
  • Thanks for the answer! I have imported all data into QGIS, and I have merged all the roads to 1 layer, but I'm unsure what to do with the addresses and big cities (start and end points of my paths). Should these layers be merged with the road layer and imported into a postgis table, or should I have 3 tables; one for the roads, one for the start points, and one for the end points? – Mace Oct 17 '13 at 11:48
  • you need to have "target" id:s in routes layer´? Have you used pgr_createTopology('<table>', float tolerance, '<geometry column', '<gid>') ? – simplexio Oct 17 '13 at 12:22
  • but my targets are points and the roads are lines. I thought it wasn't possible to merge these to one layer. – Mace Oct 17 '13 at 13:59
  • 1
    Inspired by your idea and looking online I thought of using the following select to find the source ids:Select ST_Closestpoint(ST_Collect(a.geom), b.geom) as geom from roads a inner join addresses b on ST_Dwithin(a.geom, b.geom, 1000) group by b.id, b.geom; Wouldn't that do it? – Mace Oct 19 '13 at 11:17
  • 1
    Okay. I am using the following select to get the nearest road to each of the 10 cities: "SELECT DISTINCT ON(h.id) h.id as id_city, b.*into snap_cities FROM roads b INNER JOIN cities h ON ST_DWithin(h.geom, b.geom, 1000) ORDER BY h.id, ST_Distance(b.geom, h.geom);" And i will also use this select for the addresses, and then try to use ur function together with pgr_kdjikstraCost() – Mace Oct 21 '13 at 12:43

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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.