[pgrouting-dev] Non-scheduled Routing algorithm

[Kishore Kumar]

Sorry I have calculated the complexity wrongly. And, since the
existing Dijkstra is sufficient, I linked to it here:
https://github.com/pgRouting/pgrouting/blob/gsoc-multimodal/extra/transit/sql/nonscheduled.sql#L42

There's a test case that passes the current implementation:
https://github.com/pgRouting/pgrouting/blob/gsoc-multimodal/tests/test_transit.py#L28

Thanks & Regards,
J Kishore kumar.

On Wed, Jun 8, 2011 at 9:46 PM, Jay Mahadeokar <jai.mahadeokar at gmail.com> wrote:
>
>
> 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
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>