Equitable Routes Allocation - Optimization Model
This paper presents an optimization model that helps to ensure that pick orders in a warehouse are allocated fairly and evenly among pickers. The paper begins by explaining the need for such an optimization model. It then presents a mathematical model of the optimization problem and solves it using the PuLP library in Python.
Introduction
In warehouses, products are picked according to resevered orders or demand. Similarly, in the retail sector, products are picked according to work orders created for stores and e-commerce operations. For example, X company’s employees plan the products to be picked for its stores in shopping malls, streets, and so on, taking into account the products’ sales performance, climate, and customer demographic characteristics.
While It would be planned to send to Y store 5 units of product K and 3 units of product L, it could be planned to send to Z store 2 units of product K, 1 unit of product L, and 4 units of product M.
The example is only for two stores, but a company may have hundreds of stores and thousands of products to plan. It is important to keep this scale in mind when planning. The planned store-product pairs are analyzed with the location and stock quantities in the company’s warehouse. As a result, a work order is sent to the warehouse operations team in order to be picked the products for each store.
This work order contains information on how much of which product will be picked from which warehouse location for which store.
Work orders can be generated using an analytical approach, such as an algorithm (heuristic, mathematical model, etc.), or they can be generated using a rule-based approach (maximum quantity, maximum distance, etc.).
In summary, the process usually flows from the planning team to the analytical teams and then to the warehouse operations. The warehouse operations manager needs to find a way to fairly allocate the work orders created by the analytical unit to the pickers. This is a challenging problem, as it needs to consider both fairness and efficiency.
The Problem Definition
Work orders generated by analytical employees contain the number of products to be picked and their volumes.
A work order, also known as a route, is a list of locations in the warehouse that the picker must visit to pick the planned products for the target stores.
After completing a work order, the picker delivers the picked products to the packing area and then takes the next work order, or route, and continues picking. This is how pickers complete their daily work.
Warehouse operations management aims to take a fair or balanced approach when assigning work orders to pickers. This is because they want all pickers to have an equal workload in terms of the total volume (desi) and number of routes they have completed at the end of the day.
In this context, let’s assume that the company’s warehouse operations management needs a balanced route (work order) assignment model from the Analytical department that takes into account these two goals.
Balanced Route Assignment Mathematical Model
The goal is to create a model that meets this need using an example data set. The data set used by the model includes 74 routes with a total of 5,177 products to be picked. Suppose the warehouse operations team has 8 pickers available to pick all the products. The question here is, is it possible to assign the 74 routes to 8 pickers (operators) in a fair way? That is, is there a allocation such that the total product volume and the total number of routes falling to each picker are balanced?
To achieve this, it is necessary to identify the clusters. Here, the clusters are defined as:
Operator: A picker
Route: A set of products to be picked
Total volume: The total volume of products in a route
Total product quantity: The total number of products in a route
The optimization model to be established will be modeled on these clusters.
The first two parameters used in the model are the number of products to be picked in each route (mt) and the desi quantity (dt). The average desi quantity per operator (Davg) and the average number of routes per operator (Tavg), which will help with the balanced assignment, are also input parameters to the model. The M1, M2, and M3 parameters, which will help with the solution of the model and help to determine the threshold value between desi and number of routes in the balanced assignment, are also included in the model.
The balanced route assignment model uses three types of decision variables. The first is a binary decision variable that determines whether an operator is assigned to a route. The other two variables determine the contribution of the average desi and average number of routes per operator. For example, consider a model with 3 routes and 2 operators. The average number of routes per operator is 1.5, but a route cannot be divided into two. Therefore, this decision variable is needed to assign 1 route to one operator and 2 routes to the other. Otherwise, the model will be infeasible. A similar example can be given for desi.
The objective function of the optimization model is defined as a maximization problem to ensure that all products in the routes are picked. The average desi and number of routes per operator are maximized by adding the M1 and M2 parameters to the objective function. In other words, this ensures that the assignment is close to the average desi amount and the average number of routes per operator.
The first constraint of the model specifies that each route must be assigned to a single operator. The second and third constraints help the model make an assignment that is close to the average desi and the average number of routes per operator, respectively. In other words, these two constraints allow the model to take values around the average values when making the assignment. For example, if the average number of routes per operator is determined to be 5.4, some operators may be assigned 5 routes, some may be assigned 6 routes, and some may be assigned 4 routes. This will vary depending on the data. The fifth constraint specifies the range and sign constraints for the decision variables.
Solving the Model with Python PuLP
All of Python PuLP codes is presented below to solve the model.
import pandas as pd
from pulp import *
# operator and route data
operator_list=list(range(1,9))
route_list=list(range(1,75))
route_desi=[188,199,164,199,199,188,188,188,210,188,188,155,144,199,210,210,188,199,199,199,210,177,188,199,199,199,210,210,210,199,199,188,210,210,199,199,188,199,199,210,188,166,210,210,210,210,210,210,199,199,210,210,210,199,210,210,166,188,199,177,199,177,210,199,188,188,188,188,210,199,199,210,177,164]
quantity=[18,23,17,33,52,39,37,29,38,48,15,6,6,7,6,13,28,17,91,128,99,79,63,31,40,29,41,52,57,28,74,134,156,160,132,142,154,161,133,152,77,71,59,62,63,81,76,68,60,96,68,24,56,89,51,104,57,118,67,82,91,72,109,66,82,120,45,120,39,63,81,120,69,103]
# operator (pickers) df
df_operator = pd.DataFrame(operator_list, columns=['operator'], index =list(range(len(operator_list))))
# route df
route_info = pd.DataFrame(zip(route_list,route_desi,quantity),columns=['route','desi','quantity']
, index =list(range(len(operator_list),len(route_list)+len(operator_list))))
# decision pairs : route-operator
df_operator['key'] = 1
route_info['key'] = 1
model_df = pd.merge(df_operator, route_info, on ='key').drop("key", 1)
Tavg=len(route_list)/len(operator_list)
Davg=sum(route_desi)/len(operator_list)
print('average number of routes per operator (Tavg) : ', Tavg)
print('average desi of routes per operator (Davg) : ', Davg)
print('total picked quantities : ', sum(quantity))
#### optimitaion model is building....
# parameters of model
M1=10000
M2=10000
M3=0.53
# decision variables
x=LpVariable.dicts("assign",[(i,j) for i in operator_list for j in route_list], cat='Binary')
y=LpVariable("parameter_avg_desi", lowBound=0.5, upBound=0.99, cat='Continuous')
z=LpVariable("parameter_avg_tur", lowBound=0.5, upBound=0.99, cat='Continuous')
# model and objective function
model=LpProblem("Max Amount",LpMaximize)
model += M1*y+M2*z+(lpSum([x[(i,j)]*model_df[(model_df['operator']==i) & (model_df['route']==j)].iloc[0,3] for i in operator_list for j in route_list]))
# each route should be assigned a operator
for j in route_list:
model += (lpSum([x[(i,j)] for i in operator_list]))>=1
model += (lpSum([x[(i,j)] for i in operator_list]))<=1
# considering average desi and average number of routes
for i in operator_list:
model += (lpSum([x[(i,j)] for j in route_list])) >=Tavg*z
model += (lpSum([x[(i,j)]*model_df[(model_df['operator']==i) & (model_df['route']==j)].iloc[0,2] for j in route_list])) >=Davg*y
# deteriming the priority among volume (desi) and the number of routes
model+=z<=M3*y
# model is solving check the optimal or infeasible
model.solve()
print("solved model : {}".format(LpStatus[model.status]))
print("the value of objective function = ", value(model.objective))
## results
op_list=[]
route_la=[]
assign_infoa=[]
for i in operator_list:
for j in route_list:
if x[(i,j)].value()>0:
op_list.append(i)
route_la.append(j)
assign_infoa.append(x[(i,j)].value())
df_result2=pd.DataFrame(zip(op_list,route_la,assign_infoa), columns=['operator','route','assign_flag'])
# results df
result_summary=model_df.merge(df_result2, on=['operator','route'], how='inner')
df_result_lv=result_summary[['operator','desi','quantity','assign_flag']].groupby('operator').sum()
df_result_lv.reset_index(inplace=True)
df_result_lvModel results are showed below df.
Based on these results, it is possible to see that the operators have a balanced volume (desi) and number of routes assigned to them.
from matplotlib import pyplot as plt
fig, ax = plt.subplots(figsize=(9,5))
plt.rcParams['font.size'] = 12
x_axis = df_sonuc['operator'].to_list()
y_axis = df_sonuc['desi'].to_list()
plt.bar(x_axis, y_axis, color='paleturquoise', align='edge', width=0.6)
plt.xlabel("Operator", size=12)
plt.ylabel("Total Desi", size=12)
for index in range(len(x_axis)):
ax.text(x_axis[index], y_axis[index], y_axis[index])
fig, ax = plt.subplots(figsize=(9,5))
plt.rcParams['font.size'] = 12
x_axis = df_sonuc['operator'].to_list()
y_axis = df_sonuc['assign_flag'].to_list()
plt.bar(x_axis, y_axis, color='bisque', align='edge', width=0.6)
plt.xlabel("Operator", size=12)
plt.ylabel("Total Number of Routes", size=12)
for index in range(len(x_axis)):
ax.text(x_axis[index], y_axis[index], y_axis[index])
plt.show()
As a result, a decision model that will meet the needs of the warehouse operations manager has been established. By matching the route numbers assigned to the operators, the manager can now plan his work. It should be noted that model parameters, decision variables, and constraints may vary from company to company. Here, an answer was sought to the question of how to establish a balanced assignment model with a simple approach using an example dataset. I would like to point out that this balanced job assignment model, which is made for warehouse operations, can be a source of inspiration for job assignment optimization problems in other sectors.
