You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
@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.
@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.
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".
RoutingKit (BSD 2-clause) has a sample implementation in C++ described here.
This sounds like something that Itinero could take advantage of.
The text was updated successfully, but these errors were encountered: