[pgrouting-dev] Support for Time Constraints
Stephen Woodbridge
woodbri at swoodbridge.com
Wed Mar 30 17:23:54 EDT 2011
Jay,
I can not speak for Daniel and Anton but a couple of things:
Given the time schedule, assume you can go ahead with your plan and it
can always be tweaked along the way. Hopefully they will be able to
respond directly.
Remember that they are currently based out of Japan and given the power
problems and infrastructure issues they might have spotty access to the net.
I'm sure they will have some input eventually, but you need to take
control of your application and do the best you can given what input you
are able to get from us now.
I think it is important that whatever you do, needs to be integrated
with pgRouting and you need to make sure you allow for time for that.
Best regards,
-Steve
On 3/30/2011 3:51 PM, Jay Mahadeokar wrote:
>
>
> On Wed, Mar 30, 2011 at 2:04 AM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
> 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.
>
>
>
> 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.
>
> Please also suggest any changes / improvements in the idea too :)
>
> 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
> <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
> <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>
> <mailto: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>>
> <mailto: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
>
More information about the pgrouting-dev
mailing list