[pgrouting-dev] Support for Time Constraints

[Stephen Woodbridge]

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