15 October 2021

Linear Optimization – Part II

In the first article (Optimization – Part I), we introduced the concept of Optimization: what is an optimization problem, how to build an optimization model, and how it can be implemented, using Google OR-Tools. In order to show the different stages of this process, we have created a fictitious scenario based on a typical optimization problem: The Transportation Problem.

The purpose of this article is to present to you a real-life use case and describe how it could be solved, building and implementing an optimization model.

Real-Life Use Case: How to optimize a warehouse?

The main goal of the scenario presented to us was to find an answer for one of the most typical challenges of any warehouse: optimize its available space. The way how products are distributed throughout the warehouse has some impact on the travel time spent by employees when they need to go to the shelves to get some products for an order requested by a customer. Having this in mind, we were asked for a solution that met the following requirements:

1. Propose the best location for a given product received by the warehouse, in order to minimize the travel time spent by employees in accessing products, from the main aisle (reference point) to the shelves location;

2. Redistribute the products so that those belonging to the same depositor would be located close to each other.

Figure 1 – Simplified warehouse layout

 

Figure 1 shows the simplified warehouse layout. The aisle where forklifts move on is the main one and the squares are the shelves that store products, seen from the top. If we do not consider the heights of each shelf, we can say, in simple terms, that the best locations for any product are the shelves closest to the main aisle.

 

How to redistribute the products through the warehouse?

The approach followed when solving the warehouse optimization problem was to bring it closer to the typical Transportation Problem. So, the solution would propose the best location for a given product, taking into account the following criteria:

  • Product stock rotation: average time, in months, needed to convert a product’s stock into orders. The stock rotation is used to compute the frequency of requesting a product in an order, by doing its reverse (1/rotation). Using stock rotation, we were able to decide which products should occupy the best locations: the most requested products are those that remain, in the warehouse, for a short period of time, so these will be the candidates to occupy the best shelves available in the warehouse because this warehouse receives different products from different depositors and not all of them fit in the shelves close to the main aisle.
  • Time from the main aisle to the product’s location:e., the time spent getting the product from the warehouse main aisle to the shelf where the product is stored.
  • Maximum capacity of each shelf: the number of products that fit on a shelf. This is equal to the sum of the maximum capacity of all its racks.
  • Number of products to be allocated in the warehouse: e., the number of products received by the warehouse and that have to be put away.
  • Affinity between products: allocating products from the same depositor on racks close to each other.

Optimization Model – Formula I [2]

The aforementioned criteria were used to build the optimization model that, mathematically, describes the warehouse optimization problem. For this, it was necessary to identify the decision variables of the problem, their constraints and the objective function to optimize.

Decision Variables:

Xij = number of products i allocated on shelf j.

Constraints:

1. Quantity of each type of product to be allocated in the warehouse: after redistributing the products throughout the warehouse, the total number of products i allocated in shelf j must be equal to the total quantity of products i to be stored in the warehouse.

Pi = number of products i to be allocated.

2. Maximum quantity of products that can be allocated on each shelf: the number of products i assigned to shelf j should not exceed its maximum capacity of storage.

Cap= capacity of shelf j.

 

3. Minimum quantity of products: the number of products i to put away on shelf j should be a positive integer equal to or greater than zero.

Objective Function:

tj = time from shelf j to the main aisle.

ri = stock rotation of product i.

Aj = set of products allocated on shelf j.

Rik = weight assigned to the relationship between products i and k.

The objective function has 3 sums. The first term computes the cost of assigning any product i to shelf j. This function will be used to identify how products should be spread among shelves, in order to minimize the total time from them to the main aisle and, at the same time, ensure that products with lower stock rotation occupy the best warehouse spots. The second and third terms represent the 2 types of pairwise relationships among products [2]:

  • Affinity between allocated and unallocated products (2nd summation):  Assigning a product i to a shelf where product j is already stored in, knowing that both belong to the same depositor, adds a “bonus” to the formula, if both are placed on the same shelf, minimizing, even more, the total value of the objective function.
  • Affinity between unallocated products (3rd summation): Assigning two products i and k, received by the warehouse, knowing that both belong to the same depositor, adds a “bonus”  to the formula, if both are placed on the same shelf, minimizing, even more, the total value of the objective function.

Problems with Optimization Model – Formula I

A large number of decision variables

Implementing the formula described in the previous section would lead to the calculation of a large number of decision variables. To reduce the number of existing decision variables in the model, we divided both products and shelves into 3 categories: A, B, and C. This means that products from category A represent those that are requested the most, while products from category C represent those that are requested less frequently, so they remain in the warehouse for a longer period of time. In a similar way, we divided shelves into 3 categories, as illustrated in Figure 2. Using the same analogy as before, shelves classified as category A are the shelves closest to the main aisle and those in category C are the shelves furthest from this corridor. Having the products and shelves classified as ABC, the idea would be to assign products of type A, B, and C to shelves of type A, B, and C, respectively, restricting the search universe for free shelves.

 

Figure 2 – Simplified warehouse layout divided into ABC categories

 

Quadratic term of objective function

The 3rd summation of the objective function contains the multiplication of two decision variables, making it a quadratic term and, therefore, the objective function becomes a quadratic programming problem. Many open-source optimization libraries are available online, nevertheless, such libraries are not suitable for solving quadratic programming problems, but rather for solving linear programming problems. Many of the solvers used in quadratic programming are commercial, so they require a license to use them. Some of these solvers offer a trial period which means they can be used for free, but only for a short period of time. Facing this challenge leads us to apply a workaround: transform the quadratic function into a linear function, using, for this purpose, the McCormick Envelopes method.

McCormick Envelopes

This method is often used to solve Mixed-Integer Non-Linear Programming problems [1]. The idea is to replace the multiplication of 2 variables with a new one and add 4 new constraints that establish the minimum and maximum values that this new variable can have, based on the minimum and maximum bounds established for each of the 2 variables involved in the multiplication. Let’s consider as an example, the multiplication of 2 variables x and y that can be replaced by a new variable w: xy = w. Constraints defined for this new variable w are inequalities expressed as follows:

Optimization Model – Formula II

Applying the aforementioned McCormick Envelopes method to our optimization problem, we obtain the following model:

Decision Variables:

Xij = number of products i allocated in shelf j.

Wijkj = represents the multiplication: Xij Xkj

 

Objective Function:

Tj = time from shelf j to the main aisle

Ri = stock rotation of product i

Aj = set of products allocated on shelf j.

Rik = weight assigned to the relationship between products i and k.

 

Constraints:

 

How to implement the warehouse optimization model with Google OR-Tools?

This section describes how the optimization model (Formula II) was implemented with Google OR-Tools, using, as an example, a simplified scenario of the warehouse optimization problem, showed in Figure 3. In this scenario, the warehouse has to allocate 3 boxes of product P1, 2 boxes of product P2 and 2 boxes of product P4 in 3 shelves with free storage capacity: NN.23, NN.25 and NN.27. All products and shelves belong to category A. Note that NN.25 contains one box of product P3 previously allocated to it.

Figure 3 – Simplified scenario of the warehouse optimization problem

 

In the implementation of the optimization model, 5 classes were created to represent the problem:

  • Product: products received by the warehouse. This class contains data such as the product’s name, stock rotation, quantity to allocate, as well as the depositor and the category it belongs to.
  • Location: shelves where products are stored in. This class contains data such as the shelf’s name, time from shelf to the main aisle, category, maximum capacity, free storage capacity, and list of products already stored on that shelf.
  • Cost: cost of storing a product i on a shelf j. The value of this cost is given by:
  • Allocated and Unallocated Products Relationship: the affinity between allocated and unallocated products. This class contains an attribute called weight that can be 0 or 10 (configurable value). If a product is placed on a shelf that contains at least one product from the same depositor, the weight variable is equal to 10, otherwise, it is 0.
  • Unallocated Products Relationship: the affinity between two unallocated products. This class contains an attribute called weight that can be 0 or 1 (configurable value). If two unallocated products of the same depositor are placed on the same shelf, the weight variable is equal to 1, otherwise, it is 0.

The steps followed on the optimization model implementation are presented as below:

1. Import the required libraries

Figure 4 –  Import the Google OR-Tools libraries

 

2. Create and instantiate the data model with the following information:

  • Cost of assigning each product (P1, P2 and P4) to each shelf (NN.23, NN.25 and NN.27)

Figure 5 – Function to create the Data Model and Costs of assigning each product to each shelf

 

  • Affinity between each unallocated product (P1, P2 and P4) and each allocated product already stored on each shelf (NN.23, NN.25 and NN.27). In this example, shelf NN.25 is the only one having allocated products (P3), this means that the affinity between products is calculated only for the following pairwise of products: P1 and P3; P2 and P3 and P4 and P3. As P2 and P3 belong to the same depositor (X), the weight value is only equal to 10 for this combination of products.

Figure 6 – Affinity between Allocated and Unallocated Products

 

  • Affinity between unallocated products from the same depositor (P1 and P4). These two products are both from depositor Z.

 

Figure 7 Affinity between Unallocated Products

 

  • Products to allocate and Shelves with free storage capacity

 

Figure 8 – Products to Allocate and Shelves with Free Storage Capacity

 

3. Declare the solver

Figure 9 – Declare the solver

 

4. Create the decision variables

Figure 10 – Decision Variables

 

5. Define the constraints

6. Define the objective function

7. Call the solver and display the results

Figure 11 – Result suggested by Optimizer

 

Figure 12 – Solution suggested by Optimizer

 

Figure 14 shows the suggestion returned by the optimizer, which involves allocating 3 boxes of product P1 (the one ordered the most) in shelf NN.23 (the one closest to the main aisle). Regarding product P2, this one should be assigned to shelf NN.25, where we can find a box of product P3 (also from depositor X, like P2). For product P4, the optimizer suggests the single free rack available in shelf NN.23 (the same shelf where P1 was allocated since both belong to depositor Z) and also the single free rack available in shelf NN.25 (the best spot available after assigning P2 to this shelf). In this formula, the affinity among products has an influence on how products are spread by the shelves, therefore different weight values would cause a different distribution of products by the warehouse.

In summary, in this article, we have shown, not only an optimization problem applied to a real-life use case, but also how it could be solved by building and implementing an optimization model, using Google OR-Tools.

Bibliography

[1] https://optimization.mccormick.northwestern.edu/index.php/McCormick_envelopes

[2] Li, Jiaxi; Moghaddam, Mohsen; Nof, Shimon Y. (2015). Dynamic storage assignment with product affinity and ABC classification—a case study, páginas 2 – 6.

   
   
    Sabrina Masson                       
     AI Consultant                  

 

Blog