Having coded up a semisolid implementation of time-dependent contraction hierarchies (which might not even get used, because of the very same data accessibility issues you outline), it seems at first glance quite straightforward to adapt CH preprocessing to this model. To contract a vertex you just look at whether each potential witness path has a nonzero probability of being a shortcut. I suppose you could cut preprocessing time down by replacing "nonzero probability" with "probability greater than epsilon" to get a sort of approximate hierarchy.
You refer to the edge weights as an "hmm", which I guess stands for hidden markov model. It doesn't seem like they use that term in the paper, although if you made the data time-dependent would edge weights then be a genuine markov process? Would something like the Viterbi algorithm become a useful subprocess of the overall algorithm in that case?
The current big open source routing engines tend to be written in c++ or java. Do you think using python makes a significant difference in query or preprocessing times? *
*Edit: Just noticed the Numba dependency, which probably answers this question.
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!
> 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 ;]
Did you measure memory usage for e.g. San Francisco or Berlin?
Why did you consider this non-commercial license? Especially since you say 'I don't plan on actively maintaining it'
Regarding the license and maintenance, it's what seemed the most suitable for me given the effort I'd put in and what the code actually did. But the idea was that if it's unsuitable for you, you can certainly contact me and make a request for them to be different, and I can try to license it differently on an individual basis.
I'm asking as other open source projects (like ours, see my profile) might not look in your code just because of the license. And yes, that is the tricky thing about open source: accept that other people make money with it and try to do this too ;)
### Dependencies
- NumPy is the only hard external dependency.
- Numba, if available, is used for compiling Python to native code (≈ 3× speedup).
- PyGLET, if available, is used for rendering the results on the screen via OpenGL.
- SciPy, if available, is used for slightly faster FFTs.
I don't believe any apps utilize these algorithms, and for good reason. The main problem is that SOTA is a very computationally intensive problem. On the example shown, a plain Dijkstra takes a fraction of a second (you can imagine A* is faster, and over time these have been sped up by a factor of millions, IIRC), whereas SOTA takes dozens of seconds to run. The difference increases quickly for larger networks and time budgets.
If you check out the paper I linked to, you might get a better idea of just how computationally intensive this process is. If I recall correctly, classical point-to-point pathfinding algorithms have even advanced to the stage that, with some reasonable (albeit clever) preprocessing, queries on very large networks can be done in a matter of milliseconds on mobile CPU power. Compare that to this algorithm, which takes dozens of seconds to run on a network the size of San Francisco, or at best in dozens or hundreds of milliseconds after practically prohibitive preprocesssing (e.g. 30 CPU-days and tens or hundreds of gigabytes are pretty normal) on a Core i7 CPU. It's just not scalable yet, which is why we've been working on it as a research problem (as have many other people).
Edit: There are lots of obstacles; the above was just one. Another one is that even the existing model assumes the same travel time distribution throughout the day, which is clearly unrealistic (you can imagine fixing this would blow up the running time even more). Yet another one is the problem of getting enough traffic data to construct useful travel time distributions, which means only a major company with existing data (like Google) could release an app that actually initially works with real data. Barring some kind of contract with a big company, everyone else would have to just release an app to gather data, and it would only become useful after a long time (if people are even willing to give away precise location data to random app creators).