Hi,<br><br>My thoughts on points made by Stephen:<br><br>Firstly, the main goal of the time dependent shortest path project as per my GSoc proposal is to extend the static dijkstra algorithm, to work with time dependent graphs. I made a wiki page for that and we can keep modifying it as the ideas become concrete: <a href="https://github.com/pgRouting/pgrouting/wiki/TDSP-Details">https://github.com/pgRouting/pgrouting/wiki/TDSP-Details</a><br>
<br><br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
*Input format for time dependent data:<br>
</blockquote>
<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 reverse and say:<br>
<br>
start_location,<br>
end_location,<br>
arrival_time,<br>
options </blockquote><div><br><br>This looks good. <br>A tuple will denote the arrival_time which will be time required if we start from source_location at time denoted by start_time and travel to end_location. <br><br>
So, basically we can assume that the edge weights are the time required to traverse the edge. The core time-dependent dijkstra will assume it can call a function like:<br><br>getCurrentEdgeCost( edge_id, start_time_and_date, arrival_time) - edge can be denoted by start_location and end_location. The arrival_time will be returned by function.<br>
<br>While relaxing the edge in dijkstra algorithm, instead of static cost, the above function will be called each time to know the arrival_time for that instant.<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;">
In this version you would have to figure on the route starting at the end and working backwards to the start location to figure on the route and the required start time.<br>
<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
*There has already been a brief discussion on this topic before. A quick<div><div></div><br></div></blockquote><br>
User - application developer, the person build an application using 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 data and prep it for pgRouting.<br>
2. the User will take the MBTA bus and train and subway schedules and load them into tables the closely reflect the underlying schedule data.<br>
3. the User will develop a stored procedure to read the schedule data and morph it into some predefined notion whatever that might be. This could be to load it into a more normalized table or it 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 data gets built into a temporary boost graph structures to service 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 with the exception of the schedules or whatever time dependent data we have.<br>
<br>
And with we are not using schedules and only looking at time dependent turn restrictions and oneway streets then I think using the same approach is still valid but instead of loading schedule information, we would load the turn restriction.<br>
</blockquote><div><br><br>I did not understand how we will be using bus and train schedules in this algorithm. I guess, the basic aim at this moment is just to extend dijkstra for time-dependent scenario, right? Dealing with schedules will need provision for multimodal routing I guess. Can you please clarify this point?<br>
<br>I was not exactly aware of concept of turn restrictions, so I referred here: <a href="http://wiki.openstreetmap.org/wiki/Relation:restriction">http://wiki.openstreetmap.org/wiki/Relation:restriction</a><br><br>I guess to provide support for time dependent turn restriction will just need a slight modification in original approach as per the GSoc proposal. We will just have to make sure if we are allowed to turn to particular road at that particular time, before we relax it in dijkstra algorithm. <br>
<br>Thoughts?<br> <br clear="all"></div><br></div><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>