[OSRM-talk] Using custom data
Hi list, I'm running a little experiment with using custom geo data for OSRM. Following the advice of [1], I converted my data to OSM XML format, for now neglecting all kinds of tags/attributes etc. (this could be done later). You can find the resulting OSM file here: https://dl.dropboxusercontent.com/u/56544580/extract.osm The file can be viewed correctly using JOSM. I also created a very basic profile: https://dl.dropboxusercontent.com/u/56544580/custom.lua This profile should just contain the necessary variables read by osrm-extract. It should not exclude any of the OSM nodes or ways, just let them all pass through to the routing graph. Also, there should be no turn restrictions. The processing chain (extract, prepare) runs successfully and I can also start the osrm-routed server. The locate and nearest services are working fine. However, the viaroute service returns only a valid route, if just one segment is involved. As soon as there are junctions, no route can be calculated (code 207). Can this be related to the turn restrictions? I had hoped they would be entirely ignored if switched off in the profile. Or am I missing something else important in my profile or data? Are there maybe any OSM tags which are absolutely required by OSRM directly, even if a fully customised profile is being used? Any help or suggestions on this are greatly appreciated! Many thanks and best regards, Matthias -- [1] - https://lists.openstreetmap.org/pipermail/osrm-talk/2015-May/000844.html ___ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] Using custom data
Hi Daniel, many thanks for your answer! Now I understand... Unfortunately, that makes things much more complicated :-( I though OSRM, clever as it is, would do the noding itself and not just rely on the OSM data. So I guess I have to build a topology or at least node my custom input data beforehand, in order to be able to create a noded OSM dataset. Well, I'll try that... :-) Thanks again, Matthias On 15.10.2015 17:34, Daniel Patterson wrote: Hi Matthias, Emil is right, your ways are not connected. The connection needs to happen like this: <- same node as in way 1 It is not enough to just have nodes at the same lat/lon, you actually have to refer to the same for ways to be joined. If you fix that in your file, you should be able to route on it. daniel On Oct 15, 2015, at 8:28 AM, Matthias Loeks <matth...@loeks.net <mailto:matth...@loeks.net>> wrote: Hi Emil, thanks for your answer. Well, they look correct in JOSM and I paid attention to add the nodes and then the node relations in the ways properly when assembling the OSM XML. Does OSRM rely on any additional OSM nodes at the junctions? Doesn't it node the graph itself anyway? Cheers, Matthias On 15.10.2015 14:20, Emil Tin wrote: Are you sure segments are connected at the noded? Sendt fra min HTC-telefon - Reply message - Fra: "Matthias Loeks"<matth...@loeks.net> Til:"osrm-talk@openstreetmap.org"<osrm-talk@openstreetmap.org> Emne: [OSRM-talk] Using custom data Dato: tor, okt. 15, 2015 13:19 Hi list, I'm running a little experiment with using custom geo data for OSRM. Following the advice of [1], I converted my data to OSM XML format, for now neglecting all kinds of tags/attributes etc. (this could be done later). You can find the resulting OSM file here: https://dl.dropboxusercontent.com/u/56544580/extract.osm The file can be viewed correctly using JOSM. I also created a very basic profile: https://dl.dropboxusercontent.com/u/56544580/custom.lua This profile should just contain the necessary variables read by osrm-extract. It should not exclude any of the OSM nodes or ways, just let them all pass through to the routing graph. Also, there should be no turn restrictions. The processing chain (extract, prepare) runs successfully and I can also start the osrm-routed server. The locate and nearest services are working fine. However, the viaroute service returns only a valid route, if just one segment is involved. As soon as there are junctions, no route can be calculated (code 207). Can this be related to the turn restrictions? I had hoped they would be entirely ignored if switched off in the profile. Or am I missing something else important in my profile or data? Are there maybe any OSM tags which are absolutely required by OSRM directly, even if a fully customised profile is being used? Any help or suggestions on this are greatly appreciated! Many thanks and best regards, Matthias -- [1] - https://lists.openstreetmap.org/pipermail/osrm-talk/2015-May/000844.html ___ 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 mailing list OSRM-talk@openstreetmap.org <mailto: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 mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
Re: [OSRM-talk] State of the Art - Dynamic Routing
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 <matth...@loeks.net> 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 li
Re: [OSRM-talk] Using custom data
Hi Frederik, thanks that's a good point indeed. I guess I did not mean "noding" in a strict sense which also creates nodes at bridge intersections etc, but rather the "simple" noding that Daniel described. However, probably there could also be nodes in OSM at the same coordinate but on different floors which must not be handled as the same node. I will try to handle these cases correctly based on the topological information from my input data. Still, the naive approach might be unstable and error-prone. It's just for demonstrating a proof of concept though, so it should be fine for that. Thanks for pointing me to this issue and all the best, Matthias On 15 October 2015 20:15:28 Frederik Ramm <frede...@remote.org> wrote: Hi, On 10/15/2015 05:43 PM, Matthias Loeks wrote: I though OSRM, clever as it is, would do the noding itself and not just rely on the OSM data. That would be very un-clever of OSRM because in OSM the topology has a meaning. In OSM, if two roads cross but don't have a common node, then turning from one onto the other is not possible. Carelessly "noding" such an intersection would break routing for OSM. Bye Frederik -- Frederik Ramm ## eMail frede...@remote.org ## N49°00'09" E008°23'33" ___ 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
Re: [OSRM-talk] State of the Art - Dynamic Routing
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
[OSRM-talk] State of the Art - Dynamic Routing
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
