[pgrouting-dev] GSoC Project: Highway Hierarchies Routing Support for pgRouting

[Daniel Kastl]

Hi Jinfu,

Thank you for posting to the list!
And thank you for your comment, Jay!

There are already implementations of the contraction hierarchies algorithm
available.
I know about this one for example: http://project-osrm.org/
OpenTripPlanner is using it as well:
https://github.com/openplans/OpenTripPlanner/wiki/

There are two problems I see with this algorithm:

   - Can we use an algorithm published under AGPL? Or are only the existing
   applications AGPL but not the algorithm.
   - Contraction Hierarchies does a lot of pre-processing.
   pgRouting's strength is, that the network data can be changed easily.
   Jinfu, did you already think about details?

I think an implementation of this algorithm in pgRouting is a very
ambitious GSoC project and should be planned well.
But it would be a great contribution for sure.

Jinfu, maybe you can look a bit more into details, search for existing
implementations and try to understand how they work.
Have you already used pgRouting and written pl/pgsql functions?

Daniel


On Mon, Mar 26, 2012 at 3:42 PM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:

> Hi Jinfu Leng,
>
> I did GSoc 2011 with pgRouting. I had looked in detail about this problem
> last year too. The highway hierarchies is actually not the fastest method
> now. Instead Contraction Hierarchies by Giesberger is a much better and
> faster heuristic. http://algo2.iti.kit.edu/english/routeplanning.php
> will give you all the details of latest research in this area. The source
> code of Contraction hierarchies is also available for download, so you
> could check it out too.
>
> I would also suggest you look at last years' mailing list discussions
> regarding this topic.
>
> Best of luck!
>
> On Mon, Mar 26, 2012 at 10:15 AM, Jinfu Leng <logicnut at gmail.com> wrote:
>
>> Hi all,
>>
>> I am interested in applying the GSoC project, and I want to work on
>> pgRouting. The description of the idea is pasted at the bottom. I want to
>> get some suggestions from you guys. Any suggestion is welcome. And if some
>> previous GSoC students can share your previous applications, that would be
>> great.
>>
>> In addition, I am looking for a potential mentor.
>>
>> Thanks a lot,
>> Jinfu
>>
>>  *Title*: Highway Hierarchies Routing Support for pgRouting
>>
>> *Describe your idea*
>>
>> 1. Introduction
>>
>> One of the main challenges of routing is the huge size of road networks.
>> Especially, given source node and sink node in long distance, shortest path
>> computation will be very time consuming. I would like to improve current
>> routing algorithm by adding highway hierarchies routing support.
>>
>> 2. Background
>>
>> Routing is a very common task in GIS, and pgRouting is a famous routing
>> library which provides routing functions for many GIS software, such as
>> PostGIS/PostgreSQL. Due to the huge size of road networks, finding path
>> requires significant computing time, especially for long distance source
>> and destination. This results in slow response time and unfriendly user
>> experience.
>>
>> 3. The idea
>>
>> In fact, this algorithm is not my idea. My work will base on the paper
>> [P. Sanders, D. Schultes]. Basically, this algorithm includes two steps:
>> construct the highway hierarchies; query on the highway hierarchies.
>> According to their experiments, this new approach can be about 2000 times
>> faster than the original Dijkstra’s algorithm. The tradeoff is spending a
>> few hours for generating highway hierarchies. I want to implement this
>> algorithm in pgRouting library.
>>
>> 4. Project plan
>>
>> 5.10-5.20: Read the source code and talk with the mentor - understand its
>> structure and working flow
>>
>> 5.21-6:10: Read the paper and start to do some experiments on it –
>> understand the algorithm
>>
>> 6.11-6.30: Code and test the first step: construction of highway
>> hierarchies
>>
>> 7.1-7.5: Write middle term report
>>
>> 7.6-7.20: Code and test the second step: the query – compare the output
>> with the output generated by other algorithms
>>
>> 7.21-7.31: Comprehensively test the algorithm and the library - call
>> functions from other software
>>
>> 8.1-8.10: Improve documents and write final report.
>>
>> 5. Future ideas / How can your idea be expanded?
>>
>> None
>>
>>
>> _______________________________________________
>> 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/20120326/3b684ab3/attachment-0001.html