[pgrouting-dev] Scheduled Routing Algorithm

[Stephen Woodbridge]

Hi Kishore,

Very nice diagram! This really helps me understand more of what you have 
been doing in this project and how the scheduled routing works.

Thanks,
   -Steve

On 8/10/2011 8:27 AM, Kishore Kumar wrote:
> Hi,
> Prepared this diagram(attached) depicting the file structure and flow
> of control of scheduled routing algorithm. Currently the code works
> for GTFS Trips with fixed timetable(Eg:Train). To make it multi-modal,
> it has to support GTFS Trips with only frequency information(Eg:Bus)
> and private transit(Eg:Walk, Cycle). The existing scheduled routing
> can be extended a little by also including trips which have frequency
> information only. And, for walking to be private transit options,
> since the speed of transit is going to be a constant, the straight
> line distance from X to goal divided by constant velocity will give
> the shortest time heuristic. Hence, I'll possibly finish it in a day
> or two.
>
> Once that is finished, I'll start writing documentation, tests and
> demo implementations at http://busroutemaps.in/ and of course, Code
> cleanup and optimisations.
>
> Thanks,
> J Kishore kumar.
>
> On Sat, Jul 9, 2011 at 8:47 PM, Kishore Kumar<justjkk at gmail.com>  wrote:
>> Hi,
>>
>> I commited the code[1] that implements the scheduled route using
>> modified boost astar search and Implicit graph. And, I have an issue
>> now:
>> 1. The modified astar and breadth first search boost header files are
>> copied from Boost Version 1.46.1. I intent to test it on earlier boost
>> libraries. But, what is the best approach to handle this scenario?
>> Should we notify boost developers about having a non-const version to
>> support Implicit Graphs?
>>
>> Thanks,
>> J Kishore kumar.
>>
>> [1] - https://github.com/pgRouting/pgrouting/commit/3aa2b4e951c584fa3ae03235f7b2e06379cbb229
>>
>> On Tue, Jun 28, 2011 at 3:36 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com>  wrote:
>>> Hi Kishore,
>>>
>>> I not sure I can improve on this algorithm as I'm do not think I have
>>> followed all the details and issues in implementing it. But I do have two
>>> thoughts:
>>>
>>> 1. if you are not on the boost-users mailing list [1] them you should
>>> subscribe to that list and ask questions about how to best tackle some of
>>> the boost problems you are facing. In the Subject: add the tag "[BGL]" to
>>> indicate this is a Boost Graph Library question and the developers are very
>>> helpful and responsive to question.
>>>
>>> 2. often I find that it is useful to transform my problem into another
>>> problem that has a simpler or known solution. It seems like you should be
>>> able to do this with your problem. If I understand it correct (and I confess
>>> I might not), It seems that your frequency problem could be transformed into
>>> a straight scheduling problem if your transfer is just a waiting time at a
>>> transfer point. One simple way to represent these transfer times is to add
>>> an additional edge that has the cost of the transfer associated to it.
>>>
>>> So if we think about the route like, I start at a bus station at some time
>>> X, and there is some transfer cost representing the wait time W window. so
>>> I'm now on the the bus route at X+W+edge cost, and I continue accumulating
>>> wait times and edge costs as I trasfer between lines and travel the network
>>> to my destination. If this works, then this is just a straight time
>>> dependent solution but the trick is to analyze the data and create a network
>>> suitable for this type of solution.
>>>
>>> [1] http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>>
>>> -Steve
>>>
>>>
>>> On 6/27/2011 5:40 PM, Kishore Kumar wrote:
>>>>
>>>> Hi,
>>>>
>>>> After reading on Contraction Hierarchies[1] and APSP algorithms, I
>>>> came up with a plan to find the scheduled route. Here goes the plan:
>>>>
>>>> * Pre-compute Shortest Time Graph for Directly reachable pair of stops
>>>> by going through every trip in a loop.
>>>> * Find Shortest Time Graph from every stop to every other
>>>> stop(Transitive closure) using APSP.
>>>> * Use Boost astar_search_no_init[2] function passing an Implicit
>>>> Graph[3] G with following definitions:
>>>>       Vertex : (Stop, Time)
>>>>       Edge : Trip
>>>>       Edge weight : Travel Time + Waiting Time
>>>>       Heuristic : Shortest Time from Trip destination to Target
>>>> * As Every Vertex is expanded, new Vertices and Edges are generated
>>>> for trips in the next 1 hour(or whatever is the Upper limit for
>>>> Waiting time).
>>>>
>>>> I didn't find any examples using astar_search_no_init function. [4]
>>>> solves 8-puzzle problem using Implicit Graph for astar_search
>>>> function, but it uses astar_search function with a hacked BFS code.
>>>> So, it is going to be a challenge to code this out using BGL.
>>>>
>>>> Please advise on ways to improve the algorithm.
>>>>
>>>> Thanks,
>>>> J Kishore kumar.
>>>>
>>>> [1] - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
>>>> [2] -
>>>> http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html
>>>> [3] - http://en.wikipedia.org/wiki/Implicit_graph
>>>> [4] - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
>>>> _______________________________________________
>>>> pgrouting-dev mailing list
>>>> pgrouting-dev at lists.osgeo.org
>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>
>>> _______________________________________________
>>> pgrouting-dev mailing list
>>> pgrouting-dev at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>>
>>
>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev