[pgrouting-dev] Re: Network Layering support

[Stephen Woodbridge]

Hi Jay,

If you are up for tackling another algorithm, I think this is the one 
that has really high value for pgRouting:

http://algo2.iti.kit.edu/english/routeplanning.php

The contraction highways routing is awesome stuff. There is a lot of 
pre-analysis of the network which takes a lot of compute time, but once 
that is done and stored, the resulting structures let you compute routes 
of continental distances in milliseconds.

This should be a very high priority for us as it is already in at least 
two separate tools that work with OSM data. The value add for pgRouting 
is that we could then use this algorithm for any datasets that meet the 
minimum requirements for contraction highways.

Daniel, Anton, do you agree that this is a priority?

I hope you will give this one serious consideration.

Best regards,
   -Steve

On 1/28/2011 8:22 AM, Jay Mahadeokar wrote:
> Hi all,
>
> Excuse me for bringing up an old topic again! Quoting the idea posted in
> GSoc 2010 ideas page:
>
> /Network Layering Support:
> This idea is a quite a challenging task. Network layering would allow
> the routing algorithm to change from more to less dense networks to
> enable long-distance routing.
> /
> Has this idea still got priority? If yes, I would like to have more info
> on the same.
>
>
> On Sat, Oct 16, 2010 at 10:48 AM, Jay Mahadeokar
> <jai.mahadeokar at gmail.com <mailto:jai.mahadeokar at gmail.com>> wrote:
>
>     Hi.
>
>     I am currently doing MTech in Computer Science and Engineering from
>     Indian Institute of Technology Kanpur, India. I have used pgRouting
>     while working with postGreSQL in past. I have special interest in
>     routing algorithms and would like to contribute in some way.
>
>     I was looking at the ideas posted here:
>     http://wiki.osgeo.org/wiki/OpenRouter_2010_SOC_Ideas which mentions
>     that a network layering support is desirable which would allow the
>     routing algorithm to change from more to less dense networks to
>     enable long-distance routing.  I have worked with sparse spanner
>     algorithms, and was wondering if it can be applied here. A 3 spanner
>     algorithm can allow you to get a sparse graph containing O(n^3/2)
>     edges from dense graph containing O(n^2) edges, using linear time -
>     O(m) - m s the number of edges.
>
>     It would be great if I could know more details about the
>     requirement. Example - while constructing spanner for road network,
>     do we want to consider the type of roads and give them priorities
>     accordingly?
>
>     PS - I am complete newbie when it comes to contribution to
>     opensource projects of such scale. Please excuse me for asking wrong
>     questions. I would also like to work on other ideas which may be in
>     your TODO list. I would be great if you can direct me to some links
>     which may help to get started properly.
>
>
>     --
>     Regards,
>     -Jay Mahadeokar
>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev