Vehicle Route Optimization

Executive Summary

Problem

Optimizing vehicle routes is a common problem in the logistics industry. The goal is to find the best way to visit a set of locations, optimizing for time, distance, cost, CO2 emissions, etc.

Most logistic companies use off-the-shelf optimization software, which are not flexible enough to handle the wide range of constraints and business rules.

Solution

We implemented a custom optimization algorithm that is able to handle the wide range of constraints and business rules.

Outcome

The algorithm is able to find a good solution in a reasonable time, even for the large instances.

The challenge

If you have ever heard of the Traveling Salesman Problem, you know that it is a very hard problem to solve. For n deliveries, there are (n-1)! possible routes. And a brute force solution would have a time complexity of O(n!).

This particular logistic company has a very large operation:

with multiple depots across the country
very large number of clients that had multiple deliveries per week
most clients had a requirement around delivery time (e.g. between 9am and 11am)
there are various union rules around how long a driver can operate and how often they need to take a break
there are multiple typed of vehicles and they have different volume and weight constrains
in addition some of the vehicles have multiple compartments for different types of goods (ambient, chilled, frozen, etc.)
nor every type of vehicle can deliver to every client (some vehicles are too big or too small for some of the clients)
and many more constrains that we need to take into account

So the solution space is huge and we needed to be clever about how we approach the problem.

1. Choosing the right algorithm

The first challenge was to find algorithms and techniques that can find a good (but not necessarily optimal) solution in a reasonable time. From previous experience the Data Science team had very good experience with heuristic algorithms and Adaptive Large Neighborhood Search (ALNS, a metaheuristic).

There was a previous implementation of the algorithm, but it was heavily coupled with the business logic and other parts of the system, making it very hard to maintain and extend. My contribution was to help the Data Science re-architect the algorithm and implement it in Python as a separate module. A lot of hours were spent white-boarding and pair programming with the team so that we can learn from each other. I am very proud that at the end of the day they not only got a working implementation, but also learned about engineering best practices and data structures.

See the bottom of the page for more details on ALNS

2. Speeding up the algorithm

As you might have guessed, this whole solution was implemented in Python. And everyone knows that Python is not known for its speed. So why did we choose it? The reason why we always choose Python:

We are optimizing for developer cycles, not CPU cycles

The DS and DE teams were very proficient in Python
Iteration is much faster and adding new business rules is much easier
The requirement is to run this optimizer in batch once a month/week. There is no need to optimize for the runtime.

As a technical lead on the project I adopted the following approach from the start:

Move quickly in the beginning when the requirements and constrains are loosely defined, get to a POC
Write system tests to verify the solution is at least running end to end
Peer review the code, be on the lookout for code smells and obvious inefficiencies. Teach the team about the trade-offs and best practices.
Once the interfaces and data structures are clearly defined, profile the code and find the bottlenecks.

It turned out that the biggest bottleneck was the very frequent deepcopy of the massive data structures. The concept of ALNS requires you to maintain a current, previous and best solution. When a solution is better than the previous you replace it, but if it’s not, you have to revert it. In addition some heuristics also require the ability to revert changes to the solution.

The first thing we did was to implement a custom __deepcopy__ method for the data structures. Those data structures are quite complex and have a lot of nested and recursive objects. This was a good opportunity to teach the team about the concept of deepcopy and how memory works. Armed with that knowledge the team modified some of the heuristic algorithms to remove or reduce the need for deepcopy. Seeing the performance boost help them internalize the trade-offs of copying.

A few other tricks in the bag of Python performance tricks were:

using set instead of a list when dealing with immutable objects (as they are effectively a hash table without the values)
using dict instead of a list for more efficient access/value lookup (as they are a hash table)

The exact speed boost from PoC to MVP is hard to quantify as the improvements were done in parallel with new features. But a rough estimates of mine puts at about 10x.

3. Parallelizing the algorithm

As good as ALNS and heuristics were, a single thread implementation was not be able to handle the scale of the problem we were facing. So we made a decision to use a parallelized approach, where each iteration of the ALNS is run multiple times with the same input and only the best solution was kept and passed to the next iteration (similar to a genetic algorithm).

To achieve this we used a Python library called Ray. It allows to run parallelized tasks and easily distribute them across multiple machines. Again, this was chosen based on a previous experience with the framework. There were two extra challenges around the implementation:

We needed a reliable compute infrastructure with a lot of resources(RAM and CPU) to run multiple experiments with different parameters and algorithms.
The ray I/O was not dealing very well with the large amount of data we had.

We solved the first part by using Ray on Vertex AI. It is a managed service that allows to run Ray on a cluster of machines. We build tooling and pipelines to help us create and destroy them on demand for the duration of each experiment. There were a some challenges with networking, CPU limits, choosing the correct machine type. The GCP documentation was not very extensive and the error messages on managed services are not very helpful. Still through a combination of pure luck, previous experience and a lot of debugging we managed to get an optimal solution.

The second challenge with Ray (the slow I/O) had a clear cause - the amount of data that we were passing back and forth between the driver and the workers was very large (100s ~ 1000s of MBs). Inspiration came after carefully reading the Ray documentation and understanding that Ray pickles the data.

The way the parallelized tasks were designed, was to send them the same data object, they would copy it, modify it and return it. We would then compute the best solution by comparing the results from all the workers. The solution was quite simple and elegant.

Instead of returning the full data object (e.a. ALNS solution), we would return 1 reference (to the Ray Plasma object store ) and 1 float - the evaluation score used to compare the solutions. We can then compare all the scores, find the “best” solution and retrieve the full object from the object store.

Actually we didn’t even need to do that, because we can just send back the reference to that “best” object. This significantly improved the performance of the algorithm and allowed us to speed up the experiments by 2x.

Extra material for the curious

ALNS

The Adaptive Large Neighborhood Search (ALNS) algorithm is a metaheuristic framework designed for solving complex combinatorial optimization problems. It’s an extension of the Large Neighborhood Search (LNS) and belongs to the family of local search heuristics. [1]

Metaheuristic:

A metaheuristic is a high-level problem-solving strategy that guides a subordinate heuristic to explore the search space more effectively.
It’s a general algorithmic framework that can be applied to a wide range of optimization problems with relatively few modifications.
Metaheuristics aim to find good (near-optimal) solutions, especially for problems where finding the exact optimal solution is computationally infeasible (like NP-hard problems such as the Traveling Salesman Problem).
Examples of other metaheuristics include Genetic Algorithms, Simulated Annealing, Tabu Search, and Ant Colony Optimization.

Large Neighborhood Search (LNS):

LNS is a type of local search heuristic. Traditional local search methods explore the solution space by making small changes to a current solution. [2]
LNS, in contrast, explores much larger “neighborhoods” of the current solution. It does this by destroying a significant portion of the current solution and then repairing it using some heuristic method.
By exploring larger neighborhoods, LNS aims to escape local optima more effectively than traditional local search.

Adaptive Large Neighborhood Search (ALNS):

ALNS builds upon LNS by introducing the concept of adaptivity. Instead of relying on a single destroy and repair heuristic, ALNS maintains a pool of different destroy and repair operators.
In each iteration of the search, ALNS adaptively selects which destroy and repair operators to apply based on their past performance. Operators that have led to better solutions more frequently are given a higher probability of being selected in future iterations. This is typically done by assigning weights to each operator and updating these weights based on the quality of the solutions they produce.
This adaptive mechanism allows ALNS to tailor its search strategy to the specific characteristics of the problem instance being solved. Different operators might be more effective in different parts of the search space or for different types of problem instances. [3]