[pgrouting-dev] Time dependent data and input format

Jay Mahadeokar jai.mahadeokar at gmail.com
Wed Jun 8 23:46:35 EDT 2011


Just a recap to our planned tdsp query model:

I agree. So, now can we assume we have following database tables, as per
> things discussed till now:
>    1. Ways: (On lines of the one in pgrouting-workshop)
>    - gid
>    - source
>    - target
>    - name
>    - the_geom
>    - static_length    (In case time dependent routing is not used)
>    - any other attributes..
>     2.  TimeVaryingCosts (Any other suitable name?)
>    - gid
>    - start_time_and_date  (May divide this into two columns: day_of_week
>    and time_of_day ? )
>    - travel_time / arrival_time
>     3. TurnRestrictions (Time dependent)
>    - node/source
>    - time_from
>    - time_to
>    - node_to
>    - ancestors
> If only static shortest path query is made, then only table 1 is required.
> If time-dependent shortest path query is made, table 1 and 2 will be used.
> If in time-dependent shortest path query with turn restrictions is made ,
> all 3 tables will be used.

So, for a general time dependent query, we will fetch edge information from
ways table and the time dependent costs information from the
TimeDepCosts table. (See previous msg above.)

The query on ways table can be supplied by the usual as on normal dijkstra
shortest_path() query.

How do we form the query on the TimeDepCosts table? I see two options:

1. We generate the query according to the gids obtained from the query on
ways table. We will have to query all the time slots available, or form a
query so that the time-window is appropriate and we have sufficient
travel_time info so that we can reach destination.

Here we can form query like

Select * from TimeDepCosts where gid in (list of gids queried from ways

We can allow user to more filtering parameters according to start_time ,
date ?
But this will make our query specific to the database design. As already
discussed, we cant predict the time units / requirements of applications and
so it would be better if we keep the query independent of the database

Thats the reason our weight_map assumes start time from source as 0, and all
travel times offset from the start time from source. A function that will
generate such weight map is to be written.

2. We allow user to pass the query for TimeDepCosts table too. So, we will
have our pgsql function as:

                                                ways_sql text,
                                                time_dep_cost_sql text,
                                                source_id integer,
                                                target_id integer,
                                                directed boolean,
                                                has_reverse_cost boolean)
        RETURNS SETOF path_result

This way, user can have more control on the amount of data being queried. We
will only consider the time dependent windows that fit the query.

Example of the time_dep_cost_sql can be:

Select * from TimeDepCosts where " USER_SUPPLIED_CONSTRAINTS".

The user can now supply his constraints according to time_window he needs,
start times, holidays etc according to the database table design.

The problem with this is, we cannot filter out edges according to bounding
box etc since the_geom field is not there in this table. This is because
that information would be redundant.

Thoughts? Any idea that combines the merits of both approaches?

-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110609/5c792bb5/attachment-0001.html

More information about the pgrouting-dev mailing list