> I haven't had a chance to attempt it -- although it's not obvious to me if it would help with the preprocessing time.
My initial research suggested that CH has much faster query and preprocessing times (and lower memory overhead) than arc-flags, which is why I ended up implementing it. Plus you can even combine CH with arc-flags or ALT to get pointlessly good speed. However I don't know how much faster this "arc-potentials" is than arc-flags.
Using "approximate" contraction hierarchies doesn't necessarily lead to inexact results! There's a really interesting paper by the Karlsruhe guys [0] which discusses how you can set up a contraction hierarchy where the shortcuts only store their minimum and maximum travel times. At query-time this allows you to quickly generate a "time-profile corridor" between points A and B, which is a subgraph containing only those vertices which lie on a shortest path from A to B at some departure time. Then you only need to do a quick time-dependent dijkstra on the corridor ;]
