Turn Restriction Support for GraphHopper’s Directions API

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

Turn costs and turn restrictions, defined

The time it takes to go from one place to another depends on how far we need to go (distance), and how fast we travel that distance (speed). The type of road we’re traveling on impacts our speed (think about the difference between driving on a steep and windy gravel road in the mountains, versus driving on a paved, flat highway with six or more lanes). Every trip presents a unique mix of variables, and routing engines like the open source GraphHopper routing engine, the Open Source Routing Machine or Valhalla are specially designed to use these variables to find the most optimal sequence of roads between origin and destination.

Besides the time spent driving, we often spend a significant amount of travel time on turning between roads, waiting at traffic signals, or taking u-turns after a wrong turn. In technical terms, we call these contributions to the travel time the ‘turn times’ or ‘turn costs’. Sometimes, certain turns are hampered, obstructed, or otherwise not possible. Examples might include junctions with ‘no left turn’, ‘straight only’ or similarly restrictive traffic signs. Some junctions might be physically too narrow to turn around when driving a long truck. These examples refer to what we call ‘turn restrictions’.

Turns and cost restrictions, continued

Dealing with turn costs and restrictions adds a lot of complexity to the route calculation. For every junction, one has to consider the different directions from which one may approach. This increases the number of possible routing states the routing algorithm has to keep track of, which then requires more computing time, and computer memory.

GraphHopper products aim to provide high performance route calculations because for many logistics applications, one often needs to calculate many routes (up to millions) at a time. To this end, GraphHopper uses very sophisticated algorithms that can calculate hundreds of thousands of routes per second on a single core.

Handling turn costs within these specialized solutions makes this an even more difficult problem to solve. However, including turn costs is not always 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 in a more or less straight line. Similarly, many of our Route Optimization API users are mostly interested in the calculated order of the service locations. In this context, turn costs are less important than in, say, vehicle navigation. Accordingly, GraphHopper’s Direction API has focused on providing the fastest possible route calculations excluding turn costs.

Fast or faster?

Of course, there are many situations where handling turn costs is crucial. 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 fast routing performance even when including turn costs! To be clear, calculating this way is about two to three times slower than routing without turn costs, but for most applications, it is indeed fast enough. With that said, including turn costs remains optional; you can enable turn restrictions at the cost of relatively slower routing, or disable it for maximum query speed. Fast, or faster? It’s your choice now!

Turn restrictions for the Directions API

There’s a drawback for our new algorithm: it takes significantly more time, processing power, and computer memory to generate the index data required for such fast query times. Now here’s the good news: you don’t need to worry about these deployment issues–we took care of that already! We now support turn restrictions for our hosted Routing, Isochrone and Matrix APIs on our world-wide routing instances at no additional cost. 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 more details.

What’s next?

There is yet more to come. In 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 did for the weighting of roads recently (read more about that here). This would then, potentially, allow for “penalizing” turns or adjust the turn costs based on vehicle type and/or driving preferences. Also, we are hoping to fix a few lingering gaps, like supporting the heading and pass-through parameters for speed mode and map-matching with turn costs.

Don’t forget–trying our hosted service is free! Simply sign up to get an API key here, or, if you’re a router like us, feel welcome to get personally involved with our open source projects!

Happy Routing!

Cover photo by Ian Panelo from Pexels