[pgrouting-dev] Support for Time Constraints
Stephen Woodbridge
woodbri at swoodbridge.com
Tue Mar 29 16:34:31 EDT 2011
Jay,
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:
float cost := getEdgeCost(time, vehicle_type, node_from, node_to);
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.
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.
-Steve
On 3/29/2011 2:41 PM, Jay Mahadeokar wrote:
> Hi,
>
> 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].
>
> 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.
>
> *Main motivation is:* 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).
>
> 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]):
>
> 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.
>
> Im writing down a rough pseudo-code for the dijkstra search:
>
> Note that I have modified lines 3,6,15 and 18 (from the pseudo-code
> given on wikipedia [3])
>
> 1*function* Dijkstra(/Graph/,/source/ , start_time):
>
> 2*for each* vertex/v/ in/Graph/:/// Initializations/
> 3 dist[/v/] := infinity ;/// Unknown distance function from source to v/
> time[v] := 0 ;
>
> 4 previous[/v/] := undefined ;/// Previous node in optimal path from source/
> 5*end for*;
> 6 dist[/source/] := 0 ;/// Distance from source to source/
>
> time[source] := start_time ;
> 7/Q/ := the set of all nodes in/Graph/ ;
> /// All nodes in the graph are unoptimized - thus are in Q/
> 8*while* /Q/ *is not* empty:/// The main loop/
>
> 9/u/ := vertex in/Q/ with smallest dist[] ;
> 10*if* dist[/u/] = infinity:
> 11*break* ;/// all remaining vertices are inaccessible from source/
>
> 12*fi* ;
> 13 remove/u/ from/Q/ ;
> 14*for each* neighbor/v/ of/u/:/// where v has not yet been removed from Q./
> 15/alt/ := dist[/u/] + dist_between(/u/,/v/ , time[u],end_time) ; //end_time returns the time at which we reach v from u
>
> 16*if* /alt/ < dist[/v/]:/// Relax (u,v,a)/
> 17 dist[/v/] :=/alt/ ;
> 18 previous[/v/] :=/u/ ;
> time[v] := end_time;
>
> 19*fi* ;
> 20*end for* ;
> 21*end while* ;
> 22*return* dist[] ;
> 23*end* Dijkstra.
>
>
> 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].
>
> *Questions*:
>
> 1. @Daniel - Is this somewhat what you are interested in?
> 2. Can this be considered as a GSoc project?
> 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?
> 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)
>
>
> @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. :)
>
> [1] Bidirectional A∗ Search on Time-Dependent Road Networks
> <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>
> [2] Slide Show of above paper
> <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>
> [3] http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
>
>
> On Mon, Mar 28, 2011 at 8:35 PM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
> 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.
>
> [1] http://opengraphrouter.sourceforge.net/
>
> 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.
>
> 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.
>
> 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.
>
> -Steve
>
>
> On 3/28/2011 10:46 AM, Daniel Kastl wrote:
>
> Hi Jay,
>
> In my opinion time dependent routing is a nice idea and a
> feature you
> can hardly find in existing routing libraries. I haven't seen
> any open
> source implementation yet. Someone else knows one?
>
> Currently pgRouting takes into account the network loaded when
> running
> the query. But it could happen, that network conditions change while
> travelling in the network, right? For example one could reach a road
> that is closed on certain times.
>
> It could be a very cool feature, if pgRouting could support even
> changes
> during travel time. So personally I would prefer such a project idea
> over one to speed up shortest path computation.
>
> Daniel
>
>
>
>
>
> 2011/3/28 Jay Mahadeokar <jai.mahadeokar at gmail.com
> <mailto:jai.mahadeokar at gmail.com>
> <mailto:jai.mahadeokar at gmail.com <mailto:jai.mahadeokar at gmail.com>>>
>
> Hi,
>
> I was looking at GSoc 2011 ideas page and Adding support for time
> constraints seems to be one of the ideas. I read two papers on the
> topic which are an extension to (two of the current best) techniques
> for speeding up shortest path algos.
>
> 1. Time Dependent Contraction Hierarchies
> <http://algo2.iti.kit.edu/english/1222.php> - an extension to
>
> contraction hierarchies problem that we have somewhat discussed in
> the Network layering Support thread, and we have not reached to any
> specific conclusion there.
>
> 2. Time Dependent SHARC Routing
> <http://portal.acm.org/citation.cfm?id=1431038> - which is an
>
> extension to SHARC technique.
>
> I guess, if we implement one of the above preprocessing technique,
> the extension will be a relatively simple task. Do you have any
> other approach towards implementing the time constraints? As we
> have already found, the implementation of the Contraction
> hierarchies will take significant brainstorming and effort.
>
> --
> Regards,
> -Jay Mahadeokar
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> <mailto:pgrouting-dev at lists.osgeo.org>
> <mailto:pgrouting-dev at lists.osgeo.org
> <mailto:pgrouting-dev at lists.osgeo.org>>
>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de
> <mailto:daniel.kastl at georepublic.de>
> <mailto:daniel.kastl at georepublic.de
> <mailto:daniel.kastl at georepublic.de>>
> Web: http://georepublic.de <http://georepublic.de/>
>
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
More information about the pgrouting-dev
mailing list