[pgrouting-dev] Time dependent data and input format

[Stephen Woodbridge]

On 6/11/2011 12:58 PM, Jay Mahadeokar wrote:
>
>
> On Thu, Jun 9, 2011 at 9:16 AM, Jay Mahadeokar <jai.mahadeokar at gmail.com
> <mailto:jai.mahadeokar at gmail.com>> wrote:
>
>     Hi,
>
>     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 table).
>
>     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 design.
>
>     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:
>
>     CREATE  OR  REPLACE  FUNCTION  shortest_path(
>                                                      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?
>
>
>
> Hi all,
>
> I am writing some background code will be needed for the above
> functionality.
>
> Any input on the above mentioned point? I suppose I should not start
> coding for any specific approach until we agree upon a viable query
> strategy.

Hi Jay,

I always find it easiest to answer these questions by thinking about the 
problem in terms of use cases, so:

A web app, where someone enters a start and destination and some 
constraints like departure time or arrival time and maybe restrictions 
on modes of travel.

Are there other ones we are trying to support? These should probably be 
documented as part of the project description.

Anyway, assuming the above, then the application which presumably has 
some basic knowledge of the time constraints could do something like:

Get the straight line distance between start and destination double it 
and apply some average transportation speed to approximate the time 
window. The numbers can be changed to be acceptable by the application 
as long as it over estimates the duration of travel. It can then, 
specify the CONSTRAINTS in terms of a start and end time. We do 
something similar with our spatial bounding box used to collect the 
edges needed to build the graph.

Now as far as collecting the constraints and making then accessible for 
the Boost_dijkstra, that is another problem. This problem boils down to 
the following:

1. is there an acceptable abstraction that we can use internally to 
represent various data sets that we might want to load. Or can we define 
a schema that will work for some set of constraints we wish to implement 
initially.
2. do want to move this data into some static memory structures for the 
analysis like we do for the graph and then dispose of them after the 
analysis.
3. or do we want to construct a method that can dynamically request 
constraint information from the database when it is needed by a visitor. 
(2. is probably much more efficient and the better way to go from a 
complexity and stability point of view).

Don't wait on me for additional input as I will be gone through June 
21st. Keep it simple and modular and we can change or add to it in the 
future and I;m sure whatever you come up with will be fine. After all it 
is code and it can be changed it we need to. :)

Project seems to be moving along fine.

-Steve