[pgrouting-dev] Time dependent data and input format
jai.mahadeokar at gmail.com
Thu Jul 21 15:14:06 EDT 2011
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
I have updated the code in gsoc-tdsp repository .
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
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.
SELECT * FROM time_dependent_shortest_path('
SELECT gid as id,
length::double precision as cost
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
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
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>>>
>> 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
>> 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
> out pgr_time_dep_costs;
> -- 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
> LANGUAGE plpgsql VOLATILE
> COST 100
> ROWS 1000;
This is pretty basic, but it should help get you started.
> 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,
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the pgrouting-dev