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

Kishore Kumar justjkk at gmail.com
Fri Aug 19 14:21:25 EDT 2011 

Hi,
This is my thirteenth weekly report.

Things done in the thirteenth week:
* Finished implementing multi-modal routing.[1]
* Refactored code with optimizations.
* Written gtfs2pgrouting, a data importer to be used to populate the
database.[2]
* Writing documentation and tutorial.

Things to be done by 22nd August:
* Complete documentation and tutorial.
* Prepare a demo in dotpath[3].

[1] - https://github.com/pgRouting/pgrouting/commit/40a5a8109571ade70bac15fad33b4d26d517d80f
[2] - https://github.com/justjkk/gtfs2pgrouting
[3] - https://github.com/justjkk/dotpath

Thanks,
J Kishore kumar.

On Sat, Aug 13, 2011 at 12:04 AM, Kishore Kumar <justjkk at gmail.com> wrote:
> Hi,
> This is my twelfth weekly report.
>
> Things done in the twelfth week:
> *  Implemented All pair shortest path algorithm as a separate branch.[1]
> * Used APSP in finding closure of shortest time heuristic.[2]
> * Implementing multi-modal routing.
>
> Things to be done by 15th August:
> * Finish implementing multi-modal routing.
>
> Things to be done for next week:
> * Start writing documentation, Code refactoring.
>
> [1] - https://github.com/pgRouting/pgrouting/tree/apsp-johnson
> [2] - https://github.com/pgRouting/pgrouting/commit/cb297ca2cd7d34820d063367fb31b78b5e83c8ce
>
> Thanks & Regards,
> J Kishore kumar.
>
> On Sat, Aug 6, 2011 at 1:36 AM, Kishore Kumar <justjkk at gmail.com> wrote:
>> Hi,
>> This is my eleventh week's report.
>>
>> Things done in the eleventh week:
>> * Implementing Johnson All Pairs Shortest Paths algorithm[1] for
>> computing shortest path heuristic in scheduled route algorithm.
>>
>> Things to be finished by next week:
>> * Finish implementation of Multimodal routing.
>>
>> [1] - http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/johnson_all_pairs_shortest.html
>>
>> Thanks,
>> J Kishore kumar.
>>
>> On Sat, Jul 30, 2011 at 12:48 AM, Kishore Kumar <justjkk at gmail.com> wrote:
>>> Hi,
>>> This is my tenth week's report.
>>>
>>> Things done in the tenth week:
>>> * Fixed Sub-optimal routing in the scheduled routing.[1]
>>> * Implementing multi-modal routing.
>>>
>>> Things to be finished by next week:
>>> * Complete implementation of multimodal routing.
>>> * Write documentation on using the functions.
>>>
>>> Roadblocks:
>>> * I'm attending Yahoo! Openhack this weekend. Must be back on track by Monday.
>>>
>>> Thanks,
>>> J Kishore kumar.
>>>
>>> [1] - https://github.com/pgRouting/pgrouting/commit/f8dc0f455905d9dd4dde5b6b0cd03e61738d7c5d
>>>
>>> On Fri, Jul 22, 2011 at 9:25 PM, Kishore Kumar <justjkk at gmail.com> wrote:
>>>> Hi,
>>>> This is my ninth week's report.
>>>>
>>>> Things done in the ninth week:
>>>> * Debugged the scheduled route code and fixed the segfault.[1]
>>>> * Debugging the scheduled route code which produces sub-optimal route.
>>>> * Roughly planned a way to include non-scheduled data in scheduled
>>>> routing for a multi-modal solution.
>>>>
>>>> Things to be finished by next week:
>>>> * Pass all tests for scheduled routing.
>>>> * Implement multi-modal routing for all transit types(except walk).
>>>>
>>>> Notes:
>>>> * I'm falling behind my proposed schedule by about a week. Have to
>>>> catch up in the coming week.
>>>>
>>>> Thanks,
>>>> J Kishore kumar.
>>>>
>>>> [1] - https://github.com/pgRouting/pgrouting/commit/0744c589b13492171554603a432c666723161e11
>>>>
>>>> On Fri, Jul 15, 2011 at 9:32 PM, Kishore Kumar <justjkk at gmail.com> wrote:
>>>>> Hi,
>>>>> This is my eighth week's report.
>>>>>
>>>>> Things done in the eighth week:
>>>>> * Refactored scheduled route c++ function with database connecting
>>>>> code and have a segfaulting code.[1]
>>>>> * Tried debugging the source of segfault.[2]
>>>>>
>>>>> Agenda for next week:
>>>>> * Debug the scheduled route code.
>>>>> * Integrate nonscheduled routing into scheduled routing algorithm.
>>>>>
>>>>> Thanks,
>>>>> J Kishore kumar.
>>>>>
>>>>> [1] - https://github.com/pgRouting/pgrouting/commit/81ffc1ae1f065fa63e0f22f72e9549ce987a8758
>>>>> [2] - https://github.com/pgRouting/pgrouting/commit/081607527939a0363fcebcb543b59c6cafe566e9
>>>>>
>>>>> On Fri, Jul 8, 2011 at 11:34 PM, Kishore Kumar <justjkk at gmail.com> wrote:
>>>>>> 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
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>

More information about the SoC mailing list