Thanks for the answers. I see what you're saying about the Markov properties - certainly something to think about.
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 ;]
Interesting! Yeah, I'm not terribly familiar with CH. Generally speaking, the trouble with the stochastic setting (perhaps you're already aware of this) is that it doesn't satisfy a very tempting (!) notion of sub-problem optimality that holds trivially in the deterministic setting. We used to have a simple counterexample in the paper but I think we might have had to remove it due to space constraints (here [1] is a copy). So I'd have to really think about what you're saying; it's not obvious to me that it should work in the stochastic setting, but perhaps it does. But thanks for the pointers either way, that's useful to know!
Ah, good question, no I haven't. I'm basing that comment on a vague memory of a graph showing query time vs preprocessing time for lots of algorithms. Looking back at the graph it seems ch with arc flags (chase) slightly improves query time, but for alt they only have results on non fully contracted networks (core-alt). Probably a memory issue.
Sorry if I misled - I haven't actually tried combining ch with alt as it turned out to be more than enough on its own. My point was just that ch is reported to synergise well with other methods, which makes it likely to be a good investment.
Interesting, we (GraphHopper) tested CH+ALT and saw also no improvements, also for CH with normal A*, although it is reported in papers that it should be faster. The idea about non-fully contracted networks is really nice and could be worth a try - thanks!
Wow, that seems counter-intuitive. I suppose it must be due to the computation of the heuristic, combined with how few relaxations are needed in CH.
GraphHopper is really nice work by the way. I believe you are still working on implementing stall-on-demand? Will be very interesting to see how much difference that makes on long-distance queries.
I guess it is the overhead of the heuristic that is too much compared with the saved visited nodes, but this is counter-intuitive for me as well and if I have more time will investigate this again.
GraphHopper is really nice work by the way.
Thanks!
I believe you are still working on implementing stall-on-demand?
Comments
Thanks for the answers. I see what you're saying about the Markov properties - certainly something to think about.
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 ;]
0. http://dl.acm.org/citation.cfm?id=2444020
Interesting! Yeah, I'm not terribly familiar with CH. Generally speaking, the trouble with the stochastic setting (perhaps you're already aware of this) is that it doesn't satisfy a very tempting (!) notion of sub-problem optimality that holds trivially in the deterministic setting. We used to have a simple counterexample in the paper but I think we might have had to remove it due to space constraints (here [1] is a copy). So I'd have to really think about what you're saying; it's not obvious to me that it should work in the stochastic setting, but perhaps it does. But thanks for the pointers either way, that's useful to know!
[1] https://drive.google.com/uc?id=0B0wBMIQFZpbwSERxUWRXUE94d1E
Do you have any numbers about how much faster CH+ALT was compared to pure CH?
Ah, good question, no I haven't. I'm basing that comment on a vague memory of a graph showing query time vs preprocessing time for lots of algorithms. Looking back at the graph it seems ch with arc flags (chase) slightly improves query time, but for alt they only have results on non fully contracted networks (core-alt). Probably a memory issue.
Sorry if I misled - I haven't actually tried combining ch with alt as it turned out to be more than enough on its own. My point was just that ch is reported to synergise well with other methods, which makes it likely to be a good investment.
Interesting, we (GraphHopper) tested CH+ALT and saw also no improvements, also for CH with normal A*, although it is reported in papers that it should be faster. The idea about non-fully contracted networks is really nice and could be worth a try - thanks!
Wow, that seems counter-intuitive. I suppose it must be due to the computation of the heuristic, combined with how few relaxations are needed in CH.
GraphHopper is really nice work by the way. I believe you are still working on implementing stall-on-demand? Will be very interesting to see how much difference that makes on long-distance queries.
I guess it is the overhead of the heuristic that is too much compared with the saved visited nodes, but this is counter-intuitive for me as well and if I have more time will investigate this again.
Thanks!
I've not yet digged into it but others have with less success but would be very interesting: https://github.com/graphhopper/graphhopper/issues/240#issuec...