[pgrouting-dev] Non-scheduled Routing algorithm

[Kishore Kumar]

Hi,

Sorry to respond late. Non-scheduled trips are trips that have no
strict timetable. For eg, In India, most of the bus transport
authorities follow no timetable for trips. The time at which a bus
starts is at the sole discretion of the Driver but the Agency dictates
how many trips have to made per day. Thus, we have frequency of trips
but no absolute arrival and departure times.

Peak and Slack frequency affects all routes similarly. So, I guess
peak hour routing and slack hour routing will return almost the same
result. Though, it is possible to accept a time window as a parameter
and give the route corresponding to appropriate frequency. But, that
is more complex.

Thanks & Regards,
J Kishore kumar.

On Wed, Jun 8, 2011 at 7:15 PM, Stephen Woodbridge
<woodbri at swoodbridge.com> wrote:
> 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
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>