A* Algorithm for very large graphs, any thoughts o

Question

I'm writing a courier/logistics simulation on OpenStreetMap maps and have realised that the basic A* algorithm as pictured below is not going to be fast enough for large maps (like Greater London).

The green nodes correspond to ones that were put in the open set/priority queue and due to the huge number (the whole map is something like 1-2 million), it takes 5 seconds or so to find the route pictured. Unfortunately 100ms per route is about my absolute limit.

Currently, the nodes are stored in both an adjacency list and also a spatial 100x100 2D array.

I'm looking for methods where I can trade off preprocessing time, space and if needed optimality of the route, for faster queries. The straight-line Haversine formula for the heuristic cost is the most expensive function according to the profiler - I have optimised my basic A* as much as I can.

For example, I was thinking if I chose an arbitrary node X from each quadrant of the 2D array and run A* between each, I can store the routes to disk for subsequent simulations. When querying, I can run A* search only in the quadrants, to get between the precomputed route and the X.

Is there a more refined version of what I've described above or perhaps a different method I should pursue. Many thanks!

For the record, here are some benchmark results for arbitrarily weighting the heuristic cost and computing the path between 10 pairs of randomly picked nodes:

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

Surprisingly increasing the coefficient to 1.1 almost halved the execution time whilst keeping the same route.

Answer 1

Usually A* comes along with too much memory consumption rather than time stuggles.

However I think it could be useful to first only compute with nodes that are part of "big streets" you would choose a highway over a tiny alley usually.

I guess you may already use this for your weight function but you can be faster if you use some priority Queue to decide which node to test next for further travelling.

Also you could try reducing the graph to only nodes that are part of low cost edges and then find a way from to start/end to the closest of these nodes. So you have 2 paths from start to the "big street" and the "big street" to end. You can now compute the best path between the two nodes that are part of the "big streets" in a reduced graph.

Answer 2

There's a really great article that Microsoft Research wrote on the subject:

http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx

The original paper is hosted here (PDF):

http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf

Essentially there's a few things you can try:

1. Start from the both the source as well as the destination. This helps to minimize the amount of wasted work that you'd perform when traversing from the source outwards towards the destination.
2. Use landmarks and highways. Essentially, find some positions in each map that are commonly taken paths and perform some pre-calculation to determine how to navigate efficiently between those points. If you can find a path from your source to a landmark, then to other landmarks, then to your destination, you can quickly find a viable route and optimize from there.
3. Explore algorithms like the "reach" algorithm. This helps to minimize the amount of work that you'll do when traversing the graph by minimizing the number of vertices that need to be considered in order to find a valid route.

Answer 3

GraphHopper does two things more to get fast, none-heuristic and flexible routing (note: I'm the author and you can try it online here)

1. A not so obvious optimization is to avoid 1:1 mapping of OSM nodes to internal nodes. Instead GraphHopper uses only junctions as nodes and saves roughly 1/8th of traversed nodes.
2. It has efficient implements for A*, Dijkstra or e.g. one-to-many Dijkstra. Which makes a route in under 1s possible through entire Germany. The (none-heuristical) bidirectional version of A* makes this even faster.

So it should be possible to get you fast routes for greater London.

Additionally the default mode is the speed mode which makes everything an order of magnitudes faster (e.g. 30ms for European wide routes) but less flexible, as it requires preprocessing (Contraction Hierarchies). If you don't like this, just disable it and also further fine-tune the included streets for car or probably better create a new profile for trucks - e.g. exclude service streets and tracks which should give you a further 30% boost. And as with any bidirectional algorithm you could easily implement a parallel search.