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:
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:
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:
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:
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:
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:
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:
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:
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:
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:
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:
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.