[pgrouting-dev] Scheduled Routing Algorithm

[Kishore Kumar]

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
>