Re: Where to start, graphs and routing.

Hi,

On 14 August 2011 20:25, k_b <k_b0000(at)yahoo(dot)se> wrote:
> Hi.
> For learning purpose i would like to make a small database with a small
> graph of locations, roads and public transport information.
> Then calculate the fastest or cheapest way between two points.
>
> If we think of a minimal network, as below.
>
> A ---5-- B ---10---- C
>  \                 /
>  \---------5-----/

Welcome in the club! I've been there and I can say that is very
interesting exercise. My schema was simple:
- bus stop table: just list of all bus stop and related meta data
(like this bus stop is part of transit centre X, ...)
- schedule table: contains all possible combination how to travel
between two adjacent stops: (stopA, stopB, timeA, timeB, route_n).
Table had several million rows which was necessary because of the
following anomalies:
* A -> B could be 5 min but B -> A could be less or more
* peak / off peak / weekend schedule could be different
* you can take bus A -> B -> C but on the way back bus doesn't serve
stop B (ie C -> A)

It would be possible to limit number of row in that table using
smarter encoding system for bus departure/arrival times. I didn't use
it because I generated that table from official timetables.

queries were simple; first query was something like this
select * from schedule_table where stopA = :start
then for each row from the previous query (and repeat this query):
select * from schedule_table where stopA = :stopB and timeA <
result_timeB + :threshold

After the second, third, ... query I did the following checks:
- merge parts with the same bus number (ie A -> B, B -> C => A -> C)
- increment waiting/transfer and total travel time accordingly
- remove stupid routes. This part is quite tricky and some heuristics
is needed. I removed routes with many service changes and excessive
waiting/travel times

Today, I would try to use Postgres spatial data types/extensions
because you can get bus stop locations from openstreetmap (or google
maps). Moreover you can exclude bus stops (or complete routes) which
are too far from from/to locations (again, some heuristics/rules could
be necessary)

--
Ondrej Ivanic
(ondrej(dot)ivanic(at)gmail(dot)com)