Glad to hear from someone who's worked on routing!
Yes, it's quite possible that CH can be adapted to this -- I haven't had a chance to attempt it -- although it's not obvious to me if it would help with the preprocessing time.
I have not been very interested in approximations myself, since coming up with reasonable approximations seems rather obvious/straightforward, and yet producing any bounds on the error seems to be quite the opposite (at least for me)! That said, it's only a matter of time before someone does a comprehensive empirical study on that. :-)
The HMM was actually beyond the scope of this project, which is why you don't see any mentions of it. (The reference to check out regarding the path HMM inference would be #23 on Springer.) Its only significance is that it was the model of the dataset we used, but as far as we were concerned, we merely had a GMM.
Regarding time-dependent travel times, I'm not actually sure what the best model for that is (not just from a modeling perspective or data gathering, but also storage constraints and ease of inference); it's something I've been thinking of looking into, and I think others are as well. It does seem reasonable that a Markov model might work, since the travel time on a given edge at a subsequent time step only depends on the travel times on that edge and/or on incoming edges at a previous time step. However, I don't immediately see a reason for it to be Markov in solely the time dimension, which (if it's not) means that HMM algorithms such as Viterbi might not really be meaningful here (?), since the Markov properties I can see require a space dimension as well. It seems like a more general (but sparse & mostly-planar) Bayesian network to me. I could be wrong about this though.
Regarding Python vs. C++/Java -- it does make a significant difference, but not outrageously. I'm guessing you didn't see this part on the GitHub page, but it actually turns out this code is "only" 3× slower than the C++ equivalent used for the paper. (Note that this comparison is after a fairly heavy amount of optimization on both the C++ and Python codebases. Also note that the Python optimization involved far more than using Numba, although that was a notable part of it.) I think it makes a bigger difference in query times rather than preprocessing times, since the latter is far easier to parallelize (meaning you can just make it faster by throwing more hardware at it rather than by rewriting the code). But the overall problem is so computationally intensive that the main problem isn't the implementation language, it's coming up with an appropriate algorithm so that you don't need an astronomical number of CPU-days.
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
Glad to hear from someone who's worked on routing!
Yes, it's quite possible that CH can be adapted to this -- I haven't had a chance to attempt it -- although it's not obvious to me if it would help with the preprocessing time.
I have not been very interested in approximations myself, since coming up with reasonable approximations seems rather obvious/straightforward, and yet producing any bounds on the error seems to be quite the opposite (at least for me)! That said, it's only a matter of time before someone does a comprehensive empirical study on that. :-)
The HMM was actually beyond the scope of this project, which is why you don't see any mentions of it. (The reference to check out regarding the path HMM inference would be #23 on Springer.) Its only significance is that it was the model of the dataset we used, but as far as we were concerned, we merely had a GMM.
Regarding time-dependent travel times, I'm not actually sure what the best model for that is (not just from a modeling perspective or data gathering, but also storage constraints and ease of inference); it's something I've been thinking of looking into, and I think others are as well. It does seem reasonable that a Markov model might work, since the travel time on a given edge at a subsequent time step only depends on the travel times on that edge and/or on incoming edges at a previous time step. However, I don't immediately see a reason for it to be Markov in solely the time dimension, which (if it's not) means that HMM algorithms such as Viterbi might not really be meaningful here (?), since the Markov properties I can see require a space dimension as well. It seems like a more general (but sparse & mostly-planar) Bayesian network to me. I could be wrong about this though.
Regarding Python vs. C++/Java -- it does make a significant difference, but not outrageously. I'm guessing you didn't see this part on the GitHub page, but it actually turns out this code is "only" 3× slower than the C++ equivalent used for the paper. (Note that this comparison is after a fairly heavy amount of optimization on both the C++ and Python codebases. Also note that the Python optimization involved far more than using Numba, although that was a notable part of it.) I think it makes a bigger difference in query times rather than preprocessing times, since the latter is far easier to parallelize (meaning you can just make it faster by throwing more hardware at it rather than by rewriting the code). But the overall problem is so computationally intensive that the main problem isn't the implementation language, it's coming up with an appropriate algorithm so that you don't need an astronomical number of CPU-days.
Thanks for the great questions!
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...