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!

Releasing the Map Matching API

Today we are proud to release our Map Matching API as part of our Directions API. It is a web service based on one of our open source components. You can use it to snap measured GPS points to a digital road network to e.g. clean data or attach certain data to it like turn instructions for biking trials. Read more about map matching at Wikipedia. Our Map Matching API is powered by the Apache licensed hmm-lib from BMW Car IT. ‘hmm’ stands for hidden markov model and indicates the underlying algorithm.

In the following screenshot and in these live examples you can see the Map Matching API in action. The black line represents the original GPS track e.g. received from a smartphone’s GPS. The green line represents the matched result, i.e. the part of the digital network, the black line is matched to:

mmatching

matching-sim

The Map Matching API works through tunnels, bridges, complex junctions etc. and can utilize different available vehicle profiles. Even more off-the-road examples will snap correctly – depending on the chosen GPS accuracy:

crazy-match

We are confident that it is another helpful routing tool that can be used in production for your web or mobile application. If you find any example where our Map Matching does not work as expected, please let us know in the forum.

Use this link to sign up and try the API for 2 weeks and let us know about your GPS tracks and questions!

GraphHopper Meeting Berlin, July

On 13. July, Wednesday, from 16:00 to 17:30 we’ll hold the first GraphHopper meeting at Beuth University, Haus Bauwesen, room D 451.

We’ll have the following topics:

  • Introductory talk about the GraphHopper routing and current development
  • You are invited to show us your projects based on GraphHopper.
  • Hands on workshop, where one of the topics will be indoor navigation

All talks should be 20 slides and 20s max for every slide, currently all in German language. See PechaKucha at Wikipedia for more details. To make planning a bit simpler please send a short email to info@graphhopper.com

Also please note our workshop (4th July) and talk (5th July) at FOSSGIS in Salzburg.

About

It was a great success having 5 talks of GraphHopper usages and all in all over 4 hours of discussion about the different topics like indoor routing, offline routing, map matching and traffic data integration.

GraphHopper Routing Engine 0.7 Released

Today we are happy to announce the new release of our open source road routing engine GraphHopper 0.7. It includes many improvements as well as a new round trip calculation for the flexibility mode.

round_trip2

A big thanks for this release 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.

Thanks a lot to all contributors and translators!

Here are the highlights for GraphHopper 0.7:

  • moving from Java 5 to Java 7 for the core and Java 8 for the web modules.
  • a new Croatian translation contributed from Ivan, this is language number 37!
  • round trip calculation from boldtrn
  • speed up mode (Contraction Hierarchies) can be disabled per request making several flexibility mode features available like alternative routes, round trips, weighting changes, heading settings or even turn restrictions which required a bit of refactoring
  • adaptions for the GraphHopper iOS port from clns
  • conditional restrictions can now be used for numbers like for weight not only for dates
  • a new ‘hike’ profile which differs from ‘foot’
  • bike improvements by ratrun
  • SRTM data now fetched from kurviger.de to avoid timeout problems – thanks again boldtrn!
  • We use underscore notation for all properties and file names now instead of the camelCase notation which was sometimes mixed with underscore
  • Other contributions came from ammagamma, IsNull, devemux86 and fbonzon. See more bug fixes and pull requests and the changelog

The next release 0.8 will focus on more flexibility. Furthermore we would like to use the chance and point to the new work of our map matching component, which is now based on a more precise algorithm and often results in better matchings. It includes work from Michael (MATSim) and Stefan Holder (BMW Car IT). Please try it out here and give us feedback so we can include safely it in the next release or even replace the current algorithm.

As always our GraphHopper Directions API consumes these changes and makes it possible to use alternative routes, round trip calculations, heading indication, shortest path calculation and turn restrictions for the Routing API – read here for more details.

Have a nice route and discuss here.

Alternative Roads to Rome

The roads to rome project from Moovel Labs is a nice visualization of the possibilities with GraphHopper. And it is only the start. While investigating and debugging the quality of alternative routes – a new feature from GraphHopper – we stumbled over the necessity to do a very similar visualizations. The visualization of the so called shortest path tree.

What is a shortest path tree?

The shortest path tree (SPT) contains the ‘best ways’ from a root location to any other point in the network. ‘Best way’ can mean for example the ‘shortest’, ‘fastest’ or the ‘most beautiful’ path. The SPT is unique for each root location and transportation mode (e.g. “car”). It is easy to calculate with the Dijkstra algorithm, but it is hard to make it working on large networks such as the European road network. GraphHopper can do this.

The people from the Moovel lab project e.g. used ‘fastest car’ with a starting point at Rome – see here the original image from the project:

eu_rome_web
Roads to Rome. Attribution: Moovel Lab and OpenStreetMap

We can create similar – but easier to gather – visualizations with our MiniGraphUI, a very simplistic Java Swing UI built just for development a few years ago:

it3
Northern part of Italy. Starting exploration in Rome

Shortest Path Tree Visualizations

For the visualization we made the line thickness dependent on the number of reachable leafs of the SPT. Let us change the transportantion mode to ‘walking’ instead of car (ferries included but not visualized):

it8

A further step to make the visualization more powerful is to use different colours for different road speeds:

it4

Alternatively, we can colour-encode the distance from the origin Rome:

it5

it6

 

 

 

 

 

Of course the flag colours green, white and red must be tried too, click to zoom 🙂

it7
Full SPT of Italy starting in Rome.

As well as for Germany and France:

de
Full SPT of Germany starting in Berlin.
fr
Full SPT of France starting in Paris.

All images are via OpenStreetMap (c) contributors.

Many changes would be possible to make the visualizations better looking like with a background map or better colours, but we left this task to the reader, just showing the possibilities here.

When ‘time’ is used as the ‘distance measure’ as in our examples, then these visualizations are the so called isochrone maps – see our Isochrone API for this task.

Create your own shortest path trees

Although the visualizations from Moovel are also done with GraphHopper, within the MiniGraphUI we have direct access to all the underlying graph properties, so that a SPT through full Germany with millions of nodes takes only half a minute to draw on an aged laptop after importing the data which took under 10 minutes for Italy. We can even zoom in and out. For larger areas probably some further speed tuning could be necessary. You can download GraphHopper here then replace the MiniGraphUI with this snippet, specify your OSM file, then edit config.properties and set prepare.chWeighting=no and finally run:

./graphhopper.sh clean
./graphhopper.sh miniui your-area.pbf

And we could do animations like done in an older post here or compare with old versions of OSM.

What have shortest path trees to do with alternative route finding?

As we mentioned in the intro we have stumbled over the necessity to visualize the SPT to improve the quality of alternative path search. The work for this is currently still under development.

These SPTs can be made from any origin A (‘source SPT’) as well as towards any destination B (‘sink SPT’). And with the help of those two SPTs we can find out ‘overlapping areas’ in the middle. These areas are called plateaus – if we use a bidirectional Dijkstra and extend the normal finish condition to actually make these two Dijkstras really overlap each other. And the larger these plateaus are, the better is the alternative. For example, the best path is also the best alternative with a 100% overlapping path reaching from A to B in the source SPT and backward from B-A in the sink SPT. Apart from the optimal path, these plateaus are often not too large and we need to use other properties to select good alternatives. This can be done for example with a property called ‘sharing’ which calculates the distance an alternative route shares with the best one. After several necessary tweaks with the help of zoomable and debuggable visualizations like this one:

rome-spt-alternatives

we got surprisingly good alternatives e.g. from Rome to Perugia:

it-alt