GraphHopper Maps – High Performance and Customizable Routing in Java by Peter Karich.
From the post:
Today we’re proud to announce the first stable release of GraphHopper! After over a year of busy development we finally reached version 0.1!
GraphHopper is a fast and Open Source road routing engine written in Java based on OpenStreetMap data. It handles the full planet on a 15GB server but is also scales down and can be embedded into your application! This means you’re able to run Germany-wide queries on Android with only 32MB in a few seconds. You can download the Android offline routing demo or have a look at our web instance which has world wide coverage for car, bike and pedestrian:
The trip to the current state of GraphHopper was rather stony as we had to start from scratch as there is currently no fast Java-based routing engine. What we’ve built is quite interesting as it shows that a Java application can be as fast as Bing or Google Maps (in 2011) and beats YOURS, MapQuest and Cloudmade according to the results outlined in a Blog post from Pascal and with tests against GraphHopper – although OSRM is still ahead. But how can a Java application be so fast? One important side is the used algorithm: Contraction Hierarchies – a ‘simple’ shortcutting technique to speed up especially lengthy queries. But even without this algorithm GraphHopper is fast which is a result of weeks of tuning for less memory consumption (yes, memory has something to do with speed), profiling and tweaking. But not only the routing is fast and memory efficient also the import process. And it should be easy to get started and modify GraphHopper to your needs.
Contraction hierarchies are a very active area of graph research.
Contraction Hierarchies at Wikipedia has a nice coverage with a pointer to Robert Geisberger’s thesis, Contraction Hierarchies: Faster and Simpler
Hierarchical Routing in Road Networks.
You may also be interested in:
Efficient Route Planning by Prof. Dr. Hannah Bast. A wiki for a 2012 summer course on route planning. Includes videos, slides, exercises, etc.