[pgrouting-dev] Time dependent data and input format

[Jay Mahadeokar]

Hi all,

Steve, Daniel, thanks for the input.

Well, I have written the plsql function on lines of what you suggested, for
the data format that I had created earlier and it seems to be working for
now, with cyclic issue also taken into account and all times offset from
query_start_time.

I have updated the code in gsoc-tdsp repository[1] .

I also changed the existing tdsp.h, tdsp.c and weight_map.hpp files so that
end_time is also taken into account (I had written a more complex code
earlier and thought end_time was redundant and wasn't necessary, corrected
that now).

So, now basically the tdsp query expects a data from time_dep_costs table as
set of rows: edge_id, start_time, end_time, travel_time.

Example:

SELECT * FROM time_dependent_shortest_path('
                SELECT gid as id,
                         source::integer,
                         target::integer,
                         length::double precision as cost
                        FROM ways',
                81, 359, true, false,'select edge_id, start_time, end_time,
travel_time from pgr_get_time_dep_costs(''time_dep_costs'',14,12)',0);

Here 6th parameter is the nested pgr function.

I think there is no need to pass query_start_time to the main
time_dep_shortest_path function since we are passing it to nested function
and that will always be 0 in main query (parameter 7).

Also, the parameters is_directed and has_reverse_cost seem redundant, since
in this case graph will be always directed I think. So, maybe these can be
removed.

Next step would be to write similar plsql functions for most standard data
formats. If you can suggest the most obvious cases, I can start working on
that.

[1]
https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/extra/tdsp/sql/tdsp_data_wrappers.sql

On Tue, Jul 19, 2011 at 10:29 AM, Stephen Woodbridge <
woodbri at swoodbridge.com> wrote:

> On 7/19/2011 12:24 AM, Jay Mahadeokar wrote:
>
>>
>>
>> On Tue, Jul 19, 2011 at 9:05 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.**com<woodbri at swoodbridge.com>>>
>> wrote:
>>
>>    Jay, Daniel,
>>
>>    I think we need to get our heads around this or it will be very hard
>>    for Jay to complete this as a useful tool.
>>
>>
>>    Jay says:
>>
>>        What im not clear is, how do we package this in the overall
>>        pgRouting project?
>>
>>
>>    This is exactly the problem. So here is my 2 rupees :) on this:
>>
>>
>> Wow, that was innovative! :)
>>
>
> Well probably not, sorry that is what happens when I'm too tired and try to
> be cute. <sigh>
>
>
>
>>    I think the core algorithm needs to be generic so it works with any
>>    time frames that someone might want to use.
>>
>>
>> As far as I think, this part is ready.
>>
>>    Then we layer over that application implementations using wrappers
>>    or additional code. So since most people today are using pgRouting
>>    for vehicle routing applications I think we need to implement and
>>    easy to use wrapper that deals with vehicle applications of date and
>>    time of day dependencies. This does not preclude someone else coming
>>    in later and writing a new wrapper to deal with their application
>>    working in years or microsecond intervals.
>>
>>
>> Now, general pgRouting query is somewhat like this:
>>
>> 1. Pass parameters to pgRouting query
>> 2. Extract data from database according to sql parameter passed
>> 3. Generate the graph and other parameters using data extracted
>> 4. Pass data and other parameters to internal function
>> 5. Function calculates the result
>> 6. Convert the result into pgRouting result and return it.
>>
>>  So, we have steps 3,4,5 and 6 ready.
>>
>> For tdsp, In step 2 we need to query 2 tables separately. Query to table
>> ways will be generic.Query to table time_dep_costs, should take care of
>> cyclic nature and other things.
>>
>> We can have two approaches:
>>
>> 1. Take some specific case like day and time, and write down code that
>> will take care of above thing. When we bundle this for with pgRouting
>> the query will become specific to that format.
>> Whenever a new data format is there, someone will need to re-code step
>> 2. Since, this is internal to pgRouting, this cannot be done by
>> application developer. Then we would need to recompile whole thing as a
>> separate query before using it.
>>
>> 2. We could implement specific functions that can be used as query to
>> time_dep_costs. Those can be installed as separate pgRouting functions
>> itself. For simple applications where the data is in intervals of 24
>> hours, and cyclic we can just provide a postgres plsql function and it
>> should serve the function. I am not good at plsql, but I believe it is a
>> very flexible tool and can be used for complex data formats as well
>> (thoughts?)
>>
>> I think approach 2 is much better and it keeps the main tdsp query
>> independent of the data format. We just need to write plsql functions
>> for different data formats and supply those as sql argument to tdsp
>> query to retrieve data from time_dep_costs table.
>>
>> If you think this is a good approach, I can start learning plsql in
>> detail and work on writing retrieval functions for specific data formats.
>>
>> Is this model right? I can go ahead and start work on that.
>>
>
> Yes, I think approach 2 is the better model because application developer
> should not be required to recompile anything.
>
> plsql is very straight forward, and I think we can all help with the
> learning curve or even coding some of it if we have time. I think if you
> assume a set returning function then you have inputs and a record structure
> of your results. The function takes the inputs and returns a set of records.
> So for example:
>
> -- define an output record structure as a type
> -- using pgr_ as namespace for function, change as appropriate
>
> create type pgr_time_dep_costs as (
>  edge_id int,
>  time_start float,
>  time_stop float,
>  avg_speed float,
>  transit_time float
> );
>
>
> CREATE OR REPLACE FUNCTION pgr_get_time_dep_costs(**schedule_tab text,
> start_date_time timestamp, max_time_duration_sec int, ...)
>  RETURNS SETOF pgr_time_dep_costs AS
> $BODY$
> DECLARE
>  out pgr_time_dep_costs;
>
> BEGIN
>
>  LOOP
>    -- compute values of out from the input
>
>    -- load the values into out
>    out.edge_id     := ...;
>    out.time_start  := ...;
>    out.time_stop   := ...;
>    out.avg_spd     := ...;
>    out.tansit_time := ...;
>
>    RETURN NEXT out; -- return an out record
>  END LOOP;
>
>  RETURN;  -- exit the procedure
> END
> $BODY$
>  LANGUAGE plpgsql VOLATILE
>  COST 100
>  ROWS 1000;
>
>
This is pretty basic, but it should help get you started.
>
> -Steve
>
>     For this project we need a concrete implementation that allow
>>    someone to create a table of time based restrictions of some kind on
>>    edges and reasonable easy say generate a route start at X and use
>>    these time dependent restrictions.
>>
>>    I do not think it needs to deal with every single possible case, but
>>    it should be a reason set of cases. We can always expand on this
>>    after GSoC. I think it would be good in the documentation, we add
>>    some notes about things we thought of be did not support and a short
>>    paragraph of our thoughts on how to support it in the future.
>>
>>    You need to size this to the time you have available so you can be
>>    successful. I will let Daniel be the final arbiter on this as I will
>>    be out of town again later this week and my time here seems to on
>>    overload lately.
>>
>>    The key idea here is layer of tasks, and structure. We need to
>>    bridge the gap between low-level generic code and higher level
>>    application specific presentation of which there my be many
>>    depending on the application in discussion.
>>
>>    Best regards,
>>      -Steve
>>
>
-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110722/afbf2f4a/attachment.html