Simple Route Optimization integrated in the GraphHopper Routing API

Since several months we’ve been working on our new Route Optimization API, which is a powerful API for your problems in logistics and similar areas. It includes time windows, capacity restrictions and much more features. It’ll be announced soon on its own!

Last week we had an idea: we wanted to make the integration of this new API as easy and straightforward as it can be. And the existing clients of the Routing API now just need to add ‘optimize=true’ to the request URL and the returned route is already optimized regarding overall time. So these clients can now easily solve traveling salesman problems too, and for all problems with more than one vehicle or more advanced restrictions you can still use our Route Optimization API. Of course, all times are based on real road networks instead of imprecise beeline approximations.

Several things need to be calculated under the hood to make this optimization happening:

  1. Decide to do route optimization instead of ‘just’ A-to-B routing.
  2. Now calculate all travel times between all locations (A to B, A to C, B to A, B to C, …), which gives us the travel time matrix (also known as distance matrix). For example, if you specify 5 points then 5*5-5 travel time values are calculated – this is done using our fast Matrix API which is way faster than the sum of individual point-to-point calculations.
  3. Now use the previously calculated travel time matrix to solve the underlying traveling salesman problem, i.e. to optimize the location order.
  4. Finally fetch the complete route with the correct location order including e.g. elevation data for foot and bike routing via the Routing API.

You can already use this feature with our Java and JavaScript clients. And so I did. I locally added this optimize parameter to the GraphHopper Maps UI and what I got was a bit magical! Look into this video to see what I mean.