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 component makes your recorded GPS points align to some digital roads like the one from GraphHopper. 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!

Pick the Best Electric Vehicle Charging Station Along a Route with GraphHopper

mapNearly all electric vehicles to date that rely 100% on electric energy have a severe range problem (maybe except Tesla ;)), especially cars and especially in cold seasons. If you still want to plan a long-distance tour you’ll have to include one (or more) charging station as stopover.

But how to find the best one with the least detour e.g. in this example from Hamburg to Munich?

You calculate all routes to all charging stations and pick the best. That sounds crazy but is completely reasonable in real time with GraphHopper even for hundreds of stations. In this blog post we’ll use the GraphHopper Matrix API and have created the JavaScript charging station example.

Calculate detours with the GraphHopper Matrix API

The GraphHopper Matrix API is a specially crafted piece of software to make many-to-many requests very fast. For example in logistics you need this to determine the optimal order for e.g. delivering parcels.

Now to calculate the best detour we need a similar logic: we need
A) one request, the one-to-many and
B) another request, the many-to-one.

Finally we’ll pick the fastest tour (smallest A+B). The same approach we would take to calculate an optimal ridesharing where you ‘pick up’ and ‘deliver’ people.

We also need all charging stations and grab them from OpenStreetMap via the Overpass API and use the wizard to specify amenity=charging_station and car=yes. We ignore for a moment the socket type of the station and a possible required authentication or fee.

For the German tour from Hamburg to Munich we fetch all stations from middle Germany (roughly 80) and select all which are in the center of our route e.g. within a 400km radius (reducing this is necessary for the free package).

There are several optimizations possible like the route calculating itself to consider elevation to avoid hills or a completely other vehicle like an electric bicycle. Or in real world you have to consider the opening hours of the stations or seek for multiple stops for shorter ranges, then the Tour Optimization API or special routing expertise could be necessary.

In our Hamburg-Munich case the result is the following tour of ~750km and roughly 8.5 hours plus the time required for charging or replacing the battery at this charging station in Erfurt. Compare this to the normal route which takes only 8 hours and is 775km long.

best-station-tour

Elevation data and OpenStreetMap

Handling elevation data and combine it with OpenStreetMap can be a pain. And indeed it was when we implemented this for GraphHopper roughly one year ago. But we really wanted to make it easy for our users. And it is very easy – you just need to set:

graph.elevation.provider=srtm

in the config.properties and GraphHopper will include elevation automatically! For the full elevation documentation please read this.

In GraphHopper Maps you can try it and see the elevation widget for every route for bike&foot:

elevation-widget

So GraphHopper will include elevation then automatically in

  • the import process and therefor also calculate more precise distances
  • the API where it adds three dimensional points (GHPoint3D) instead of just GHPoint
  • the web API where it uses a third dimension. As we also use a compact form called encoded polyline for this, you need the adapted decoding procedure when consuming the route and not using GeoJSON.

But to make a vehicle (e.g. bike) actually using the height information you need to tell it that uphill its slower than downhill via bike2. So you need a flag encoder with two weights per edge. But it is easy to enable:

graph.flagEncoders=bike2

With this logic in place it should be easy to improve our mountain bike profile to prefer up and down hill. It is important to note that for ‘preferring’ a specific feature it is not necessary to increase the speed. You can just tune this behavior via the priority implemented for bike and foot. Read more about how to write your own flag encoder here.

Other providers and more configurations

The nice thing about our modular approach is also that you can use a complete different provider like we do with CGIAR (improved SRTM data) or even inject your elevation data into the OSM. You just need to change this in the config

graph.elevation.provider=cgiar

Also you can have an in-memory or on-disc storage for this elevation data. E.g. to reduce RAM usage you use the default setting, but to speed up the import and not having SSD discs you set

graph.elevation.dataaccess=RAM_STORE

The nice thing is that you also can use our ElevationProvider implementations for you own Java application. Is it currently not separated from GraphHopper but it is relative separated and GraphHopper core is not big :)

See how Falk, Ride with GPS and Volo benefit from using GraphHopper

There are several users of GraphHopper. We have an already long but incomplete list including ‘older’ applications like Komoot or GPies. In the last months we have added some more – namely that are route.nl (Falk), Ride with GPS and Volo.

Route.nl

route.nl screenshot

Falk created a route planner based on GraphHopper

Quoting Sander van Tulden from Falk.nl:“We love Graphhopper :) We use it in our online platform route.nl where we serve free routes for recreational customers in the Netherlands, Belgium and Germany. We tried a lot of existing OSM solutions but Graphhopper fitted our needs best.”

Ride with GPS

ridewithgps

Ride with GPS a route planner dedicated for cyclists

From the founder, Cullen King: “We are very happy with the pace of development of the GraphHopper project, which sees improvements on a weekly basis. We currently self host Graph Hopper along with the rest of our OSM map stack, and are 100% satisfied with the rock solid performance of the routing servers. We have no doubts that it will continue to scale to meet the needs of our fast growing business.”

Volo

Volo restaurant delivery service

Volo a restaurant delivery service

Volo was recently acquired from Rocket Internet which was written about on Gründerszene [DE] and TC. Volo uses GraphHopper for its underlying tour optimization algorithm.

Let us know if you have more interesting use cases of GraphHopper!

Visualize and Handle Traffic Information with GraphHopper in Real-time for Cologne (Germany, Köln)

As our Directions API currently does not include traffic data we still show you that it is possible to integrate traffic data into GraphHopper if you have the data. A few days ago I’ve blogged about a simple way to feed GraphHopper with generic traffic data from elsewhere. Today we look into one specific example: Cologne.

ghmaps-with-traffic

This German city has a nice open data community and an open data portal. There I found the traffic data and it is noted that the update is done every 5-10 minutes so we have rough real time traffic information. For other open data or other cities have a look into codefor.de

The source repository for the necessary changes is also at github. The most important change was to visualize the traffic information directly in the browser, this helps a lot when debugging things – still lots of room for you to improve it. Using leaflet.canvas is a bit complex as we would need to separate the traffic information into the tiles structure. Instead I’m using the big canvas solution from CartoDB making everything really simple.

Three further simple steps are necessary when extending the old example:

  • Fetch data periodically
  • Parse and interpret the data correctly
  • Locking when writing the data and locking when routing

Fetching the data and parsing it is a simple procedure done within DataUpdater.fetch. Also surrounding the data feeding method with a write-lock is easy:

public void feed(RoadData data) {
    writeLock.lock();
    try {
        lockedFeed(data);
    } finally {
        writeLock.unlock();
    }
}

And finally we need to surround every route request with a read-lock:

GraphHopper tmp = new GraphHopper() {
    @Override public GHResponse route(GHRequest request) {
        lock.readLock().lock();
        try {
            return super.route(request);
        } finally {
            lock.readLock().unlock();
        }
    }
}.forServer().init(args);

Now we just need to fetch the road network for this area and start the server:

  1. wget http://download.geofabrik.de/europe/germany/nordrhein-westfalen/koeln-regbez-latest.osm.pbf
  2. ./td.sh datasource=koeln-regbez-latest.osm.pbf
  3. Visit http://localhost:8989 to try the routing and see the traffic infos

And you’ll see regularly updates of the speed where routing should be influenced, at least the duration for the route:

Speed change at 50.94432295851602, 7.057916495227443. Old: 30.0, new:5.0
Speed change at 50.944496505815735, 7.057842025768907. Old: 60.0, new:45.0
Speed change at 50.94422920435813, 6.982818132995898. Old: 65.0, new:45.0
Speed change at 50.96702284992454, 7.03188984955171. Old: 45.0, new:20.0
Speed change at 50.90650702086146, 7.0605028341376235. Old: 70.0, new:45.0
Updated 86 street elements. Errors:0

To start from scratch you can remove the graph-cache folder and the old speed values will be used. Still this is only a rough prototype. For example:

  • Map matching not yet integrated
  • Fallback to old values -> either store within RoadData or separate GH instance
  • UI: artifact when zooming. No concrete info is shown on mouse over
  • Use two directions for speed if no one-way street
  • Of course it is best to try the system in German-early times and hope that many traffic jams events are there ;)

This is only one city, but we collect more here! Now have fun to test and tweak the system!

Integrate traffic data into your route planner

Update: there is a new blog post which shows integration of real time traffic info into GraphHopper from a real world example, including a simple UI based on HTML5 canvas.

There are several companies having its own traffic data e.g. those companies having an own fleet or fetching it from an external source. Often on the GraphHopper mailing list people ask how they can integrate this into GraphHopper and until now there was only descriptive information but no code example. This post will change this, where I’ve created a little demo project at github for this task. The demo is easy to use and provides a simple web service where you can POST your own JSON data influencing the routing. If you look at the Readme there are only three steps involved:

  • Start the route planner server with the area of your choice: ./td.sh datasource=your-osm-file.pbf
  • Visit http://localhost:8989 to try the routing
  • Now feed some data and try routing again:
    curl -H "Content-Type: application/json" --data @traffic.json http://localhost:8989/datafeed
    

The simulated traffic jam is marked red. The routing therefore tries to avoid it.

The necessary code is very minimal: just take the double value from JSON and use it as speed for the identified street:

edge.setFlags(carEncoder.setSpeed(edge.getFlags(), value));

A street is a so called ‘edge’ in GraphHopper, read more about internals e.g. in this presentation or in the official documentation. But how to find this GraphHopper edge from the coordinates (list of latitude,longitude)? Currently we just take the very first coordinate of the provided points list in the JSON:

Point point = entry.getPoints().get(0);
QueryResult qr = locationIndex.findClosest(point.lat, point.lon, EdgeFilter.ALL_EDGES);
EdgeIteratorState edge = graph.getEdgeProps(qr.getClosestEdge().getEdge(), Integer.MIN_VALUE);

But in reality this can get more complex and could be improved by using our map matching component. So we just hope here no other edge can be mixed up with a close but completely different edge. Such problems are possible if you get the data from external none-OpenStreetMap data sources or from vehicles on the road without a high precision coordinate information. Other important points on the TODO-list for this demo are that the routing should be locked while updating the graph and that stopping the server should flush the graph to make the newly received data persistent. Nevertheless this shows nicely how easy it is to feed GraphHopper with your own data where the possibilities are endlessly to e.g. block complete roads or prefer roads for routing and more. Let us know about your use case!