[pgrouting-dev] Support for Time Constraints
Jay Mahadeokar
jai.mahadeokar at gmail.com
Wed Mar 30 15:51:27 EDT 2011
On Wed, Mar 30, 2011 at 2:04 AM, Stephen Woodbridge <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
>> >
>>
>> [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
>>
>>
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110331/98f3ab72/attachment-0001.html
More information about the pgrouting-dev
mailing list