Optimizing Warehouse Efficiency: The Storage Location Assignment Problem

Photo by Adrian Sulyok on Unsplash

This article is part of a series about optimizing the placement of items in a warehouse with Python. Follow me for Part 2!

You can also read a slightly updated version of this article on my personal blog.

Table of Contents

1. Introduction
2. Warehouse Modeling
3. Solving the SLAP
4. References

Introduction

Warehouse managers face increasing pressures due to rising costs, evolving customer demands, shorter product lifecycles, and workforce turnover. Since order picking within a warehouse accounts for up to 50% of the expenses, reducing picking times is a critical lever to cut costs and streamline processes [1]. Shortening pick times can be achieved through improved picking strategies and efficient assignment of items to storage locations. In this post we want to explore how to enhance item-to-storage location assignments, starting with an overview of the underlying decision problem and diving into solutions.

Understanding the SLAP

The Storage Location Assignment Problem (SLAP) revolves around the allocation of products to storage locations. It depends on various factors, including warehouse characteristics, product types, and demand profiles. This problem shares similarities with the Quadratic Assignment Problem and is, therefore, NP-hard. We will see later what implications that brings for solving the problem. Mathematically, it can be expressed as follows:

Figure 1: MIP formulation of the SLAP [2]

Warehouse Modeling

To develop and compare solutions for SLAP, it’s crucial to find a way to represent a real warehouse. Consider Figure 2 for an example for how a real life warehouse could look like.

Figure 2: Conventional warehouse layout with two aisles and three racks

It is not hard to imagine a warehouse like this as a graph like we can see in Figure 3:

Figure 3: Graphical representation of the underlying graph

Toy Problem

For the rest of this post we will work with a small toy problem. Lets consider a warehouse with the following properties:

• one aisle
• two racks
• the aisles can be accessed from top and bottom
• every rack has three storage locations resulting in six storage locations in total

This will result in the follwing layout where the black tiles represent nodes that can be walked on and the blue tiles represent storage locations.

Warehouse layout

This results in the following distance matrix between the storage locations

Distance matrix

Solving the SLAP

Data Preperation

Finding item-to-storage location assignments requires historical order data. From this data, information such as item order frequencies or item affinity is calculated. For our toy problem it is sufficient to generate the data ourselves. In reality order data can be retrieved from a WMS or online sources like Kaggle.

First lets generate a item for every location in our small warehouse:

Now we can generate the affinity between the items. We set the maximum affinity to 9, that means the highest value two items can be ordered together is 9. Then we loop though all the items and randomly select a value for the affinity.

size = len(storage_locs)
product_pairs_frequency = np.zeros((size, size))
upper_bound = 9
for i in range(size):
    for j in range(size):
        if i == j: 
            product_pairs_frequency[i][j] = 0
        else:
            product_pairs_frequency[i][j] = random.randrange(0, upper_bound)

The item order frequency can now be determined by going through the product_pairs_frequency matrix for every item.

product_frequency = {}
for i in range(size):
    product_frequency[i] = product_pairs_frequency[i].sum()

Mixed Integer Programming

First let us consider the mixed integer programming formulation proposed in the beginning. The model can easily formulated like this:

import gurobipy as gp
from gurobipy import GRB

model = gp.Model("SLAP_PA")

# decision variables
y_i_j = {}
for i in products:
    for j in storage_locs: 
        y_i_j[i, j] = model.addVar(vtype=GRB.BINARY, name=f"Item{i}_at_Loc_{j}") 

# objective function

model.setObjective(gp.quicksum(y_i_j[h, j] * y_i_j[i, k] * dist_mat[j, k] * product_pairs_frequency[h, i] 
                               for h in products for i in products for j in storage_locs for k in storage_locs)),  GRB.MINIMIZE)

# constraints
for j in storage_locs: #storage_locs_new
    model.addConstr(gp.quicksum(y_i_j[i, j] for i in products) == 1, name=f"Location{i}_constraint")

for i in products:
    model.addConstr(gp.quicksum(y_i_j[i, j] for j in storage_locs) == 1, name=f"Item{j}_constraint")

model.optimize()

After the problem is solved we can print the solution:

# Print the optimal solution
if model.status == GRB.OPTIMAL:
    print("Optimal Solution Found:")
    for i in products:
        for j in storage_locs:
            if y_i_j[i, j].x > 0.5:  # Check if the variable is assigned to 1 (approximately)
                print(f"Item {i} stored at storage location {j}")
else:
    print("No optimal solution found.") 

This will result something like this (depending on the item affinity that is generated at random):

Example solution for the SLAP

When we check the affinity matrix for product 0 we can see that it was ordered eight times with product 1!

This looks promising but a warehouse with six storage locations isn’t very useful. When we try to solve this problem with larger warehouses we will quickly see what it means when a problem is NP-complete:

We can not solve large instances of this problem in a reasonable time. Solving this problem with our toy problem with only six locatios takes a few seconds. Solving it with ten locations already takes nine minutes. A model with eleven locations already takes almost one hour to solve! It is obvious that an optimal solution can not be computed in reasonable time.

Runtime of MIP model

Given the complexity of SLAP, solving it typically involves heuristics or metaheuristic search methods. Therefore in the next part of this series we will look into a genetic algorithm for solving the SLAP.

About Me

I’m a student passionate about the possibilities of using Operations Research and Machine Learning to improve logistics and supply chain processes.

If you have a similar problem let’s connect on Linkedin or shoot me a mail!

References

[1] R. de Koster, T. Le-Duc, and K. J. Roodbergen, “Design and control of warehouse order picking: A literature review,” European Journal of Operational Research, vol. 182, pp. 481–501, Oct. 2007.

[2] M. Kofler, A. Beham, S. Wagner, and M. Affenzeller, “Affinity based slotting in warehouses with dynamic order patterns,” in Topics in Intelligent Engineering and Informatics, pp. 123–143, Springer International Publishing, 2014.