[pgrouting-dev] Non-scheduled Routing algorithm

[Jay Mahadeokar]

On Wed, Jun 8, 2011 at 6:49 PM, Kishore Kumar <justjkk at gmail.com> wrote:

> 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.
>
>
Hi Kishore,

Seems that I am not able to understand the problem statement clearly. Can
you explain it in more detail? Maybe along with Steve's query.

I am quite curious since you mentioned the worst-case complexity as O(n!).
Almost all problems that exist today which are treated as hardest (NP-hard
problems) can be solved in exponential time worst case i.e O(c^n). (Sorry
for mentioning too much theory here :-) )
Even this exponential bound is better than the factorial time bound! [1].
So, I have a feeling that the problem you are dealing with can be solved in
better worst case bound.

Maybe you can give one example of input and the desired output which can
make things clearer.

[1] http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions


>
> 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.
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>



-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110608/75398885/attachment.html