[SoC] Re: Multi-modal public transit routing for pgRouting
justjkk at gmail.com
Fri Jul 1 15:59:29 EDT 2011
Following is the sixth week's report.
Things done in the sixth week:
* Hibernated code changes to pgRouting's core library.
* Read thesis and researched algorithms for solving scheduled routing
* Came up with a plan to use Implicit Graph and directly code using
* Spent a large chunk of time learning to use Boost library using code
Agenda for next week:
* Finish overdue task of implementing Scheduled routing.
* Write SQL functions and wrappers.
* Mid-term deliverable should be ready by this week.
* Discovered that the problem I'm trying to solve(and the solution) is
a specialization/use-case of Time Dependent Shortest Path which is
another ongoing gsoc project. So, the more efficient code/algorithm
will replace the other in the coming months.
 - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
 - http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
 - http://en.wikipedia.org/wiki/Implicit_graph
 - http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000342.html
 - https://github.com/wpm/Boost-Implicit-Graph-Example
 - https://github.com/wpm/Astar-Maze-Solver
 - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
 - https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp
J Kishore kumar.
On Sat, Jun 25, 2011 at 12:36 AM, Kishore Kumar <justjkk at gmail.com> wrote:
> This is the fifth week's report.
> Things done in the fifth week:
> * Finished reading Research Report of OpenTripPlanner.
> * Sketched a rough algorithm for scheduled routing which internally
> uses pgrouting A-star SQL function or A-star from boost library.
> Related/Unrelated activities:
> * Modifying pgRouting core library's A-star function to be more generic.
> * Played with OSM API by writing a Ruby on Rails web app that connects
> via OAuth.
> Things to be finished by next week:
> * Quickly finish or hibernate modifications to pgRouting core library.
> * Finish Implementing scheduled routing function.
> * Write documentation and tests for the implemented functions.
> Oh, I guess this report looks ugly without any reference links. Hope
> to get more links next week.
> J Kishore kumar.
> On Sat, Jun 18, 2011 at 1:43 AM, Kishore Kumar <justjkk at gmail.com> wrote:
>> This is the fourth week's report for my project.
>> Things done in the fourth week:
>> * Tweaked the pl/pgsql prototype for non-scheduled routing to accept
>> GTFS formatted data.
>> * Discussed on the list regarding the optimality of the implementation
>> and the problems.
>> * Worked on the flask app:
>> * generated GTFS for Chennai bus routes with frequency
>> * modified frontend to call non-scheduled routing function and
>> display results. Can be tested live here
>> * Daniel pointed me to a very useful resource, a research report of
>> OpenTripPlanner. Reading it.
>> Things to be finished by next week:
>> * Finish reading .
>> * Start developing scheduled routing algorithm.
>> * Write wrappers and tests for non-scheduled routing.
>> * Start writing documentation for wrappers and core functions.
>> * The OpenTripPlanner shares the same goal as this project or bigger.
>> Need to discuss whether these two projects can help each other in any
>> way. Like the possibility of rewriting the routing engine of OTP with
>> pgrouting version, etc..
>> J Kishore kumar.
>>  - https://github.com/pgRouting/pgrouting/commit/657164066784c06e6ca0d98662d7951e3b096993
>>  - http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000315.html
>>  - https://github.com/justjkk/dotpath/commit/730120bf602697af1012528730e7f05c28f2fe3a
>>  - http://busroutemaps.in/mtc-nonsc
>>  - http://www.nctr.usf.edu/wp-content/uploads/2011/06/77926.pdf
>>  - http://opentripplanner.com/
>> On Sat, Jun 11, 2011 at 12:59 AM, Kishore Kumar <justjkk at gmail.com> wrote:
>>> This is the third week's report for my project.
>>> Things done in the third week:
>>> * Sketched algorithm and table structure for solving Non-scheduled
>>> routing problem.
>>> * Writing a pure pl/pgsql function as a prototype implementing the
>>> non-scheduled routing function to test the algorithm and
>>> Things to be finished by next week:
>>> * Finalize algorithm for non-scheduled routing using the prototype.
>>> * Implement Non-scheduled routing core function either in c if necessary.
>>> * Write wrapper SQL functions for Non-scheduled routing function
>>> covering major use cases.
>>>  - http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000294.html
>>>  - https://github.com/pgRouting/pgrouting/commit/169cdf25da6235ccec4a73a8e03a164bfe8f780d
>>> On Fri, Jun 3, 2011 at 10:27 PM, Kishore Kumar <justjkk at gmail.com> wrote:
>>>> Wow, the last week went too fast and I'm presenting my second week report
>>>> with this mail.
>>>> Things done in the second week:
>>>> * Collected more GTFS data through chennai-rail-gtfs project.
>>>> * Finalized database topology and confirmed with mentor.
>>>> * Wrote a couple of test cases for testing the SQL functions.
>>>> Things to finish by next week:
>>>> * To sketch the public transit routing algorithm as a modified a_star
>>>> * To implement sm_public_transit_route function in c.
>>>> * Couldn't find enough time till today to finish this week's objectives.
>>>> This resulted in cutting down on writing tests. Should write tests alongside
>>>>  - https://github.com/justjkk/chennai-rail-gtfs
>>>>  - http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000266.html
>>>> - https://github.com/justjkk/pgrouting/commit/54b5a24fa8b8d88a25d42d161357ea79237861af
>>>> Thanks & Regards,
>>>> J Kishore kumar.
>>>> On Fri, May 27, 2011 at 11:58 PM, Kishore Kumar <justjkk at gmail.com> wrote:
>>>>> I am J Kishore kumar. My GSoC project aims to add public transport routing
>>>>> functionality to the pgRouting library. All project related documents are
>>>>> linked and managed through this wiki page. Following is the first week
>>>>> report of this project.
>>>>> Things done before first week(till May 23rd):
>>>>> * Discussed with pgRouting developers regarding the feasibility of the
>>>>> project and algorithms.
>>>>> * Implemented unit testing infrastructure for testing the existing code
>>>>> * Created a small flask application that uses pgRouting library and
>>>>> draws routes on a Openlayers map.
>>>>> * Started creating GTFS data for Chennai Railway network to use it in
>>>>> writing test cases for this transit library.
>>>>> Things done in the first week:
>>>>> * Added more trips and stop schedules that are converted from pdf
>>>>> documents released by railway authorities to .
>>>>> * Started with actual transit module code and debugging.
>>>>> * Adding more route's trips to (yet to commit).
>>>>> Things to finish by next week:
>>>>> * Discuss with mentor and finalise database topology(current topology is a
>>>>> subset of GTFS without support for fare).
>>>>> * Write tests for single modal transit route functions(thus deciding what
>>>>> are the input and output parameters).
>>>>> * Debugging c code written for postgresql functions is very hard. Should
>>>>> learn debugging techniques from project developers.
>>>>> * Marriage function in family has diverted me from spending more time.
>>>>> Will become better in a week.
>>>>> J Kishore kumar.
>>>>>  -
>>>>> - https://github.com/pgRouting/pgrouting/wiki/Automated-Testing-%28Unit-Tests%29
>>>>>  - https://github.com/justjkk/dotpath
>>>>>  - https://github.com/justjkk/chennai-rail-gtfs
>>>>>  - https://github.com/pgRouting/pgrouting/tree/gsoc-multimodal
More information about the SoC