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:

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!

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!