0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ One easy solution is dynamic programming. Compute if the passenger can be at location i at time t. $\endgroup$ – Kaveh May 3 '13 at 14:00
  • $\begingroup$ can you elaborate further. $\endgroup$ – mkuse May 3 '13 at 15:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh May 3 '13 at 15:48
-1
$\begingroup$

The obvious way of doing this is via time-dependent or time-independent graphs where you run a Dijkstra on it. This is also described in the lectures I mention below.

Also you should have a close look into transfer patterns (used at google) and RAPTOR (used at microsoft). There is a nice introduction into transfer patterns at university freiburg in lectures 9-11. RAPTOR is implemented in OpenTripPlanner and later this year probably also in my GraphHopper project.

But the complication is that the shortest route may not be the fastest route to the destination.

Of course, but why not just use the time as weight instead of the distance? So 'shortest' and 'fastest' is not really a big difference ...

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Because they cannot be used as weights, you can't use the edges whenever you want but only on particular moments. $\endgroup$ – Kaveh May 9 '13 at 12:22
  • $\begingroup$ When you model the graph in the time-independent way you don't have this problem. $\endgroup$ – Karussell May 9 '13 at 21:56
  • $\begingroup$ It would be helpful if you explain how the problem can be modeled as a time-independent graph. $\endgroup$ – Kaveh May 10 '13 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.