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

[Jinfu Leng]

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