[pgrouting-dev] Scheduled Routing Algorithm

[Kishore Kumar]

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