[pgrouting-dev] Support for Time Constraints

[Jay Mahadeokar]

Hi,

I have documented the design details [1] and written an example tutorial [2]
to try out the time_dependent_shortest_path algorithm. I guess this is
enough to show the functionality, although, the data and examples along with
the wrapper functions need to be worked on in next few weeks.

Any feedback / corrections are welcome.

[1] https://github.com/pgRouting/pgrouting/wiki/TDSP-Details
[2] https://github.com/pgRouting/pgrouting/wiki/TDSP-Tutorial-and-Example

On Tue, Jul 5, 2011 at 11:54 AM, Jay Mahadeokar <jai.mahadeokar at gmail.com>wrote:

> Hi,
>
> An update -
>
> I have coded the functions to retrieve data from time_dep_costs table and
> it is presented to the core tdsp algorithm along with the data from ways
> table. The query seems to be working nicely for now.
>
> The query format is:
>
> CREATE OR REPLACE FUNCTION time_dependent_shortest_path(
>         sql text,
>         source_id integer,
>         target_id integer,
>         directed boolean,
>         has_reverse_cost boolean,
>         time_dep_sql text,
>         query_start_time integer)
>         RETURNS SETOF path_result
>         AS '$libdir/librouting_tdsp'
>         LANGUAGE 'C' IMMUTABLE STRICT;
>
>
> I have updated the github branch accordingly [1].
>
> The script to generate time_dependent_costs data can be found at [2]. I
> updated travel time of rows with class_id 106 and start_time as 9 or 19 to a
> large value.  (Signifying that the roads are blocked in those times) I also
> played around with the travel_time values a bit.
>
> If you do following queries:
>
> 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
> ,travel_time from time_dep_costs',14);
>
> 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
> ,travel_time from time_dep_costs',9);
>
> The outputs are different. The path returned by second query where
> query_start_time is 9 avoids the edge (81,82) since its cost is too high,
> and instead takes a longer route of 39 hops.  On other hand, path returned
> by 1st query where query_start_time is 14 returns shortest path of 20 hops.
>
> It would be great if anyone can check the code, run queries and give
> feedback for improvements.
>
> Now the next task should be to finalise framework to generate proper test
> data and test the functionality rigorously.
> Also, we need to write proper wrapper functions that will neatly map the
> data from time_dep_costs table into data that can be presented to core
> function. This means that the factors like cycles in time (23 hrs to 00 hrs)
> need to be considered. Also it will be better if the costs in table is in
> time units instead of distance units. I will try and come up with a suitable
> model soon.
>
> Any inputs in this regard are welcome.
>
> [1] https://github.com/pgRouting/pgrouting/tree/gsoc-tdsp
> [2]
> https://github.com/pgRouting/pgrouting/blob/gsoc-tdsp/extra/tdsp/sql/data_generate_tdsp.sql
>
>
> On Thu, Jun 23, 2011 at 2:56 AM, Daniel Kastl <daniel at georepublic.de>wrote:
>
>>
>>
>> 2011/6/23 Stephen Woodbridge <woodbri at swoodbridge.com>
>>
>>> Hi Daniel, Jay,
>>>
>>> Ok, sorry for my *rant* about OSM attributes!
>>>
>>> So it looks like osm2po does the importing and classification via its
>>> black box java .jar file and you can use the tables afterwards. Ok this
>>> could work, but I'm not sure I like the idea of using someone's black box to
>>> import the data. Long term it would be better to just use osm2pgrouting and
>>> to understand the issues that I presented and a write a stored procedure to
>>> do the classifications that are needed.
>>>
>>
>> Hi Steve,
>>
>> This was just meant to be an easy and quick way for Jay, if he doesn't
>> want to spend much time with studying OSM attributes.
>> But of course I prefer some OS tool, too.
>> I have tried to convince Carsten (the author of osm2po) to make his really
>> nice conversion tool available as Open Source, but I accept that he doesn't
>> want to do so (yet ;-).
>>
>> So I think it's good to see how osm2po organizes the tables.
>>
>> Daniel
>>
>>
>>
>>>
>>> I have not been on the osm routing list, but I'm sure we can get guidance
>>> from them to setup appropriate classifications. Or if someone want to to try
>>> out osm2po we can review the resultant tables and look at how they
>>> classified segments.
>>>
>>> -Steve
>>>
>>>
>>>
>> --
>> Georepublic UG & Georepublic Japan
>> eMail: daniel.kastl at georepublic.de
>>  Web: http://georepublic.de
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>


-- 
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110707/dcd42d1a/attachment.html