[pgrouting-dev] Non-scheduled Routing algorithm

[Kishore Kumar]

Jay,
Thanks for commenting on this issue. Inline response below:

On Wed, Jun 8, 2011 at 3:58 PM, Jay Mahadeokar <jai.mahadeokar at gmail.com> wrote:
>
> Ex - If frequency of edge u-> v is 2 hours. One departure was at 12:00 PM.
> Then if you arrive at u at 12:30 PM, then your changeover time at u will be
> 1:30 mins. Since, next departure is only possible at 2 pm.

Not really. The data we are dealing with is non-scheduled trips data.
So, we cannot say the changeover time as 1:30 mins. Instead, consider
the service follows a Uniform Distribution and get the mean waiting
time as half of the headway seconds(i.e, Changeover time penalty = 1
hour). I'm also solving scheduled routing problem(easier than this)
but that is 2 weeks later.

> So, I think this can be again reduced to a variant time-dependent dijkstra
> algorithm.
>
> The only difference being - your travel_time is now constant for each edge,
> But your change_over time depends on the time at which your dijkstra search
> starts. So, the algorithm should again take O(m + n log n) time. You need to
> modify dijkstra to suit your need.
>

Again, this algorithm is not time-dependent(or I don't see it). So, a
non-scheduled routing query returns the same result independent of
whether the time of the day is 5am or 9am.

Let me try implement the algorithm tonight and get back if I encounter
a deadend.

Thanks,
J Kishore kumar.