[pgrouting-dev] GSoC Project: Highway Hierarchies Routing Support
for pgRouting
Stephen Woodbridge
woodbri at swoodbridge.com
Mon Mar 26 11:09:17 EDT 2012
I am happy to give my insights on this and to answer questions if I can.
If we do it via email I will try to collect the information and create a
new documentation page on the website to help future hackers.
I have Linux and work in Linux, but I have a small amount of know about
Windows, but if you go very deep into Windows I will not be of much
help. My strength is finding solutions to problems so ask questions and
I will do my best to answer them and explain as much as I can.
What OS are you working on?
-Steve
On 3/26/2012 10:10 AM, Steve Horn wrote:
> If you guys arrange something to meet up on Skype or a Google hangout to
> show the ins and outs of the development environment, I would love to
> attend. I'm still struggling with getting a proper environment set up
> for development of pgRouting.
>
> Perhaps others would be interested in this as well?
>
> On Mon, Mar 26, 2012 at 9:34 AM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
> 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/
> <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>
> <mailto: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
> <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>
> <mailto: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>
> <mailto:pgrouting-dev at lists. osgeo.org
> <mailto:pgrouting-dev at lists.osgeo.org>>
>
> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
> <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>
> <mailto:pgrouting-dev at lists. osgeo.org
> <mailto:pgrouting-dev at lists.osgeo.org>>
>
> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de
> <mailto:daniel.kastl at georepublic.de> <mailto:daniel.kastl@
> 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 <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
> <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
> <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
>
>
>
> --
> Steve Horn
>
>
>
> _______________________________________________
> 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