[pgrouting-dev] Non-scheduled Routing algorithm

[Stephen Woodbridge]

Hi Kishore,

What is a real life example of a non-scheduled trips?
Is this for example bus lines that run on a schedule, but you are trying 
to compute the best route and change overs independent of knowing a 
start time?

If so, would you want to deal with the fact the day time schedules might 
run at a higher frequency the say night time schedules or say rush hour 
schedules. I this case you might want more information about when this 
non-scheduled trip will take place so you can use the correct frequency 
tables.

-Steve

On 6/8/2011 9:19 AM, Kishore Kumar 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.
>
>> 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