Optimizing Routes with Vehicle Capacities

Using Vehicle carrying capacities within route optimizations

Optimizing routes is hard. Especially when you have to produce solutions that businesses can use in the real world. This means taking into account what individual vehicles can and can't carry. After all, there's no point in letting one vehicle visit all the locations on your delivery schedule if it only has sufficient carrying capacity to visit one or two stops at a time.

Incorporating carrying capacities into route optimizations can have profound effects on the type of solution you end up with. To demonstrate this, let's take a look at a simple, two vehicle optimization around ten locations (including the depot) in Paris:

Route optimization with no vehicle capacities

As you can see there are a few locations scattered around the map, and two vehicles - one red, the other white. If you look closely at the vehicle table you'll notice that neither vehicle has a capacity specified under the far right header column. This means that the optimization, when run, will not test for any carrying capacities and we'll receive a route optimization that allows any vehicle to visit any stop without fear of overloading the vehicle.

Here's what the solution looks like:

Optimized vehicle route solution with no vehicle capacities

So we only needed one vehicle to visit all the stops in our problem (because there was sufficient time given in the problem specification - we'll examine the effect of limited time on route optimizations on another blog post). That's probably what you'd expect, so no great revelations there.

Optimizing Routes with a Single Capacity Requirement

Now let's pretend that we need to deliver something more bulky, like crates, and can only carry a limited number of them on each trip. In this case we can edit one of our vehicles to give it a carrying capacity of 10 Crates (Optergon allows you to specify any type of capacity you want - so if your vehicles are transporting giraffes, it's not a problem), like so:

Adding a vehicle capacity for inclusion into a route optimization

Now our Red Pickup can carry a limit of 10 Crates. Of course, we need to have some pickup and drop-offs requiring crates in the locations. Adding these is a simple task, and after a few seconds our vehicles and locations look like this:

Route optimization schedule showing vehicle capacities and location drop-offs

In this case we are going to drop off 4 Crates (from the depot) to both Alesia and Hopital Broussais. Since only the Red Pickup has carrying capacities for crates, we'd expect it to be the vehicle that visits those locations - and not the White Pickup.

Sure enough, the solution we get looks like this:

Route optimization with vehicle capacities

Looks pretty much the same, right? Well, it would be if you think about it. The primary difference is that you can see the Red Pickup completed the schedule because it was the only one able to carry Crates from the depot to the specified locations. And, since it could carry a maximum of 10 Crates but only needed to deliver 8 in total there was no need to modify the optimal route.

You might also notice that this solution is slightly more expensive than the original. Can you spot why?

If you look at the specified vehicle costs (i.e. fixed cost, distance cost, and time cost) you'll notice that the Red Pickup has a slightly greater Fixed Cost. This means that in our original solution, all things being equal, we used the cheaper vehicle - the White Pickup. However, as soon as the Red Pickup had to be used to make deliveries, it made sense to avoid sending out the White Pickup at the same time in order to avoid both fixed costs.

Check out how different costs can alter and change the characteristics of optimized solutions to learn more.

Optimizing Routes with Excessive Capacity Requirements

But what if we had more crates to deliver than our Red Pickup could carry in a single trip? We can test this scenario out by adding a single additional drop off from the depot, like so:

Route optimization with addition delivery capacity requirements

Now we have a carrying capacity of 10 Crates but a requirement to drop off 12. Something will have to change. Optimising this problem results in a different route:

Route optimization showing multi-trip solution as a result of vehicle capacity limitations

In this case the Red Pickup had to return to the depot after making two drop-offs in order to pick up the third and final one before delivering it. Notice too that the cost of the solution has increased because the vehicle travelled further and took longer (including a turnaround at the depot as depicted by the striped stopover in the vehicle's linear timeline).

Optimizing Routes with Multiple Capacity Requirements

But what if we had a different capacity requirement that could only be met by the White Pickup. Let's say, Pallets. We could alter the schedule to require drops off of Pallets and specify that the White Pickup has a capacity of 10 Pallets, like so:

Route optimization with multiple vehicle capacity requirements

Now we'd expect both vehicles to be used since there are location capacity requirements that cannot be met by any single vehicle in our schedule. As expected, here's what we get:

Optimized route with multiple vehicle capacity requriements

Now you can see that the White Pickup has also been utilized for a single trip in which it dropped off 5 Pallets at Place de la Bastille, made one more stop and then returned home. Since the Red Pickup still had more Crates to drop off than it could carry in a single trip, it had to return to the depot like last time.

Optimizing Routes with Multiple Dynamic Capacity Requirements

But what if we had to pickup something from one location (that's not the depot) and drop it off at another location. How would that affect the solution? To test this out, let's add a pickup and drop-off of 6 Pallets from one stop to another:

Route optimization with capacity pickups & drop-offs between locations

Notice that our White Pickup has capacity for 10 Pallets but we are dropping off 5 Pallets from the depot and 6 Pallets from Rue de Plantes for a total of 11 Pallets. What do you expect will happen?

Here's the result:

Optimized route with multiple carrying capacity requirements & inter location drop-offs

This solution might surprise you. After all, the White Pickup only went out once but had to carry 11 Pallets with a capacity of only 10. In actual fact, it dropped off the 5 Pallets from the depot before picking up the 6 from Rue de Plantes - all without exceeding its carrying capacity of 10 Pallets.

Not only that, but it's found a route that is both efficient and well optimized while simultaneously catering for these carrying capacities.

The alternative might have been to send the vehicle out to make the inter-location delivery and go back to the depot to pickup the additional 5 Pallets before delivering those. That, of course, would have cost your business more time, fuel and money.

By incorporating real-world, dynamic and excessive capacity conditions within route optimizations it is possible to build incredibly efficient solutions that are achievable in the real world. Not only that, but you can use these optimizations to determine whether or not it is actually possible to meet your delivery commitments at all - given the natural constraints on your business (i.e. number of vehicles available, operating times, carrying capacities, number of deliveries, etc). This is, in itself, extremely useful for companies that might otherwise spend a lot of money growing their fleet instead of utilizing the vehicles they have more efficiently.

Naturally, once you have your solution it's a cinch to send route maps with real-time traffic data to the drivers and packing slips to the depot/warehouse managers in charge of packing.