Hi,<br><br>I tried to survey existing time dependent routing algorithms that do not do pre-processing as in CH and SHARC. The problem is formally defined in [1]. It gives a bidirectional A* algorithm for time-dependent scenario. The paper is explained in short in [2].<br>
<br>Now, the algorithm discussed there is complex and also involves pre-processing the distances from set of landmark nodes to all other nodes which is used by the potential function in A*.But, the paper states the problem very formally. <br>
<br><b>Main motivation is:</b> People are not really interested in the distance they travel, but instead they want the route which will lead to their destination quickest (in least time).<br><br>For starters, I was thinking of modifying simple dijkstra algorithm for time dependent routing. In simple words, the problem can be framed as follows (For formal problem statement refer [1]):<br>
<br>Each edge has a range of costs associated with it. The cost depends on the start time at which we want to traverse the road which will be governed by the traffic and other parameters. We can assume a function which will return the cost of edge and time required to cross the edge, if we pass the edge id and start time to it.<br>
<br>Im writing down a rough pseudo-code for the dijkstra search:<br><br>Note that I have modified lines 3,6,15 and 18 (from the pseudo-code given on wikipedia [3])<br><br><pre> 1 <b>function</b> Dijkstra(<i>Graph</i>, <i>source</i> , start_time):<br>
2 <b>for each</b> vertex <i>v</i> in <i>Graph</i>: <i>// Initializations</i><br> 3 dist[<i>v</i>] := infinity ; <i>// Unknown distance function from source to v</i><br> time[v] := 0 ;<br>
4 previous[<i>v</i>] := undefined ; <i>// Previous node in optimal path from source</i><br> 5 <b>end for </b>;<br> 6 dist[<i>source</i>] := 0 ; <i>// Distance from source to source</i><br>
time[source] := start_time ;<br> 7 <i>Q</i> := the set of all nodes in <i>Graph</i> ;<br> <i>// All nodes in the graph are unoptimized - thus are in Q</i><br> 8 <b>while</b> <i>Q</i> <b>is not</b> empty: <i>// The main loop</i><br>
9 <i>u</i> := vertex in <i>Q</i> with smallest dist[] ;<br>10 <b>if</b> dist[<i>u</i>] = infinity:<br>11 <b>break</b> ; <i>// all remaining vertices are inaccessible from source</i><br>
12 <b>fi</b> ;<br>13 remove <i>u</i> from <i>Q</i> ;<br>14 <b>for each</b> neighbor <i>v</i> of <i>u</i>: <i>// where v has not yet been removed from Q.</i><br>15 <i>alt</i> := dist[<i>u</i>] + dist_between(<i>u</i>, <i>v</i> , time[u],end_time) ; //end_time returns the time at which we reach v from u <br>
16 <b>if</b> <i>alt</i> < dist[<i>v</i>]: <i>// Relax (u,v,a)</i><br>17 dist[<i>v</i>] := <i>alt</i> ;<br>18 previous[<i>v</i>] := <i>u</i> ;<br> time[v] := end_time;<br>
19 <b>fi </b> ;<br>20 <b>end for</b> ;<br>21 <b>end while</b> ;<br>22 <b>return</b> dist[] ;<br>23 <b>end</b> Dijkstra.<br></pre><br>This will be a very basic implementation and there will be much scope for improvement and implementation using better and complex techniques as given in [1]. <br>
<br><b>Questions</b>:<br><br>1. @Daniel - Is this somewhat what you are interested in?<br>2. Can this be considered as a GSoc project? <br>3. pgRouting mainly provides routing for postgres. So, do we assume the data pertaining the time-dependent values for each edge present in the postgres database? If yes we will need to finalise the format of the data stored right?<br>
4. Is there already a standard format for storing time-dependent edge weights data, or we should assume the function that returns the edge cost as black box and just code the time dependent functionality without worrying as to how the function actually gets the values from (database or somewhere else)<br>
<br><br>@Stephen - I have not yet looked at the multimodal routing implementation. I guess the idea I have proposed is different from that one right? Will look into it if this one does not shape well. :)<br><br>[1] <a href="http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBcQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.144.2183%26rep%3Drep1%26type%3Dpdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNFnYYtw2Ap_dNyjbYcaPnmB-bMZOQ&sig2=DTMTucn2TMhT0eXTiqKlTg">Bidirectional A∗ Search on Time-Dependent Road Networks</a><br>
[2] <a href="http://www.google.com/url?sa=t&source=web&cd=2&ved=0CCAQFjAB&url=http%3A%2F%2Fctw08.dti.unimi.it%2Fslides%2FB5%2FB5-1-Nannicini.pdf&ei=Sh2STeDIJY-qcb-F1YkH&usg=AFQjCNGEl-mbYR1MF9HBKY-dbBxrX8xfcw&sig2=ylApFLDB6FTQNuYUwaPQDQ">Slide Show of above paper</a><br>
[3] <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm</a><br><br><br><div class="gmail_quote">On Mon, Mar 28, 2011 at 8:35 PM, 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;">Last years GSoC project for OpenGraphRouter [1], implemented multimodal routing and incorporated bus and train schedules along with time dependent routing. So you would say what you start time was and it would then compute the routes based on travel time, between nodes, transfer times at stations, etc. Basically at nodes that were stations, we link in the schedule for that stop and costs to the connecting nodes were dynamically computed from the schedules and the arrival time at the stop. Arrival time was based on your start time plus the travel time to that stop.<br>
<br>
[1] <a href="http://opengraphrouter.sourceforge.net/" target="_blank">http://opengraphrouter.sourceforge.net/</a><br>
<br>
It would be cool if we could use the work done here and migrate that back to pgRouting or integrate it with the contraction highways.<br>
<br>
I think the abstraction of this is that we need a method that gets the cost and for regular highway nodes and edges it would mostly just return a static value assigned to that object. But for we had time dependent turn restrictions or we had multimodal station, it would lookup the cost based on a schedule or timetable linked to that object.<br>
<br>
This would allow the schedules and timetables to be hidden from the implementation. And different types of objects could point to different methods for computing the costs.<br>
<br>
-Steve<div class="im"><br>
<br>
On 3/28/2011 10:46 AM, Daniel Kastl 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">
Hi Jay,<br>
<br>
In my opinion time dependent routing is a nice idea and a feature you<br>
can hardly find in existing routing libraries. I haven't seen any open<br>
source implementation yet. Someone else knows one?<br>
<br>
Currently pgRouting takes into account the network loaded when running<br>
the query. But it could happen, that network conditions change while<br>
travelling in the network, right? For example one could reach a road<br>
that is closed on certain times.<br>
<br>
It could be a very cool feature, if pgRouting could support even changes<br>
during travel time. So personally I would prefer such a project idea<br>
over one to speed up shortest path computation.<br>
<br>
Daniel<br>
<br>
<br>
<br>
<br>
<br>
2011/3/28 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>>><br>
<br>
Hi,<br>
<br>
I was looking at GSoc 2011 ideas page and Adding support for time<br>
constraints seems to be one of the ideas. I read two papers on the<br>
topic which are an extension to (two of the current best) techniques<br>
for speeding up shortest path algos.<br>
<br>
1. Time Dependent Contraction Hierarchies<br></div>
<<a href="http://algo2.iti.kit.edu/english/1222.php" target="_blank">http://algo2.iti.kit.edu/english/1222.php</a>> - an extension to<div class="im"><br>
contraction hierarchies problem that we have somewhat discussed in<br>
the Network layering Support thread, and we have not reached to any<br>
specific conclusion there.<br>
<br>
2. Time Dependent SHARC Routing<br></div>
<<a href="http://portal.acm.org/citation.cfm?id=1431038" target="_blank">http://portal.acm.org/citation.cfm?id=1431038</a>> - which is an<div class="im"><br>
extension to SHARC technique.<br>
<br>
I guess, if we implement one of the above preprocessing technique,<br>
the extension will be a relatively simple task. Do you have any<br>
other approach towards implementing the time constraints? As we<br>
have already found, the implementation of the Contraction<br>
hierarchies will take significant brainstorming and effort.<br>
<br>
--<br>
Regards,<br>
-Jay Mahadeokar<br>
<br>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br></div>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>><div class="im">
<br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
<br>
<br>
--<br>
Georepublic UG & Georepublic Japan<br></div>
eMail: <a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a> <mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a>><br>
Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a> <<a href="http://georepublic.de/" target="_blank">http://georepublic.de/</a>><div class="im"><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>