2

I have three tables ==> ways, nodes and cities (OpenStreetMap)
ways : Edges with required attributes for routing (source, target, cost, etc.)
nodes : Each and every nodes linking the edges
cities : The actual nodes I'll use to compute shortest ways

I need to have the shortest way between each adjacent cities, which means I don't want to calculate the shortest way between each and every cities (this will take too much time and needs to be usable on a large dataset).
Below is a picture to have a better understanding of the problem. Keep in mind those numbers are arbitrary and I'm looking for a method that would be working on a large set of data (1000+ cities).

Shortest way needed

What I want is to find a way to compute the shortest way between [2, 1], [2, 3] but NOT [1, 3] as it will just be the addition of the two others.

For now, I've tried pgr_dijkstra MANY-TO-MANY with pgRouting, the problem is that when I supply the same array as source and target, it takes too much time and can't even display the results because of some memory issue. [id_node from the table cities has been extracted from the source/target of the road sections]

SELECT * FROM pgr_dijkstra('SELECT id, source, target, cost, reverse_cost FROM ways',
array(SELECT id_node FROM cities), array(SELECT id_node FROM cities), TRUE);

The main goal is to build a graph with cities as nodes, and ways (weighted by the time needed) as edges.
Is it possible to realize that using pgRouting or do I need to make a python script ? And in that case, are they some resources I can use ?

Edit 1: Network simplification

Following @ThingumaBob advice, I drastically simplified the network by removing unecessary nodes. This was actually harder as I thought because of underpasses/overpasses. I first tried to treat them as well but I just end up inserting them without simplification (I could have done it with a recursive function or else, but it was too much time for a small improvement).
I guess my code will speak of itself :

CREATE TABLE network (
  id serial NOT NULL,
  source integer,
  target integer,
  cost double precision,
  geom geometry(LineString,4326),
  CONSTRAINT network_pkey PRIMARY KEY (id))
  WITH (OIDS=FALSE);
ALTER TABLE network
  OWNER TO "Me";

--Inserting reconstructed network
INSERT INTO network (
--Merging the network and returning simple geometry without bridges (ST_Crosses)
WITH nobridges AS (SELECT (ST_Dump(ST_LineMerge(ST_Union(lines.geom)))).geom
          FROM ways AS lines
          WHERE NOT EXISTS (SELECT 1 FROM ways w
              WHERE ST_Crosses(w.geom, lines.geom))),
--Retrieval of bridges
    bridges AS (SELECT DISTINCT w1.geom
          FROM ways w1, ways w2
          WHERE ST_Crosses(w1.geom, w2.geom)),
--Union of the two geometries and adding an ID
    merged AS (SELECT (ROW_NUMBER() OVER ())::int AS id, tb.geom
          FROM (SELECT nb.geom FROM nobridges nb
                UNION
                SELECT b.geom FROM bridges b) AS tb),
--Re-computation of costs for each edges
     costs AS (SELECT m.id, sum(ST_Length(w.geom::geography)/1000)/
               avg(w.kmh::double precision) AS cost, m.geom
          FROM ways w, merged m
          WHERE ST_Contains(m.geom, w.geom)
          GROUP BY m.id, m.geom),
--Creation of nodes and adding an ID
     nodes AS (SELECT (ROW_NUMBER() OVER ())::int as id, nd.geom
          FROM (SELECT DISTINCT geom
                FROM (SELECT ST_StartPoint(m.geom) as geom
                      FROM merged m
                           UNION
                           (SELECT ST_EndPoint(m.geom) as geom
                           FROM merged m)) AS node_all) AS nd)
 --Creation of the final table by assigning a source and a target to each edges, thus, having a functional network system
SELECT c.id, n1.id as source, n2.id as target, c.cost, c.geom
    FROM costs c
    LEFT JOIN nodes n1
        ON ST_Intersects(n1.geom, ST_StartPoint (c.geom))
    LEFT JOIN nodes n2
        ON ST_Intersects(n2.geom, ST_EndPoint (c.geom))
);

In the end, I found myself reconstructing the graph from scratch but I guess this was a better solution as it was quite fast. I don't if it's properly optimized but it works...

It gives me this : enter image description here
As it doesn't fix my problem, it still reduce potential shortest way calculation. I'm still open for any suggestions on how to calculate only directly-connected cities

  • ...that is, by definition, the many-to-many version you tried ,) but, way more important: the function needs valid NODE IDs from those nodes that connect the network and built the graph (you seem to have selected the cities id?) – ThingumaBob Aug 18 '17 at 16:25
  • 1
    could you union the resulting set of routes of a 'all-to-all' dijkstra into a single multiline feature, split that by the cities and re-node it via pg_routing to a network? wouldn't cut the duration, but works...no? – ThingumaBob Aug 18 '17 at 17:12
  • well, the ids of the cities have been extracted from the roads themselves (source and target) so this shouldn't be an issue. As for your suggestion, that would surely do the trick, the thing is, I want to avoid having to compute 'all-to-al'l as I have many cities and the process time will probably be awfully long. But that's a nice idea for a smaller set of data. – BFlat Aug 20 '17 at 14:03
2

Since no one joined in, and if you don´t mind, I´ll share some thoughts without this being a satisfying answer (I share a work-related intereset in this).

I highly doubt you have much of an alternative to get a generalized network like the one you are looking for; this is due to the fact that the adjacency matrix of neighbouring cities you imply (to be able to, sort of, avoid unnecessary calculations) is based on a shortest path calculation as well, and for it to be the shortest path connecting each pair, well, by definition you will each have to traverse the whole graph to find it (or use a heuristic algorithm like A* maybe with its pros and cons).

In your example, as Evan said, there is no way to determine that an existing path {1, 2} is part of the shortest path of [1, 3] before walking all (dijkstra) or lots of (A*) other paths. Also, you shouldn't simply assume that if you reach a city with an existing path to the target of the running search, this is the shortest path and skip the search (imagine a triangle 'network': if you already have the path {B, C} and reach B in your search for [A, C], you shouldn`t skip and take {A, B, C} due to your assumption...).

With this said, I think you could at least try and speed up the 'all-to-all' search in some ways.

While the pgr_dijkstra(many-to-many) function is certainly a lot more sophisticated than what I could propose, writing your own function to do an 'all-to-all' search with pairwise one-to-one-dijkstra could give you the benefit of control:

  • For example, if you subsequentially merge all found paths to single linestrings (with accumulated cost and updated source/target of respective nodes) and recursively route on the updated network, you´ll get your generalized network in one turn without post-processing and the algorithm might get a speed boost with decreasing node/edge count.
  • (You´d have to clean your base network accordingly (i.e. get rid of dangling nodes/edges if there is no city assigned [you can use pgr_analyzeGraph to find those]) and at least keep track of visited cities to avoid reverse search.)
  • Additionally, you can try and carefully get only subsets of your data for each search, based on the bounding box of the city pair in question (fast) or by radius search (medium fast) or something similar. That could reduce the individual runtime a lot (or fetching those subsets for each iteration might defeat that purpose...not 100% sure, but I think it does help, with indexes and cleaned tables), but could also lead to unexpected errors (i.e. no path found due to cut-off network).

This should 'easily' be doable in PL/PgSQL (if you are familiar), maybe even by adjusting the pgr_dijkstra(many-to-many) function itself to your needs (although unlikely, due to external C dependencies or general inaccessibility...I haven´t checked).
You could as well switch to Python scripting with one of the many dijkstra implementations (I googled it and came up with heaps...I hope linking them here/now is not necessary), but you´d at least lose the benefits of spatial indexes (the whole control advantage is even more present then, though, since you can easily implement some break conditions in the main algorithm to skip the search whenever you want...if you really want).

As I said, I´m on it, for my own project. If I find something, I´ll update my answer. Maybe someone joins in with an ingenius (or obvious...) solution...

  • Thanks a lot for that exhaustive answer! I really appreciate your help. To answer your first point, getting rid of unecessary nodes by merging lines between key nodes should definitely improve later calculations. As for the second point, as I'm working on openstreetmap data, there is a lot of double road sections forking from the main one (to symbolize two-tracks with separated lanes), roundabouts, merging lanes, etc. and whatnot. So yes, I can clean up the network, but to some extent. – BFlat Aug 21 '17 at 12:54
  • 1
    I also found a similar post here that suggest using p̶g̶r̶_̶a̶p̶s̶p̶W̶a̶r̶s̶h̶a̶l̶l̶ deprecated ==> Use pgr_floydWarshall instead to derive the smallest network (something like the Steiner tree I think) gis.stackexchange.com/questions/114784/… – BFlat Aug 21 '17 at 14:31
0

If you want the points from 1,2, and 2,3. You don't have it find every possible route from the Cartesian product of {1,2} and {2,3} Then you are finding the routes from {1,3}. Instead, UNION it.

SELECT ARRAY[1,2], *
FROM pgr_dijkstra('SELECT id, source, target, cost, reverse_cost FROM ways', 1, 2, TRUE)
UNION ALL
  SELECT ARRAY[2,3], *
  FROM pgr_dijkstra('SELECT id, source, target, cost, reverse_cost FROM ways', 2, 3, TRUE);

Also, from the comments, @ThingumaBob is right too. Those are node ids. Logically it doesn't know how to resolve your arbitrary city ids into nodes.

  • but wouldn't this assume to know the topological adjacency (e.g. neighbouring cities) of all cities (consider a large table)? – ThingumaBob Aug 18 '17 at 17:10
  • Sure, but you have to make those assumptions, afaik. If you have a Many to Many pgr_dijkstra what do you do if the three cities are equidistant from each other? How do you know not to calculate 1,3 which was part of your question? – Evan Carroll Aug 18 '17 at 17:16
  • That it to say, afaik, it doesn't know that 1,3 is invalid by proxy of 1,2 until it does the calculations. It's up to you to filter that useless calculation out. If you want to optimize that out because you assume it can't possibly found a route that is faster because of the reverse cost of 1,2, then you have to explicitly do that with a union. I could be totally off here. Pg_routing isn't really my thing. I'm no expert at that. – Evan Carroll Aug 18 '17 at 17:18
  • I agree, if you want to avoid unnecessary calculations, you need to somehow create that topology of adjacent cities and calculate the one-to-one path for each pair. creating that topology is really tricky, though. – ThingumaBob Aug 18 '17 at 17:23
  • I understand how this would work with a few cities, but I'm working on a huge amount of data and I can't process them pair by pair. I assume this would work inside a loop over all the entries of my table though... As for the arbitrary ids of the cities, they aren't, I'll edit my post to be as clear as possible. – BFlat Aug 20 '17 at 14:11

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.