[pgrouting-dev] Time dependent data and input format
Jay Mahadeokar
jai.mahadeokar at gmail.com
Mon Jul 25 13:24:11 EDT 2011
Hi all,
It seems that we are on track (or even a bit ahead) of the planned schedule
in the tdsp proposal. I would like to believe that the core algorithm is now
ready and the wrapper function for the data format that I am currently
working on is also working. According to [1] we had kept Jul 26th to Aug
16th for completing remaining tasks, testing, documentation, bug fixing and
writing tutorials.
Steve, is there any specific input data format for which I should write
plsql wrapper function? I think we should finalise this within this week and
get the coding part done.
We had also earlier discussed about time dependent turn restrictions(not
part of the main project plan), but I am not sure if we can fit this in
schedule. I hope we can look at it after GSoc.
Daniel, Anton, is there anything specific that I need to do with regards to
the project, so that it can be bundled with the pgRouting 2.0? Currently I
am using a modified CMake file[2], and not compiling the test framework.
Till now, I have not worked with this testing framework designed by Kishore
(right?) so should I read any docs that will get me introduced with it?
Finally, back in February, I had got the All Pairs Shortest Path Algorithm
working, but proper testing, documentation and tutorial is left for that.
Should time permit, can we include this also as part of GSoc or keep it
separate?
[1] https://github.com/pgRouting/pgrouting/wiki/TDSP-Tentative-Project-Plan
[2] https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/CMakeLists.txt
On Fri, Jul 22, 2011 at 12:44 AM, Jay Mahadeokar
<jai.mahadeokar at gmail.com>wrote:
> 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
>
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110725/3f85da73/attachment.html
More information about the pgrouting-dev
mailing list