[pgrouting-dev] Non-scheduled Routing algorithm

[Jay Mahadeokar]

Hi Kishore,

My reply inline:

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

> Hi,
>
> I was working on solving the Non-scheduled Routing problem. I made notes in
> the GSoC spiral book and attached them here.
>
> Non-scheduled Routing - It is primarily to be used for public transport
> routing where the absolute timetable of trips is not available or when the
> vehicles themselves don't follow any schedule.
>
> Type of Output:
> There are two kinds of outputs I can imagine.
> (a). List the Changeovers[1] that have maximum frequency and minimize the
> total travel time and then find Route numbers serving from one Changeover to
> another. Eg: http://busroutes.in/chennai/path/1859/1976/
> (b). Find and return a single sequence of routes corresponding to least
> total travel time.
>
> While output (a) gives more route numbers and calculates and dilutes the
> expected total travel time, output (b) gives more accurate total travel
> time.
> The problem with output (b) is that it ignores any alternate routes serving
> any successive changeovers and only takes the one with least travel time.
> Hence, I decided to go with output (a).
>
> To get a list of changeovers, two graphs should be generated from GTFS
> input:
> * Frequency Graph - effective frequency between any two stops
> * Travel Time Graph - expected travel time between any two stops
>
> And, the algorithm to find the changeovers:
> * Initially, store the direct travel time from source to destination as
> cutoff.
> * Explore the state-space of stops by exploring stops with small travel
> time first.
> * Update cutoff value as the shortest travel time to destination.
> * Prune the branches at cutoff.
> * After all branches are pruned, return the path corresponding to the
> cutoff travel time as the sequence of changeovers.
>
>
Let me rephrase the problem. Please tell me if I understood it correctly..

So, the input to your algorithm is a graph, where nodes are the stops, and
edges are the travel times between stops. The edges can be only traversed
(i.e they actually exist) at certain time instances.

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.

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.


I hope I am not missing any point here. Please correct me if I am wrong.
Also any clarification needed?


> After the sequence of changeovers is calculated, it is trivial to get the
> list of routes that serve between them.
>
> Performance:
> Let n be the number of stops and m be the number of trips,
> * Generating Frequency Graph and Travel Time Graph from the GTFS input have
> an ϑ(n^2) space complexity and ϑ(n^2 * m) time complexity.
> * Finding the list of changeovers has an O(n!) time complexity[worst case]
> and o(n) in the best case.
>
> I am no algo expert and cannot think of a better performing algorithm.
> Thoughts on this?
>
> Thanks & Regards,
> J Kishore kumar.
>
> [1] - Changeover is an intermediate stop where the passenger gets down from
> one vehicle and boards another vehicle bound to a different route.
>
> _______________________________________________
> 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/71f837ae/attachment.html