[pgrouting-dev] GSoC Project: Highway Hierarchies Routing Support
for pgRouting
Steve Horn
steve at stevehorn.cc
Mon Mar 26 10:10:01 EDT 2012
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
> 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<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>> 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 <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<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@**georepublic.de<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<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<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
--
Steve Horn
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120326/833f6268/attachment-0001.html
More information about the pgrouting-dev
mailing list