<br><br><div class="gmail_quote">On Wed, Jun 8, 2011 at 6:49 PM, Kishore Kumar <span dir="ltr"><<a href="mailto:justjkk@gmail.com">justjkk@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Jay,<br>
Thanks for commenting on this issue. Inline response below:<br>
<div class="im"><br>
On Wed, Jun 8, 2011 at 3:58 PM, Jay Mahadeokar <<a href="mailto:jai.mahadeokar@gmail.com">jai.mahadeokar@gmail.com</a>> wrote:<br>
><br>
> Ex - If frequency of edge u-> v is 2 hours. One departure was at 12:00 PM.<br>
> Then if you arrive at u at 12:30 PM, then your changeover time at u will be<br>
> 1:30 mins. Since, next departure is only possible at 2 pm.<br>
<br>
</div>Not really. The data we are dealing with is non-scheduled trips data.<br>
So, we cannot say the changeover time as 1:30 mins. Instead, consider<br>
the service follows a Uniform Distribution and get the mean waiting<br>
time as half of the headway seconds(i.e, Changeover time penalty = 1<br>
hour). I'm also solving scheduled routing problem(easier than this)<br>
but that is 2 weeks later.<br>
<div><br></div></blockquote><div><br>Hi Kishore,<br><br>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.<br><br>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 :-) ) <br>
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. <br><br>Maybe you can give one example of input and the desired output which can make things clearer.<br>
<br>[1] <a href="http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions">http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions</a> <br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div> </div></blockquote><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">
> So, I think this can be again reduced to a variant time-dependent dijkstra<br>
> algorithm.<br>
><br>
> The only difference being - your travel_time is now constant for each edge,<br>
> But your change_over time depends on the time at which your dijkstra search<br>
> starts. So, the algorithm should again take O(m + n log n) time. You need to<br>
> modify dijkstra to suit your need.<br>
><br>
<br>
</div>Again, this algorithm is not time-dependent(or I don't see it). So, a<br>
non-scheduled routing query returns the same result independent of<br>
whether the time of the day is 5am or 9am.<br>
<br>
Let me try implement the algorithm tonight and get back if I encounter<br>
a deadend.<br>
<br>
Thanks,<br>
J Kishore kumar.<br>
<div><div></div><div class="h5">_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>