[pgrouting-dev] GSoC Project: Highway Hierarchies Routing Support
for pgRouting
Stephen Woodbridge
woodbri at swoodbridge.com
Mon Mar 26 09:34:46 EDT 2012
Hi Jinfu,
I think the Contraction hierarchies algorithm would be great to have in
pgrouting. As Daniel notes one of the advantages of pgrouting is the
dynamic nature of configuring the graph before computation, but given
the performance boost of this algorithm, there would also be great value
in having a solution that is less flexible but 2-3 orders of magnitude
faster!
Learning the postgresql api, development restrictions, and debugging can
add significant time to your effort. It would give you a big head start
if you were to dive into that before GSoC started to learn a little bit
about it. A few suggestions, might be to take an algorithm that you have
already written and just try to integrate it into pgrouting. Another
would be to take a bug and try to fix it. Either of these efforts would
require you to learn the basics about how to setup a development
environment, compile pgrouting, debug code in the server and generally
familiarize you with the environment that you would be constrained to
work in. I would be happy to mentor an effort like this if you have the
time and want to learn about pgrouting.
Regarding contraction hierarchies, the AGPL license is so invasive that
probably only Universities and Colleges can use the published code.
While it would allow us to figure out the integration issues it is not a
practical license for inclusion in pgrouting. This would mean that we
would need a new implementation of the algorithm to make it useful to
the project.
Every project has problems and limitations, but I like to think of the
possibilities and focus on how to move forward. It is good to be aware
of the problems and issues from the outset, because then you have time
to work around them or avoid them.
So if you break this down into tangible tasks that represent potential
stopping points you might have something like:
1. write code to extract data from postgresql, preprocess it, write
results back to postgresql
2. write code to process a route request, ie: get data, solve request,
return results.
3. rewrite algorithm to be AGPL clean
Any one of these might be a valid GSoC project, although 2 is rather
small following to 1. Item 3 by itself could be a good GSoC project
assuming it meets the requirements and this would give you a better
understanding of the code and how it works so future integration of it
into pgrouting would be easier and might be more dynamic if we
understood how to propagate changes through the preprocessed data if
that is possible.
I'm willing to co-mentor any pgrouting GSoC projects.
Best regards,
-Steve
On 3/26/2012 2:59 AM, Daniel Kastl wrote:
> 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 <mailto: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
> <mailto: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 <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 <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
> Web: http://georepublic.de <http://georepublic.de/>
>
>
> _______________________________________________
> 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