3 ms·
To be fair, contraction hierarchies are inflexible for exactly the reasons OP described. CRP (aka multi-level dijkstra) is more flexible, but there's always a t
by morganherlocker 6y ago
To be fair, contraction hierarchies are inflexible for exactly the reasons OP described. CRP (aka multi-level dijkstra) is more flexible, but there's always a trade off between query speed, pre-process/weight-update speed, and route quality. These services are very expensive to run at global scale if you need multi-modal or live congestion support.
- lorenzhs 6y agoCustomizable Contraction Hierarchies go a long way towards solving that, they're quite similar to CRP with regards to both customization and query time. Also, route quality isn't part of the trade-off: all of these methods are exact. I would argue that updating the routing algorithm's data structure isn't the expensive part of reacting to live traffic. Getting and processing the raw data sounds a lot harder than re-running the customization phase of routing preprocessing.