Thread: Where to start, graphs and routing.

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-----/


To travel from A to C can be done in two ways, either via B at a total cost of 15, or directly at a cost of 5.
Let's now say that there are tow buses, one travelling A-B-C and one travelling A-C.
Lets say the departure schedule from A is:

bus A-B-C:
leaves A: 10:00, arrives C 10:15.
leaves A: 11:00, arrives C 11:15.


bus A-C  :
leaves A 10:15, arrives C 10:20.
leaves A 11:05, arrives C 11:10.



To get started somewhere i have a few questions about how to make the data model, etc.
1.
What is a good practice, having the graph represent
a) the roads and bus stops,
b) the graph to represent the bus routes and stops, or
c) having the graph to represent every single bus trip (for each departure)?

b) feels quite natural as the network gets smaller, but how do i then represent each and every tip made on the route?
Eg. the bus departures on the route once per hour.



2.
What are the minimum information i need about the graph?
Nodes (stops), edges (travel way), neighbour list of some sort, and some sort of cost to ride on a edge.
Anything else. Direction information?


3.
Is it possible to write recursive SQL in PostgreSQL without using procedural language? How, are there examples?


4.
How do i handle waiting time from the start point, or arrival time to destination?
As an example i don't want the result to be only trips with A-C (as this is cheepest path),
instead i want both options because sometimes A-B-C will bring me to the destination earlier
then A-C, and sometimes it is good to wait for A-C even though there is A-B-C departuring earlier.

if time is 09:55 -> take A-B-C. (obvious).
if time is 10:01 -> take A-C. (obvious).
if time is 10:55 -> take A-C. (not obvious).


5.
Last question, are theree any books covering topics like this?



Thank you.

karl

Hi,

On 14 August 2011 20:25, k_b <k_b0000@yahoo.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.ivanic@gmail.com)

Ondrej Ivanič <ondrej.ivanic <at> gmail.com> writes:

> On 14 August 2011 20:25, k_b <k_b0000 <at> yahoo.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.

You might want to take a look at PG Routing, which seems to be maturing quite
nicely and folded into the PostGIS tribe:  http://www.pgrouting.org/

Sorry for noise if you already know about it a...