Customizable Contraction Hierarchies go a long way towards solving that, they're quite similar to CRP with regards to both customization and query time. Also, r

Customizable 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.