[n4r9]

Hi! If I remember rightly, you can run contraction hierarchies but stop short of the full contraction, and use the core vertices as "hubs"?

Hope you don't mind but I took a little look at your posting history and saw this: https://news.ycombinator.com/item?id=41954120

I've been researching this lately, as we've recently implemented traffic patterns in our routing model and are just now working on live traffic updates. The easiest way to adapt our existing code looks like Customizable Contraction Hierarchies. There's a really nice review paper here: https://arxiv.org/abs/2502.10519 . The technique is to apply nested dissections to build a "metric-independent" hierarchy based purely on connectivity, which gives a decent quality of contraction regardless of transit times. Is that what you mean by decomposing the network into "cells"?

[DennisL123]

I was referring to variants of Customizable Route Planning. Easiest to implement is likely the partitioner of Sommer et al, and a unidirectional multi-level dijkstra.

[n4r9]

Ah, I guess you mean this paper then: https://www.microsoft.com/en-us/research/wp-content/uploads/...

There are many similarities between this approach and customisable contraction hierarchies. The latter allows a particularly elegant query-time algorithm involving only a couple of linear sweeps, I suspect even in the many-many scenario.

[DennisL123]

Yep, that’s the one. There are a number of follow-up papers that engineer individual aspects of the implementation.