<p>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 <a href="http://ad-wiki.informatik.uni-freiburg.de/teaching" rel="nofollow">I mention below</a>.</p>

<p>Also you should have a close look into <a href="http://ad.informatik.uni-freiburg.de/files/transferpatterns.pdf" rel="nofollow">transfer patterns</a> (used at google) and <a href="http://research.microsoft.com/apps/pubs/default.aspx?id=156567" rel="nofollow">RAPTOR</a> (used at microsoft). There is a nice introduction into transfer patterns <a href="http://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012" rel="nofollow">at university freiburg</a> in lectures 9-11. <a href="https://github.com/openplans/OpenTripPlanner/wiki/Raptor" rel="nofollow">RAPTOR is implemented</a> in OpenTripPlanner and later this year probably also in my GraphHopper project.</p>

<blockquote>
  <p>But the complication is that the shortest route may not be the fastest route to the destination.</p>
</blockquote>

<p>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 ...</p>

CC BY-SA 3.0
2013-05-09T12:22:43.840Z
Because they cannot be used as weights, you can't use the edges whenever you want but only on particular moments.
Kaveh
CC BY-SA 3.0
2013-05-09T21:56:50.503Z
When you model the graph in the time-independent way you don't have this problem.
Karussell
CC BY-SA 3.0
2013-05-10T00:58:12.990Z
It would be helpful if you explain how the problem can be modeled as a time-independent graph.
Kaveh
CC BY-SA 3.0
2013-05-09T10:34:23.927Z
2013-05-09T10:34:23.927Z
Karussell
<p>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. </p>

<p>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. </p>

<p>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.</p>

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

CC BY-SA 3.0
2013-05-03T14:00:21.397Z
One easy solution is dynamic programming. Compute if the passenger can be at location i at time t.
Kaveh
CC BY-SA 3.0
2013-05-03T15:44:30.893Z
can you elaborate further.
mkuse
CC BY-SA 3.0
2013-05-03T15:48:06.783Z
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 [cs.se] which has a broader scope.
Kaveh
<graph-theory><graph-algorithms>
Designing a Transport network path suggestion tool
mkuse
# Designing a Transport network path suggestion tool

(Asked by: username_0 on 2013-05-03)

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.

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: One easy solution is dynamic programming. Compute if the passenger can be at location i at time t.  
> **username_0**: can you elaborate further.  
> **username_1**: 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 [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_2 on 2013-05-09. Score: -1

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](http://ad-wiki.informatik.uni-freiburg.de/teaching).

Also you should have a close look into [transfer patterns](http://ad.informatik.uni-freiburg.de/files/transferpatterns.pdf) (used at google) and [RAPTOR](http://research.microsoft.com/apps/pubs/default.aspx?id=156567) (used at microsoft). There is a nice introduction into transfer patterns [at university freiburg](http://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012) in lectures 9-11. [RAPTOR is implemented](https://github.com/openplans/OpenTripPlanner/wiki/Raptor) 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 ...

> **Comments:**
> **username_1**: Because they cannot be used as weights, you can't use the edges whenever you want but only on particular moments.  
> **username_2**: When you model the graph in the time-independent way you don't have this problem.  
> **username_1**: It would be helpful if you explain how the problem can be modeled as a time-independent graph.  

---

