Time-Dependent Contraction Hierarchy

storm 2017-09-10 08:43:14 UTC #1

Hello community,

In the real world we have many junctions with time-turn restrictions, edges with traffic jams etc…
Using ALT and CH algorithms we need to preprocess a graph every time when the weight of endges are changed.

There are a few customizable algorithms e.g. CustomizableContractionHierarchy.

github.com

RoutingKit/RoutingKit/blob/master/doc/CustomizableContractionHierarchy.md

# CustomizableContractionHierarchy

CustomizableContractionHierarchies (CCH) are an index-based speedup technique for shortest paths in directed graphs that can quickly be adapted to new weights. CCHs use, contrary to regulars CHs, a three phase setup:

1. Preprocessing
2. Customization
3. Query

The preprocessing is slow but does not rely on the arc weights. The Customization introduces the weights and is reasonably fast. Finally, the actual paths are computed in the query phase. A common setup consists of doing the preprocessing once and the customization per user upon login. Further one can use a customization to incorporate live-traffic updates.

All classes and functions are defined in `<routingkit/customizable_contraction_hierarchy.h>`.

## Preprocessing

The central object is the index itself and is called `CustomizableContractionHierarchy`. It is used as following:

```cpp
std::vector<unsigned>tail = ...;
std::vector<unsigned>head = ...;
std::vector<unsigned>node_order = some_expensive_ordering_routine(tail, head);

This file has been truncated. show original

What are the prospects for using CCH(or other Time-Dependent algorithms) in GraphHopper?

Best regards, Storm.

karussell 2017-09-10 12:29:18 UTC #2

Thanks for the linked repository and this sounds really interesting, especially as it is under a nice license and doesn’t look like the most complicated C++

There are no plans now from us as with ALT such things are already possible. For most scenarios like traffic jams etc there is no re-preprocessing necessary unlike with CH, you can read about this in more detail in this blog post.

But of course: we would love having this! Maybe you have time and interests in a contribution to GraphHopper ?