.png)
3 months ago
2
Improve your routes
So let’s say that you operate a courier fleet. Every day you must schedule your parcel deliveries by assigning them to the distribution vans, making sure that they get delivered on time, that you don’t overload any van, that work is evenly assigned between drivers, that drivers do not work past their contractual and legally-binding periods, that you minimize fuel consumption… The list can go on and on depending on your particular business. This particular situation was previously described first-hand by Kamil Bujel of GOGOVAN in another article.
They addressed the problem by using an off-the-shelf optimization package to help them sort out the daily grunt work of manually scheduling the vehicles. Kamil describes this process at length in his article, as well as the trouble they went through trying to get the algorithm to work within reasonable time and memory bounds. But why was the optimization solution behaving the way it did? Why did it consume so much memory? Taken like that, the optimization solution works like a black box and its users have little or no insight on what might be happening inside.
What if we could take a peek inside one of these optimization algorithms? What kind of magic are they performing under the hood in order to spit out an “optimized” solution? I decided to write this article on the wake of Kamil’s own article. It so happens that, among other things, I have been developing one such route optimization algorithm for my own company and this article is a brief distillation of what I have learned by implementing a particular type of optimization algorithm.
Discrete Optimization
Optimization is a misnomer as we rarely find the very best solution. All research in this field, starting with the infamous Travelling Salesman Problem (TSP), will tell you that optimal solutions can only be found in toy problems. Real problems, with hundreds of vehicles and delivery locations, are just way too big to be fully searched in useful time, so we must make do with some smarts. Also, the type of optimization I am discussing here is of the discrete type. If you are familiar with continuous optimization, then you can make use of gradients in order to follow the steepest path down to the global minimum. There is no such luck in discrete optimization. What is the derivative of adding another van to the mix, or removing one delivery, or moving one delivery between vans? You must try the option, evaluate the result, and then decide what to do. That is essentially how we would mentally do this type of optimization, maybe using a couple of obvious rules, such as geographically grouping deliveries.
I have already mentioned some terms that are not very well defined. I mentioned a minimum. But a minimum of what? Do we want to minimize vehicles, distance, time, fuel consumption? This one is really simple to answer: we want to minimize the daily operational cost. But how do you calculate this cost? Read on, curious reader.
Route Optimization
How does route optimization work? What does it take to calculate an optimal assignment of vehicles to the jobs we must service? How are times and sequences calculated so that we minimize our operational costs while keeping our customer satisfaction high and driver churn low? Where do we start? How do we end?
This article will tell you about one of the possible solutions to this problem, an extension of the infamous Travelling Salesman Problem (TSP) using some extensions with exotic names. Here, I will explain an implementation that solves this problem, by addressing the requirements of a real distribution company, like GOGOVAN. If you haven’t done so yet, please read Kamil’s article to get a good glimpse on how one such company operates and what are their optimization challenges.
Instead of using an off-the-shelf solution, I am going to conceptually develop an approach to solve the same problem based on taboo search, local search, and variable neighborhood search. Let’s learn about these concepts as we go along.
In this business of courier delivery, you have to cope with a relatively large number of daily deliveries of relatively small and light parcels. Deliveries are made in similar vans with given cargo capacities, usually measured in weight, volume, units, or any mix of these three. Accounting for vehicle cargo capacity is important as this is a hard restriction to this problem, meaning that you cannot overload a van due to safety and legal reasons. You cannot devise a solution to your parcel distribution problem where one or more vans carry more load than allowed. This is not a feasible solution. When I talk about feasible solutions, I mean solutions that do not violate hard restrictions such as this one. Note that a feasible solution may violate soft restrictions, such as when the van is scheduled to arrive late at a given customer. Under such a circumstance, this solution would be more expensive (by applying a late arrival cost penalty) than another where all vans deliver on time. Please note that the choice of what is a hard or a soft restriction is entirely yours, I’m just illustrating this concept with restrictions I have used before.
As is usual in this type of delivery scenario, all vehicles are loaded in just one location, the central warehouse, once per day (early in the morning, I would presume from tracking my online purchases). The purpose of the optimization algorithm is then to plan all daily deliveries by making sure that delivery times are met while maintaining the lowest possible operational cost.
If this optimization process is a culinary recipe, what are the ingredients that we need to care about? We have customers, deliveries, vans, drivers, roads, traffic, and operational costs. Let’s model each of these so we understand the type of information we require.
Customers
Customers can be easily modeled as simple geographic locations, namely by their latitude and longitude. Georeferencing customers is an important step because we will need to derive trip duration and distance between any two arbitrary locations in our operations map. In order to calculate these, all customer locations must be translated into geographic coordinates in order for the distance and time calculation methods to work properly. If these customers have specific delivery time windows, then these can also be considered and recorded. If you do so, also consider whether breaking these time windows is a hard or a soft restriction. Remember, hard restrictions invalidate a solution and soft restrictions merely increase the solution cost. More on this when we look at cost minimization.
Deliveries
Deliveries are simple statements that one van must visit a customer location and spend there a given amount of time delivering a parcel with a given cargo dimension (weight, volume, units). This means that a single delivery must be thought of as a trip from where the vehicle is up to the delivery place, plus the time required to perform the delivery. The optimizer will try to juggle deliveries around in time and through the vans so as to produce an efficient solution, with a low cost.
Vehicles
Besides a unique identifier for each van, such as the license plate, we need a record of each van’s maximum cargo capacity. When assigning deliveries to a given van, we are deducting the delivery cargo dimension from the available vehicle cargo, and the remaining value must be positive. If not, we will be overloading the van.
Besides these data, we must also record any relevant operational costs per van, such as rentals, cost per km or other costs that might be used for the optimizer to minimize.
I’m also going to make the assumption that each vehicle has its own driver, so drivers are not a scarce resource. What we do need to consider, though, are any contractual arrangements such as the maximum working time per day, or company working hours. Using this simplification these restrictions can be applied to the vans themselves and we worry not about the driver as an optimization entity.
Roads and traffic conditions
The road network and traffic impedance are external conditions that are imposed on the model and that must be taken into account. Here, one has a range of possibilities, from the most expensive and sophisticated ones — sourcing this data from a specialized provider such as Google or Here, to the cheapest and less exact — calculating all distances using geodesic measures compounded with a distance factor, and an average speed for trip duration calculations. If you are going with the first, traffic is also an option either as a real-time feed or as a typical impedance for a given time interval. Anyway, you must be able to build a matrix of distance and duration pairs between any two points as this is prime material for the optimization algorithm.
Costs
I kept mentioning the operational costs because these will help measure the quality of the solutions the optimizer will generate. In order to do so, we must create a cost function that converts all of the previous ingredients to the same metric: economic cost. Distances are converted to cost using a cost per km rate. Delays are converted to cost using penalties. Vehicle usage is converted to cost using the van’s daily discount rate or the lease rate. You can look at these costs as real ledger costs and/or as your personal preferences concerning the optimization process. For instance, if you don’t care about the number of vans to use, you can set their individual costs to zero. On the other hand, if you want to minimize the number of vans, assign a usage cost per vehicle. Thus, the optimizer will prefer solutions with fewer vans. The same goes for distance. Note that the optimizer will only look at the output of this cost function when deciding the best solution, nothing else. That’s why all the important variables must be converted into a cost and included in this cost function.
The Optimization Process
Now that all ingredients have been collected, we can start cooking.
I will use the term “solution” to denote a feasible configuration, which is simply a collection of vehicles each one containing an ordered collection of planned deliveries. These planned deliveries include information about starting and ending times as well as their geographical routes.
Press enter or click to view image in full size
For each solution, one can calculate an associated cost through the cost function. The optimizer will try its best to minimize this cost, i.e., to find a solution with the minimum possible cost given all restrictions and computation time.
The Initial Solution
The first thing we need to do is to create the initial solution. Much like hastily putting all your children’s toys inside a box in such a way that the lid closes, we will use whatever heuristics necessary to create one such feasible solution. Mind you, it will be a bad solution carrying a high cost. But it will be feasible. This is our starting point — we can now start to improve.
The Improvement Loop
Improving on the initial solution entails a very simple concept: making a small perturbation to the initial solution (ensuring that we still get a feasible solution) and then evaluating its cost. But what is a perturbation? It can be as simple as changing the order of deliveries in a single van or transferring one delivery from one vehicle to another. It can be as simple or complex as you like. In a sense, this is a neighborhood and the search within it is a local search.
Press enter or click to view image in full size
Please note that a neighborhood can be thought of as an algorithm that performs a single type of perturbation. In the picture’s case, it works by moving one delivery from one van to another. Note also that the order of deliveries within a van is also of importance because it dictates the order by which deliveries are made and, consequently, what routes will be traveled. This has a clear implication on distance cost.
As I noted before, it is not possible to know beforehand if a given perturbation will reduce the cost or not. Contrary to continuous optimization, we cannot calculate gradients of the cost function and follow them down to the (hopefully) global minimum — we must make the change and evaluate its merit. Did it reduce the cost, increased it or stayed the same? And what are we going to do about it? If it reduced the cost we can adopt it as our next best solution — the incumbent solution. The incumbent solution is the best solution so far, the one with the lowest cost, the one you will use at the end when the optimization process ends.
But what if our perturbation increases the solution cost? Do we discard the solution and try another move until we get a lower cost? Or do we adopt the worse solution in hopes that it will lead to an even better solution down the road? If you were skying downhill, this would be like climbing a nearby mound in hopes of a steeper slope on the other side.
From my experience, you can do both but under different circumstances. The first approach is what is called a greedy search and seems to work best when the number of different possible solutions — the state space — is very large. In these scenarios, the number of possible solutions is so large that you can almost always count on a descending path. Not so for smaller state spaces. Here, experience taught me to allow the cost to increase so that the optimizer is able to find a deeper nearby cost valley, where it can look for a better solution.
Now we can go back, run the loop with our updated solution, generate another perturbation and see what happens. This is a good time to decide if we are sticking with the same neighborhood or if we should use another one. This decision can be very important especially when one of the neighborhoods seems to be stuck on a local minimum, unable to generate better solutions. The way you decide when to change the neighborhood and to what neighborhood to change to is essentially heuristic. This is what variable neighborhood search (VNS) is, in a nutshell.
It’s Strictly Taboo…
There is a final ingredient to this scheme: we must do like Ariadne in the maze, and mark the path we tread. Every generated solution must be kept on a list for future memory, in order to forbid the optimizer to explore it again. Hence its name: the taboo list. Whenever the optimizer generates a new solution, it must look at the taboo list and check if that solution was already generated (or visited). If so, it should try another one, probably the second best.
Stopping Criterion
So when do we stop? As I said before, it is next to impossible to know that you found the best possible solution, so there must be a preset criterion to stop the improvement loop and report the incumbent solution. Here, I leave it to your imagination. Mine was not very far-fetched, so I used a strict time criterion. Before running the optimization process, I specify by how long I am willing to wait for an “optimized” solution. And that’s it.
Alternatively, you can count the number of loops that the process has calculated and stop after N non-improving loops.
Closing Remarks
I hope this makes more sense now. After all, these are simple concepts with fancy names, rolled around the computational power of modern technology. But I have merely scratched the surface here. There are many more minute details that are waiting to trip you up, especially when you start using the power of parallelization. No spoilers for you, go ahead and explore this fascinating world of discrete optimization!
Recommended Reads
