Help

October News from GraphHopper

It is and was a special year, and we almost forgot to send out a newsletter, even though we developed many new features. You can subscribe to the low frequent newsletter when you register here.

The biggest change is that all our routing-related APIs like the Matrix API, Isochrone API, Routing API and Route Optimization API now support turn restrictions. Read our blog post about it where you can understand why we were able to live without it for so many years.

GraphHopper route respecting a turn restriction
© OpenStreetMap contributors. Contains Street imagery by filipc.

Directly related is a cool new feature that we call ‘curbside’ support and it allows you to specify on which side of the road your vehicle should do the pick up or delivery because you want to avoid e.g. crossing the road or U-turns.

There are a number of new feature specifically created for the Route Optimization API. You can now schedule activities and jobs without a fixed pre-assigned location. Another feature allows you to specify driver shifts to better support the modeling of different operating days for vehicles. Furthermore, you can now specify a minimum number of jobs for each driver to better distribute work over your drivers. And finally, you can solve vehicle routing problems without knowing the actual starting position of your drivers, i.e. drivers no longer necessarily need a starting coordinate.

The year 2020 was also the year where we released version 1.0 of the open source GraphHopper routing engine. This new version brought many new features such as fast alternative routing and customizable routing. The customizable routing is still an alpha feature and not yet available in the GraphHopper Directions API, but we want your feedback now! And in the meantime we already released version 2.0. Try it out now and give us a star at GitHub!

Happy Routing!

GraphHopper Routing Engine 2.0 Released

Today we are releasing version 2.0 of the open source GraphHopper routing engine.

GraphHopper calculates optimal routes in road networks, for example taken from OpenStreetMap, for many different vehicle types and finds the ideal itinerary when using public transit. It is released under the Apache License 2.0 and you can easily try its road routing capabilities on GraphHopper Maps. Besides the route calculations the GraphHopper engine offers a lot more features like the map matching (“snap to road”), the navigation and the isochrone calculation (for a point it finds all reachable roads within a specified time).

View GraphHopper on Github.

Since the last stable release 1.0 we merged over 30 pull requests. The following contributors were involved in the 2.0 release:

easbar, michaz, Octanas, jb2martel, ratrun, gcheval, boldtrn, otbutz, karussell, oflebbe, msbarry

Thank you!

The new features

The main time was used to clean up and refactor the internal structure of GraphHopper which is still an ongoing issue. One result was that the Android demo was removed, see #1940 for the discussion. Which itself resulted in an upgrade to Java 8 of the core and other modules in #2077. It means that the offline routing feature of GraphHopper could still be used for Android projects but not for all older versions. The “client-hc” module used for online route calculation is not affected.

Another big effort was to make the so called CH preparation faster, which is one of the most time consuming parts of the import process, see #2132 from easbar. With these changes the edge-based CH preparation is 2 to 3 times faster, which helps us to improve our update frequency by several days for the world wide road network that we support in our Directions API.

The routing requests with the speed mode that supports turn restrictions (edge-based CH) are now over 30% faster, see #2054 from easbar.

The isochrone calculation is now faster for edge-based traversal. See to #2092 from michaz.

A new nice feature #1953 was developed from msbarry that improves the resolution of elevation data:

https://user-images.githubusercontent.com/1480504/76612184-22630780-64f2-11ea-92aa-09f9aff49b88.png
This 2km straight segment loses all elevation details…
https://user-images.githubusercontent.com/1480504/76612269-4d4d5b80-64f2-11ea-8195-f6cad7c720d9.png
…but with the new feature we get that elevation detail back

To make it easier to use GraphHopper in an Android navigation application we integrated the server-side part of it in the main repository, see #2081 and #2071. A working Android navigation demo that uses this feature is available here.

There were many other bug fixes and improvements, e.g. #2094 which is a bug fix for the isochrone code and #2101 which is a bug fix in the alternative route calculation.

Discuss this release in our forum. Happy Routing!

Distribute work evenly over your drivers

Suppose you have 50 deliveries and you hire four drivers to make those deliveries. Each driver is either paid for a certain number of hours or is paid for a certain number of jobs. In this case, you wouldn’t necessarily want one driver to get all 50 deliveries, even if this minimizes the total variable transport costs. You also wouldn’t necessarily want two drivers to get 25 deliveries each. In fact, you want to use all four of your drivers more or less equally.

The classical vehicle routing problem, which minimizes the number of drivers as well as the total variable costs, has now changed into a new problem. You are essentially saying: “Minimize my total costs, but please keep in mind that I have promised my drivers that they will have at least half a day’s work or will be allowed to make at least 10 deliveries.”

As we have learned from our customers, this is not some rare, niche problem, but a very common one. We already offer some possibilities to solve this problem, described in this blog post: Balance load among all vehicles.

We have now extended our toolbox a bit more: we’ve made it possible to specify a minimum number of orders for each driver. Let’s illustrate this with an example. I have taken the problem above and put our four drivers and 50 deliveries somewhere in Berlin. If I now minimize the number of drivers and the time it takes to process these 50 deliveries, I get the following picture:

As you can see, one driver gets all 50 deliveries and works them off in a beautiful round trip.
But if I now determine that each driver should get at least eight orders assigned ("min_jobs"=8), the following solution results:

As you can see, beautiful round trips are still created, but with the new constraint applied.

If a driver still has too many orders, you can limit the number of orders upwards. For this purpose, you have to specify the maximum number of jobs ("max_jobs"). Please note that, while the max number of jobs is a hard constraint, the minimum number of jobs is a soft one. This means that even if it is not possible to fulfill a minimum number of jobs, we will get as close as possible to the number specified.

If you’d like to learn a little bit more about how you can implement it, I recommend this article. The JSON counterpart for the above example can be found here (without min_jobs) and here.

And if you don’t have an account with us yet, feel free to register and get a free standard subscription for two weeks to try it out.

Have fun optimizing!

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:

Optimized route suggested by GraphHopper to visit nine locations in São Paulo, with minimal driving in between. The total distance is 5187m and the estimated driving time is 622s.

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:

Optimized route when including the curbside=right parameter for every location. The total distance is 5761m and the estimated driving time is 685s.

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

How to solve a traveling salesman problem with a week-planning horizon and driver shifts?

Introduction

A few years ago, we wrote a tutorial to show you how to model a traveling salesman problem with a week-planning horizon. Since then we have been improving our API a lot and I would like to show you how easy it is now to model this with driver shifts.

For example, suppose you have ONE employee who has to visit 25 customers over the next week. Let us also assume that the employee has certain daily working hours and the customers to be visited have several time slots. Your task is to plan his routes from Monday to Friday in such a way that the total transport costs are minimized. The result can be as follows:

tutorial-example-1

Instructional Content

In our documentation you will find the general setup of the Json request and how to submit this request to our servers. In the following I will show step by step how to model the above problem..

1. Specify your vehicle type

Suppose the employee has a car and the capacity doesn’t matter, then your Json specification should look like this:

"vehicle_types":[
   {
      "type_id": "car_type",
      "profile": "car"
   }
]

Therefore you need a “type_id”, with which you can refer to it in your vehicles. In addition, you need to specify the profile “car” (you can read more about the profiles you can select here). In this way, transport times and distances are calculated based on the road network. The results correspond exactly to what you get when working with our Routing API and GraphHopper Maps.

2. Specify your vehicles and shifts

Let us assume the worker can work from Monday to Friday. Now you specify the time either with the recommended Unix time stamp (the number of seconds since 1970-01-01) or for example, you count the seconds from Monday morning 00:00 and define the whole week in seconds. For example, Monday 9am is then represented by 9hour * 3600sec/hour = 32400sec. In turn, Wednesday 1pm corresponds to 2day * 24hour/day * 3600sec/hour + 1day * 13hour/day * 3600sec/hour = 219600sec.

Let us also assume your worker can work 8 hours per day and need to start at 8am. Then you can define your vehicles as follows:

"vehicles": [
{
   "vehicle_id": "fieldworker-1",
   "type_id": "car_type",
   "shifts": [
      {
         "shift_id": "monday",
         "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
         },
         "earliest_start": 28800,
         "latest_end": 57600
      },
      {
         "shift_id": "tuesday",
         "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
         },
         "earliest_start": 115200,
         "latest_end": 144000
      },
      ...
      {
         "shift_id": "friday",
         "start_address": {
            "location_id": "your_home",
            "lon": 13.39238003043599,
            "lat": 52.50385692772726
         },
         "earliest_start": 374400,
         "latest_end": 403200
      }
]
}
]

According to the above example, your vehicles always start and end at the location of “your house” (the coordinates must be given in longitude/latitude). If you want to allow your employee to end his route at a different location, simply enter an “end_address”.

3. Specify your customers

Customers can be specified as ordinary services much like this:

"services": [
   {
      "id": "customer-id",
      "name": "visit pharmacy",
      "address": {
         "location_id": "customer-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 3600
   },
...

]

Here, it is assumed that a visit takes 1 hour (3600 seconds). If this customer can only be visited on Tuesday or Friday, you can assign specific time windows to your services. Let us assume this customer can only be visited on Tuesday. Furthermore, you can only visit him from 9am to 11am or from 2pm to 4pm then you need to specify multiple time windows like this:

"service": [
   {
      "id": "customer-id",
      "name": "visit pharmacy",
      "address": {
         "location_id": "customer-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 3600,
      "time_windows": [
         {
            "earliest": 118800,
            "latest": 126000
         },
         {
            "earliest": 136800,
            "latest": 144000
         }
      ]
   },
...

]

If you have more visits than your worker can serve in a week, you might want to prioritize certain visits over visits that can be postponed. You can do this by assigning priorities (1 = high prio, 2 = normal (default) prio, 3 = low prio) to your jobs, just like this:

"services": [
   {
      "id": "customer-id",
      "name": "visit pharmacy",
      "address": {
         "location_id": "customer-location-id",
         "lon": 9.999,
         "lat": 53.552
      },
      "duration": 3600,
      "priority": 1
   },
...

]

4. Specify the algorithm

Finally, you must specify your optimization goal. If you solely want to minimize overall completion time, specify it like this

"objectives" : [{
   "type": "min",
   "value": "completion_time"
}]

Entire example

If you want to play around with vehicle (type) definitions like profiles and operation times or customer specifications like time windows etc. here you can find an entire example. Just copy the problem to our route editor, solve it and analyse the solution. You can either do it by looking at a map or at the raw json data.

Closing remark

Congratulations! You should now be able to model a simple traveling salesman with a week planning horizon and driver shifts. If you want to know, how you can refine your optimization goal to get a more balanced solution in terms of working time or if you want to add additional relations between your visits, e.g. customer A need to be visited directly after customer B, visit our documentation site or just asks questions in our forum.

Happy routing!

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’.

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.

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!

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

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