IEEE Robotics & Automation Magazine - June 2023 - 38

without improved solutions. r ()) , s, and a
are the reward function, state, and action
of Q-learning, respectively.
In [30], the perturbation strength
is determined according to perturbation
iteration P and perturbation attempt
P .) The authors define P with three
parameters,
i.e., a constant coefficient,
the number of batches, and the number
of nonimproving iterations. They set
.
P 50=)
In addition, only one perturbation
is used in [30]. A large P may lead to
recovering a random restart, and a small
one can explore a few new solutions
only. P is proper within 20 according to
our pilot runs. Therefore, in this work,
{, ,, },
PP {, ,,, ,}.
addition, two perturbation types are designed, and Pu is used to
determine the type of perturbation, i.e., P {, }.01=u
!!f12 20
N20
==}
)
05 10 15 20 25
"
THEREFORE, SIMILAR
ORDERS CAN BE
COMBINED INTO A
BATCH AND PICKED
SIMULTANEOUSLY IN A
PICKING ROUND, THUS
IMPROVING THE PICKING
EFFICIENCY.
„
In
BATCHING ALGORITHM
The initial solution of RAILS is obtained by a batching algorithm.
A dynamic time window is first used to deal with fluctuating
orders. Let
s nnl .Nq
=R !
In a time window (,
tt tw+ ),
if s 1 C /,2 orders are waiting to be processed in the next
time window. If /2##s
one batch that is allocated to a picker based on the earliest
picking completion time. If
CC, the orders are combined into
C ,1 s the orders are combined
into different batches according to a heuristic rule introduced
as follows. Then batches formed are assigned to pickers
based on the earliest picking completion time. In the third
condition, if the number of items of the remaining orders
except for the batched orders is less than /,C 2 they are processed
in the next time window.
The most frequently purchased goods often are stored in the
same picking aisles. Therefore, similar orders can be combined
into a batch and picked simultaneously in a picking round,
thus improving the picking efficiency. When the third condition
is met, a heuristic rule HSL is proposed to group orders
into batches by the seed algorithm [31] based on the similarity
among orders. The seed algorithm consists of seed order
selection and order addition. This article chooses the order m
with the earliest arrival time as the seed order. According to
Ho et al. [31], the order can be effectively combined by taking
the similarity of picking aisles of orders as the standard for
order addition. The log-likelihood similarity is often used in
recommender systems to reveal the correlation of items that are
purchased by different customers [32]. It can effectively extract
information between two items. In addition, the picking priority
of orders with a close due date should be higher than other
orders. Orders with similar due dates should be combined into
the same batch for picking as far as possible. Therefore, the
comprehensive similarity between orders m and n is as follows:
h =
mn
22 2|| |31 2
-n
()
Dd
38
IEEE ROBOTICS & AUTOMATION MAGAZINE JUNE 2023
(10)
+Snm log
|1 =Smn
+Snm log
The larger the value of hmn ,
the
higher the similarity between the two
orders, and the greater the probability
that the two orders are allocated to
a batch. The most correlated orders
are grouped into a batch to decrease
the picking route.
of order n. ,,
dn is the due date
|| and 3| are the row
12
entropy, column entropy, and matrix
entropy, respectively. The three entropies
contain the possible information
about picking aisles between orders.
Let Smn be the number of same picking
aisles of orders m and n,
Sm be
the number of unique picking aisles
of order m,
Sn be
DS SS Snm nm
SS
S
mn
+
mn
12
,,
the number of
unique picking aisles of order n, and Snm be the number
of picking aisles that neither m nor n has. In addition,
,
=+ ++ || and 3| can be obtained
by the following formulas:
loglog
mn + m
SS
S
|2 =Smn loglog
SS
S
mn
mn + n
SS
S
+
|3=+ ++ (13)
Note that if
Smn loglog
Smn
D
Sm
,, ,
D
S
m
S loglog Snm
n
n
D
S
,
Snm
D
SS Smn mn or Snm 0= we set a near-zero positive
number to represent it. The pseudocode of the batching
algorithm is shown in Algorithm 2.
LOCAL SEARCH PHASE
RAILS's local search operations, as shown in Tables 3
and 4, are performed in a local search phase. A shift operation
is performed first to shift orders to different batches.
Then, a swap operation is performed that can still find possible
order combinations when the picker is fully loaded.
Order shift and order swap will create new batches. Both
play important roles in minimizing order tardiness. In addition,
batch swap and batch shift are performed when there
are still orders delayed.
After an operation is executed, the move is accepted if the
values of F or g(z) are less than or equal to their historical
optimal values. Note that g(z) is the sum of the total picking
time and tardiness with the weighting coefficient. Meanwhile,
a delta-evaluation operator is designed for neighborhood
searching. In it, we only perform the fitness function of the
different parts after a move is executed. Hence, it spends much
less computational burden than that of evaluating a complete
solution.
+Sn
mnm
nm
+Sm
nnm
nm
SS
S
n
mn + n
+S log
m
+
SS
S
m
mn + m
+S log
n
SS
S
+
SS
S
nnm
n
(11)
mnm
m
(12)
IEEE Robotics & Automation Magazine - June 2023

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2023
