[pgrouting-dev] Re: Non-scheduled Routing algorithm

[Kishore Kumar]

Mailman ate my Richtext message again. :(

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.

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.