[Enhancement] Customizable Contraction Hierarchies

[airbreather]

On what looks like April 1, 2016, J. Dibbelt et al. published "Customizable Contraction Hierarchies" (DOI: 10.1145/2886843).

If their abstract is to be believed, this splits the preprocessing up into two steps: the first step is still the expensive workhorse, but it's done in a way that's independent of the exact edge weights; the second step "customizes" the preprocessed graph by adding in actual edge weights and can run much faster.

A hypothetical use case for this kind of thing would be if we wanted to route around bleeding-edge dynamic data. Consider a live feed that provides information such as "an accident at this location is causing routes using this particular edge to take an extra 2 minutes to travel along that edge".

• Traditionally, in order to accommodate this kind of data efficiently, I believe we'd have to do a ton of re-processing that's almost certainly impractical to do on a very regular basis unless the data set is very localized: by the time you finish the preprocessing of a graph that incorporates this information, it's easy to imagine this data already being outdated.
• If this CCH approach lives up to its claims, one could simply re-run "customization" to incorporate the new information into future route plans at a fraction of the cost of a traditional full contraction. As a logical extension of this, mobile clients might be able to react to these re-"customizations" and compute new routes on-the-fly while a traveler is actively traversing the route; if the optimal route changes as a result, the application could alert the user that a better route may be available and offer to switch to the new route.

RoutingKit (BSD 2-clause) has a sample implementation in C++ described here.

This sounds like something that Itinero could take advantage of.

[xivk]

Yes, already aware of this, and this is something I was planning on implementing anyway. As I said, let's dicuss on slack or something?

[xivk]

Added a development plan for this:

http://docs.itinero.tech/docs/itinero/development/features/2017-11-16-customizable-ch.html

@airbreather The idea is to start in this in the next weeks, the first step would be to build a proof of concept in the current 1.x codebase. Afterwards apply what we've learned to design a good way to implement this, either in 2.0 or 1.x.

[xivk]

Closing this issue here because the dev-plan is there now.

[jerryfaust]

@airbreather, Are you aware of any updates on the status of this issue? If there is a containing branch, I could do some testing/debugging. Respectfully.