[pgrouting-dev] Scheduled Routing Algorithm
justjkk at gmail.com
Mon Jun 27 17:40:12 EDT 2011
After reading on Contraction Hierarchies 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 function passing an Implicit
Graph 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
I didn't find any examples using astar_search_no_init function. 
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.
J Kishore kumar.
 - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
 - http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html
 - http://en.wikipedia.org/wiki/Implicit_graph
 - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
More information about the pgrouting-dev