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

[Jay Mahadeokar]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120326/f6e204be/attachment.html