[pgrouting-users] Re: improve performance of isoline computation

Tue Jun 7 09:41:07 EDT 2011

You can compute the cost to all nodes in the network connected to the 
start node in a single pass. I have been able to do this with some 
simple modes to the pgRouting code. Basically you want to do a Dijkstra 
solution then extract all the node in the graph. if you want the actual 
path to each of these node it is relatively trivial to reconstruct the 
the solved tree  using the predecessor map. I have to run out the door 
at the moment but I will try to post more on this tonight.

-Steve

On 6/7/2011 9:22 AM, Mayeul KAUFFMANN wrote:
> Hi Jaak,
> Thanks for your answer! At the end I need to know the time FROM (almost)
> every single cross in the network TO each one of a few point. The
> computation is very close to computing several complete sets of
> isolines, then searching on which isolines a single point lies, this is
> why I asked my question this way.
> About your answer "Pgrouting can find one isoline, this is the result of
> driving_distance", do you mean that you are using a similar approach to
> the link below to compute isolines?
>
> http://underdark.wordpress.com/2011/05/13/catchment-areas-with-pgrouting-driving_distance/
>
> Thanks again!
> Mayeul
>
> PS: your link just shows a pin called "Start" in the middle of the
> Indian Ocean, on Google maps (using Firefox).
>
>
> El mar, 07-06-2011 a las 15:19 +0300, Jaak Laineste escribió:
>> Hello,.
>>   Pgrouting can find one isoline, this is the result of
>> driving_distance. This gives number of points, if you connect them
>> you'll get isoline. If you need many isolines, then you should call it
>> many times, like for 5,10,20 minutes, for same point(s) etc. It is
>> sub-optimal this way also, but it is fast, below second for single
>> iteration, and for most uses sufficient.
>>
>>
>>   My recent test with it (isolines from certain point in certain
>> distances, in KML
>> format): http://maps.google.com/?q=http://46.51.131.48/dd/index.php?lat=59.43475%26lon=24.74786%26dist=1,2,3,4,5
>>
>>
>>   Or maybe I misunderstood what exactly do you mean by isoline here?
>>
>>
>> Jaak
>>
>>
>>
>> On 07.06.2011, at 19:00, pgrouting-users-request at lists.osgeo.org
>> wrote:
>>>
>>> Message: 1
>>> Date: Tue, 07 Jun 2011 12:37:09 +0200
>>> From: Mayeul KAUFFMANN<mayeul.kauffmann at jrc.ec.europa.eu>
>>> Subject: [pgrouting-users] improve performance of isoline
>>> computation
>>> To: pgrouting-users at lists.osgeo.org
>>> Message-ID:<1307443029.10348.130.camel at ISFLXMK2>
>>> Content-Type: text/plain; CHARSET=US-ASCII
>>>
>>> Hi,
>>>
>>> 1. I've seen at http://www.pgrouting.org/ that "pgRouting provides
>>> functions for [...] Driving Distance calculation (Isolines)".
>>> But I could not find any documentation on this (or I misunderstood
>>> "isolines")
>>>
>>> In the past I have been doing this using pgrouting with this
>>> iterative
>>> algorithm (written in bash and allowing parallelism) which is quite
>>> costly:
>>> To compute isoline with departure from A, compute travel time
>>> between A
>>> and any point of the network.
>>>
>>> This is quite similar to this:
>>> http://underdark.wordpress.com/2011/02/09/creating-catchment-areas-with-pgrouting-and-qgis/
>>>
>>> http://underdark.wordpress.com/2011/05/13/catchment-areas-with-pgrouting-driving_distance/
>>>
>>>
>>> This is costly because some parts of the network get traversed many
>>> time
>>> by the algorithm. If point B is between A and C, then once you have
>>> computed the cost from A to B, you can use this piece of information
>>> to
>>> find the shortest path from A to C.
>>>
>>>
>>>
>>> I searched for documentation here:
>>> http://www.pgrouting.org/docs/foss4g2010/index.html
>>>
>>> Searching on Google:
>>> site:lists.osgeo.org/pipermail/pgrouting-users/ isolines
>>> site:lists.osgeo.org/pipermail/pgrouting-dev/ isolines
>>> gave no result either
>>>
>>>
>>> Are there any other solution to the isoline problem that I'm not
>>> aware?
>>>
>>> 2. Finally, my ultimate goal is as follows:
>>> given a set of many departure points d1 to d1000, for each of them,
>>> find
>>> which of the arrival points (A, B, C, D, E) is the shortest one.
>>>
>>> My idea would be to use the following approach, but modified:
>>> http://underdark.wordpress.com/2011/05/13/catchment-areas-with-pgrouting-driving_distance/
>>>
>>> with modification as follows: after finding the best path from d1 to
>>> A,
>>> if this costs 100, you can search the best path from d1 to B
>>> stopping
>>> the search when the cost is larger than 100.
>>>
>>> Is any of the two above problems already implemented in compiled
>>> code,
>>> or the best I can do is to write my own code based on
>>> shortest_path() or
>>> driving_distance() ?
>>>
>>> Thanks for any help!!
>>> Mayeul
>>>
>>>
>>> PS: for those who wonder: this is to study the impact of
>>> transportation
>>> disturbance (in countries currently at war) on access to health
>>> infrastructure, hence: how to go to the closest hospital.
>>>
>>> --
>>> Dr. Mayeul KAUFFMANN, Conflict Specialist
>>> European Commission, Joint Research Centre (JRC)
>>> Institute for the Protection and Security of the Citizen (IPSC)
>>> Global Security and Crisis Management - ISFEREA
>>> Via E. Fermi 2749 - I-21027 Ispra (VA), ITALY
>>> Phone: (+39) 033278 5071
>>> http://isferea.jrc.ec.europa.eu/Staff/Pages/Kauffmann-Mayeul.aspx
>>>
>>> (Office: building 26b, 1st floor, room 140. TP: 267)
>>>
>>>
>>>
>>>
>>>
>>> ------------------------------
>>>
>>> _______________________________________________
>>> Pgrouting-users mailing list
>>> Pgrouting-users at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>
>>>
>>> End of Pgrouting-users Digest, Vol 33, Issue 3
>>> **********************************************
>>>
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>