17

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.

Improve this question
3
  • 3
    I think that most routing algorithms do not operate with a "sense of geometry", instead a geometric attribute is calculated and used as a cost (i.e. distance measure of a polyline). I've never used Neo4j, but it looks really capable and I may be using it soon. I just took a look at the documentation and it looks possible to use A-Star: docs.neo4j.org/chunked/stable/graph-algo.html docs.neo4j.org/chunked/stable/… pgRouting is also capable, and I'm a huge fan of it. It would be interesting to compare the performance of these two solutions.
    – Allan Adair
    Aug 24, 2011 at 9:55
  • First, I would suggest to Look at urbansim an opensource land use model. As for your routing question, If this is planning application, then I would suggest looking at software like TransCAD, CUBE, PLANAR, or EMME/2 first for functionality and user interface. They usually give out 1 hour or 2 hour demo cds of their software (software you can run for an hour or two to get a feel for it). If you want to build something for online use or desktop use, then look at pgRouting; however, from experience, sometimes, it's not as easy as how the workshop/tutorial portrays it.
    – dassouki
    Aug 24, 2011 at 12:50
  • I got pgrouting with a-star working and it is awesome! It answers yes on my first 3 questions. Still i wonder if someone here knows anything about generating verbose navigation directions. Is there some tooling that cooperates with pgrouting that generates verbose directions ("After 200m turn left, etc") from the output of the calculated route?
    – mrg
    Aug 25, 2011 at 14:02

2 Answers 2

Reset to default
9

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:

  • In pgRouting you don't have to worry about AStar implementation in sql, that allready implemented.
  • Yes, pgRouting can give you list of nodes and edges
  • I don't think that pgRouting can give you such information with out some custom work around queries. But maybe I'm wrong, maybe somebody has done this and can help you more about this question.

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

Improve this answer
4
  • It is good to hear from someone who has actually tested both systems. Meanwhile i have a lot more experience with pgrouting. I noticed that pgrouting builds the entire graph for each query and that makes it rather slow for large networks (Germany size), so i don't see why pgrouting would require less memory than Neo4j. My next try will be to get the entire graph static in ram and route on that (with neo4j, nx_spatial etc) to ensure a faster response for real time routing.
    – mrg
    Nov 23, 2011 at 18:58
  • Yes, more larger the graph, the more difference is between pgrouting and neo4j. Probably if you put entire graph into memory than it would be the fastest solution, no question about that. Neo4j is quite fast when all graph is loaded into memory. Don't know about nx_spatial, I have not tested it, but maybe I will. I believe that it could outperform even Neo4j. But this solution is good if it is acceptable for the your application.
    – Mario Miler
    Nov 23, 2011 at 19:55
  • 1
    @mrg not sure if it is still a problem for you but there is OSRM (C++) and GraphHopper (Java). Both scale to world wide graphs and e.g. GraphHopper needs under 1gb for Germany (where I'm the author of)
    – Karussell
    May 6, 2013 at 5:39
  • Karussell, thank you for the info! I had already found OSRM, but GraphHopper is new for me.
    – mrg
    May 7, 2013 at 6:18
0

You can also have a look at our RW Net 4 package (www.routeware.dk). It can do such shortest path calculations using A* straight from a SHP file. The Basic package at €500 seems sufficient for your needs.

Improve this answer
1
  • Thank you for your fast response, but my project is still in a phase that I am unsure if it warrants spending money right now. Also i got pgrouting working on my data so for now that unknown has been tackled.
    – mrg
    Aug 25, 2011 at 14:06

Your Answer

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

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