Turn Restriction Support for GraphHopper’s Directions API

Today we are proud to announce another big improvement of GraphHopper’s Directions API: We have added turn restriction support to our routing solutions.

Turn costs and turn restrictions

The time it takes to go from one place to another obviously depends on how far and how fast we travel. Our speed critically depends on the type of road we use, because this can range from something like a steep and windy gravel road in the mountains to a flat highway with six or more lanes. Finding the optimal sequence of roads between two places is exactly the problem routing engines like the open source GraphHopper routing engine, the Open Source Routing Machine or Valhalla solve.

Besides the driving we often spend a significant amount of travel time on turning between roads, waiting at traffic signals or even taking u-turns in case we need to change the direction after reaching some intermediate stop. In technical terms we call these contributions to the travel time the ‘turn times’ or ‘turn costs’. Sometimes certain turns are not desired at all or not even possible for some reason. For example at some junctions there are ‘no left turn’, ‘straight only’ or similar traffic signs, or a junction might be too narrow to turn around when driving a long truck. In this case we are speaking of ‘turn restrictions’.

Junction in Brussels where left turns are forbidden
A junction in Brussels with a ‘right turn only’ sign. Street imagery by filipc licensed under CC-BY-SA.

Fast or faster?

From a route calculation perspective dealing with turn costs and restrictions adds a whole lot of complexity. The reason this makes the computation so much harder is that for every junction one has to consider the different directions one might be coming from. This increases the number of possible routing states the routing algorithm has to keep track of and therefore requires more computing time and computer memory.

An important goal of the GraphHopper products is providing high performance route calculations, because for many logistics applications one not only needs to calculate a few, but often millions of routes. To achieve this goal GraphHopper uses very sophisticated algorithms that allow calculating hundreds of thousands of routes per second on a single core.

Handling turn costs within these specialized solutions makes this an even harder problem to solve. At the same time including turn costs is not always strictly necessary to perform realistic route calculations. For example waiting times at traffic signals can be modeled by reducing the average travel speed in city areas. Turn times (or even turn restrictions) become less important when the travel points are far from each other or the route mostly consists of driving around the countryside. Similarly, many users of our Route Optimization API are mostly interested in the calculated order of the service locations and therefore turn costs are less important in this context than in, e.g., vehicle navigation. For these reasons GraphHopper’s Direction API so far focused on providing the fastest possible route calculations excluding turn costs.

But of course there are many situations where handling turn costs is crucial and last year we made a lot of progress in this direction and were able to add turn cost support for GraphHopper’s fastest routing algorithm (Contraction Hierarchies, CH). Previously, this was only supported for the flexible and hybrid routing modes. With the enhanced CH algorithm the GraphHopper engine now achieves very fast routing performance even when including turn costs. It is about two to three times slower than routing without turn costs, but for most applications it is fast enough. This is also still optional: You can enable turn restrictions at the cost of slower routing or disable it for maximum query speed. Fast or faster, its your choice now.

GraphHopper route ignoring a turn restriction
Route in Brussels as calculated by GraphHopper (green line) ignoring the turn restriction.© OpenStreetMap contributors.
GraphHopper route respecting a turn restriction
Route in Brussels as calculated by GraphHopper (green line) respecting the turn restriction.© OpenStreetMap contributors.

Turn restrictions for the Directions API

One drawback of our new algorithm is that it takes significantly more time, processing power and computer memory to generate the index data needed to achieve such fast query times. But here is the good news: You do not need to worry about these deployment issues, because we took care of this already! We now support turn restrictions for our hosted Routing, Isochrone and even Matrix APIs on our world-wide routing instances at no additional costs. We obtain the turn restriction data from OpenStreetMap which has very good coverage of law-enforced turn restrictions for many areas. Note that so far we only offer turn restriction support for the OpenStreetMap network and not yet for the TomTom network. Take a look at our documentation for all the details.

What’s next?

There is still more to come. The last months we have improved much of the routing engine’s turn cost related architecture and we are working towards making the turn cost model widely customizable similar to the way we recently did this for the weighting of roads (read more about this here). For example, this will allow penalizing left (or right) turns or adjust the turn costs for certain vehicle types or driving preferences. Also we are hoping to be able to fix a few gaps, like supporting the heading and pass-through parameters for speed mode and map-matching with turn costs.

Do not forget that trying our hosted service is free. Just sign up to get an API key here or even get involved with our open source projects.

Happy Routing!

Cover photo by Ian Panelo from Pexels