GraphHopper’s new curbside feature: Never drive the right road the wrong way again

Imagine you are in a foreign city and need to visit fifty different locations that day. Which way should you go? Or let alone which is the best order to visit all these places? GraphHopper’s Route Optimization API is a powerful tool that lets you easily calculate efficient round tours like this for a selection of different vehicle types in no time. And this is only the tip of the iceberg. You can solve similar problems for an entire fleet of vehicles, setup constraints like time- and capacity restrictions, solve problems including pickup and delivery and much more. Have a look at the full documentation here or browse the other articles on this blog.

Finding an efficient round trip

Let’s look at a round trip through São Paulo, Brazil calculated by GraphHopper. For simplicity this example only uses nine locations:

So you got an efficient order to visit the locations and you can see which roads to take to get from one place to another as well. However, just arriving at the right locations with a minimum driving time in between might be not good enough. What if you end up on the side of the road opposite to your destination? In Brazil people are driving on the right side of the road, but for locations 4 and 7 of our example are on the left side of the road when considering the suggested driving direction? This might be fine if you are cycling on a small residential road with a cargo-bike, but it would be far from ideal if you needed to cross six lanes during rush hour when driving a truck. And what about changing your direction after your visit to one of the locations, as is the case for locations 2,3,5 and 9 in our example? Same problem here: Depending on your vehicle it might be very inconvenient or even impossible to turn around, so you need to keep going straight and take a few extra turns to get back on track. This extra turning or driving is not considered in our solution above and likely means that the real driving time will exceed the estimated one.

Arriving the right way

Can the round trip not be improved by visiting the locations in a slightly different order? Doesn’t it help to take a little detour here and there so you always arrive at your destination without having to cross the street? Yes, and it is exactly for this reason that we added the new curbside parameter to our services. It is very simple, so lets have a look.

You just need to specify curbside=right for each service location that shall be visited without having to cross the street. If you are in a country with left-side traffic it would be curbside=left. Our route optimization algorithms will then consider this constraint when looking for an optimal solution for you. Here is the São Paulo example again, this time using the curbside parameter:

Isn’t that great? The new solution’s distance and estimated driving time is about 10% higher, but all the locations are visited such that upon arrival you will already be on the same side of the road as your destination. Also the solution includes no u-turns and you can simply keep going the same direction you came from at each location. With the curbside parameter such u-turns are excluded automatically, because specifying it not only enforces arriving at a location in a certain way, but also leaving it in the same direction when continuing to the next stop.

Note that the order of the locations has changed significantly compared to our first example that did not use the curbside parameter. For example, the solution suggests you visit the two locations in the southeast at the very beginning instead of the very end of your round trip. In many cases such changes are probably easily worth it as they save you lots of time (and nerves) you would usually spend crossing the street, turning your vehicle or taking extra detours to get back on the suggested route.

Some more details

A few more technical details for those who are interested: To find out on which side of the road your destination lies it is necessary that your input coordinates are next to (not in the middle of) the road. So for example when you are working with street addresses you should, e.g., use the coordinates of the building you would like to visit. In many cases you can obtain these coordinates using our Geocoding API.

And what happens if you use the curbside parameter for a location in a dead-end street or a street that later splits into several dead-end streets? Obviously at some point after visiting the location you have to turn around and instead of suggesting the u-turn right at the location the optimized solution will include a u-turn at the end of the street or the next junction if there is no other possible way. The time needed to turn around will be included in the total estimated travel time. Another interesting case are one-way roads: One-way roads can, well, only be traveled in one direction, so if you specify the `curbside` parameter for locations next to one-way roads they will either be ignored or you will get an error. You can control this behavior using the curbside_strictness parameter.

Technical Note

As you might know performing route optimization for hundreds or even thousands of locations often requires calculating millions of routes. To implement the curbside feature we had to adopt our highly optimized routing algorithms to handle routing between directed roads rather than just points. This allows us to deal not only with curbside constraints, but also with turn restrictions that are enabled by default when using the curbside feature. You can read more about turn restrictions in this previous blog post.

Try it yourself!

Even better, not only have we added the curbside parameter to our Route Optimization API, it also works with our Routing and Matrix APIs, and of course it is also available with the latest (1.0) version of our open source routing engine that you can use with free and open OpenStreetMap data!

If you are not a GraphHopper user yet, get a free API key or check out our open source projects on GitHub.

Happy routing everyone!

Cover photo by Zichuan Han from Pexels