<br><br><div class="gmail_quote">On Wed, Mar 30, 2011 at 2:04 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;">
Jay,<br>
<br>
Currently in pgRouting you can have different cost columns, like distance, traversal time, etc that is stored on the edge. I think that is would be very advantageous with we could pass a pgpsql function to fetch the cost. We could easily set up a standard signature for such a function. like:<br>
<br>
float cost := getEdgeCost(time, vehicle_type, node_from, node_to);<br>
<br>
or something like that. Where time could be NULL for some default behavior, or a value that would be used to figure out the cost. vehicle_type might be helpful if there are multiple costs to traverse a link based on say, car, carpool, bus, truck, walking, taxi, etc. This could also be used to implement the rules for bus and train lines.<br>
<br></blockquote><div><br><br>Sounds good. Again since the GSoc Application deadline looming on 8th April, can this be considered as a valid GSoc project? If yes, I would start writing down the proposal for the same. Would like to hear thoughts of Daniel or Anton on the same.<br>
<br>Please also suggest any changes / improvements in the idea too :)<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;">
Regarding the multi-modal routing, What you proposed is very close to the multimodal implementation. You define a start time and start node and a destination. As the route is evaluated, the time is incremented by the cost of each edge or node. In the multimodal, we had the ability if I'm not mistaken to have a cost at a node, this might have been implemented by adding some segment with the cost on that. This was used for the cost of waiting for a scheduled item, like a bus, train to a stop.<br>
<br>
-Steve<div><div></div><div class="h5"><br>
<br>
On 3/29/2011 2:41 PM, Jay Mahadeokar wrote:<br>
</div></div><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">
Hi,<br>
<br>
I tried to survey existing time dependent routing algorithms that do not<br>
do pre-processing as in CH and SHARC. The problem is formally defined in<br>
[1]. It gives a bidirectional A* algorithm for time-dependent scenario.<br>
The paper is explained in short in [2].<br>
<br>
Now, the algorithm discussed there is complex and also involves<br>
pre-processing the distances from set of landmark nodes to all other<br>
nodes which is used by the potential function in A*.But, the paper<br>
states the problem very formally.<br>
<br>
*Main motivation is:* People are not really interested in the distance<br>
they travel, but instead they want the route which will lead to their<br>
destination quickest (in least time).<br>
<br>
For starters, I was thinking of modifying simple dijkstra algorithm for<br>
time dependent routing. In simple words, the problem can be framed as<br>
follows (For formal problem statement refer [1]):<br>
<br>
Each edge has a range of costs associated with it. The cost depends on<br>
the start time at which we want to traverse the road which will be<br>
governed by the traffic and other parameters. We can assume a function<br>
which will return the cost of edge and time required to cross the edge,<br>
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<br>
given on wikipedia [3])<br>
<br>
1*function* Dijkstra(/Graph/,/source/ , start_time):<br>
<br>
2*for each* vertex/v/ in/Graph/:/// Initializations/<br>
3 dist[/v/] := infinity ;/// Unknown distance function from source to v/<br>
time[v] := 0 ;<br>
<br>
4 previous[/v/] := undefined ;/// Previous node in optimal path from source/<br>
5*end for*;<br>
6 dist[/source/] := 0 ;/// Distance from source to source/<br>
<br>
time[source] := start_time ;<br>
7/Q/ := the set of all nodes in/Graph/ ;<br>
/// All nodes in the graph are unoptimized - thus are in Q/<br>
8*while* /Q/ *is not* empty:/// The main loop/<br>
<br>
9/u/ := vertex in/Q/ with smallest dist[] ;<br>
10*if* dist[/u/] = infinity:<br>
11*break* ;/// all remaining vertices are inaccessible from source/<br>
<br>
12*fi* ;<br>
13 remove/u/ from/Q/ ;<br>
14*for each* neighbor/v/ of/u/:/// where v has not yet been removed from Q./<br>
15/alt/ := dist[/u/] + dist_between(/u/,/v/ , time[u],end_time) ; //end_time returns the time at which we reach v from u<br>
<br>
16*if* /alt/ < dist[/v/]:/// Relax (u,v,a)/<br>
17 dist[/v/] :=/alt/ ;<br>
18 previous[/v/] :=/u/ ;<br>
time[v] := end_time;<br>
<br>
19*fi* ;<br>
20*end for* ;<br>
21*end while* ;<br>
22*return* dist[] ;<br>
23*end* Dijkstra.<br>
<br>
<br>
This will be a very basic implementation and there will be much scope<br>
for improvement and implementation using better and complex techniques<br>
as given in [1].<br>
<br>
*Questions*:<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<br>
data pertaining the time-dependent values for each edge present in the<br>
postgres database? If yes we will need to finalise the format of the<br>
data stored right?<br>
4. Is there already a standard format for storing time-dependent edge<br>
weights data, or we should assume the function that returns the edge<br>
cost as black box and just code the time dependent functionality without<br>
worrying as to how the function actually gets the values from (database<br>
or somewhere else)<br>
<br>
<br>
@Stephen - I have not yet looked at the multimodal routing<br>
implementation. I guess the idea I have proposed is different from that<br>
one right? Will look into it if this one does not shape well. :)<br>
<br>
[1] Bidirectional A∗ Search on Time-Dependent Road Networks<br></div></div>
<<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" target="_blank">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</a>><div class="im">
<br>
[2] Slide Show of above paper<br></div>
<<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" target="_blank">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</a>><div class="im">
<br>
[3] <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" target="_blank">http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm</a><br>
<br>
<br>
On Mon, Mar 28, 2011 at 8:35 PM, Stephen Woodbridge<br></div><div><div></div><div class="h5">
<<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>>> wrote:<br>
<br>
Last years GSoC project for OpenGraphRouter [1], implemented<br>
multimodal routing and incorporated bus and train schedules along<br>
with time dependent routing. So you would say what you start time<br>
was and it would then compute the routes based on travel time,<br>
between nodes, transfer times at stations, etc. Basically at nodes<br>
that were stations, we link in the schedule for that stop and costs<br>
to the connecting nodes were dynamically computed from the schedules<br>
and the arrival time at the stop. Arrival time was based on your<br>
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<br>
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<br>
the cost and for regular highway nodes and edges it would mostly<br>
just return a static value assigned to that object. But for we had<br>
time dependent turn restrictions or we had multimodal station, it<br>
would lookup the cost based on a schedule or timetable linked to<br>
that object.<br>
<br>
This would allow the schedules and timetables to be hidden from the<br>
implementation. And different types of objects could point to<br>
different methods for computing the costs.<br>
<br>
-Steve<br>
<br>
<br>
On 3/28/2011 10:46 AM, Daniel Kastl wrote:<br>
<br>
Hi Jay,<br>
<br>
In my opinion time dependent routing is a nice idea and a<br>
feature you<br>
can hardly find in existing routing libraries. I haven't seen<br>
any open<br>
source implementation yet. Someone else knows one?<br>
<br>
Currently pgRouting takes into account the network loaded when<br>
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<br>
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>
<mailto:<a href="mailto:jai.mahadeokar@gmail.com" target="_blank">jai.mahadeokar@gmail.com</a>><br></div></div><div><div></div><div class="h5">
<mailto:<a href="mailto:jai.mahadeokar@gmail.com" target="_blank">jai.mahadeokar@gmail.com</a> <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>
<<a href="http://algo2.iti.kit.edu/english/1222.php" target="_blank">http://algo2.iti.kit.edu/english/1222.php</a>> - an extension to<br>
<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>
<<a href="http://portal.acm.org/citation.cfm?id=1431038" target="_blank">http://portal.acm.org/citation.cfm?id=1431038</a>> - which is an<br>
<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>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a>>><br>
<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>
eMail: <a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a>><br>
<mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a><br>
<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>><br>
<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> <mailto:<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>
<br>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<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>><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></div></div>
Regards,<br>
-Jay Mahadeokar<br>
<br>
</blockquote>
<br>
</blockquote></div><br><br clear="all"><br>-- <br>Regards,<br>-Jay Mahadeokar<br><br>