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

[Matthias Loeks]

Patrick,

thanks again for your explanations and opinions about dynamic updates to 
the graph.


Being aware of the complex scenario that dynamic updates introduce, I'd 
still like to think about the great features that it would allow for!
Implementing per-request dynamics to some extent would enable use cases 
like traffic-based routing, disaster routing (avoiding locked down 
roads), truck routing ... and much more.

Anything of these topics on the OSRM roadmap? ;-)

Of course, the "how" (to implement) is crucial here... Due to my lack of 
knowledge about both CH and C++, I cannot offer help unfortunately.
I thought it has to be possible somehow, since GraphHopper offers this 
traffic data integration thing [1], which might show the way how to do this?


Best,
Matthias

--
[1] - https://github.com/karussell/graphhopper-traffic-data-integration


On 14.10.2015 13:05, Patrick Niklaus wrote:

certain edges in the contracted graph should have to be ignored


If that set of 'dynamic edges' is known in advance you could use a
technique that does not contract nodes adjacent to that edges. This
would mean for those edges you could update the weights without
re-contraction. On the pre-processing side adding support for this is
quite trivial, essentially it is a variation of partial contraction.
However adding an interface for
updating the graph would be new. The main problem there is that you
either add some sort of "override set" to the query graph, or have a
copy for each graph for each thread.
The first implementation will incur high penalties on query time (you
would need an additional check every time you read the edge weight),
the second approach would have a high memory usage.

Currently we don't plan to implement this. But if anyone likes to give
it a try, I will of course help were I can.

Best,
Patrick

On Wed, Oct 14, 2015 at 12:18 PM, Matthias Loeks  wrote:

HI Patrick,

many thanks for your extensive answer and your interesting insights into the
possibilities of achieving dynamic routing with CH.

While partial graph contraction may be an option for adding traffic data
e.g. every 15 minutes, I'm afraid that it is still not an option if each
individual request has to deal with e.g. different  avoid areas.
Each request would then need a differently contracted/pre-processed graph...
(impossible to pre-process on the fly)

Do you think there is any possibility to add some sort of "dynamic layer" on
top of the contracted graph? Based on the information in this layer, certain
edges in the contracted graph should have to be ignored by the routing
algorithm.
Is such a thing possible and are there any plans to incorporate this (or
similar concepts) into OSRM? Or is this just contrary to the CH approach and
only solveable with a usual (slow) Dijkstra?

Thanks a lot for your help!

Cheers,
Matthias


On 09.10.2015 15:37, Patrick Niklaus wrote:

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


___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org

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

[Daniel Patterson]

Matthias,

  For small networks (city-sized), many algorithms can be used and have 
performance good enough for interactive queries.  OSRM aims to offer fast 
queries for *global* road networks, but the price is that a lot of 
pre-processing has to be done. If you're just looking at smaller regions (like 
city-sized networks), you can often fully re-process with OSRM in just a few 
minutes in most cases.  Scaling fast updates and fast queries to a global-scale 
road network is an active area of research.
  
  There is a very good overview paper (from April 2015) of general routing 
problems and known solutions here, and it's not too heavy on the math:

http://arxiv.org/abs/1504.05140 

  I would recommend spending some time reading it, it will really help you 
understand the state-of-the-art and the trade-offs in time/space.  There is 
also quite a lot of reading material in German here:  
http://i11www.iti.uni-karlsruhe.de/teaching/sommer2015/routenplanung/index 
  

daniel


> On Oct 15, 2015, at 8:38 AM, Matthias Loeks  wrote:
> 
> Patrick,
> 
> thanks again for your explanations and opinions about dynamic updates to the 
> graph.
> 
> Being aware of the complex scenario that dynamic updates introduce, I'd still 
> like to think about the great features that it would allow for!
> Implementing per-request dynamics to some extent would enable use cases like 
> traffic-based routing, disaster routing (avoiding locked down roads), truck 
> routing ... and much more.
> Anything of these topics on the OSRM roadmap? ;-)
> 
> Of course, the "how" (to implement) is crucial here... Due to my lack of 
> knowledge about both CH and C++, I cannot offer help unfortunately.
> I thought it has to be possible somehow, since GraphHopper offers this 
> traffic data integration thing [1], which might show the way how to do this?
> 
> Best,
> Matthias
> 
> --
> [1] - https://github.com/karussell/graphhopper-traffic-data-integration
> 
> 
> On 14.10.2015 13:05, Patrick Niklaus wrote:
>>> certain edges in the contracted graph should have to be ignored
>> 
>> If that set of 'dynamic edges' is known in advance you could use a
>> technique that does not contract nodes adjacent to that edges. This
>> would mean for those edges you could update the weights without
>> re-contraction. On the pre-processing side adding support for this is
>> quite trivial, essentially it is a variation of partial contraction.
>> However adding an interface for
>> updating the graph would be new. The main problem there is that you
>> either add some sort of "override set" to the query graph, or have a
>> copy for each graph for each thread.
>> The first implementation will incur high penalties on query time (you
>> would need an additional check every time you read the edge weight),
>> the second approach would have a high memory usage.
>> 
>> Currently we don't plan to implement this. But if anyone likes to give
>> it a try, I will of course help were I can.
>> 
>> Best,
>> Patrick
>> 
>> On Wed, Oct 14, 2015 at 12:18 PM, Matthias Loeks  wrote:
>>> HI Patrick,
>>> 
>>> many thanks for your extensive answer and your interesting insights into the
>>> possibilities of achieving dynamic routing with CH.
>>> 
>>> While partial graph contraction may be an option for adding traffic data
>>> e.g. every 15 minutes, I'm afraid that it is still not an option if each
>>> individual request has to deal with e.g. different  avoid areas.
>>> Each request would then need a differently contracted/pre-processed graph...
>>> (impossible to pre-process on the fly)
>>> 
>>> Do you think there is any possibility to add some sort of "dynamic layer" on
>>> top of the contracted graph? Based on the information in this layer, certain
>>> edges in the contracted graph should have to be ignored by the routing
>>> algorithm.
>>> Is such a thing possible and are there any plans to incorporate this (or
>>> similar concepts) into OSRM? Or is this just contrary to the CH approach and
>>> only solveable with a usual (slow) Dijkstra?
>>> 
>>> Thanks a lot for your help!
>>> 
>>> Cheers,
>>> Matthias
>>> 
>>> 
>>> On 09.10.2015 15:37, Patrick Niklaus wrote:
>>> 
>>> 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.

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

[Patrick Niklaus]

> certain edges in the contracted graph should have to be ignored


If that set of 'dynamic edges' is known in advance you could use a
technique that does not contract nodes adjacent to that edges. This
would mean for those edges you could update the weights without
re-contraction. On the pre-processing side adding support for this is
quite trivial, essentially it is a variation of partial contraction.
However adding an interface for
updating the graph would be new. The main problem there is that you
either add some sort of "override set" to the query graph, or have a
copy for each graph for each thread.
The first implementation will incur high penalties on query time (you
would need an additional check every time you read the edge weight),
the second approach would have a high memory usage.

Currently we don't plan to implement this. But if anyone likes to give
it a try, I will of course help were I can.

Best,
Patrick

On Wed, Oct 14, 2015 at 12:18 PM, Matthias Loeks  wrote:
> HI Patrick,
>
> many thanks for your extensive answer and your interesting insights into the
> possibilities of achieving dynamic routing with CH.
>
> While partial graph contraction may be an option for adding traffic data
> e.g. every 15 minutes, I'm afraid that it is still not an option if each
> individual request has to deal with e.g. different  avoid areas.
> Each request would then need a differently contracted/pre-processed graph...
> (impossible to pre-process on the fly)
>
> Do you think there is any possibility to add some sort of "dynamic layer" on
> top of the contracted graph? Based on the information in this layer, certain
> edges in the contracted graph should have to be ignored by the routing
> algorithm.
> Is such a thing possible and are there any plans to incorporate this (or
> similar concepts) into OSRM? Or is this just contrary to the CH approach and
> only solveable with a usual (slow) Dijkstra?
>
> Thanks a lot for your help!
>
> Cheers,
> Matthias
>
>
> On 09.10.2015 15:37, Patrick Niklaus wrote:
>
> 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

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

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

[Matthias Loeks]

HI Patrick,

many thanks for your extensive answer and your interesting insights into 
the possibilities of achieving dynamic routing with CH.


While partial graph contraction may be an option for adding traffic data 
e.g. every 15 minutes, I'm afraid that it is still not an option if each 
individual request has to deal with e.g. different avoid areas.
Each request would then need a differently contracted/pre-processed 
graph... (impossible to pre-process on the fly)


Do you think there is any possibility to add some sort of "dynamic 
layer" on top of the contracted graph? Based on the information in this 
layer, certain edges in the contracted graph should have to be ignored 
by the routing algorithm.
Is such a thing possible and are there any plans to incorporate this (or 
similar concepts) into OSRM? Or is this just contrary to the CH approach 
and only solveable with a usual (slow) Dijkstra?


Thanks a lot for your help!

Cheers,
Matthias

On 09.10.2015 15:37, Patrick Niklaus wrote:

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
___
OSRM-talk mailing list
OSRM-talk@openstreetmap.org
https://lists.openstreetmap.org/listinfo/osrm-talk

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