3

I'm a complete noob when it comes to OpenStreetMap and open-source map matching. I want the collective wisdom of more experienced user to evaluate whether a certain approach is doable. I'll first describe the goal and then I'll describe a reasonable suggestion. It's up to you to either confirm whether the approach can work or is doomed to fail.

I have a lot of GPS data coming from trucks that drive on the public road. They send a GPS-signal with timestamps (and other meta-data) frequently (every 10 seconds). As there is a delay in receiving these data points, real time information is not of interest.

The goal is to map match each route driven by a truck using Valhalla Meili and OpenStreetMap (OSM). Ultimately, the desired output for each route is a sequence of segment-id's with useful timestamps. Moreover, we want this output to be reasonably stable over time (if there are no changes to the road that immediately impact the routable network, a piece of road should have a stable ID in principle). The stability is a hard requirement as the ultimate goal is to provide useful statistics over time that can be compared to each other as long as there were no significant changes to the road network itself.

I understand that Valhalla could generate such an output where the id's in the output are actually the Way ID's of OSM (How stable are these? I understand that stability cannot be guaranteed, but as long as the road network doesn't change, how stable are these ID's generally speaking?). Furthermore, I noticed that a Way ID in OSM can actually go over junctions! This is a big no-no to me. A road segment should maximally be a piece of road that one cannot legally leave (so definitely in between junctions).

I'm almost capable of asking my question, but first, is the following understanding correct?

To map match using OSM and Valhalla Meili, the steps are as follows:

  • First OSM a process (which is also in the Valhalla package?) should turn the Way ID's and nodes into a routable network (a graph).
  • Valhalla Meili will map match based on HMM and Viterbi using this graph.
  • We get an output where the subsequent Way ID's are communicated as well as which datapoints are coupled to those Way ID's.

Somewhat correct?

Now here's the real question: How does Valhalla turn OSM into a graph? As 'Ways' can go over junctions, this process should take nodes into account. Is it possible to preprocess OSM in such a way that we associate to each segment (which to me is a piece of road in between junctions, so smaller than a Way ID) a unique identifier which is derived from the Way ID and is stable in the sense that we can use a fixed logic to 'number' these pieces of road?

So basically, is it possible to feed Valhalla a version of OSM where ways are first broken into smaller pieces (which I call segments) and get an output based on these segments?

As I said, I have zero experience with this material and I want to know whether looking at a solution like this is even possible.

2 Answers 2

1

Valhalla pre-processes the OSM base data to a tag-enhanced noded network topology (i.e. the 'segments' you mention, or edges), and creates a hierachically tiled routing graph with it.

You can have Meili return OSM way_ids via the Trace attributes (or the respective low-level) API, along with internal topology attributes like intersection meta data and edge properties - including geometry representations of edges and nodes traversed.


However:

As you rightfully suspect, OSM way_ids (and node_ids, both children of the osm_id prime identifier) do not follow any network topology rules commonly needed for routing graphs - meaning that there will be different edges of a pre-processed graph in Valhalla having the same way_id.

OSM does indeed not guarantee osm_id continuity - the policies here dictate this to be rare, but if nodes cannot be updated without loss of referential integrity (new lanes, roundabouts, trunks, you name it), the OSM identifier references will change.

Furthermore, updates to the OSM data will require a complete re-processing of the routing graph for Valhalla - e.g. erasing any custom references established to relate with an external, static database.

With that in mind, you can either

  • work with a static, pre-segmentized network with surrogate ids; due to the relational model of the OSM data, this is an extremely resource heavy (and customized) process, and cannot receive OSM updates, but you can efficiently relate results to an external, static database via key ids
  • work with an unmodified OSM dataset as intented for Valhalla and keep references with incrementally added edges through (very costly) geometric likelihood queries (i.e. store in, and compare/relate to a statistical database via geometric predicates, e.g. equality or overlap)
1
  • Looking at those two options, option two seems very complex and resource-intensive (and expensive in upkeep). The first option was indeed the type of solution we were looking at. We're only interested in Belgium and this process should run once a month (we wish to work with the same graph each month). How reasonable is it to make a pre-segmentized network where the surrogate id's are derived from the way id's and node structure and can Valhalla Meili communicate those segment id's (or edge-id's) in its output? Mar 8, 2023 at 13:45
1

I can't say about Valhalla's details as we use a different approach but

  1. you can create a key for road segments with the triplet (node1, node2, way_id) for your analysis. I guess it should be possible to map Valhalla's id to this key
  2. the osm ids can change but in our experience it is very rare except in some regions (e.g. Chile) where there are some automated changes to OSM.
  3. whenever you update the OSM data, you update the key mapping and can perform some sanity check on potentially missing keys.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.