[pgrouting-dev] Support for Time Constraints
Jay Mahadeokar
jai.mahadeokar at gmail.com
Tue Mar 29 14:41:53 EDT 2011
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
> 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>>
>>
>> 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>
>>
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>>
>>
>>
>> --
>> Georepublic UG & Georepublic Japan
>> eMail: 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
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
--
Regards,
-Jay Mahadeokar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20110330/7dcd2fad/attachment.html
More information about the pgrouting-dev
mailing list