GraphHopper Route Optimization API goes Beta

Since several months we’ve been working on the Route Optimization API – a new part of the GraphHopper Directions API. And today it goes into beta status, i.e. we trust the software and our architecture enough that it can be used in production. Although it is used in production already we allowed us to change the API and even break it in certain areas which won’t happen anymore.

What is the Route Optimization API?

The Routing API solves the problem of finding routes between predefined locations where the order cannot change. Now the new Route Optimization API solves the heavier problem where the order of locations can be optimized. Furthermore, an arbitrary number of constraints like time windows, capacity restrictions of vehicles, driver skills and even driver breaks can be taken into account, and our API does not only allow solving single vehicle problems, but can consider multiple vehicles with multiple start and end locations. These problems are known as vehicle routing problem (where the traveling salesman problem is one problem type). Our Route Optimization API makes these complex problems easy to solve.

Traveling Salesman Problems (TSP)

In a later blog post we’ve covered the so called traveling salesman problem in more detail. For now here is a small example of a sightseeing tour through Berlin where randomly selected POIs were chosen: Checkpoint Charlie, the television tower, Berliner Ensemble, Berliner Dom and Staatsoper. One can define it as a simple routing request, with 3 via points and a fixed start and end point, and just needs to add the optimize parameter (optimize=true) to the Routing API. Look at the illustration below. It saves roughly 10% travel time (76min instead of 85min), and the more locations you have the bigger the savings can be.

The unoptimized version is 6.4km and takes 85 minutes when walking – the optimized version below.

The optimized route is 7.1km long and takes only 76 minutes.

Vehicle Routing Problems (VRP)

Furthermore, our Route Optimization API is able to solve vehicle routing problems with more than one vehicle,  i.e. real world scenarios happening everyday in supply chains of logistics. Therefore we’ve also added some more vehicle profiles including trucks to improve the estimated arrival time further. We will be covering this problem in more detail in a later blog post, but for now let us look at the following simple example:

Assume a fleet manager needs to dispatch 3 vehicles with start and end location at the main station. Each vehicle only has the capacity of serving 7 customers at maximum. In total, 20 customers that are randomly located in Berlin need to be served such that total transport time is minimized. This is a very prominent form of a vehicle routing problem, a capacitated vehicle routing problem. And the solution will then look like

This gives a first impression of what can be solved with our API. However, the problems one can actually solve with our API can be more complex e.g. minimize completion vs. transport time, minimize maximum makespan and many more interesting problems. Just play with our official live examples and customize them as they are open source. Sign up and get started!