GraphHopper Routing Engine 0.8 Released

We are proud to release version 0.8 of our open source GraphHopper routing engine! Here is the polished snap-to-road feature in two screenshots:

matching-sim

A big thanks goes to all of our contributors and translators!

To become a contributor see our contributing guidelines and e.g. the good first issues. Read here to see how to become a sponsor and how to benefit from our expertise or donate us.

Here are the highlights for GraphHopper 0.8:

  • the new map matching algorithm based on hidden markov chains is finally integrated and gives us a big quality improvement, thanks to @michaz (GraphHopper) and @stefanholder (BMW Car IT). This feature was already deployed 2 months ago in our GraphHopper Directions API. Some improvements were done by @kodonnell.
  • the osm import module is split from the core #450 making Android and iOS integration cleaner
  • there is a new overlay module #781 allowing you to specify GeoJSON at import time to change properties like access and speed of the routing graph
  • new ‘more standard’ code formatting for all repositories #770
  • many UI fixes like upgrading to leaflet 1.0, thanks to @fbonzon (Bikewithme)
  • updated the iOS port, thanks to Calin @clns
  • travis build enhancements like running against jdk9 and deploying snapshots #806, thanks to @mprins
  • a new ‘on-demand’ weighting with a new data encoder #730
  • elevation interpolation in tunnels&bridges #713, thanks to @highsource (DB Systel)
  • fixing time calculation for turn costs #393
  • a new short_fastest weighting #747
  • Several updates to Android build/sample from @devemux86 (talent)
  • several bug fixes (incl. three major)

The changelog is here – please read about the necessary changes to your config.properties and/or your Java code. Dowload the new version here. As the documentation has slightly improved we’d like your input here as well.

In the next release we expect bigger changes to come like one top secret 😉 and this exciting work from @devemux86 which continues the work from VTM (OpenScienceMap) and has OpenGL support, allows map rotation, iOS support and more, while keeping compatibility with the Mapsforge file format.

And if you like OpenStreetMap as we do, consider supporting them via money.

Happy routing!

The daily bug hunt

Yesterday we got a support request that a certain route request fails and just says ‘route not found’. We wanted to quickly reply that the open source routing engine has an option where you can reduce to a sufficient minimum, but as it turned out he meant the hosted GraphHopper Routing API where we already use a properly configured engine. So something was wrong with it. And in the geographical area we detected nothing strange with the OpenStreetMap data, (although for Google Maps we found one ;)) and so it had to be something in the routing engine.

Grabbing the area via the export button at openstreetmap.org was easily done, but we could not reproduce this on my local machine. And so we would need to somehow use the remote data, which is a bit too big to fit on my local computer (~50GB).

How do you remotely debug a Java application in a safe way?

fruit-bug

Let me explain this for NetBeans but it should work similar for any other Java IDE. Add the following options to your remote Java application:

java -agentlib:jdwp=transport=dt_socket,server=y,suspend=n,address=8888 ...

You can find out more about these settings via

java -agentlib:jdwp=help

As a side note: there is also an old settings “-Xdebug -Xrunjdwp:transport=dt_socket,server=y,address=8888,suspend=n” but for that we got an error: “OutOfMemoryError: Java heap space” which did not go away even when trippling the -Xmx setting (maximum RAM for the JVM). After switching to a different off-heap graph storage method (MMAP_STORE_SYNC) we got it working with the old method.

Now, how can you open the port 8888 without making it public to anyone? Instead just 8888 use localhost:8888, then the socket is not publicly accessible and so you can safely access it through a SSH tunnel:

ssh -L 8888:localhost:8888 user@server

Then click ‘Debug’ in the Netbeans menu, then ‘Attach Debugger’ and press ‘okay’. Keep localhost and 8888 or if you do not have a SSH tunnel use the remote server IP. It should then open a new output window telling you that you are connected. In our case we still had a problem:

Not able to submit breakpoint LineBreakpoint GraphHopper.java. Reason: Breakpoint's source file does not belong into the preferred source root '.../.m2/repository/com/graphhopper/graphhopper/0.7.0/graphhopper-0.7.0-sources.jar'

This is easy to fix. Go to Window->Debugging->Sources and deselect the entry for graphhopper 0.7.0 as the open project with 0.8-SNAPSHOT itself is sufficient in my case.

Finally er were able to remotely debug into the JVM

Nice! But we were still not able to figure out what went wrong ;(

The reason was that this bug was not related to runtime (i.e. finding the route) but it was related to how we post-process the OpenStreetMap network to make it less error-prone. Read more about the details here and if you liked this maybe you would like to contribute 🙂 ? Have a look into our quickstart and sign-up to our forum.

contribute

We hope you enjoyed reading this bug hunt and you can apply the findings to your own debug sessions!

Releasing GraphHopper 0.5

Today we are proud to release version 0.5 of our open source road routing engine GraphHopper. Try it out on GraphHopper Maps:

graphhopper maps route planner

We’ve improved the GraphHopper core and the GraphHopper Directions API which now includes route optimization. Download now via maven snippet or zip package.

A big thanks for this 0.5 release goes again to all of our contributors and translators! This release also includes features sponsored by Geofabrik, curbside and komoot. Read here to see how to become a sponsor and how to benefit from our GraphHopper knowledge or donate us now. Additionally the developer Sander from Falk.nl has contributed #397. The default map tiles of GraphHopper Maps are now provided for free (!) from Omniscale.

Thanks a lot to all contributors and translators!

Now here are the highlights for GraphHopper 0.5:

  • Implemented forcing the route direction, the so called ‘heading’, at start, via and end points. Very useful for navigation applications, #434, thanks @jansoe !
  • The turn instructions are now translated in over 34 languages, including the new Sorbian language. See all languages and contributors & thanks to them!
  • Further improved bike routing, thanks @ratrun !
  • One GraphHopper installation can now include multiple profiles even if CH is enabled, see #464. This makes such installations a lot more memory efficient and decreases import time. Sponsored from komoot! A major refactoring was necessary for #464, see #447
  • Improvements related to Android and GPX export, thanks @devemux86 !
  • Added nearest API to snap point to road, #397, thanks @Svantulden !
  • Updated the iOS port of GraphHopper, thanks @clns !
  • Updated the browser port of GraphHopper via TeaVM, thanks @konsoletyper ! See the live examples.
  • A demo was created which uses live traffic data to influence the routing and also contains a simple traffic visualization on a map for LeafletJS
  • Some minor breaking changes in the web API regarding error messages
  • Several other smaller bugs and improvements
  • All changes and necessary refactorings are documented in the changelog

An “alternative routes” branch was created here which also includes round trip calculation, but due to several limitations this is not yet merged into master.

Have fun and let us know your requirements!

Simple Route Optimization integrated in the GraphHopper Routing API

Since several months we’ve been working on our new Route Optimization API, which is a powerful API for your problems in logistics and similar areas. It includes time windows, capacity restrictions and much more features. It’ll be announced soon on its own!

Last week we had an idea: we wanted to make the integration of this new API as easy and straightforward as it can be. And the existing clients of the Routing API now just need to add ‘optimize=true’ to the request URL and the returned route is already optimized regarding overall time. So these clients can now easily solve traveling salesman problems too, and for all problems with more than one vehicle or more advanced restrictions you can still use our Route Optimization API. Of course, all times are based on real road networks instead of imprecise beeline approximations.

Several things need to be calculated under the hood to make this optimization happening:

  1. Decide to do route optimization instead of ‘just’ A-to-B routing.
  2. Now calculate all travel times between all locations (A to B, A to C, B to A, B to C, …), which gives us the travel time matrix (also known as distance matrix). For example, if you specify 5 points then 5*5-5 travel time values are calculated – this is done using our fast Matrix API which is way faster than the sum of individual point-to-point calculations.
  3. Now use the previously calculated travel time matrix to solve the underlying traveling salesman problem, i.e. to optimize the location order.
  4. Finally fetch the complete route with the correct location order including e.g. elevation data for foot and bike routing via the Routing API.

You can already use this feature with our Java and JavaScript clients. And so I did. I locally added this optimize parameter to the GraphHopper Maps UI and what I got was a bit magical! Look into this video to see what I mean.

 

Map Matching use cases, or why an Open Source and Open Data alternative is superior to the Google Maps Roads API

A map matching software makes your recorded GPS points ‘snap’ to some digital road network. E.g. the open source map matching component from GraphHopper is a highly customizable solution also available as SaaS. The following picture illustrates this map matching process from recorded data (blue) to matching data (green):

The screenshot shows the real world data in blue and the calculated matched roads in green.
This screenshot shows the real world data in blue and the calculated matching roads in green.

But why is this ‘snap to road’ useful? For that we will look today into three possible usage scenarios. Before we start we need to clarify the wording a bit. A GPS point is a location on earth with latitude and longitude data, and a GPX point is a GPS point with an associated timestamp. So when you record your walking or biking trail you often have a GPX file which is a list of GPX points.

1. Attach data available in the digital map

The Google Maps Roads API allows you to make GPX tracks align to their proprietary road network, which is useful. They also allow you to attach the maximum allowed speed but no further information and only for business customers. A solution like a map matching component from GraphHopper which is based on OpenStreetMap has some advantages over that:

  • You can attach not only maximum speed values to your data after the matching, but also turn instructions, street names, surface values, access restrictions, road types and well, nearly any way tag which is stored in OpenStreetMap. And as GraphHopper supports elevation, enhancing the input data with elevation afterwards is possible and easy too.
  • If you find a mistake in the matching which is caused due to a problem in the data or because of missing data in developing countries, then you can easily change this in OpenStreetMap and rerun again. For example allryder uses this process to track urban transport data in emerging regions. Also you can find illegal turns of bicyclists and more which e.g. urban planners can use to improve bikeability of their city. You can read through a German description from ratrun of more of these data wrangling problems.
route_with_maxspeed
Attach any OpenStreetMap way tag to the GPX track like maxspeed=50 in this example.

2. Make recorded routes and speeds more precise

If you track vehicles the data will suffer from GPS device precision errors, which also means that the speed and location is not that exact. Having more precise road network data and use this to enhance your recorded data will help you to calculate more precise distance and speed values for your tracked vehicles.

3. Identical road segments

Once you have recorded the GPX tracks and transformed them into digital paths you know the road IDs. With that information you can easily detect if two vehicles are passing the same road although the GPS coordinates are completely different and just ‘similar’ in location. This makes it easier to assign values like the measured speed to a road. Also this data can be used for traffic influenced routing.

And more

Furthermore an open source solution makes it easy to

  1. Attach your own data like any user rating to the recorded data
  2. Customize the software to your needs e.g. for electric vehicles or improve the matching algorithm itself
  3. Combine the results with a powerful routing algorithm as done in the use case ‘Identical road segments’

Have fun when playing around and let us know about your use case!