<br><br><div class="gmail_quote">On Sun, Jun 12, 2011 at 1:07 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div class="im">On 6/11/2011 12:58 PM, Jay Mahadeokar wrote:<br>
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div class="im">
<br>
<br>
On Thu, Jun 9, 2011 at 9:16 AM, Jay Mahadeokar <<a href="mailto:jai.mahadeokar@gmail.com" target="_blank">jai.mahadeokar@gmail.com</a><br></div><div class="im">
<mailto:<a href="mailto:jai.mahadeokar@gmail.com" target="_blank">jai.mahadeokar@gmail.com</a>>> wrote:<br>
<br>
Hi,<br>
<br>
Just a recap to our planned tdsp query model:<br>
<br>
<br>
<br>
I agree. So, now can we assume we have following database<br>
tables, as per things discussed till now:<br>
<br></div>
1. Ways: (On lines of the one in pgrouting-workshop)<div><div></div><div class="h5"><br>
<br>
* gid<br>
* source<br>
* target<br>
* name<br>
* the_geom<br>
* static_length (In case time dependent routing is not used)<br>
* any other attributes..<br>
<br>
2. TimeVaryingCosts (Any other suitable name?)<br>
<br>
* gid<br>
* start_time_and_date (May divide this into two columns:<br>
day_of_week and time_of_day ? )<br>
* travel_time / arrival_time<br>
<br>
3. TurnRestrictions (Time dependent)<br>
<br>
* node/source<br>
* time_from<br>
* time_to<br>
* node_to<br>
* ancestors<br>
<br>
<br>
If only static shortest path query is made, then only table 1 is<br>
required.<br>
If time-dependent shortest path query is made, table 1 and 2<br>
will be used.<br>
If in time-dependent shortest path query with turn restrictions<br>
is made , all 3 tables will be used.<br>
<br>
<br>
So, for a general time dependent query, we will fetch edge<br>
information from ways table and the time dependent costs information<br>
from the<br>
TimeDepCosts table. (See previous msg above.)<br>
<br>
The query on ways table can be supplied by the usual as on normal<br>
dijkstra shortest_path() query.<br>
<br>
How do we form the query on the TimeDepCosts table? I see two options:<br>
<br>
1. We generate the query according to the gids obtained from the<br>
query on ways table. We will have to query all the time slots<br>
available, or form a query so that the time-window is appropriate<br>
and we have sufficient travel_time info so that we can reach<br>
destination.<br>
<br>
Here we can form query like<br>
<br>
Select * from TimeDepCosts where gid in (list of gids queried from<br>
ways table).<br>
<br>
We can allow user to more filtering parameters according to<br>
start_time , date ?<br>
But this will make our query specific to the database design. As<br>
already discussed, we cant predict the time units / requirements of<br>
applications and so it would be better if we keep the query<br>
independent of the database design.<br>
<br>
Thats the reason our weight_map assumes start time from source as 0,<br>
and all travel times offset from the start time from source. A<br>
function that will generate such weight map is to be written.<br>
<br>
2. We allow user to pass the query for TimeDepCosts table too. So,<br>
we will have our pgsql function as:<br>
<br>
CREATE OR REPLACE FUNCTION shortest_path(<br>
ways_sql text,<br>
<br>
<br>
time_dep_cost_sql text,<br>
source_id integer,<br>
<br>
target_id integer,<br>
directed boolean,<br>
<br>
has_reverse_cost boolean)<br>
RETURNS SETOF path_result<br>
<br>
<br>
This way, user can have more control on the amount of data being<br>
queried. We will only consider the time dependent windows that fit<br>
the query.<br>
<br>
Example of the time_dep_cost_sql can be:<br>
<br>
Select * from TimeDepCosts where " USER_SUPPLIED_CONSTRAINTS".<br>
<br>
The user can now supply his constraints according to time_window he<br>
needs, start times, holidays etc according to the database table design.<br>
<br>
The problem with this is, we cannot filter out edges according to<br>
bounding box etc since the_geom field is not there in this table.<br>
This is because that information would be redundant.<br>
<br>
Thoughts? Any idea that combines the merits of both approaches?<br>
<br>
<br>
<br>
Hi all,<br>
<br>
I am writing some background code will be needed for the above<br>
functionality.<br>
<br>
Any input on the above mentioned point? I suppose I should not start<br>
coding for any specific approach until we agree upon a viable query<br>
strategy.<br>
</div></div></blockquote>
<br>
Hi Jay,<br>
<br>
I always find it easiest to answer these questions by thinking about the problem in terms of use cases, so:<br>
<br>
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.<br>
<br>
Are there other ones we are trying to support? These should probably be documented as part of the project description.<br></blockquote><div><br>I agree, we need to document the use-cases. A separate thread for this discussion?<br>
<br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
Anyway, assuming the above, then the application which presumably has some basic knowledge of the time constraints could do something like:<br>
<br>
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.<br>
<br>
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:<br></blockquote><div><br>Just a correction, in this case we will not be using boost_dijkstra, but instead core_tdsp() function which we have build ourselves.<br>
</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
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.<br>
</blockquote><div><br>Well, we had agreed upon the following schema for testing purpose:<br><ol><li>
<p>Ways: (On lines of the one in pgrouting-workshop)</p>
<ul><li>gid</li><li>source</li><li>target</li><li>name</li><li>the_geom</li><li>static_length (In case time dependent routing is not used)</li><li>any other attributes</li></ul>
</li><li>
<p>TimeDepCosts</p>
<ul><li>gid</li><li>day_of_week</li><li>time_of_day</li><li>travel_time / arrival_time</li></ul>
</li></ol>The time_dep_costs table schema can vary according to application and its needs and the nature of data available.<br><br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
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.<br></blockquote><div><br>We are doing exactly that! The Weight_Map data structure that is supplied to the core_tdsp() is designed specifically to fulfil the above functionality. It assumes the start time as 0, and all other times offset from start time. So, there will be schema specific wrapper functions that will help generate the weight_map data structure.<br>
<br>Which brings me back, to my original question (couple of messages back), what is the best way to generate weight_map, ie retrieve data from time dependent cost table.<br><br>Well, I think for now, I am going to go with approach #1. i.e user will supply his query. This might retrieve unwanted data, since we cant filter by the_geom in table#2. But, I think we can refine this by adding constraints like: where gid IN (list_of_edgeids_retrieved_from_ways)<br>
<br>So, I guess this approach combines the merits of both approaches discussed before. We can provide flexibility to application as well as add constraint on the number of rows retrieved.<br><br>Thoughts?<br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
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).<br>
<br>
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. :)<br>
<br>
Project seems to be moving along fine.<br>
<br>
-Steve<div><div></div><div class="h5"><br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>