4 ms·

OSRM founder, here. Yes, you are right, many of the speedup techniques are related. My personal opinion is, tho, that looking at the identification of important

OSRM founder, here. Yes, you are right, many of the speedup techniques are related. My personal opinion is, tho, that looking at the identification of important nodes is best captured by the ideas of applying partitioning to multi-level dijkstra and by what’s called hub-labels. The latter has a close relationship to Contraction Hierarchies.

n4r9 1y ago
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 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 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 1y ago
  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 1y ago
    Ah, I guess you mean this paper then: https://www.microsoft.com/en-us/research/wp-content/uploads/2013/01/crp_web_130724.pdf 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 1y ago
      Yep, that’s the one. There are a number of follow-up papers that engineer individual aspects of the implementation.

n4r9 1y ago

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 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 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 1y ago
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 1y ago
  Ah, I guess you mean this paper then: https://www.microsoft.com/en-us/research/wp-content/uploads/2013/01/crp_web_130724.pdf 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 1y ago
    Yep, that’s the one. There are a number of follow-up papers that engineer individual aspects of the implementation.