I am trying to optimize the allocation of of products inside a fictive warehouse, having a predefined number of aisles (3
in the example code below) where products can be placed. For now, the only optimization criterion that I would like to impose in the objective function is:
- products that have been frequently part of the same order (i.e., people ordering product $A$ also ordered product $B$) should be placed in the same aisle
As input I have a list of historical orders (randomly created in the example), where each order is composed of one or more products/articles. Using the list I build a co-occurrence matrix, that shows the number of times two articles were part of the same order, for each pair of articles.
The following code (full of comments) shows how I implemented the model using Docplex (IBM Decision Optimization CPLEX Optimizer Modeling for Python):
from docplex.mp.model import Model
import numpy as np
import pandas as pd
import docplex
print(docplex.__version__)
# docplex version: 2.22.213
# Cplex version: 20.1.0.0
################## Clean and Prepare Data ##################
# number of (historical) orders containing one or more articles
num_orders = 50
# number of different articles (products) available
num_articles = 40
# number of records, i.e., couples (o, a) of order-article, meaning that the article a is part of order o
s = (250, 1)
# aisles of the warehouse, with respective capacity (maximum number of articles that can be placed in them)
aisles = {1: 15, 2: 17, 3: 20}
# building a dataframe from the input data
order_col = np.random.randint(low=1, high=num_orders, size=s)
arts_col = np.random.randint(low=1, high=num_articles, size=s)
temp = np.array([1]*s[0]).reshape(s)
cols = np.concatenate((order_col, arts_col, temp), axis=1)
df = pd.DataFrame(cols, columns=["ORDER_NUMBER", "ARTICLE_CODE", "TEMP"])
# missing articles due to randomness in building the "ARTICLE_CODE" column of df
missing_articles_randomness = set(range(1, num_articles+1)).difference(set(df["ARTICLE_CODE"]))
to_add = pd.DataFrame()
to_add["ORDER_NUMBER"] = df["ORDER_NUMBER"].iloc[:len(missing_articles_randomness)]
to_add["ARTICLE_CODE"] = list(missing_articles_randomness)
to_add["TEMP"] = 1
# they need to be appended to the dataframe so that the corresponding row and column shows up in the co-occurrence matrix
df = df.append(to_add, ignore_index=True)
# create the co-occurrence matrix
temp_count = df.pivot_table(index="ORDER_NUMBER", columns="ARTICLE_CODE",
values="TEMP", aggfunc="count").fillna(0)
coocc = temp_count.T.dot(temp_count)
np.fill_diagonal(coocc.values, 0)
coocc.head()
################## Create Optimization Model ##################
mdl = Model("coocc_v1")
R = range(1, num_articles+1)
id_1 = [(i, j) for i in R for j in R[i:]]
# binary variable indicating whether two articles are located in the same aisle
arts_same_aisle = mdl.binary_var_dict(id_1, name="asa")
id_2 = [(c, j) for c in aisles for j in R]
# binary variable indicating whether an article a is located in an aisle c
art_aisle = mdl.binary_var_dict(id_2, name="aa")
# each article can be placed in only one aisle
constr_1 = mdl.add_constraints([mdl.sum([art_aisle[c, j] for c in aisles]) == 1 for j in R])
# each aisle has a maximum capacity
constr_2 = mdl.add_constraints([mdl.sum([art_aisle[c, j] for j in R]) <= cap for c, cap in aisles.items()])
# definition of arts_same_aisle_i_j: 1 if article i and article j are in the same aisle, 0 otherwise
for i in R:
for j in R[i:]:
arts_same_aisle[(i, j)] = mdl.logical_or(*[mdl.logical_and(art_aisle[c, i] == 1, art_aisle[c, j] == 1) for c in aisles])
# the 'co-occurrence score', that is, positioning articles in the same aisle if they are frequently part of the same order
obj1 = mdl.sum([arts_same_aisle[i, j] * coocc.loc[i, j] for i in R for j in R[i:]])
# the goal is to maximize the objective function
mdl.maximize(obj1)
################## Model Solving ##################
solution = mdl.solve(log_output=True)
# Total (root+branch&cut) = 759.07 sec. (477653.82 ticks)
# integer optimal solution
# objective value: 393.0
sol_df = solution.as_df()
sol_df = sol_df.loc[sol_df["name"].str.startswith("aa")]
for n, i in zip(["aisle", "article"], [1, 2]):
sol_df[n] = sol_df["name"].apply(lambda x: x.split("_")[i])
s = sol_df.groupby("aisle")["article"].apply(list)
print(s)
which gives
aisle
1 [15, 26, 40]
2 [1, 2, 3, 4, 5, 6, 9, 14, 17, 18, 19, 20, 23, ...
3 [7, 8, 10, 11, 12, 13, 16, 21, 22, 24, 27, 30,...
Name: article, dtype: object
Unfortunately, the solving time explodes when the number of different articles or aisles increases, and I could not find a non-trivial reformulation of the model that significantly reduces the solving time of the problem.
Is there a way to reformulate the problem to make it usable in a real-life scenario, with thousands of articles and tens / few hundreds of aisles?