[pgrouting-dev] Re: Network Layering support

Fri Jan 28 19:33:21 EST 2011

Hi Jay,

*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>
> .
> *

I think I saw it already once somewhere, but couldn't find it now anymore.
Instead I found these two pages:

   - http://en.wikipedia.org/wiki/Contraction_hierarchies ... so it seems
   OpenTripPlanner uses CH:

   http://opentripplanner.org/browser/trunk/opentripplanner-routing/src/main/java/org/opentripplanner/routing/contraction
   - http://cloudmade.com/about/open-source ... Cloudmade uses CH

But I think it would fine to just ask Robert Geisberger for the source code.

> **
> 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.
>

Needs to be updated for 2011. It was just a collection of ideas, but not a
requirement for students to follow.

Daniel

>
> 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> 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>> 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
>>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> 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
>
>

-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110129/28b77e34/attachment.html