Re: [OSRM-talk] State of the Art - Dynamic Routing

[Patrick Niklaus]

If you want to ingest dynamic data like traffic information into the
routing, the main objective is to reduce pre-processing times so that
the data will not be stale before you can actually serve requests from
it.

There are several ways you can achieve this:
1. Don't do any pre-processing.
 In that case you just use a normal Dijkstra based search.
2. Do pre-processing but don't update it on traffic updates.
For example if you use something ALT-based you can calculate the
heuristic using the average value and still yield good performance.
3. Re-run pre-processing and make it fast enough for your given update cycle.
The primary knobs you can turn there are:
- reduce the size of your dataset
- reduce the quality of the pre-processing

We have been working on supporting 3 in OSRM with CH. We added a
parameter to now contract the graph completely but only partially.
This as dire consequences for query times however, depending on which
quality factor you pick. If you contract the graph only 95% you will
half your pre-processing time and increase the runtime 100x depending
on your dataset size. Features like alternative searches, distance
tables and similar will not work with this approach since it is much
too slow.

You can try partial contraction with `4.8.1` by using the `-k`
parameter like `-k 0.95` will contract the graph only to 95%.

Supporting real time traffic updates while still supporting
continental sized networks is not exactly trivial, even more so if you
support advanced features like turn restrictions. Consider the fact
that just reading/writing such a graph from/to disk might take longer
than your usual update cycle.

We are working on making it easier to support this for smaller
datasets though (like countries). Of course CH is really not suited
that well for this task, but it enables you to use the same platform
and process until CH can be replaced with alternative approaches.

Best,
Patrick

On Fri, Oct 9, 2015 at 3:03 PM, Matthias Loeks  wrote:
> Hi all,
>
> I would love to see the great OSRM framework supporting more dynamic route
> calculations.
> For instance, it would be great to be able to specify individual vehicle
> profiles/parameters and avoid areas (e.g. road closures) on a per-request
> basis.
>
> As I understand, this required flexibility is contrary to the approach of
> contraction hierarchies in general and thus very hard to achieve. The
> routing can only be that fast because all dynamic input information is
> pre-computed in the graph during the pre-processing, right?
>
> However, I noticed that this topic was already discussed from time to time
> on the list [1,2] and on github [3-5]. Plus there are similar CH-based
> projects starting to support dynamic input at least to some extent (e.g.
> GraphHopper Traffic Data Integration [6]). So in the end it *does* seem to
> be possible, at least partly?
>
> All in all, I'd like to know what is the current state of the art of such
> efforts on the roadmap? What *is* possible and what is definitely not? Is
> there anything in this direction being worked on currently or soon?
>
> It would be great to hear any thoughts, updates and/or ideas from you on
> this topic.
>
> Many thanks and all the best,
> Matthias
>
>
> --
> [1] -
> https://lists.openstreetmap.org/pipermail/osrm-talk/2015-August/000898.html
> [2] -
> https://lists.openstreetmap.org/pipermail/osrm-talk/2013-June/000179.html
> [3] - https://github.com/Project-OSRM/osrm-backend/issues/165
> [4] - https://github.com/Project-OSRM/osrm-backend/issues/683
> [5] . https://github.com/Project-OSRM/osrm-backend/issues/892
> [6] - https://github.com/karussell/graphhopper-traffic-data-integration
>
>
>
>
> ___
> OSRM-talk mailing list
> OSRM-talk@openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk

___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

[OSRM-talk] State of the Art - Dynamic Routing

[Matthias Loeks]

Hi all,

I would love to see the great OSRM framework supporting more dynamic 
route calculations.
For instance, it would be great to be able to specify individual vehicle 
profiles/parameters and avoid areas (e.g. road closures) on a 
per-request basis.


As I understand, this required flexibility is contrary to the approach 
of contraction hierarchies in general and thus very hard to achieve. The 
routing can only be that fast because all dynamic input information is 
pre-computed in the graph during the pre-processing, right?


However, I noticed that this topic was already discussed from time to 
time on the list [1,2] and on github [3-5]. Plus there are similar 
CH-based projects starting to support dynamic input at least to some 
extent (e.g. GraphHopper Traffic Data Integration [6]). So in the end it 
*does* seem to be possible, at least partly?


All in all, I'd like to know what is the current state of the art of 
such efforts on the roadmap? What *is* possible and what is definitely 
not? Is there anything in this direction being worked on currently or soon?


It would be great to hear any thoughts, updates and/or ideas from you on 
this topic.


Many thanks and all the best,
Matthias


--
[1] - 
https://lists.openstreetmap.org/pipermail/osrm-talk/2015-August/000898.html
[2] - 
https://lists.openstreetmap.org/pipermail/osrm-talk/2013-June/000179.html

[3] - https://github.com/Project-OSRM/osrm-backend/issues/165
[4] - https://github.com/Project-OSRM/osrm-backend/issues/683
[5] . https://github.com/Project-OSRM/osrm-backend/issues/892
[6] - https://github.com/karussell/graphhopper-traffic-data-integration




___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk