Matching

While routing is the solution to find a route in a graph for a given start and end point, matching can be understood as the generalization of that approach towards a list of track points. In OS-Matcher this list consists of geo points and the graph is a street map. In that way routing becomes applicable to the street matching problem which is common today especially in the tolling industry.

Note

Street Matching Problem

Given a time bound track and a street map we want to identify the most likely route over the map that was taken by the track provider.

See also

See Data structures for information of the track and map data.

The OS-Matcher is challenging this problem by solving stepwise rather small routing steps of the matching and combines them to a routing solution. And the algorithm is an extension of the steps described in Routing.

First the track is processed to become a List of sampling points. That means for each track point a candidate search is performed, identifying segments in the street map from which the data point might had originated. Only those track points with at least one candidate are considered later on since, without a candidate on the street map, the algorithm has no useful hints from the track point where to route to on the street map.

Note

Some implemented optimizations are dependent on additional meta data for the track, like heading and velocity. Not providing those can lead to poor matchings.

Track to sample points

Fig. 13 Track to sample points

Beginning with the first sampling point, a routing is performed to the subsequent one. After a successful routing we search from the end of our found routing to the next sampling point and perform the next routing. Iteratively like that we get a matching of our whole track.

However an iterative matching approach like that can lead into situations where no routing can be performed even thou the real world track might would have been plausible. Let us take our example from Track to sample points and add a one-way street at an unfortunate position, which makes the track point \(E\) a sampling point with a candidate. Now our iterative approach will find a route connecting the candidates of sampling point \(A\) until \(E\) but cannot get further.

Matching leads into dead end

Fig. 14 Matching leads into dead end

The OS-Matcher idea is the usage of backtracking (see backtracking).

Note

One of the major assumptions is that the OS-Matcher is only routing between two points which are relatively near to each other. Like that routing for each possible candidates pair as described in Routing remains cheap since the routes are short considering only some street segments sometimes only one. However, if a track has many big holes (e.g. due to connection loss for an GPS vehicle track) this can lead to an increase in computing complexity if the edge points just before and after the hole have several to many candidates.