<br><br><div class="gmail_quote">On Sun, May 1, 2011 at 10:39 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><div></div><div class="h5">On 4/30/2011 1:27 PM, Jay Mahadeokar wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi,<br>
<br>
My thoughts on points made by Stephen:<br>
<br>
Firstly, the main goal of the time dependent shortest path project as<br>
per my GSoc proposal is to extend the static dijkstra algorithm, to work<br>
with time dependent graphs. I made a wiki page for that and we can keep<br>
modifying it as the ideas become concrete:<br>
<a href="https://github.com/pgRouting/pgrouting/wiki/TDSP-Details" target="_blank">https://github.com/pgRouting/pgrouting/wiki/TDSP-Details</a><br>
<br>
<br>
<br>
<br>
*Input format for time dependent data:<br>
<br>
<br>
I would think that you need:<br>
<br>
start_time_and_date,<br>
start_location,<br>
end_location,<br>
options<br>
<br>
It you wanted to get fancy, it might be nice to be able to do the<br>
reverse and say:<br>
<br>
start_location,<br>
end_location,<br>
arrival_time,<br>
options<br>
<br>
<br>
<br>
This looks good.<br>
A tuple will denote the arrival_time which will be time required if we<br>
start from source_location at time denoted by start_time and travel to<br>
end_location.<br>
<br>
So, basically we can assume that the edge weights are the time required<br>
to traverse the edge. The core time-dependent dijkstra will assume it<br>
can call a function like:<br>
<br>
getCurrentEdgeCost( edge_id, start_time_and_date, arrival_time) - edge<br>
can be denoted by start_location and end_location. The arrival_time will<br>
be returned by function.<br>
<br>
While relaxing the edge in dijkstra algorithm, instead of static cost,<br>
the above function will be called each time to know the arrival_time for<br>
that instant.<br>
<br>
In this version you would have to figure on the route starting at<br>
the end and working backwards to the start location to figure on the<br>
route and the required start time.<br>
<br>
*There has already been a brief discussion on this topic before.<br>
A quick<br>
<br>
<br>
User - application developer, the person build an application using<br>
our finished pgRouting product.<br>
<br>
Client - the person using the application built by "User"<br>
<br>
1. the User will take data like from MassGIS and load the network<br>
data and prep it for pgRouting.<br>
2. the User will take the MBTA bus and train and subway schedules<br>
and load them into tables the closely reflect the underlying<br>
schedule data.<br>
3. the User will develop a stored procedure to read the schedule<br>
data and morph it into some predefined notion whatever that might<br>
be. This could be to load it into a more normalized table or it<br>
might be to service a specific query and return a normalized record.<br>
4. the Client make a route request<br>
5. a wrapper script queries the networks and the schedules and this<br>
data gets built into a temporary boost graph structures to service<br>
this request.<br>
6. results are returned to the Client and stuff is cleaned up.<br>
<br>
I think this is basically the same flow we use today in pgRouting<br>
with the exception of the schedules or whatever time dependent data<br>
we have.<br>
<br>
And with we are not using schedules and only looking at time<br>
dependent turn restrictions and oneway streets then I think using<br>
the same approach is still valid but instead of loading schedule<br>
information, we would load the turn restriction.<br>
<br>
<br>
<br>
I did not understand how we will be using bus and train schedules in<br>
this algorithm. I guess, the basic aim at this moment is just to extend<br>
dijkstra for time-dependent scenario, right? Dealing with schedules<br>
will need provision for multimodal routing I guess. Can you please<br>
clarify this point?<br>
</blockquote>
<br></div></div>
The multi-modal aspects are probably more important to Kishore's project, but in general this is also just a time dependent problem. Both these problems have the same issue of tracking time along the solution wave-front and at nodes you have to evaluate what out-bound links are value given some rules. The rules are based on your arrival time at that node.<br>
<br>
So in your case given the the arrival time, your out-bound links might be modified by time dependent turn-restrictions and your average speed on the out-bound links might be effected by traffic feeds or historical average speed based on time of day, etc.<br>
<br>
In Kishore's case, the valid out-bound links will be determined by modal schedules, and average link speeds will be determined by the mode of travel, like walk, bike, taxi, train etc. At nodes that are transfer points, then there may need to be rules about minimum transfer times, which equate to wait time between arrival and potential departures.<br>
<br>
So if we think about these as abstractions, then at nodes we can have rules like:<br>
<br>
1. restrictions<br>
- time dependent<br>
- vehicle class dependent restrictions<br>
o mopeds not allowed on divided highway<br>
o Bus only lanes, or HOV lanes<br>
o Emergency vehicle only lanes<br>
o pedestrian ways<br>
o bike lanes and paths<br>
2. schedules<br>
- time dependent (this is very similar to restrictions)<br>
- vehicle class dependent<br>
3. transfer costs<br>
- additional code of making a left hand turn in a right side country<br>
- cost to transfer modes in multi-modal network<br>
- toll cost<div class="im"><br>
<br>
<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I was not exactly aware of concept of turn restrictions, so I referred<br>
here: <a href="http://wiki.openstreetmap.org/wiki/Relation:restriction" target="_blank">http://wiki.openstreetmap.org/wiki/Relation:restriction</a><br>
</blockquote>
<br></div>
Yes, this is a good document. I believe it is missing an important case:<br>
<br>
G<br>
|<br>
A---------<-------B-----------<---------C<br>
|<br>
F--------->-------E----------->---------D<br>
|<br>
H<br>
<br>
So this depicts a street (G-B-E-H) crossing a divided roadway (A-B-C) west bound and (F-E-D) east bound. Now we don't need to worry about turning the wrong way on the oneway segments as that is handled.<br>
<br>
If there is No U-turns at this intersection, then we need a restriction that says you may not turn on AB via BE from FE, about you are allowed to turn onto AB from via BE from EH or from the opposite direction ED is restricted from CB via BE, but EH is ok.<div class="im">
<br>
<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I guess to provide support for time dependent turn restriction will just<br>
need a slight modification in original approach as per the GSoc<br>
proposal. We will just have to make sure if we are allowed to turn to<br>
particular road at that particular time, before we relax it in dijkstra<br>
algorithm.<br>
</blockquote>
<br></div>
Right. In Dijkstra, you typically have a pointer to your parent node, ie: the node you came from. And you have a list of node you can go to. In this case it is easy to add a reference to a restrictions on a given node. If the reference is null, then there are not restrictions. If you have a reference then restrictions could be stored in an array or list like:<br>
<br>
has_time, time_from, time_to, node_to, ancestors[]<br>
<br>
has_time, time_from, time_to - controls time dependancy or always valid<br>
<br>
In my above example, we would have two restrictions for the No U-turns like:<br>
<br>
at node B:<br>
0, 0, 0, node_to=A, ancestors[E,F]<br>
<br>
at node E:<br>
0, 0, 0, node_to=D, ancestors=[B,C]<br>
<br>
Maybe there is also a time dependent restriction on the divided road that restrictions traffic from turning onto the side road in the morning rush-hour, then we would add an additional restrictions to the above:<br>
<br>
at node B:<br>
1, 7AM, 9AM, node_to=G, ancestors=[C]<br>
1, 7AM, 9AM, node_to=E, ancestors=[C]<br>
<br>
at node E:<br>
1, 7AM, 9AM, node_to=B, ancestors=[F]<br>
1, 7AM, 9AM, node_to=H, ancestors=[F]<br>
<br>
So if we translate that into a table design we have something like:<br>
<br>
node, time_from, time_to, node_to, ancestors<br>
<br>
which would be very easy to create and maintain.<br></blockquote><div><br>Thanks Steve, for the detailed explanation.<br><br>I agree. So, now can we assume we have following database tables, as per things discussed till now:<br>
<br><ol><li>Ways: (On lines of the one in pgrouting-workshop)<br></li></ol><ul><li>gid</li><li>source</li><li>target<br></li><li>name</li><li>the_geom</li><li>static_length (In case time dependent routing is not used)<br>
</li><li>any other attributes..</li></ul> 2. TimeVaryingCosts (Any other suitable name?)<br><ul><li>gid</li><li>start_time_and_date (May divide this into two columns: day_of_week and time_of_day ? )<br></li><li>travel_time / arrival_time<br>
</li></ul> 3. TurnRestrictions (Time dependent)<br><ul><li>node/source</li><li>time_from <br></li><li>time_to <br></li><li>node_to <br></li><li>ancestors</li></ul><br>If only static shortest path query is made, then only table 1 is required.<br>
If time-dependent shortest path query is made, table 1 and 2 will be used.<br>If in time-dependent shortest path query with turn restrictions is made , all 3 tables will be used.<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;">
<br>
OK, it is late here and I have flooded the list with a lot of mail tonight. I hope this all makes some sense and that the other threads might be useful.<br>
<br>
Best regards,<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Thoughts?<div class="im"><br>
<br>
<br>
<br>
--<br>
Regards,<br>
-Jay Mahadeokar<br>
<br>
<br>
<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></blockquote><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>