Routing algorithm for geographical data

Question

I have a graph extracted from an American city: vertices represent road intersections, edges/arcs represent road segments connecting the intersections. For each road segment, I have the length and allowed driving speed. Furthermore, roads belong to different classes such as highway/residential/primary roads/....

I am looking for a routing algorithm which does the following:

• Compute a pairwise travel time matrix for each intersection (i.e how long it would take to travel from intersection i to intersection j.
• Query the quickest route from intersection i to j and returns a path (sequence of edges/arcs).
• The algorithm should be able to take updates into consideration. For instance, if there is a congestion on road segment (x,y) which increases its anticipated travel time, or if road segment (x,y) becomes blocked, the data structures should be updated incrementally, thereby updating all affected shortest paths (i.e. update all shortest paths through (x,y)).

The distance matrix will be queried very often so this should be precomputed, but the actual shortest paths can be computed at a later stage if that's more efficient. The number of nodes in the graph is roughly 5000-10000.

I was hoping that people could refer me to literature about this, preferably something that doesn't take weeks to implement. Obviously, simply running Dijkstra for each intersection takes too long. Running Floyd–Warshall all-pairs shortest path algorithm could be a possibility, but I'm not so sure how to update the result if the cost of one of the edges/arcs changes. Furthermore, it seems to be a slow approach since the algorithm ignores that most of the routes go through a small subset of the road segments.

I'm not necessarily looking for an exact approach. A good approximation suffices. Any pointers to literature or algorithm descriptions are welcome. I presume that any kind of routing software needs a similar algorithm. I'm mainly interested in something that works; it shouldn't necessarily be state of the art.

If this isn't the right place to ask, please let me know (especially if you know a better place :) ). Just to emphasize: I'm not looking for a software/database package, I'm looking for an algorithm.

Answer 1

Here is a l non-exhaustive List of algorithms.

A good comparison: https://arxiv.org/pdf/1504.05140.pdf

• transit node routing (Bast et al)
• contraction hierarchies
• Highway hierarchies
• A-star in combination with arc flags and landmarks (Goldberg et al)

Most of them are on Wikipedia.

From an implementation standpoint, the easiest is Landmarks for A-Star. Just use standard A-Star and as heuristic take the distance to the landmarks.

Details here: http://www.fabianfuchs.com/fabianfuchs_ALT.pdf Page 7 and Equation 2.3.

Check out the lectures from Prof Bast: https://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012 (Maybe newer versions also exist).

— please excuse the terrible formatting of this answer. Write a comment and I’ll fix it. I’m writing from mobile

Answer 2

As well as Floyd-Warshall, for all-pairs routing, you could consider Johnson's algorithm. An alternative to running Dijkstra for each intersection could be to run A* as the latter is usually considered to be faster.

I recommend you have a look at PgRouting, which is a plugin to PostGIS. It would be straightforward enough to import your data to PostGIS. PgRouting has about a dozen algorithms (including Johnson's, Dijkstra, A*, Shooting Star and variants on these), which would save you time in implementation that you could invest in bench-marking to compare speeds.

Answer 3

Have a look into the open source routing engine GraphHopper (note: I'm the author) which should be able to solve your problem fast as GraphHopper uses contraction hierarchies (CH). But even without CH, which requires preprocessing, you can use the one to many algorithm and you can incorporate traffic information and it will be still fast.

The none open source Matrix API is able to solve arbitrary matrices of size 1000x1000 and bigger across Europe (involving tens of millions of nodes) in seconds! And a small graph like you have with a 5 000x5 000 matrix request should be easily done in seconds too - even when using the (still very fast) open source version.