Load balancing in the context of vehicle routing problems is a way to achieve a more evenly distribution of jobs or activities over your drivers’ routes. There are a number of reasons to balance load. The most obvious ones are resource utilization and fairness.

Why do we need a blog post for this? Why aren’t solutions balanced by default?

Simply because there are a number of optimization goals and in many cases planners want to minimize vehicles and variable transportation costs. However, this is often contrary to balanced vehicle routes. Let us illustrate this with a simple example. Assume there are four drivers with the same start location (green marker). They need to conduct 10 deliveries (blue marker). There are no further constraints like capacity restrictions or time windows. If your first optimization goal was the minimization of vehicles, and, the second, the minimization of completion times, you would specify it as follows:

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

The best solution is to just deploy a single vehicle as illustrated in the figure below.

What about the other 3 drivers? They are idle and want to be employed as well.

To achieve this, you need to refine the optimization goal. GraphHopper offers you three simple ways:

1. min-max completion times
2. min-max activities
3. min-max completion times AND min-max activities

min-max completion times

When using this goal, GraphHopper minimizes the maximum of completion time of all employed drivers, or to put it in simpler words, it continuously reduces the longest route by moving stops to shorter routes. Specifying this objective is as easy as this:

{ "objectives": [ 
   { "type": "min-max", "value": "completion_times" } 
  ] 
}

Let us analyze the resulting solution of the example above.

As you can see, 3 drivers are employed. This increases fixed employment costs as well as transportation costs. At the same time, however, it significantly reduces the completion time of the entire plan, i.e. of the last delivery. In other words, this optimization goal can be used to deliver more in less time. Wait, there are 4 drivers, why do I only see 3?

It is because the employment of a fourth driver cannot reduce the longest route anymore. But what if driver 4 got already paid? He needs to work! This brings me to the second option.

min-max activities

When using this objective, GraphHopper minimizes the longest route in terms of number of activities. It can be defined like this:

{ "objectives": [ 
    { "type": "min-max", "value": "activities" }
  ]
}

It results in a solution where all drivers are employed.

This is nice! Unfortunately, the forth driver (route marked in red) only has one activity now and by far the shortest route. Furthermore, the longest route from the last example (in terms of completion time) got even longer and got 2 new activities. In this example, it might be more favourable to keep this longest route as it was and distribute activities/stops evenly to all other routes. This can be achieved with the following optimization goal.

min-max completion times & min-max activities

It combines the two optimization goals above and can be specified as easy as this:

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

Applied to our example above, it yields the following solution.

This is a nice and balanced solution – at least when it comes to the specified indicators completion time and activities. Actually, there are various other indicators that requires your business to be balanced like unload time, tour length or demand. If you require other indicators than described here, please contact us.

If you want to try out our Route Optimization API or any other API such as Routing API, Map Matching API, Geocoding API, Isochrone API or our lightning fast Matrix API, register here and you get a free trial automatically.

Happy Routing!

We had the opportunity to improve two critical components of our Directions API.

The Matrix API is now up to 20 times faster for large matrices, which makes our Route Optimization API also significantly faster as it uses the Matrix API under the hood. You can find more details in our recent blog post.

The Geocoding API supports the new external provider “gisgraphy” and is currently the only alternative to the default provider that does not only support reverse geocoding but also autocomplete. Please read the documentation for a feature overview that also lists our other external providers like “nominatim” and “opencagedata“.