Routing

Routing is defined as a threefold-function \(R(A,B,M) = r\) where \(M\) is the street map and \(A\) and \(B\) are start and endpoint of the street map. \(R\) returns a valid navigation route from \(A\) to \(B\) on the street map \(M\).

The street map \(M\) in use is the OSM map. Start and endpoint \(A\) and \(B\) are GPS locations, which may not necessarily lay on the street map.

The routing algorithm falls apart into three parts:

Routing

After the candidates are found (see Candidate search), we have a list of pairs \(P = \{ (s,t) | s \in C^A, t \in C^B \}\).

The street map \(M\) is in its core a graph of nodes and edges (\(G(V,N)\)), the candidates are points on the edges and therefore not part of the graph. To overcome that, the nodes of the edge a candidate is placed on, become the first selected nodes in the routing.

Candidates on one way streets

Fig. 7 Candidates on one way streets

Notice, if the used street map supports information on travel directions, here already a filtering step is done by only considering one node of the edge aka the street segment.

For each combination of the one or two possible first nodes of \(A\) and \(B\) now a routing is done on the graph of the street map using a routing algorithm. The default algorithm in OS-Matcher is Dijkstra’s algorithm with the geographical length of an edge as its cost function.

So we end up with a list of routes, one for each pair \((s,t)\) and for each combination of possible nodes (\(n_i^s\) and \(n_j^t\)) for the edges (\(e_s\) and \(e_t\)) \(s\) and \(t\) are placed on.

Since all the routes are starting from candidates of the same track point \(A\) and likewise are ending on candidates of the same track point \(B\), often the resulting routes are very similar.

Basically similar routes

Fig. 8 Basically similar routes

In Fig. 8 we see two basically similar routes like that.

Contrary, in Fig. 9 we see two basically different routes.

Basically different routes.

Fig. 9 Basically different routes.

When very similar and very different routes are likewise found for the same start and end points, as we see in the following example, mathematically justifying how to choose the most realistic route is very difficult:

Finding the most realistic route

Fig. 10 Finding the most realistic route

In Fig. 10, \(C_1^A\) is the best candidate and \(C_3^A\) produces the shortest route, but both are not correct - \(C_2^A\) leads to the actual route.

To solve the problem, the routes are getting clustered, where each cluster represents a set of basically similar routes.

Clustering

As motivated above, a cluster is a set of routes which are representing basically similar routes. All routes in a cluster are ranked by a comparison class BestSimilarRouteComparator, which compares the candidate’s rank according to the system described in Candidate search.

Any new route which shall be placed into a cluster is compared to the highest ranked member of that cluster, the role model of that cluster, using a similarity function. The function isSimilar() compares two routes \(r_0\) and \(r_1\) against several criteria. Only when all of them are met, the route will be added to the cluster.

The criteria are:

  • max length difference, the outermost two routes may differ in length (it is recommended to set this value to \(4 \cdot candidate\ search\ radius\))

  • the source node of one is contained by the other, \(n^s_{r_1} \in r_0\) or \(n^s_{r_0} \in r_1\)

  • the target node of one is contained by the other, \(n^t_{r_1} \in r_0\) or \(n^t_{r_0} \in r_1\)

  • source and target node are not visited twice

Note that the second and third criteria do not need to be fulfilled by both routes, only by one.

Similarity criteria

Fig. 11 Similarity criteria

Let’s recap the example illustrated by Fig. 10. The track point \(A\) originates indeed from the roundabout. But due to the drift of \(A\) (may be induced due to data noise or inaccurate map data), the best candidate sits on a one-way street to the south (\(C_1^A\)). The best (shortest) route however starts at the most unlikely candidate (\(C_3^A\)), while the actual route starts at (\(C_2^A\)).

Clustering is a way to overcome those and similar situations by filtering out unlikely routes which are just considered because of its candidate rank. Within a cluster, however, the candidate’s rank assures that we get the most accurate starting point from all the basically similar routes.

Clustering

Fig. 12 Clustering

Now we have a set of clusters, each having a role model.

Final Evaluation

From each cluster the role model is chosen and all of those role models are compared using the class BestRouteComparator. The Comparator has three criteria:

  • length, which selects the shortest route

  • cost, which selects the route with the lowest routing costs

  • number of points, which selects the route with the least number of nodes

The comparator comes in two flavors of criteria preference:

  • cheapest, criteria order \(cost > length > number\ of\ points\)

  • shortest, criteria order \(length > cost > number\ of\ points\)

The best route according to this comparison is then the result of our routing \(R(A,B,M) = r\).