Routing Lechugas at Mercadona Tech
At Mercadona Tech, we deliver a lot of Lechugas (Spanish: lettuce) per year.
Our challenge at the last mile is to generate quality delivery routes that guarantee we can efficiently deliver our Jefes orders on time while promoting a respectable and safe working ecosystem for our drivers.
Over a week, we generate more than 4000 routes.
But how do we generate all those routes?
This article will introduce one of the problems we tackle within the last mile vertical. We’ll provide examples of how we approach and solve this problem.
When using our app to order groceries, you first introduce a postal code and then shop for groceries to be delivered. Over the course of a week, we have thousands of orders to deliver. Doing this efficiently is the job of our delivery system.
Seeing it in a simple way, our delivery problem can be viewed as solving a TSP (traveling salesman problem) where the driver should follow a sequence of orders to be delivered.
— Image 1 — One route with orders to deliver.
This is a well-known computer science problem with many algorithms for solving it. Exact solutions can be found for up to tens of thousands of deliveries. Heuristics algorithms can develop good enough solutions in a reasonable time, even in the order of millions of deliveries.
The theory is good, but in practice, we have a fleet of trucks to generate routes for, and we need to distribute the orders to deliver in the best possible sequence.
— Image 2 — Multiples routes with orders to deliver.
In order to do this, we need to solve the VRP (Vehicle routing problem), which is an NP-hard problem (this means that the size of problems that can be optimally solved are reduced), and a generalization of the TSP.
But do you think that by solving that kind of problem we can give the best service to our Jefes (customers)?
If you thought it was enough, I’m here to tell you that the answer is no. We offer a delivery window for our Jefes that usually is of 1 hour, so they can better know when the order will arrive. With this in mind, only some of the solutions to the VRP will fit with what we want. So finally, here is when the problem that we must solve the VRPTW (Vehicle Routing Problem with Time Windows).
— Image 3 — Multiples routes with orders to deliver in a given time window.
On top of that, we also need to deal with changes in the orders, traffic, weather, and other types of events making it more complex.
In order to solve it, we have multiple systems and steps; the big picture can be seen next.
— Image 4 — Diagram of the different parts of our system.
Divide and conquer
We decompose the original problem into sub-problems (clustering deliveries by date and areas) and solve these sub-problems, which makes the scope of the problem smaller.
To solve these sub-problems, we use a meta-heuristic, where the goal is to explore the search space to find a near-optimal solution efficiently.
But the world is not perfect; we could have orders with imprecise coordinates, capacity problems, or other situations that make it challenging to find a solution where all the orders fit. This generates another problem where we need to fit the remaining orders on top of the routes generated by the optimization.
Human & machine collaboration
Dealing with these challenges requires collaboration, so we involve our “gerentes de reparto” in decision-making. By leveraging their insights and experience, we collectively devise strategies to optimize the allocation of remaining orders. After completing the adjustments on the routes, we have a new step.
— Image 5 — View of our manual routing tool.
The recalculation
Once the route adjustments are completed, we enter the stage of route recalculation. While the orders are now allocated to the routes, the sequence may not be optimal. Since, at this step, we only have a reduced number of routes to optimize, we can overcome this challenge by employing an exact algorithm that systematically computes all possible combinations of delivery. Through this process, we aim to find the best delivery sequence within the route.
Conclusion
By using these strategies, we can achieve best-in-class route optimization and, consequently, an ideal delivery experience without sacrificing execution time. All this routing process helps us to deliver our Jefes orders on time while promoting a respectable and safe working ecosystem for our drivers.
Stay tuned for upcoming posts where we will deepen into the fascinating world of Engineering at Mercadona Tech. We are excited to share our knowledge. So, keep an eye on our channels for our future posts!
If you want to join our team and contribute to our delivery systems or work on any other challenging problems at Mercadona Tech, check out our open roles on LinkedIn.
