[pgrouting-dev] Scheduled Routing Algorithm

[Kishore Kumar]

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
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mmptr_flowchart.pdf
Type: application/pdf
Size: 58391 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110810/24ad7995/mmptr_flowchart-0001.pdf