gregerhardt
commented
9 years ago UPDATE: I've come to a solution that serves my needs for the time being, so this is not a time-critical issue for me. Although if it is implemented, I would look into switching over.
It is a bit tangential, but in case anyone is interested, here are some of the tools that I've used or looked into:
I am using the DTA Anway classes (https://code.google.com/p/dta/) to store my networks. This is derived from a dynamic traffic assignment project, but gives me a package to read networks in a couple of different formats, and deal with intersection control, centroid connectors and such things. I originally used an SP algorithm implemented in this package, but I was naively re-calculating the paths with each call, so it was slow.
To speed things up, I considered: pandana, networkX, aequilibrae, and scipy. Of those, I found:
- pandana doesn't currently have the SP functionality exposed, although it looks promising when that happens.
- networkX seemed to struggle with the size of my network (~15,000 nodes), and I got feedback that it's SP was slow.
- aequilibrae looks promising as a traffic assignment/travel modelling package. It's SP method is based on scipy, so for my purposes I opted to go directly to the source.
- It turns out that scipy has some pretty good SP implementations. You specify the network in a sparse matrix format, and it gives back 1) a matrix containing the impedance between each node pair, and 2) a matrix containing the predecessor nodes in the shortest paths, which allows you to re-construct the path. In my case, I can just calculate the paths once, and then re-trace what I need for each GPS point using the predessor matrix. This improved my runtime by 2 orders fo magnitude, so I'm happy. The downside is that it does it for every node pair, so the resulting matrices can be quite large in terms of their memory footprint, but it works ok for me.
My bottlneck is currently in matching points to the N nearest links, but that is another topic.
fscottfoti
songololo
knaaptime
smmaurer
Can the underlying shortest path functionality in pananda be exposed so it can be called using a python method? Given a node pair A-B, I want to get back 1) the impedance from A to B, and 2) the sequence of node or link IDs that define the shortest path from A to B. Doing this for a list of node pairs is even better.
My specific use case is that I am matching probe vehicle GPS points to the a network. Since they are only collected every 60 seconds, I need to impute the path between points, so I end up building many "short" shortest paths to do so. My current implementation works, but is slow, and I'm hoping your multi-threaded C++ implementation can speed things up.
pandana looks like it could turn into a nice general purpose networks container for transportation modelling/analysis, and I think exposing more of this functionality would help in that regard. Many thanks!