[pgrouting-dev] GSoC Project: Highway Hierarchies Routing Support
for pgRouting
Steve Horn
steve at stevehorn.cc
Mon Mar 26 13:04:57 EDT 2012
I have a Ubuntu box set up that I can use for development.
A 30-45 minute virtual meeting with screen sharing would be really helpful.
I'd hope to see stuff like how you have your development environment
configured, how you go about debugging the code, and how the build process
works.
To make the time more valuable I was thinking we could set something up to
where many people could join in and learn at the same time.
On Mon, Mar 26, 2012 at 11:09 AM, Stephen Woodbridge <
woodbri at swoodbridge.com> wrote:
> 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<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/<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>
>> >
>> <mailto: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<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<pgrouting-dev at lists.osgeo.org>
>> >
>> <mailto: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<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>
>> >
>> <mailto: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<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>>
>> <mailto:daniel.kastl@
>> 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 <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<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<pgrouting-dev at lists.osgeo.org>
>> >
>> http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
>> <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<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/7bdc12d3/attachment-0001.html
More information about the pgrouting-dev
mailing list