Just Eat Takeaway.com embraces the power of Operations Research

I wanted to write about Operations Research (OR) in my first article as I was introduced to OR twelve years ago when I was a sophomore in industrial engineering, and it has been a very big part of my life since then. My aim with this article is twofold:

• Introduce one of the fundamental tools in OR, Mathematical Programming, to the people outside of our domain.
• Demonstrate how OR can help to solve a major real-time decision optimisation problem in Just Eat Takeaway.com (JET): courier-order assignment problem

Photo by Antoine Dautry on Unsplash

From Words to Equations: OR Uses Mathematical Programming to Describe Optimisation Problems

Operations research is not something new and is sometimes known as Operational Research. It has its roots in scientific research for military operations during World War II (Operations in OR referred to military operations back then). In the post-war world, OR has been recognised and adopted by many different types of businesses and industries. Throughout my history with OR, I have witnessed applications in very different domains answering questions such as:

• How to schedule on-duty pharmacies to minimise total distance to be travelled by people in need of emergency medicine, respecting the limited availability of pharmacies?
• Which sell or buy bids to accept in the day-ahead electricity market auction to maximise market surplus while ensuring that the supply meets the demand?
• Which connecting flights to be delayed (and by how much) in order to find a balance between on-time performance of the airlines and the number of passengers missing their connections?
• How to assign pending customer orders to couriers travelling around the city to minimise delivery times and maximise network efficiency?

As OR practitioners, we typically formulate a decision optimisation problem via mathematical programming. The programming part is to create a model that represents the given problem in mathematical terms. Such a model typically contains three major elements:

1. Decision variables

In order to model the “how” part of our problem, we define variables that represent our decisions. Our decision variables could be one of the following types:

• continuous → How much should I save to live comfortably when I retire? (e.g. floating point numbers)
• binary → Should I delay this flight or not?
• integer → How many days a particular pharmacy should be on-duty this month?

Solving problems with binary or integer variables are generally harder to solve than the problems of similar size with only continuous decision variables (because of the non-convexity of the feasible set of the decision variables).

2. Objective function

Objective function answers the “what” question in the problem. What do we want to minimise or maximise? Objective function is a function of our decision variables that indicates the corresponding value of different decisions we could take. Depending on the form of the function, linear vs non-linear or convex vs non-convex, the difficulty of solving the problem would change. Roughly speaking, it is generally harder to solve non-linear optimisation problems than the linear ones. It is also generally the case that convex problems are easier than the non-convex ones as a local optimum may not be globally optimal for the latter.

3. Constraints

Many times our decisions are constrained by different factors such as resource limitations, business rules, legal obligations and so on that we cannot make any decision we would like. Our decisions have to satisfy all the constraints in our problem, otherwise, they are called infeasible and cannot form a solution to our problem. Similar to the objective function, the form of the constraint equations highly affects the difficulty of solving the corresponding optimisation problem.

In the next section, we are going to build a mathematical model for a highly simplified version of the courier assignment problem that is solved repeatedly in real-time by the food delivery companies.

Who Should Be Delivering Your Food: The Courier Assignment Problem

Let I and J represent the set of couriers and orders, respectively, at any given time in a region (e.g. a city). For the sake of simplicity, we will assume there are more available couriers than the number of orders we need to assign, ⎢I⎥≥⎢J⎥, and a courier can be assigned at most one order. This ensures that our problem has always a feasible solution.

Decision variables

Given courier 𝑖 ∈ I and order 𝑗 ∈ J, our decision is whether to assign order 𝑗 to courier 𝑖. To represent such decisions, we define variable x(ij), where x(ij) = 1 if order 𝑗 is assigned to courier 𝑖, and 0 otherwise. It is a binary variable and we have⎢I⎥×⎢J⎥many such decision variables in our problem.

Objective function

Suppose that there is a cost value, c(ij), associated with the assignment of order 𝑗 to courier 𝑖. You can think of the cost as an aggregate value that encompasses how good the assignment is in terms of customer and partner service and network efficiency. The lower the cost value the better the assignment is. Then, our objective function is to minimise the total cost of assignment, f(x), which is the sum of individual costs over all accepted courier-order pairs (i.e x(ij) = 1):

Constraints

We have two sets of constraints: (1) Each order has to be assigned to exactly one courier (2) A courier can be assigned to at most one order or not assigned at all.

In the first constraint set, we create an equation for each order 𝑗 (that is how we read the expression after the comma). The sum of the assignments associated with order 𝑗 must be one (we represent the summation with sigma over the courier set I). That is how we include the requirement that each order has to be assigned to exactly one courier in our mathematical model. In the second constraint set, we create an inequality for each courier 𝑖 that the sum of the assignments for courier i must be at most one. That is, it is feasible to allow some couriers to be unassigned.

Mathematical model

Having defined all parts of our model, we can now write it all together as shown below. By convention, we first state the objective function, then our constraints which our decisions are “subject to”.

Since the objective function and the constraints are linear functions, and the decision variables are binary (hence integer), this model is in the class of Integer Linear Program. It is also a Mixed-Integer Linear Program (MILP) which allows continuous variables in the problem although we do not have any.

Optimal solution

When we fix each decision variable to a particular value, the set of those values forms a solution. If this solution satisfies all the constraints, then we call it a feasible solution to our problem. We are only interested in feasible solutions to our problem and a feasible solution that achieves the minimum (or maximum depending on the objective) objective value is an optimal solution to our problem (optimal solution may not be unique as there can be multiple solutions having the same objective function value). In our courier assignment problem, we would like to find the set of order-courier pairs that gives the minimum total cost value.

Optimisation methods

Methods that can guarantee finding an optimal solution to the problem are called exact methods for that problem. A well-known and commonly applied exact method to solve MILP problems is the Branch-and-Bound (B&B) method. It is a “smart” enumeration method that solves a series of relaxed versions of the problem (where some or all of the integrality requirements of the decision variables are dropped). All of the mathematical optimisation softwares I have used so far employ some form of a B&B method as the underlying solution procedure.

Optimisation softwares (solvers)

There are quite a few commercial or open source solvers that can be used to solve such problems. Gurobi, IBM ILOG Cplex, FICO Xpress, MOSEK are well known commercial ones whereas GLPK, CBC, SCIP, HiGHs are some examples of open-source solvers (not all of them allow non-academic purposes though).

These solvers use more or less standardised file formats (e.g. ‘.lp’ or ‘.mps’) to get the mathematical model as an input. Applications can write the mathematical model to one of those files and then pass the file to a solver to solve a given problem. Many of those solvers also provide their own APIs in different programming languages for the applications to build the models easily and solve the problems directly in the same process. Additionally, there are solver independent modelling languages or frameworks such as PuLP, Pyomo, Google OR-Tools, JuMP that can be used to construct the model and then to choose any of the supported solvers. Those are very useful when you do not want to depend on a particular solver in your application.

Conclusions

The courier assignment problem is a major operational decision optimisation problem in the food delivery industry. We presented a highly simplified version of this problem, formulated it as an MILP problem and briefly mentioned the state-of-the-art method and the softwares.

However, the actual problem is much larger and more complex. The system state changes as couriers move, new orders come, orders are picked up or delivered. Not every courier can deliver every order. At peak times, multiple orders need to be assigned to a single courier and the order of the deliveries need to be decided. Finding optimal solutions may not always be practical given the restricted time that an algorithm can take to solve the problems. The powerful methods that OR provides should be tailored to the problem at hand and the parameters of the developed algorithms need to be fine-tuned by means of carefully designed experiments.

As a team of Operations Research scientists, we own our developed algorithms, maintain them, and improve them by research and experimentation. We aim to create a positive impact on our business, our stakeholders, and the whole food delivery market. We care about having scientific rigour in our solutions and being meticulous in what we develop. We are also excited by the other domains of our delivery network that could also benefit from the OR models and solution approaches.

If you want to join our excitement, Just Eat Takeaway.com is hiring! Want to come work with us? Apply today.