Improve performances on distance coverage routing - PostgreSQL

Question

I have to create layers of land coverage from one point to anywhere around on a given street network for a given distance (ex: FROM house, DISTANCE 30000m)

An important factor to understand; I need the result to be exactly superposed over my network, and the coverage to represent only the parts of the road (let say, the addresses) that can be reached from the network for the given distance. Nothing more. I need to be precise, because it will be used for emergency services and efficiency analysis over the covered network. And to add to the fun, the tool must not only give the right answer, but do it in a decent length of time, as it will ultimately be open to other uses on a public web interface (so no, I don't only need an application that will generate the right routing over a night of work!)

The point is not to find the shortest way to get to a known point, so basic pgrouting tools can't get me a direct answer.

I developped a working algorithm, and it works well on long routes, but as soon a I enter a "real" network (as for a city, or even a village), it crashes... well, it simply run for hours.

Basically, my algorithm goes like this:

First, we link our network table to our previous results to make sure we don't take a route that as been looked uppon, unless we have more "remaining distance" to cover at this point, which mean that our new route is better.

FOR a in EXECUTE 'SELECT aa.ogc_fid, aa.'||col_contr||' as cost, aa.the_geom, aa.source, aa.target

   FROM '||table_name||' aa LEFT JOIN temp res ON res.ogc_fid = aa.ogc_fid AND res.dist > '||distance||' 

    WHERE (aa.source = '||debut||' 
            OR aa.target = '||debut||')
            AND (ARRAY[aa.ogc_fid] &&  ARRAY['||array_to_string(fromSegment,',')||']) = false
            AND res.ogc_fid is null' 

LOOP

After that (I'll short the code), IF(distance > a.cost) THEN

We insert the informations in the result table, and launch back the function from this node, which developps a tree.

ELSE (we don't have enough "remaining distance" to cover the line)

We return a st_line_substring of the lenght we can cover, and the function stops

So it's a reccursive function that tries to cover every possible routes from the startpoint to the given distance...

Any idea about how to improve it's speed? I think the answer would be to modify the fist FOR statement... but after hours of brain boiling, I have to admit that I can't do it alone!

Thanks

Some new details Suppose this fictive (and horrible, sorry, not on my computer) network, with the blue point as a startpoint for a given distance.

Driving_distance would give a result such as this (red dots being end vertex for the distance, and green ones intermediate vertex on the path).

The problem I face here (but still, not on my computer, can't try it tonight, maybe I'm wrong) is that I need a very precise and stuck-on-the-network polyline result. With these dots, I guess I could recreate the path, using some kind of point_to_line function, but it would not work for complexe polylines that are not straight from startpoint to endpoint (like, if the road makes an "S"...).

Same problem with isocrone:

The coverage here is not what I need, simply because it covers spaces that cannot be reached on the real network (like the segment in the pink ellipse, which is pass the terminal red dot).

(Sorry about the pictures, I'll probably give you some real screenshots of the problem tomorrow)

Answer 1

pgRouting driving_distance function returns not only vertex(node)_id, but also edge(link)_id and cost. (See Official document - 'Examples' part and yellow nodes/links of bellow image.)

So, I think that you can find red point efficiently from driving_distance result like...

for [edge(link) which is not listed in result and connect listed vertex(node)]
  calculate (distance - cost) point from (start/target) point

Answer 2

Not sure I understand your function, but isn't "Driving Distance" computation what you want to do? This already exists in pgRouting: http://www.pgrouting.org/docs/1.x/dd.html

Answer 3

Is it something like this you are trying to create? This shows how far you can get in 1,2,3 minutes on a network.

Answer 4

Ok, thanks group!

Me and my partner finally made it today. I still have work to do in cleaning the code, but be assured that I'll post a summary of the technique here as soon as possible.

A glimpse of the solution for now: Our function was working "in depth", building a single route as long as possible, and then unfolding the branches of the tree backward.

It was working, but was awfully long.

What we have now works "in width", using a FIFO (first in, first out) array technique. It is now thousands of times faster, and the result is exactly what we wanted!

More details later... Thanks again for your help!

By the way, I dropped the Driving_distance pgRouting function a bit too fast. I now believe that you're right, it could be done with it, even though it would need a good amount of post-process work to give me what I was looking for. Still, a good way to look at for any similar problem!

Answer 5

It sounds that what you want is an isochrone polygon where the cost is the geometric length instead of the usual travel distance in time.

You should look at the answers for Drive-time polygons.