Hi Jinfu,<div><br></div><div>Thank you for posting to the list!</div><div>And thank you for your comment, Jay!</div><div><br></div><div>There are already implementations of the contraction hierarchies algorithm available.</div>
<div>I know about this one for example: <a href="http://project-osrm.org/">http://project-osrm.org/</a> </div><div>OpenTripPlanner is using it as well: <a href="https://github.com/openplans/OpenTripPlanner/wiki/">https://github.com/openplans/OpenTripPlanner/wiki/</a></div>
<div><br></div><div>There are two problems I see with this algorithm:</div><div><ul><li>Can we use an algorithm published under AGPL? Or are only the existing applications AGPL but not the algorithm.</li><li>Contraction Hierarchies does a lot of pre-processing. pgRouting's strength is, that the network data can be changed easily. <br>
Jinfu, did you already think about details?</li></ul><div>I think an implementation of this algorithm in pgRouting is a very ambitious GSoC project and should be planned well.</div><div>But it would be a great contribution for sure.</div>
<div><br></div><div>Jinfu, maybe you can look a bit more into details, search for existing implementations and try to understand how they work.</div><div>Have you already used pgRouting and written pl/pgsql functions?</div>
<div><br></div><div>Daniel</div><div><br></div><br><div class="gmail_quote">On Mon, Mar 26, 2012 at 3:42 PM, Jay Mahadeokar <span dir="ltr"><<a href="mailto:jai.mahadeokar@gmail.com">jai.mahadeokar@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Jinfu Leng,<br><br>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. <a href="http://algo2.iti.kit.edu/english/routeplanning.php" target="_blank">http://algo2.iti.kit.edu/english/routeplanning.php</a><br>
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.<br><br>I would also suggest you look at last years' mailing list discussions regarding this topic.<br>
<br>Best of luck!<br><br><div class="gmail_quote"><div><div class="h5">On Mon, Mar 26, 2012 at 10:15 AM, Jinfu Leng <span dir="ltr"><<a href="mailto:logicnut@gmail.com" target="_blank">logicnut@gmail.com</a>></span> wrote:<br>
</div></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div class="h5">
<div class="gmail_quote">Hi all,<div><br></div><div>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.</div>
<div><br></div><div>In addition, I am looking for a potential mentor.</div><div><br></div><div>Thanks a lot,</div><div>Jinfu</div><div><br></div><div>
<p style="margin-bottom:0in"><a name="1364dbdc4468e68b_1364d5285fe65702_1364d4fa69bbe6b0_OLE_LINK3"></a><a name="1364dbdc4468e68b_1364d5285fe65702_1364d4fa69bbe6b0_OLE_LINK4"></a><a name="1364dbdc4468e68b_1364d5285fe65702_1364d4fa69bbe6b0__GoBack"></a>
<font color="#000000"><font face="Arial, serif"><font><b>Title</b></font></font></font><font color="#000000"><font face="Arial, serif"><font>:
Highway Hierarchies Routing Support for pgRouting</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font><b>Describe
your idea</b></font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>1.
Introduction</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>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. </font></font></font>
</p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>2.
Background</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>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.</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>3.
The idea</font></font></font></p>
<p style="margin-bottom:0in"><a name="1364dbdc4468e68b_1364d5285fe65702_1364d4fa69bbe6b0_OLE_LINK2"></a><font color="#000000"><font face="Arial, serif"><font>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. </font></font></font>
</p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>4.
Project plan</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>5.10-5.20:
Read the source code and talk with the mentor - understand its
structure and working flow</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>5.21-6:10:
Read the paper and start to do some experiments on it – understand
the algorithm</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>6.11-6.30:
Code and test the first step: construction of highway hierarchies</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>7.1-7.5:
Write middle term report</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>7.6-7.20:
Code and test the second step: the query – compare the output with
the output generated by other algorithms</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>7.21-7.31:
Comprehensively test the algorithm and the library - call functions
from other software</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>8.1-8.10:
Improve documents and write final report.</font></font></font></p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>5.
Future ideas / How can your idea be expanded? </font></font></font>
</p>
<p style="margin-bottom:0in"><font color="#000000"><font face="Arial, serif"><font>None<br><br>
</font></font></font></p></div></div>
<br></div></div>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><span class="HOEnZb"><font color="#888888"><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>
</font></span><br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66,99,171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66,99,171)" target="_blank">http://georepublic.de</a></span><br>
</div>