support CH for matching

[karussell]

Currently it is based on none-CH routing giving us several advantages. We should try CH and see if it is faster.

[kodonnell]

I've quickly hacked this, and in my (single) test case (three points separated by a few hundred kms), I go from 38s to 2.8s, which is pretty significant. (Benefits are likely to be less for frequent GPS points, I'm guessing ...)

I'm happy to try to implement CH, but first I'd be interested in hearing the following:

• what are the above 'several advantages'?
• are the main disadvantages of CH that we lose flexibility (turn restrictions, alternative routes, etc.)?
• any suggestions on how to do it? I basically just passed the GraphHopper instance to the routeLength part of spatialMetrics, as I couldn't figure out how to run CH in a similar fashion as it is now. It worked (after disabling some error detection), but it's not pretty.
• probably related, but any expansion on TODO allow CH, then optionally use cached one-to-many Dijkstra to improve speed?

[karussell]

are the main disadvantages of CH that we lose flexibility (turn restrictions, alternative routes, etc.)?

Both mentioned points are not yet implemented with CH but are at least possible. Still 'loosing flexibility' is correct: if you want to change something 'per-request' then it is a lot harder with CH, if possible at all.

any suggestions on how to do it?

The GraphHopper.getAlgorithmFactory picks the correct algorithm and replace the new DijkstraBidirection call. Probably not much more necessary.

then optionally use cached one-to-many Dijkstra to improve speed?

For map matching we use hidden markov chain where we have several possibilities per measurement and we need all combinations of distances to estimate the transition probability and therefor we can use a faster one-to-many algorithm, but CH should speed this up already enough. Also one-to-many improvement is a lot easier applicable after #66

[kodonnell]

The GraphHopper.getAlgorithmFactory picks the correct algorithm and replace the new DijkstraBidirection call. Probably not much more necessary.

Hmmm, I played with that, but then it requires duplicating a lot of the logic in GraphHopper.calcPaths (setting up weights, etc.). I thought it'd be better to just use GraphHopper.calcPaths directly, but that comes with a downside: a new QueryGraph is created each time, so we lose the virtual nodes (which are required later on in the map matching). I've hacked around this by changing virtualEdgesMapKey and (reverseVirtualEdgesMapKey) to return a key based on fetchWayGeometry (so it's independent of the virtualNode IDs and still matches those in here). It works, but isn't pretty - what do you suggest?

• somehow utilise GraphHopper.calcPaths? And just remove all virtual nodes from the path in SpatialMetrics.routeLength, so we don't have to track them? This has the added benefit that we don't need to do a double lookup (i.e. here and in the actual routing). But we can't (?) use one-to-many Djkistra ...
• basically copy the content of GraphHopper.calcPaths into SpatialMetrics.routeLength, so we can re-use the QueryGraph.
• something else?

It'd be good if we consider this part of a bigger scope to allow the user to e.g. change/configure the algorithm (if that's in scope).

[karussell]

I'm not sure about the problem. I think you just need to replace the call to new DijkstraBidirectionRef with the factory.createAlgo()? (Of course as I didn't try it it might not be sufficient)

[kodonnell]

To call createAlgo you need e.g. AlgorithmOptions. Unless there's a way to get that easily, then don't you have to do all of this?