The Flexibility of GraphHopper

I often hear some misconceptions about the flexibility of GraphHopper. In this post I speak about GraphHopper core.

Flexibility Mode

GraphHopper is designed to be fast and flexible. For example you can route through entire Germany in about 1 second on average without any speed-up method, I’ll call this ‘flexibility mode’. You have to keep in mind that this involves traversing millions of nodes in the road network. In this mode you have all possibilities and advantages like on-demand profiles, small base graph, support for multiple vehicles and so on. A naive implementation for OpenStreetMap data probably won’t reach this query speed, even if coded in C++. Additionally we fight with the memory waste and garbage collection in Java.

Speed up Mode

The main disadvantage for the flexibility mode is that long queries will need lots of RAM, which is also not very handy on mobile devices. So you’ll have to limit the length of the route, increase the heuristical nature of the algorithm OR which is our default mode: switch to the speed up mode which uses a special algorithm called contraction hierarchies. The speed up mode comes with disadvantes e.g. only one query profile is possible or a bigger base graph. But it dramatically reduces the necessary RAM per query and as a nice side effect makes the query 50-500 times faster, depending on the length of the route. These are the reasons that the default mode for GraphHopper is the speed up mode. (And our Directions API is provided only in this speed up mode.) With GraphHopper switching between modes is just a configuration change (chShortcuts=fastest or chShortcuts=no) and our architecture was build with this in mind and is open for new and completely different speed-up algorithms. The benefit of this simplicity is that you can play around and tune the routing of one or more vehicles with various options in the flexibility mode, and then if you need performance or want to use it on mobile devices you can switch to the speed up mode.

Advertisement

Digitalizing GPX Points or How to Track Vehicles With GraphHopper

Recently I was asked again if I know a method, or even better a tool, which makes GPX points more align to the existing streets in OpenStreetMap. E.g. currently in Mapillary all recorded streets are not really smooth and digitalized if you look at them in detail. GraphHopper cannot do this out of the box but provides a toolchain which will make this digitalization easier.

Update: this is now open source.

Map Matching

The necessary process before an import would be Map Matching. Quoting (my own words ;)) from Wikipedia:

Map matching is the process of associating a sorted list of user or vehicle positions to the road network on a digital map. The main purposes are to track vehicles, analyze traffic flow and finding the start point of the driving directions.

Or as a picture:

I’m explaining in this blog post the simple steps which can taken to implement something like this with a very simple method. This is not an invention by me, other papers suggesting a similar technique. Also we should use some open testing data additionally to the normal unit tests. Some wordings are necessary before we go deeper:

• A GPS point is a tuple or object which contains latitude, longitude (, elevation) at which position it was recorded.
• A GPX point is a tuple or object which contains latitude, longitude (, elevation) and the timestamp at which it was recorded. And a GPX list ist a list of GPX points.
• In the digital world of maps we need a data structure to handle the road network. This data structure is a graph where the junctions from real world are nodes and the streets between them are the edges.

The question is also why would we need a routing engine at all?

Because:

• firstly you don’t need to write the import process of OpenStreetMap and the closest edge lookup and probably some other tools necessary for map matching and
• secondly the routing process will fill gaps between larger distances of two GPX points, and will be able to guess those gaps depending on the vehicle and
• thirdly using a routing engine will make the outcome more realistic, e.g. avoiding going left and then returning the identical street to go further in the straight direction.
• Lastly with GraphHopper you’ll be easily able to provide such a procedure even for the world wide case as it stores everything very compact and can be used in-memory or on-disc.

We start with an example:

All maps are from Lyrk and data is from OpenStreetMap contributors

In the left map you see the street parts highlighted where only the edges closest to the GPX points are selected. Whereas in the right map the most probable way was taken via a routing engine like GraphHopper.

The simple algorithm

The results for the map on the left side are easy to get, see the gist for example 1. For the map on the right side can try the following procedure explained in pseudocode here or see example 2 as gist for a more complete one:

1. Find 3 closest edges per GPX point
2. Associate every edge with a weighting, which is the distance from the edge to the point. The larger the distance the smaller is the probability that the best path goes through it.
3. Find the best path from the first GPX point to the last, but take into account the weighting and therefor the distance to the GPX points
4. As a post-processing step you need to assign the GPX points to the resulting path, you can do so via the edge ids and to find the coordinates you can either use path.calcPoints or the lower level API ala edgeState.fetchWayGeometry.

This simple algorithm should work in the most cases and is very fast

The enhancements

There are two limitations of this simple algorithm:

• If there are loops in the GPX list, then the Dijkstra from step 3 will throw data away
• and it will happen that another route than the route marked with GPX points is taken. E.g. in the case if the GPX signal is not that frequent and the edge of one point is rather short, which means it will have a small influence on the overall weighting of the taken route.

The following improvements are possible

• You could do a simple workaround and cut the incoming GPX list when you detect a loop and feed those GPX-list-parts to the algorithm.
• Or find the best route not from start to end but ‘step by step’. For example from pointX to pointX+4, then pointX+4 to pointX+8 and so on, where you need to merge the results. To avoid suboptimal paths at the intersection (here pointX+4) you’ll need to ‘overlap’ the routes. So you will need to calculate the routes for pointX to pointX+4, then pointX+3 to pointX+7, …. instead. Merging will be more complex probably.
• A more complex solution could be to maintain a list of e.g. 3 alternative end-results. As you already get 3 edge candidates for every GPX point you can then try to find all routes between them. You could think that this will slow down the search a lot but with GraphHopper you can tweak e.g. the Dijkstra or DijkstraOneToMany algorithm to do this in an efficient manner. E.g. if you want to get the best result but you want to search from multiple destinations you can do: DijkstraBidirectionRef dijkstra = new DijkstraBidirectionRef(hopper.getGraph(), flagEncoder, weighting); dijkstra.initFrom(nodeFrom, distanceToPossibility1); dijkstra.initFrom(node, distanceToPossibility2); … dijkstra.initTo(nodeTo, distanceToEndPossibility1); dijkstra.initTo(nodeTo, distanceToEndPossibility2); …

There are lots of other problems which you’ll encounter, that is the ugly real life with GPS signal errors, tunnels and so on. One example problem is if you are tracking e.g. a truck waiting in front of traffic lights in a one way street. You’ll see several nearly identical GPX points but as they have an error associated they won’t be identical and it could happen that they go ‘backwards’ in the one-way which will result in an extra loop if use the ‘step-by-step’ variant of the shortest path calculation:

Languator: Language Detection for Local Queries

When you have an address lookup service like photon you need language detection for the short local queries like “Berlin Alexanderplatz” to e.g. apply a specific analysis chain. Of course German language is rather simple, but detecting if it is French or Italian etc is much more complex.

I tried the language-detection from google code. And although it has high precision for normal text, it is relative slow (creating the profile and querying) and not specific to local queries although short generic queries should work (e.g. Twitter data). Another problem is the complex and inflexible Java API as it uses lots of statics etc. E.g. the size of the n-grams is not configurable.

So I hacked together a new language detection called languator in Java specific for short local queries and fed it with OpenStreetMap data. E.g. I used the germany.pbf to create the German language profile and france.pbf for the French profile and so on. If you keep in mind that you have lots of foreign names for POI and street in every country the following error values are okayish and better than what I found from other tools:

English: 22.9%, German: 7%, French: 20%, Italian: 18.8%

Another good thing is that you can feed languator with these 4 countries in 20 minutes and create millions of queries from those countries which takes ~10 minutes, which is at least 2 times faster than the google code tool.

I invite you to beat my numbers: fork and have fun!

Releasing GraphHopper 0.3 – Plan Your Outdoor Trips Beyond Two Dimensions

Today we are happy to finally release version 0.3 of GraphHopper – the Open Source road routing engine. Here is a screenshot showing our slightly polished UI

It shows a route result where elevation was enabled. Try it yourself at GraphHopper Maps or see the variety of already implemented use cases!

Highlights:

• You can easily enable elevation and Graphhopper will not only automatically import and display this, but you can actually use it for routing! E.g. for bike routing hills will be avoided. But also even for horse-routing.
• GraphHopper runs on Raspberry Pi and even in the Browser!
• GraphHopper is now available in 19 languages! See here for the details.
• A more powerful and compact API, including GPX support with turn instructions and elevation information.
• The address suggestions is done via photon and is available as part of our Web Routing API which is currently in closed alpha.

Thanks a lot to all contributors: NopMap, ratrun, konsoletyper, dardin88, lmar and b3nn0. And all the translators!

Details:

• You can store two weights per edge (dependent on the direction) – this allows using GraphHopper for interesting new use cases:
  • Biking and hiking tours can now avoid hills as up- and down-hill speed can be different.
  • With traffic data you can make routing more precise as speed values has to be different for the two directions.
• To make use of this new feature we implemented to read elevation data. For now only hgt files are supported but more will follow. This makes GraphHopper different to many routing engine, especially because we can scale with elevation to world wide coverage (although elevation data is only available for +-60°).
• The elevation Leaflet widget from MrMufflon is very useful and has a nice dragging feature
• Support to read OSM relations like for biking routes and overall improved bike routes as it is easier to tweak them
• Support for more than 2 points – still we need an improved UI to use this feature
• A new web API format which improves compactness and introduces the new but optional 3rd dimension. Additionally it makes it possible to retrieve the sub-path geometry for every turn instruction. See the documentation.
• Upgraded the Android demo to the latest mapsforge 0.4.3, and a further fix of an ugly bug
• Support to make it possible to click on instructions and see them on the map. Additionally navigation software can now easier find the next instruction
• Lots of the documentation is now in the source, which is better for the user to have up-to-date information. Or where it is possible to look at old docs too.
• and a lot more bug fixes …

Last but not least some months ago there was an article about GraphHopper in the Java Magazine and a session at FOSDEM. Did I mention that you should check out our enterprise offers 😉 ? Feel free to join our mailing list or follow us!

Have fun!

GraphHopper in the Browser: TeaVM makes Offline Route Planning possible in JavaScript!

Today I can make an exciting news.

Alexey Andreev is the author of a Java-bytecode to Javascript compiler called TeaVM. You may know GWT or Scala.js but TeaVM does not compile the sources, it compiles the bytecode to JavaScript so you cannot only use Java as the source language. Of course other advantages exists.

Now after a chat with him and lots of work (he did), he finally reached the goal to run GraphHopper in the Browser, either via a normal bidirectional Dijkstra or a fast algorithm called Contraction Hierarchies – see below for a demo!

But what would be a use case?

You might think: “Boooring! Yet another project running in JavaScript!” – Well, far away from boring! Think about FirefoxOS which currently has no offline navigation. About a year ago I had a discussion with (probably) some FirefoxOS guys on hackernews about this topic. I did not really believed that something like this could be possible at that time, but now I’m really proud that I can say that GraphHopper with TeaVM is one step in this direction!

Another use case could be a hybrid solution with GraphHopper in the back end and GraphHopperJS on the client. So this opens up new possibilities!

There were lots of problems.

One of the problems Alexey solved already months before the GraphHopper stuff was the missing ‘long’-type support in JavaScript. TeaVM emulates this via a ‘lo’ and ‘hi’ structure. But this is rather simple compared to other tricks he had to apply.

Another, not yet really solved, problem is the file-access: how would you load the graph only partially into memory? In Java I can just use memory mapping if there is only a few RAM available. But is there memory mapping in the browser from JS? (Unanswered question on stackoverflow for over a week now). Currently Alexey stores the data as JSON in the html file, but this is too inefficient and wastes too much memory. Hopefully we can find a better solution – maybe IndexedDB could be part of this solution.

Why is this only the first step towards an offline Navigation?

For offline navigation you will need geocoding which turns address strings into coordinates and also offline maps:

• For geocoding we would need a search engine like Lucene (Java) or something like my prototype of a JavaScript search engine called JSii (now I finally know a use case for this ;)). Additionally we need data, maybe consume OSM data from Nominatim or if it is just a city feed the streets directly to an index – this should be very easy.
• Offline maps is not that hard because you could use data from GraphHopper itself to print the map for the current nearby area, although this will be inefficient for larger areas it will be sufficient for most navigation applications. There are already some powerful libraries for in-browser rendering available – see here.

Try GraphHopper in the Browser!

Warning: this will load the routing data for Greater London ~14MB and can take a while!

If you zoom a bit in and out to cache the tiles, you can disconnect from the Internet and calculate offline routes anywhere! This should also work for mobile phones, of course calculating will be ‘slightly’ slower as Alex reported from 10x slower and even worse: on my old phone every browser I tried even crashed. Another minor bug is when you click outside of the routing area the app will stop working.

Get Started

Build teavm

1. git clone TeaVM
2. mvn clean package

Build GraphHopperJS

1. git clone modified GraphHopper
2. mvn clean package -DskipTests=true
3. unzip target/graphhopper-teavm-0.3-SNAPSHOT-teavm.zip
4. mv graphhopper-teavm-0.3-SNAPSHOT graphhopper-teavm
5. Create a gh-directory.js via the GraphhopperJsonGenerator class and specify “<your-osm-file> gh-directory.js” as command line arguments. TODO: Uncomment the query part as this requires to have moscow area.
6. cp gh-directory.js graphhopper-teavm
7. firefox index.html (don’t enable firebug as this slows down everything!)

Next steps

• I’ll try to integrate the changes Alexey did into GraphHopper for the next release.
• Currently this is just for standalone usage and not accessible from “outside JavaScript” (already done via TeaVM @PreserveOriginalName ?)
• Finally a fully navigation experience with geocoding and offline maps based on this work would be interesting.

Similar Projects

The only offline route planner in JavaScript I found was a public transport library called localroute, but not sure if it also works in the Browser. Let me know if there are similar projects as it is really hard to search for Routing & JavaScript 😉

Thanks!

A huge thanks to Alexey for making this possible – don’t forget to look into TeaVM !

 

GraphHopper News: Article in Java Magazine and FOSDEM 2014

Today the new Java Magazine from Oracle was published. You’ll need to register to view it or download one of the apps (Android, iOS). In this latest magazine my article about GraphHopper was published. It is about how I solved some big (data) problems in Java as well as some OpenStreetMap things to know and more!

If you are interested to hear more about this you can visit FOSDEM in Brussels (2nd February) where I talk about GraphHopper.

Update: Get the slides here!

Driving Directions with GraphHopper and Java on Raspberry Pi

GraphHopper is a fast and Open Source routing engine written in Java. The sources are at Github and you can try it online. Some months ago Java itself was ported to Raspberry Pi (ARM) and the latest versions even have the JDK from Oracle preinstalled. So there is no reason to not trying GraphHopper on Raspberry Pi as today my device arrived! I was using NOOBS and installed Raspbian where the JDK from Oracle and git-core were already installed. If you have an older release do:

sudo apt-get install oracle-java7-jdk

Now the GraphHopper setup itself is done with 4 easy steps, you’ll need internet access for downloading some files as well as for displaying the tiles:

1. git clone https://github.com/graphhopper/graphhopper/
2. # Avoid the “-server” option and reduce the default memory usage for  graphhopper. E.g. for Berlin you can do:
   export JAVA_OPTS=”-Xmx100m -Xms100m”; cd graphhopper
3. ./graphhopper.sh import europe_germany_berlin.pbf
   # This will take a bit and if it is finished you’ll see “[INFO] Started Jetty Server”. You should do this on your desktop and copy the resulting ‘europe_germany_berlin-gh’, ‘core/target’, ‘web/target’ and ‘tools/target’ folders instead of waiting so long. Under the hood it will do:
   # 1. get maven
   # 2. compile GraphHopper (takes 10min!?)
   # 3. install a smaller area ‘Berlin’ (6min for import, 5min for CH preparation). You can avoid this if you create the GraphHopper files on your Desktop which is a lot faster and then copy them to your Raspberry Pi via scp -r europe_germany_berlin-gh pi@raspberrypi:/home/pi/graphhopper/
   # 4. start a server at localhost:8989
4. Now you can access the started server via your browser e.g. from Raspberry Pi itself with iceweasel or chromium-browser (midori won’t work)
   http://raspberrypi:8989/
   If this doesn’t work try http://localhost:8989/ or connect Pi to your LAN and access GraphHopper web from your Desktop via the same URL.

Here is a screenshot – via tiles from Lyrk:

Raspberry Pi has less limitations compared to Android!

• You have a JDK 7 from Oracle, not the Dalvik thing which supports Java 5 only. So you can do even the GraphHopper file creation (“import”) directly on the mobile machine although this will be slower (factor 5-10) compared to my laptop. Also you can out of the box start and use a server on the machine. Sharing GraphHopper routing on Android is currently no out-of-the-box-solution but one should be able to make it working too.
• You have a fully working Debian distribution with nice ‘apt-get’ capabilities
• You can use all the available RAM and not only the 32MB which is a limitation per App on Android. So routing will be faster because until the 500MB (limit on Raspberry Pi) you can use the in-memory settings of GraphHopper or if using the slower MMAP setting then Raspberry Pi will load more data into the RAM compared to Android.
• On Android you can have offline maps via the mapsforge project. You couldn’t do the same for Raspberry Pi but there is now a branch called ‘rescue’ which enables you to have offline maps for Raspberry Pi. This branch already works, but is not yet released.
• For full maps you will need a separate monitor – e.g. this here? And address search which is currently only possible via online service.

GraphHopper an Open Source and Flexible Alternative to Google Maps API

Update: No need to install and maintain GraphHopper on your own expensive hardware. Sign up to the GraphHopper Directions API for business which makes it very easy, cost effective and reliable to consume GraphHopper routes with always up-to-date software and OpenStreetMap data.

On Monday we released version 0.2 of GraphHopper an Open Source road routing engine. GraphHopper is comparable fast to Google or Bing Maps, but if you use it in a LAN or directly from within your application it is a lot faster as it avoids the round trip over the internet, but furthermore if you need one-to-many or even many-to-many routes then GraphHopper is orders of magnitude faster. In this blog entry I’ll show you how to get everything you need to setup GraphHopper on your own servers. Hosting GraphHopper on your own servers also means: you can query it as much as YOU like, currently this means 300 to 600 queries per second which is dependent on your hardware, of course. This is measured from real life car routes larger than 100km. Now, as you’ll set up a fault tolerant system with at least two servers this means you can put a load of over 100 mio requests per day on your system. This is 1000 times more than the limit of the Google Maps Business API and again: for one/many-to-many the benefits are even larger.

1. Install GraphHopper

Do so, either via our quick start docs or directly from the source which is my preferred way as you can easily stay up-to-date and try out minor code changes a lot faster. Although it will require that you’ve installed git and the JDK:

$ git clone git://github.com/graphhopper/graphhopper.git
$ cd graphhopper
$ ./graphhopper.sh web europe_germany_berlin.pbf

You should see this console output: It will start a jetty server on port 8989 – so if no exception occured you can go to http://localhost:8989 and if you clicked on two positions you should see the route for a car (default – can be changed in config.properties):

2. World Wide Routing Service

I assume you need car, pedestrian and bicycle routing for your personal world wide routing service. For this routing service you need two runtime servers (to make the system fault tolerant) and for each at least 52GB RAM. Additionally you need one ‘smaller’ preparation server with at least 32GB of RAM to prepare the graph for fast routing – you only need it for updating the OpenStreetMap data e.g. once a week. If you want to avoid this overhead then ask us as we already GraphHopper files regularly for world wide coverage. Site notes:

• In Germany there is at least one provider where you get those three servers for under 250€ per months.
• If you cannot effort 2*64GB servers you could have a look into the memory mapped settings but this is slower – maybe not that slow via SSD, not yet deeply benchmarked.
• If you don’t need the speed up, e.g. if your routes are rather small or you want a personalizable request then you ‘only’ need 2*12GB of RAM. Or less for the memory mapped case, which could even make it suitable for world wide routing on your 64bit Desktop! (Okay, still you need the geocoding and tiles, but that is for another blog post ;))

World Wide Download

On the preparation server download the OpenStreetMap data for the whole world e.g. from here. Then do

 ln -s planet-latest.pbf planet-car.pbf
 ln -s planet-latest.pbf planet-bike.pbf
 ln -s planet-latest.pbf planet-foot.pbf

Import and Prepare

Still on the preparation server import and prepare the GraphHopper folders for car

 export GH_WEB_OPTS="-Dgraphhopper.osmreader.acceptWay=CAR"
 export JAVA_OPTS="-XX:PermSize=100m -XX:MaxPermSize=100m -Xmx28000m -Xms28000m"
 ./graphhopper.sh import planet-car.pbf

Do the same for bike and foot . This process takes 1h for the import and 2 to 5h for the preparation – depending on the vehicle.

3. Move to Leaflet and GraphHopper

Finally your client code needs to move away from Google Maps. Have a look into this description how to handle leaflet in general and into our own code how to handle the routing. Vote +1 for this issue to avoid this work :). Additionally to JavaScript we also provide a pure Java API useful for in-app communication.

Conclusion

Although GraphHopper is not yet feature complete it can already offer a production ready road routing service which is also easy to set up. Furthermore GraphHopper won’t take high administration costs as it is already very robust and used under high load in some companies for several months. Last but not least GraphHopper is easy to customize and can satisfy a wide range of different business needs.

Releasing GraphHopper 0.2 – Further & Faster Road Routing!

Today we’re releasing version 0.2 of our Open Source road routing engine GraphHopper written in 100% Java.

Faster!

• All algorithms are faster due to bug fixes and fine tuning
• A preparation is necessary for our optional speed-up technique called Contraction Hierarchy. This preparation is also faster.

Further!

• We finally fixed GPS-exact routing so you don’t have to workaround a junction-to-junction results

More exciting news will follow …

Have fun and try GraphHopper Maps with world wide coverage for pedestrians, cars and bicycles! You need support? Have a look at our enterprise options!

Notes:

• Get started!
• Download the source, the apk or the war file.
• If you have questions join our mailing list!
• See all fixed issues and the full list of changes for easier migration.

Free the Java Duke now and use it in Blender!

Duke, the Java mascot is a well known ambassador for Java. It is so important even Oracle still has a prominent site for it. The only problem is that the original source files can only be opened with a commercial application called lightwave3d.

For GraphHopper I took those files and created an OpenStreetMap variant with lightwave3d:

But I wondered why there is no possibility to use the files in Blender. Actually there is a plugin for Blender from Remigiusz to import the DXF files, but at the beginning it did not work for those none-standard files. So I contacted Remigiusz and the story begins. He not only improved his importer to make it working, but he invested hours to make a really nice Blender version for the Java Duke files!

Have a look:

The files are at Github! Thanks a lot again to Remigiusz!