Customer Check-Out Counters and Operators Schedule Optimization
Problem Statement
The supermarket has 10 checkout counters, with 6 of them being operated. Currently these 6 checkout counters are being operated by employees that have low skill. The supermarket has 3 types of employees available to operate: highly skilled, skilled, and low skill. They have 15 of each type of employee available. Each type of employee can check out 30, 25, and 20 customers per 2-hour time interval based on their skill level. The management has identified that by every extra customer they checkout, they expect a profit of 2 USD. The management wants to (i) identify the demand of the checkout counters in various time intervals during the day [i.e, 8AM to 10AM, 10AM to 12AM, 12AM to 2PM, 2PM to 4PM, 4PM to 6PM and 6PM to 8PM] and to (ii) optimize the number of checkout counters open, and the skill level of the operators to manage the customers efficiently.
Solution Outline
Let’s divide the problem into 2 stages. Stage I -Identifying the customer checkout demand in different time intervals mentioned in the problem. Stage II -Checkout counters optimization and the operators schedule.
Stage I -Identifying the customer checkout demand in different time intervals mentioned in the problem.
There are many ways to identify the customer demand such as bar code scanning, manual counting, etc. Let us assume that the demand of the customers is being monitored by a security camera at the checkout counters. I would like to automate this process by using Deep Learning object identification algorithm in Python.
Let’s Dive into Deep Learning
Let’s start simply by taking a small 10 minutes Mr. Bean cartoon episode and try to find the run time of Mr. Bean in the total video. This work can be scalable to a higher level to find customer demand and their wait times.
First, the most important thing to do in a video classification is to break the video into images as video is nothing but image snaps. By doing this, we are converting the video classification problem into an image classification problem.
count = 0
videoFile = "Train.mp4"#capturing the video from the given path
cap = cv2.VideoCapture(videoFile)
frameRate = cap.get(5) #frame rate
x=1
while(cap.isOpened()):
frameId = cap.get(1) #current frame number
ret, frame = cap.read()
if (ret != True):
break
if (frameId % math.floor(frameRate) == 0):
filename ="Mrframe%d.jpg" % count;count+=1
cv2.imwrite(filename, frame)
cap.release()
print ("Done!")
The python code above reads and breaks the video into images and saves them. Next comes the brute force approach of labelling a few images manually with 1 for Mr Bean presence and 0 for absence for training our model. Now, our training .csv file is ready.
# Read the labelled csv file
data = pd.read_csv('Mrmapping.csv')
data.head() # printing first five rows of the file# Read the labelled images
X = [ ] # creating an empty array
for img_name in data.Image_ID:
img = plt.imread('' + img_name)
X.append(img) # storing each image in array X
X = np.array(X) # converting list to array
Now we have the labelled images with their labels. Before building our model, lets preprocess it.
from keras.models import Sequential
from keras.applications.vgg16 import VGG16
from keras.layers import Dense, InputLayer, Dropoutbase_model = VGG16(weights='imagenet', include_top=False, input_shape=(224, 224, 3)) # include_top=False to remove the top layerX_train = base_model.predict(X_train)
X_valid = base_model.predict(X_valid)
X_train.shape, X_valid.shape# converting to 1-D
X_train = X_train.reshape(125, 7*7*512)
X_valid = X_valid.reshape(54, 7*7*512)# centering the data
train = X_train/X_train.max()
X_valid = X_valid/X_train.max()
Next comes the building, compiling and training of the model.
# 1. Building the model
model = Sequential()
model.add(InputLayer((7*7*512,))) # input layer
model.add(Dense(units=1024, activation='sigmoid')) # hidden layer
model.add(Dense(2, activation='softmax')) # output layer# 2. Compiling the model
model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])# 3. Training the model
model.fit(train, y_train, epochs=100, validation_data=(X_valid, y_valid))
Our model performed with 94% of accuracy on this video. Now, let’s calculate the Mr Bean’s run time.
# Predicting the Images
predictions = model.predict_classes(test_image)# Run Time Output
print("The screen time of Mr Bean is", predictions[predictions==1].shape[0], "seconds")
print("The screen time of others is", predictions[predictions==0].shape[0], "seconds")
So, this is how we can calculate the runtime of Mr Bean in a given video and this work can be scalable to find the customer checkout demand and their wait times in different time intervals.
Complete Python Code hyperlinked.
Let’s say by using this algorithm, we found the customer checkout demand as 8AM to 10AM — 100 No.s, 10AM to 12AM — 110 No.s, 12AM to 2PM — 120 No.s, 2PM to 4PM — 130 No.s, 4PM to 6PM — 120 No.s and 6PM to 8PM — 110 No.s.
Stage II -Checkout counters optimization and the operators schedule.
Now, let’s start our mathematical optimization model and then we will move to a typical spreadsheet modelling. A typical model contains 1. Input Parameters, 2. Decision Variables, 3. Objective Function and 4. Constraints.
- Input Parameters
(i) Di = Customers demand in ‘ i ’ time intervals, where i =[1,2,3,4,5,6], [i.e, 8AM to 10AM, 10AM to 12AM, 12AM to 2PM, 2PM to 4PM, 4PM to 6PM and 6PM to 8PM]
(ii) Rj= Counter operators per hour rate, where ‘ j ’ = [1,2,3], [i.e, High Skilled, Skilled, Low Skilled]
(iii) Tj = Operators average checkout times productivity/capability, where ‘ j ’ = [1,2,3], [i.e, High Skilled, Skilled, Low Skilled]
(iv) M = Monetary value for one extra customer checkout in the time interval
(v) COi = Current number of operators working (Currently only low skilled) in ‘ i ’ time intervals, where i =[1,2,3,4,5,6], [i.e, 8AM to 10AM, 10AM to 12AM, 12AM to 2PM, 2PM to 4PM, 4PM to 6PM and 6PM to 8PM]
(vi) CCi = Current number of counters operating in ‘ i ’ time intervals, where i =[1,2,3,4,5,6], [i.e, 8AM to 10AM, 10AM to 12AM, 12AM to 2PM, 2PM to 4PM, 4PM to 6PM and 6PM to 8PM]
2. Decision Variables
(i) Ci = No. of counters to operate in ‘ i ’ time intervals, where i =[1,2,3,4,5,6], [i.e, 8AM to 10AM, 10AM to 12AM, 12AM to 2PM, 2PM to 4PM, 4PM to 6PM and 6PM to 8PM]
(ii) Oij = No. of ‘ j ’ type operators to be deployed in ‘ i ’ time intervals, where i =[1,2,3,4,5,6], [i.e, 8AM to 10AM, 10AM to 12AM, 12AM to 2PM, 2PM to 4PM, 4PM to 6PM and 6PM to 8PM], ‘ j ’ = [1,2,3], [i.e, High Skilled, Skilled, Low Skilled]
3. Objective Function
Operator cost saving = Σ COi*2*R3
Monetary value gained or lost in ‘ i ’ time interval = (Σ Oij*Tj — Di)*M
Maximize total cost savings = Σi COi*2*R3 +Σi (Σj Oij*Tj — Di)*M
4. Constraints
(i) Ci ≤ 10
(ii) Σj Oij = Ci
(iii) Σi Oij ≤ 15
(iv) Σj Oij*Tj ≥ Di
(v) Ci, Oij Integers and ≥ 0
The above mathematical optimization model helps in finding the optimal number of counters to operate in different time intervals with the operators schedule.
Now, let us see the spreadsheet modelling and the result.
After creating the spreadsheet modelling as above, by using MS Solver add in MS Excel, I have optimized our objective function and the result is, C1 = 10 counters in time interval 1, C2 = 10, C3 = 10, C4 = 7, C5 = 4, C6 = 4 similarly and O11 = 2 High skilled operators in time interval 1, O12 = 0, O13 = 8, O21 = 0, O22 = 3, O23 = 7, O31 = 0, O32 = 10, O33 = 0, O41 = 7, O42 = 0, O43 = 0, O51 = 4, O52 = 0, O53 = 0, O61 = 2, O62 = 2, O63 = 0 similarly.
By performing our optimization analysis, we can save 492 USD per day which is 0.18 Million a year which is not a less amount.
I would like to thank my friend Chris Chou for proofreading this content.
Python Code Reference
[1] Pulkit Sharma, Deep Learning Tutorial to Calculate the Screen Time of Actors in any Video (with Python codes) (2018), https://www.analyticsvidhya.com/blog/2018/09/deep-learning-video-classification-python/
