[pgrouting-dev] Scheduled Routing Algorithm

[Stephen Woodbridge]

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