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

Tue Jun 7 09:22:13 EDT 2011

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

-- 
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)