[pgrouting-dev] Re: Network Layering support
Stephen Woodbridge
woodbri at swoodbridge.com
Fri Jan 28 19:43:43 EST 2011
On 1/28/2011 6:15 PM, Jay Mahadeokar wrote:
> Hi,
>
> It seems,there has been a lot of research in speedup techniques for
> routing.Engineering Route Planning Algorithms
> <http://algo2.iti.kit.edu/english/1575.php> gives a nice overview of all
> the techniques invented till 2008.
>
> It also provides comparisons in pre-processing time and space required
> for each of the techniques. (I have attached the table for quick reference)
Yes on think the transit nodes variations is similar to contraction
hierarchies and and either of these would be a good addition and better
than the bi-direction hierarchical levels algorithm.
No doubt that any major undertaking along these lines will require
significant investment of time and energy.
> *Interesting point made in the paper: *
> /Advanced algorithms for routing in road networks require thousands of lines
> of well written code and hence require considerable programming skill.
> In par-
> ticular, it is not trivial to make the codes work for large networks.
> Here is
> an incomplete list of problems and complications that we have seen in
> routing
> projects: Graphs have to be glued together from several files. Tools for
> reading
> files crash for large graphs. Algorithm library code cannot handle large
> graphs
> at all. The code slows down several times when switching from a custom graph
> representation to an algorithm library. 32-bit code will not work.
> Libraries do
> not work with 64-bit code. Our conclusion from these experiences was to
> design
> our own graph data structures adapted to the problem at hand. We use C++
> with encapsulated abstract data types. Templates and inline functions
> make this
> possible without performance penalties.
> /
> *Source Code *(Quote from their web-page)
> /The source code of our implementation of contraction hierarchies (CHs)
> is now available under the terms of the AGPL. If you are interested in
> getting the source code write an email to Robert Geisberger
> <http://algo2.iti.kit.edu/english/geisberger.php>.
> /
Right, but there are also a few other implementations of the contraction
hierarchies in the wild that might not be based on their code, like the
MONAV implementation, which is released on GPLv3, and at least one
person was looking at it in conjunction with Boost (google: contraction
hierarchies boost)
> They have also come up with another paper in 2010: "A comparison for
> high-level approaches for speed-up in path finding algorithms
> <http://algo2.iti.kit.edu/english/1695.php>" but the full-text does not
> seem to be available. (I think this might be useful too)
>
> The GSoc page lists Network Layering (Contraction Hierarchies) and
> Highway Hierarchies as two separate problems. But Contraction
> Hierarchies technique seems to outperform HH in almost all categories,
> and comparatively its less complex.
>
> I think it will require a lot of brain-storming before we can narrow
> down any particular technique to implement, and also analyse the
> feasibility / difficulty of implementation of the same. Hoping to hear
> all your opinions on this.
> *
> PS:*
> I have started work on my Masters thesis, and I plan to explore this
> area further and maybe extend the work. (I need to do 8+16+16 thesis
> credits over the course of this semester and next 2 semesters, 4 credits
> is eq to 1 subject). A GSoc project in summer would be an added incentive!
>
>
> On Fri, Jan 28, 2011 at 11:45 PM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
> 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>
> <mailto: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 <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list