I am building a route planning system, but i have still to decide what underlying routing engine i will use. So far i have found pgrouting and neo4j.
I have my route network in a postgresql/postgis database (imported from a shapefile). I have made queries to extract nodes (endpoints of ways where you have to make a decision what direction to go or dead ends) and to extract edges (often made up by several consecutive ways). All my edges are bidirectional.
My main goal is to calculate routes on this network using an A-star algorithm where distance =cost.
My feeling tells me that a graph database like neo4j is the way to go (as it seems to be made for just this purpose), but they don't seem to support A-star by default and also there is no real sense of geometry. It seems better suited for social networks instead of maps.
- Would pgrouting fulfill my needs?
- Is it fast enough for on the fly queries (+-2000 nodes, +-4000 edges)? Normally this would be a few ms for A-star, but i am unsure about this implemenatation in sql.
- Does pgrouting A-star give me a list of nodes and edges?
- In most examples i see about pgrouting i notice there is usually a list of commands after calculation of the route (like "At X turn left, etc"). Does pgrouting produce this or is this from another system?
Hopefully someone can give me some information about what system to choose. Neo4j, pgrouting, or some other system.
Best Answer
I'm currently exploring the same problem as you, for the purpose of research paper. Before I started to test these two databases, I had the same presumption as you. That Neo4j graph database would be perfect solution for this kind of problem. And partially it is, but with lot of problems.
First problem is that A-Star is only implemented if you are using embedded database, not via REST API (server). If you want to use Neo4j with REST API, then only Dijkstra algorithm is supported. Second problem is hardware memory requirements for Neo4j. For routing (Dijkstra) on "larger" networks you need a lot of RAM. For large network I mean something like size of Germany OSM road database. I have run my tests on 6GB RAM server (that's all I have currently) and only smaller networks could be routed without OutOfMemory exception errors. "Small" networks in my test cases are for example, OSM road database for Austria or Croatia. Concurrent queries I still haven't tested with Neo4j.
All of these problems do not exist in pgRouting. Memory is not such an issue but concurrent queries increase needed amount of memory. For example, if you have two concurrent requests, double amount of memory is needed. This wasn't an issue even for a Germany OSM dataset, pgRouting routed without any problems all concurrent requests.
Performance: In most cases, Neo4j outperforms pgRouting. But only if there is enough memory for the given dataset and if all nodes and relationships are in memory (hot start). Increase/decrease in performance depends on lot of factors but mostly on size of network and distance (hops) between source and target node.
Your network size is quite small, so you shouldn't have any problems with memory. Probably Neo4j is not a bad choice but you have to adapt to a "little" different data model than in standard relation databases.
To answer you questions:
I dont know if it will help you directly, but one of the fastest routing server I found is osm2po. It works with OSM dataset and is quite fast. Only dijkstra is currently implemented but developer announced AStar also. I hope that some of this will help you. :)