Helping Oda optimize depot locations

With the mission of building the world’s most effective retail system, Oda wants to be efficient in all levels of the value chain. An important piece in the value chain is the depots, which are small facilities where the packed groceries are moved from trucks to the yellow vehicles that drive to customers. With thousands of customers receiving orders from the depots every day, the locations of the depots must be chosen carefully to minimize distribution costs. With Oda’s recent expansions to new areas such as Helsinki and Berlin, this decision is more important than ever. As students specialized in optimization, we have, through the work on our master’s thesis, created an algorithm for Oda that evaluates which depot locations seem most profitable to open.

This text is written by David Gulaker, Johannes Log Indbjo and Mathias Waage Sørensen

This is no simple task. To find the cheapest depot locations, we must find the cost of delivering orders to customers. This depends on the routes driven between customers, and finding these routes is a complex problem in itself. Another aspect is to decide which set of depots to make use. The number of possible combinations increases exponentially with the number of possible locations. Let’s say we want to consider 20 possible depot locations. If you can open any number of depots, that gives over one million possible combinations of open depots. If estimating the routes for one of these takes 5 minutes, it would still take 10 years to work through all combinations 🤯 And spending 5 minutes computing routes lead only to a rough estimate. The newest research in the field still uses weeks on finding the optimal routes for only one of these problems. Clearly, spending millions of weeks to find an answer is not possible. Therefore, it is necessary to create a clever algorithm that finds good estimates of routing costs in much shorter time by evaluating just a few of the depot combinations. Luckily, this seems to be possible.

Different depot locations and routes from these.

Modelling Oda’s distribution logistics 🚚

So, the problem is computationally complex to solve. But the problem itself seems very clear, right? Locate the depots so that the deliveries are made as cheaply as possible. However, when we dig into the details, the problem is dependent on many industry-specific aspects. What will the depots actually cost? What size should the vehicles be? How many drivers should have permanent contracts? How far from the city do we want to deliver products? All these questions need to be answered to assure that the problem resembles the reality.

Modelling Oda’s distribution logistics involves many trade-offs. The problem must be solvable in reasonable time, while we must also solve a problem that is as close to reality as possible. Finding this balance between efficiency and accuracy is not easy. We have therefore used a lot of time discussing how the problem should be modelled. Frequent meetings with Oda representatives have made us able to model the problem in a way that brings value and reflects reality, while our supervisor and the academic community on NTNU have helped us find smart ways to model the problem efficiently.

Oda invited us to talk about some of these topics in their guest lecture at NTNU in March.

Dealing with uncertain demand 📊

Another challenge with working with the long-term view is how to represent the variations in demand. How many customers should be served each day is uncertain, as it is not known until the ordering closes the night before. The demand will also vary through the week. Maybe a busy Monday needs twice the number of vehicles as a quieter Thursday. How can we estimate the routes when we don’t know who or how many we should deliver to? Our solution has been to simulate the demand on many different days using what we know of the demand distribution and taking into account the demographics of the area. This way, we can generate scenarios. For instance, one scenario can be that 2000 customers make orders, while another can be that only 500 orders are placed. Each scenario is assigned a probability reflecting the likelihood for this demand to occur. With this we are able to take into account the range of possible demands in a realistic way.

The figure illustrates how a solution is evaluated with respect to 4 scenarios.

A problem too complex to solve 💻

Being able to define algorithms that are fast enough to solve realistic problem sizes is a challenge in itself. For those familiar with computational complexity, the problem is NP-hard as it is a compound problem consisting of two other NP-hard problems, namely the vehicle routing and facility location problem. For those not so familiar with the terms, let’s just say the problem is so hard to solve that finding the best solution for realistic problem sizes is merely a dream. While most of the research literature can solve problems with up to hundreds of customers in reasonable time, typically in the magnitude of hours, we need to solve problems with thousands.

To cope with this, we use heuristics, which finds solutions that are good enough (but probably not optimal). In fact, what we do is to construct a smart way to guide the search through combinations of depot locations. Let’s say we consider depot location A, B and C, then possible solutions are for instance to open A and B, A and C or only A. We figure out that A costs 100, and want to further explore how much it costs to open A and B. We create routes with depot A and B open and figure out that it costs 120. Since opening B led to a worse solution because of higher costs, we prevent the search from trying to open B again for a certain period. We say that B becomes tabu. In very simplified form, this is an example of what is called a Tabu Search, which is the basis for how our search works. The aim is that more time is used to explore solutions that seem promising. With this, we can identify good solutions within just a couple of hours.

The plot shows how the cost is reduced during the search as better solutions are found.

The hope is that the master thesis can help to make Oda’s value chain even more efficient, ultimately giving us customers cheaper groceries delivered on our doorstep. We also aim to answer questions that give Oda more insights, like how many customers are needed before a new depot should open and how the solution is affected when changing the opening cost of the depots. Finally, we have to say that having the opportunity to work with a business case like this in the master thesis is so motivating! We are truly grateful to be given this challenge from Oda and are glad for the emphasis they put on collaborating with students and academia in developing the future of retail.