Designing a Transport network path suggestion tool

I am working on a suggestion system to passengers on transits to take. The thing is we are formulating stations on a transport network (eg. bus transport) as nodes and route between spatially adjacent stations as edges. The weights on edges being the time it takes to reach between stations.

We are in search of route, a person should take if he/she desires to go from node A to node B. I am aware that I can use the shortest path problem to find a shortest route. But the complication is that the shortest route may not be the fastest route to the destination. This is because on the shortest route one of the leg of the journey has very low bus frequency and thus may take longer.

Let me elaborate it further. What I mean is that say A--C--B is the shortest route but the frequency of buses is hourly. But A--D--B is another route which is longer that A--C--B but has more frequency say once in 10 minutes. Thus in this case A--C--B is the desired route. It is quite clear that the standard shortest path may not give the desired result.

Can you suggest a solution to this problem? I was thinking may be detect all unique cycles involving node A & B. And compute actually required time (taking into account bus frequencies) on that route. But I am not sure how to go about this.

• One easy solution is dynamic programming. Compute if the passenger can be at location i at time t. – Kaveh May 3 '13 at 14:00
• can you elaborate further. – mkuse May 3 '13 at 15:44
• Let $V$ be the set of locations. For $i\in V$ and time $t$ (say $t$ min after the passenger departs), let $M[i,t]$ be one iff the passenger can be at location $i \in V$ at time $t$. ps: Please check our FAQ for the scope of cstheory, your question is probably more suitable for Computer Science which has a broader scope. – Kaveh May 3 '13 at 15:48