46

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?

Improve this question
3

3 Answers 3

Reset to default
23

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).

Improve this answer
15

Not sure if it is newer but pgRouting has a Shooting-Star algorithm:

Shooting-Star algorithm is the latest of pgRouting shortest path algorithms. Its speciality is that it routes from link to link, not from vertex to vertex as Dijkstra and A-Star algorithms do. This makes it possible to define relations between links for example, and it solves some other vertex-based algorithm issues like “parallel links”, which have same source and target but different costs.

ESRI's Network Analyst extension uses the hierarchical approach you mentioned to limit solving times:

Finding the exact shortest path on a nationwide network dataset is time-consuming due to the large number of edges that need to be searched. To improve performance, network datasets can model the natural hierarchy in a transportation system where driving on an interstate highway is preferable to driving on local roads. Once a hierarchical network has been created, a modification of the bidirectional Dijkstra is used to compute a route between an origin and a destination.

There is a very detailed white paper with examples on this approach at the ESRI site - however it requires you to log in to download (Hierarchical Routes In ArcGIS Network Analyst White Paper).

Improve this answer
11

Contraction Hierarchy is a very fast algorithm:

This algorithm is RAM friendly while executing a query (to hold a contracted graph some more RAM is necessary as well as massive preprocessing)

There are some other algorithms - including the ones that solve public transit routing:

Microsoft is also doing some research:

(well, Daniel Delling is from Karlsruhe too)

You can get a nice introduction and overview of available algorithms:

Warning: german (!) lectures. but at least the headers can help you to get more information (ALT, Arc-Flags, CHASE, ...) or the appended literature!

update

GraphHopper now implements contraction hierarchies and also other algorithms, you can also try out the demo.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.