13

I have a set of postgis scripts which generates two tables - one of a set of points and the second a set of roads which surround them. All data is in the same projection and both outputs are stored in postgres 9.2 tables with postgis 2.1

The pgrouting topology of the road network has been created and the points table has a column containing the nearest road segment.

I'd like then to generate a subset of the road network which represents the smallest network that connects all points using something like a minimum spanning tree. The road network is undirected, and costs are simply the route length.

I can do this in QGIS/Grass using the v.net family of modules but ideally I'd like to keep this final step in SQL as well.

I've looked at the new apspWarshall postgis function but I'm at a loss as to how it can be encouraged to focus its energy on connecting the points and not the whole network.

This is the short script I've put together in an attempt to create a framework to solve this but I can't see where its possible to focus the function to start with a subset of the edges.

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
FROM   pgr_apspWarshall('SELECT gid AS id, 
                                source, 
                                target, 
                                st_length(the_geom) AS cost 
                         FROM   road_network
                        ',
                        false, false
                       ) AS tree
JOIN   road_network As roads
ON     tree.id2 = roads.gid

In single path shortest path problems the function asks for the start and end but apparently not in the all points problems. Equally in Grass the v.net.spanningtree and v.net.steiner expect a set of points and lines as a combined network to work with.

Does anyone have an suggestions for how to do this in PostGIS?

  • i not sure that i understand question but does docs.pgrouting.org/2.0/en/src/tsp/doc/index.html#pgr-tsp Traveling Sales Person algorithm help you ? – simplexio Sep 30 '14 at 11:37
  • 1
    Thanks. It doesn't really I'm afraid. Travelling salesman assumes a journey from a to b to c and so forth in a linear fashion. What I want is the minimum network that links every point together efficiently such that any point could commence a journey to any other point in the knowledge that there aren't any superfluous paths to get lost down. In other platforms this is usually done with a Minimum Spanning Tree function, Steiner Tree (en.wikipedia.org/wiki/Steiner_tree_problem) or similar. If you like, TSP is great for the the logistics company but I want to plan the roads they'd use. – Adrian Sep 30 '14 at 12:24
2

This answer is not complete or tested, but try something like this:

according to questions/39210:

with index_query as (
SELECT
        ,ST_Distance(i.geom, i.b_geom) AS dist
        ,ST_MakeLine(i.geom, i.b_geom) as geom
FROM(
SELECT
        ,a.geom
        ,b.geom AS b_geom
        ,rank() OVER (PARTITION BY a.id ORDER BY ST_Distance(a.centroid_geom, b.the_geom)) AS pos
FROM points a, points b 
WHERE a.id <> b.id) i
WHERE pos = 1
) select ST_Union(geom) from index_query;

i think this is not very efficient.

  • Really appreciate this - thank you. This has given me some new angles to explore I hadn't thought of. This code will find the nearest unconnected neighbours from a table of points. The added complication I have is that the points in my case are connected along a network of linestrings but I wonder if I can replace the ST_Distance query with a pgRouting road distance, although it would be significantly slower than an unrouted point query. – Adrian Nov 20 '14 at 14:52
2

@Adrian, I am really unfamiliar with the pgrouting results, however the documentation is very detailed. My answer is based on a two-step function, which will be very inneficient in SQL but [likely] produces the results. This [untested] solution will NOT optimize which is the best starting point, but will reduce the entire route network to only the edges which connect all stops, then routes efficiently to all stops.

Step 1 (sub-selection of a road network subset which connects all stops) This uses the multiple-destination (K Dijkstr path) routing function to return a collection of paths that (when cost <> -1) actually do connect all of your stops.

SELECT id1 as path, st_astext(st_linemerge(st_union(b.the_geom))) as the_geom
FROM pgr_kdijkstraPath(
’SELECT id, source, target, cost FROM edge_table’,
min(all_your_stop_ids), [array_of_all_your_stop_ids], false, false
) a,
edge_table b
WHERE a.id3=b.id
GROUP by id1
ORDER by id1

The problem I have here is the syntax for assembling an array from your stop table, as it wasn't really described in the question. However, let's assume that SQL syntax can assemble that array and that the minimum id stop should be the starting point for all the K paths to the remaining target stops.

Step 2 (final selection of the minimum paths based on the above subset road network paths which connect all stops) This is essentially what you started with, but I propose that you equa-join your road network to the initial result on id1 (path) so that only the subset of roads is used in the final Field-Warshal routing:

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
FROM   pgr_apspWarshall('SELECT R.gid AS id, 
                                R.source, 
                                R.target, 
                                st_length(R.the_geom) AS cost 
             FROM   road_network AS R JOIN
                   (SELECT id1 as path
                     FROM pgr_kdijkstraPath(
                            ’SELECT id, source, target, cost FROM edge_table’,
                            min(all_your_stop_ids), 
                            [array_of_all_your_stop_ids], false, false
                           ) a,
                     edge_table b
                    WHERE a.id3=b.id
                    GROUP by id1
                    ORDER by id1
                        ',
                        false, false
                  ) AS  Just_K_Paths
         on R.id1 = just_K_paths.id1',       /* this join reduces R down to K paths */
         false, false
        ) AS tree
  JOIN   road_network As roads
  ON     tree.id2 = roads.gid

So, in summary...the inner k_dijkstra_path routing query reduces the total road network to only the paths connecting all your stops, then the outer fField_Warshal routing uses only those edge ids to solve the path-optimization query....maybe.

  • Thank you - this is very helpful and my first new lead. I'm looking at it now. I'm just trying to work out how to generate the minimum stop id and the array. I have a table of the required ids but 'SELECT min(id) FROM node_table' and 'SELECT ARRAY[id] FROM node_table' produce syntax errors when inserted into your code but work as free-standing code (my poor understanding I'm sure) – Adrian Feb 27 '15 at 9:39

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.