[SoC] Re: Multi-modal public transit routing for pgRouting

Fri Jul 8 14:04:29 EDT 2011

Hi,
Here is the seventh week's report.

Things done in the seventh week:
* Learnt a lot about Generic programming, Boost Graph library and Eclipse CDT.
* Successfully coded astar search on Implicit graphs using Boost library[1].

Pending task:
* Writing the code to connect user facing SQL function to scheduled
route c++ function.

[1] - https://github.com/pgRouting/pgrouting/commit/3aa2b4e951c584fa3ae03235f7b2e06379cbb229

Thanks,
J Kishore kumar.

On Sat, Jul 2, 2011 at 1:29 AM, Kishore Kumar <justjkk at gmail.com> wrote:
> Hi,
> 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
> problem.[1][2][3]
> * Came up with a plan to use Implicit Graph and directly code using
> boost library.[4]
> * Spent a large chunk of time learning to use Boost library using code
> examples.[5][6][7]
>
> 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.
>
> Side-notes:
> * 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[8]. So, the more efficient code/algorithm
> will replace the other in the coming months.
>
> [1] - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
> [2] - http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
> [3] - http://en.wikipedia.org/wiki/Implicit_graph
> [4] - http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000342.html
> [5] - https://github.com/wpm/Boost-Implicit-Graph-Example
> [6] - https://github.com/wpm/Astar-Maze-Solver
> [7] - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
> [8] - https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp
>
> Thanks,
> J Kishore kumar.
>
> On Sat, Jun 25, 2011 at 12:36 AM, Kishore Kumar <justjkk at gmail.com> wrote:
>> Hi,
>> 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.
>>
>> Thanks,
>> J Kishore kumar.
>>
>> On Sat, Jun 18, 2011 at 1:43 AM, Kishore Kumar <justjkk at gmail.com> wrote:
>>> HI,
>>> 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.[1]
>>> * Discussed on the list regarding the optimality of the implementation
>>> and the problems.[2]
>>> * Worked on the flask app:
>>>  * generated GTFS for Chennai bus routes with frequency[3]
>>>  * modified frontend to call non-scheduled routing function and
>>> display results. Can be tested live here[4]
>>> * Daniel pointed me to a very useful resource, a research report[5] of
>>> OpenTripPlanner[6]. Reading it.
>>>
>>> Things to be finished by next week:
>>> * Finish reading [5].
>>> * Start developing scheduled routing algorithm.
>>> * Write wrappers and tests for non-scheduled routing.
>>> * Start writing documentation for wrappers and core functions.
>>>
>>> Roadblocks/Issues:
>>> * 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..
>>>
>>> Thanks,
>>> J Kishore kumar.
>>>
>>> [1] - https://github.com/pgRouting/pgrouting/commit/657164066784c06e6ca0d98662d7951e3b096993
>>> [2] - http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000315.html
>>> [3] - https://github.com/justjkk/dotpath/commit/730120bf602697af1012528730e7f05c28f2fe3a
>>> [4] - http://busroutemaps.in/mtc-nonsc
>>> [5] - http://www.nctr.usf.edu/wp-content/uploads/2011/06/77926.pdf
>>> [6] - http://opentripplanner.com/
>>>
>>> On Sat, Jun 11, 2011 at 12:59 AM, Kishore Kumar <justjkk at gmail.com> wrote:
>>>> Hi,
>>>> 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[1].
>>>> * Writing a pure pl/pgsql function as a prototype implementing the
>>>> non-scheduled routing function to test the algorithm and
>>>> efficiency[2].
>>>>
>>>> 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.
>>>>
>>>> [1] - http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000294.html
>>>> [2] - https://github.com/pgRouting/pgrouting/commit/169cdf25da6235ccec4a73a8e03a164bfe8f780d
>>>>
>>>> On Fri, Jun 3, 2011 at 10:27 PM, Kishore Kumar <justjkk at gmail.com> wrote:
>>>>> Hi,
>>>>> 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[1] project.
>>>>> * Finalized database topology and confirmed[2] with mentor.
>>>>> * Wrote a couple of test cases for testing the SQL functions[3].
>>>>> 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.
>>>>> Roadblocks:
>>>>> * 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
>>>>> implementation.
>>>>> [1] - https://github.com/justjkk/chennai-rail-gtfs
>>>>> [2] - http://lists.osgeo.org/pipermail/pgrouting-dev/2011-June/000266.html
>>>>> [3]
>>>>> - 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:
>>>>>>
>>>>>> Hi,
>>>>>> 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[1]. 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[2] for testing the existing code
>>>>>> base.
>>>>>> * Created a small flask application[3] that uses pgRouting library and
>>>>>> draws routes on a Openlayers map.
>>>>>> * Started creating GTFS data for Chennai Railway network[4] 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 [4].
>>>>>> * Started with actual transit module code[5] and debugging.
>>>>>> * Adding more route's trips to [4](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).
>>>>>> Roadblocks:
>>>>>> * 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.
>>>>>> Thanks,
>>>>>> J Kishore kumar.
>>>>>> http://twitter.com/justjkk
>>>>>> [1] -
>>>>>> https://github.com/pgRouting/pgrouting/wiki/Multi-modal-Public-Transit-Routing
>>>>>> [2]
>>>>>> - https://github.com/pgRouting/pgrouting/wiki/Automated-Testing-%28Unit-Tests%29
>>>>>> [3] - https://github.com/justjkk/dotpath
>>>>>> [4] - https://github.com/justjkk/chennai-rail-gtfs
>>>>>> [5] - https://github.com/pgRouting/pgrouting/tree/gsoc-multimodal
>>>>>
>>>>
>>>
>>
>