There are works like Reach for A* from Microsoft researchers and Highway Hierarchies by Sanders and Schtolz (if I spell the name correctly) from Karlsruhe Uni. Both of them reduce the calculations order a lot, and speed up thousand times on large graphs (see the results in the linked documents). The latter work led to Open Source Routing Machine, which unfortunatly isn't popular enough and not adapted (I couldn't compile it although tried hard).
At the same time, the dbs that I tried, Spatialite and PgRouting, according to their docs, offer just Dijkstra and A* algorithms. I've not even seen bi-directional search mentioned, which saves calculation time twice in my experience.
Are there better algorithms for databases or other applications?
Answer
The truth is that most people use a custom variation of the A* algorithm. You will see this across the most of the "big guys"(I can't say who they are in a public forum, but I can tell you that you probably use one of them - guaranteed), where the modification of the heuristics is very dependent on the datasets that they use.
You mentioned pgrouting already, which I would consider a "traditional" option. It is good for doing simple routing algorithms and for most problems. It is also easy to use and uses a traditional database at its backend.
Nevertheless, it really depends on the scale and type of problem you are trying to solve and routing is a graph problem.
Once again, the "big guys" usually have a lot of data that is associated with their graph (for example, traffic data, bus routes, walking paths) that affect the routing algorithm. These are known as multi-modal trip planners (where you also have a choice of planning "modes" - no bike paths - only public transit - that kind of thing). You can think how trip planning also becomes a time sensitive issue (i.e if you walk back a few edges back, you will be able to catch the subway that takes you to your destination forward much faster than if you just tried to navigate the edges forward using the lowest cost).
The "big guys" don't store their data in a traditional database per se, they use pre-computed graphs (welcome hadoop/mapreduce clusters!). As you can imagine, these graphs become really big, so knowing how to connect the edges of adjacent graphs can be a challenge.
Anyway, I would recommend you look at some multi-modal routing graph projects:
Graphserver comes to mind. Not a lot of documentation but a lot of pure coding awesomeness (AFAIK, I believe MapQuest uses a variation of this project for some of their routing products).
Another option would be the OpenTripPlanner which has a lot of smart people behind it (including people from graphserver).
No comments:
Post a Comment