# A Two-Stage Path Planning Method for the Rearrangement Problem in Modular Puzzle-Based Storage System

Authors: Penghui Guo; Fei Xiao; Wanzhi Rui; Zhengrong Jia; Jin Xu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The modular puzzle-based storage system consists of multiple storage modules. The system has multiple input/output (IO) points which can simultaneously deal with multiple orders in one batch. When a batch of orders comes in advance, it is necessary to rearrange the items near each IO point to reduce the picking time of customers. To complete the rearrangement quickly, this paper proposes a two-stage path planning method considering the simultaneous movement of multiple items. This method includes two stages: planning single moves and merging single moves. In the first stage, the sequence of single moves of each module needs to be obtained so as to convert the system from an initial state to a target state. In the second stage, the single moves in the sequence are merged into block moves and parallel moves to reduce the steps of movement. The simulation results show that the single move planning method can be used to solve the rearrangement problem stably and effectively and that the single move merging method can greatly optimize the experimental results with the optimization rate more than 50% in different configurations.


---

## Body

## 1. Introduction

With the rapid development of e-commerce and manufacturing, the automated warehousing system has become a vital link of modern logistics systems and supply chain [1, 2]. Traditional warehousing systems such as automated storage and retrieval systems (AS/RS) generally contain aisles for the vehicle to move and transport items. These systems have been extensively researched by scholars [3–5]. In these systems, the aisles occupy the space that could be used to store items, thereby limiting the storage density. In some fields of application, there are higher demands for storage density and space utilization of storage systems, for example, the ship storage systems and the automated parking systems.To achieve high-density storage, a so-called puzzle-based storage (PBS) system [6] has been developed in recent years. Different variants of PBS systems have been used in warehouses and distribution centers, automated parking systems, container handling in port terminals, and so on [7–10].The PBS systems consist of many adjacent square storage cells arranged in a rectangular grid. Each cell either stores an item or is empty, and the item may only be moved from its current cell to its adjacent empty cell (referred to as an escort) (see Figure1). This process of moving a single item to its adjacent empty cell is called a single move. In some models of PBS systems, multiple items are allowed to be moved simultaneously in a step, called the merged move, which means merging multiple single moves.Figure 1
The moving process of a PBS system.As shown in Figure2, the merged move includes block move and parallel move. The block move means that a series of items arranged adjacently on a straight line, or a block of items can be moved to an adjoining escort. The parallel move means that multiple single moves or block moves can be performed in one step, if their pathways are not in conflict with each other. Obviously, compared with the single move, the merged move can save steps and improve the efficiency of the PBS system. However, the scheme for the merged move that is directly considered in the planning stage will make the computation more complicated, and it is infeasible.Figure 2
Block move and parallel move. (a) Case of block move. (b) Case of parallel move
(a)(b)In recent years, multiple variants of the PBS system have been studied. Gue and Kim [6] were the first to propose the concept of the PBS system that was an inspiration from the famous 15-puzzle game. They provided optimal solutions to retrieve one item in a PBS system with one escort in the lower left corner which is the location of the IO point. For the larger problems with multiple escorts arranged in a straight line near the IO point, they proposed a heuristic method. In addition, the block move was taken account in the model established by them. The limitation of their work is that one or more escorts must be located near the IO point in the initial state. Kota et al. [11] proposed a general solution for a PBS system with multiple escorts using integer programming (IP). This approach seems to be impractical due to its poor computational efficiency. Through a further study based on the research results in [6], Kota et al. [12] derived an optimal analytical expression for retrieving a single item when one or two escorts are placed randomly in the PBS system. And they proposed a heuristic method of dealing with more than two escorts placed randomly in the system. However, the block move and the parallel move are not considered in their work.Yalcin et al. [13] studied the single-item retrieval problem with multiple escorts placed randomly in the PBS system. They used an exact search algorithm and developed several search-guiding estimate functions to reduce the search space. To solve larger problem instances, they presented a heuristic method. However, in their research, only the single move is allowed.Furmans et al. [14] proposed a puzzle-based storage system named GridFlow. They presented an optimal algorithm for retrieval of one item with one escort and one AGV. Alfieri et al. [15] proposed a puzzle-based storage system using a limited set of AGVs. They used a heuristic method similar to that in [6] to divide the system into several regions according to predetermined rules. The parallel move was taken account in their method. However, their method is limited in that the escorts of the system need to be initially arranged in a straight line near the IO point.Mirzaei et al. [16] made a study of joint retrieval of multiple items in the PBS system. When more than one item needed to be retrieved, the items would be placed at a “joining location” and then moved to the IO point together. They proposed an optimal method for the joint retrieval of two items and a heuristic method for the joint retrieval of three or more items. However, in their work, it is assumed that only one escort is initially located at the IO point and the merged move is not considered.Gue et al. [17] proposed a puzzle-based picking system named GridStore with decentralized control. The system consists of many conveyor modules. Each conveyor module can move items in four directions. It has its own independent controller and communicates with its adjacent conveyor to decide its next action. The authors gave the proof that the system is deadlock free and studied the performance of the system in several configurations. Shekari Ashgzari and Gue [18] proposed a puzzle-based goods-to-person system named “GridPick+”. The system is based on a grid of conveyor modules and decentralized control similar to the GridStore in [17]. It can bring the required items to four edges of a rectangular grid while GridStore can only bring the items to the southern boundary.Zaerpour et al. [10] proposed a multilevel puzzle-based storage system, which is referred to as the Live-Cube system. They assumed having sufficient escorts on each level to create a virtual aisle for the requested item. A closed-form formula for expected retrieval time was derived by using traditional methods for the aisle-based system. Zaerpour et al. [19] derived the closed-form formulas for the Live-Cube system with two-storage classes. Zaerpour et al. [20] estimate the optimal layout for the Live-Cube system with two-storage classes. However, these works are based on the virtual aisle strategy, assuming that there are enough escorts on each level.The above literature focuses on the PBS system in the form of a single PBS module or multilevel PBS system with a specific configuration. The modular system consisting of multiple PBS modules was not studied yet. Moreover, most of the above work did not allow the merged move (including both the block move and the parallel move at the same time). Although the merged move can be performed through the decentralized control and communication protocol in the GridStore proposed by Gue et al. [17], it is difficult to control each storage cell independently in other applications.Differing from the above literature, this paper studies a modular puzzle-based storage system (MPBS system), which consists of multiple cyclic-structure PBS modules. The system has multiple IO points for transacting a batch of orders at the same time. When a batch of orders comes in advance, the MPBS system will prearrange the items near each IO point to made them consistent with each order. A path planning method considering the merged move is proposed. It involves two stages: the planning of single moves and the merging of single moves. As shown in Figure3, in the first stage, the sequence of single moves of each PBS module is obtained without consideration of the merged move; in the second stage, the single moves in the sequence are merged into block moves and parallel moves, to reduce the steps of the system. This paper offers the following contributions:(1)
A new type of PBS system consisting of multiple PBS modules is introduced, which may motivate a further study of this new kind of PBS systems(2)
A single move planning method is proposed to solve the rearrangement problem in the MPBS system(3)
The methods of merging single moves into the block move and merging single moves into the parallel move are proposed, respectively, to reduce the steps of movement(4)
A planning framework that generates single move plan in the first stage and merges single moves in the second stage is proposed, for the PBS systems to allow multiple items to move simultaneouslyFigure 3
A two-stage path planning method considering the merged move.The remainder of this paper is organized as follows. Section2 describes the structure and workflow of the MPBS system as well as two subproblems discussed in this paper. These two subproblems correspond to the two stages mentioned above, respectively. Section 3 proposes the single move planning method aiming at the first subproblem. Section 4 refers to the methods of merging single moves into block moves and parallel moves to deal with the second subproblem. Section 5 makes an analysis of simulation and experimental results. Section 6 gives a conclusion and discusses the directions for future research.Figure 4
Schematic diagram of an MPBS system.


## 2. Problem Description

The structured components and related concepts involved in this paper are described as follows:Module: it means a PBS module. Multiple PBS modules can be connected to form an MPBS system.Slot: it means the storage cell of the PBS module. A slot may be either empty or occupied by an item.Escort: it means the empty slot.Port: it is a slot in a module connected to adjacent module (see Figure4).Input/output (IO) point: the IO point is a slot in a PBS module for items to be picked out.Picking module: it is a PBS module with an IO point to pick items out (see Figure4).Stocking module: it is a PBS module without an IO point, which can store items and move them to the picking module (see Figure4).Move: it means a process which can be performed in one step in the MPBS system. The move includes both a single move and a merged move whose definitions are explained in Section 1 and shown in Figure2. The single move includes both an internal move and an exchange move.Internal move: it means moving an item inside a module.Exchange move: it means moving an item from a port (which stores an item) of a module to another port (which is an escort) of its adjacent module, that is, the two connected modules exchange an escort and an item. An exchange move is a common move of two connected modules.Exchange demand: if a module needs to move an item in or out, it will send an exchange demand to its adjacent module. One exchange demand corresponds to one exchange move.State: the state of a module is described by the storage status on each slot. The state of the MPBS system involves the state of every module.Order: the order includes a series of items that need to be picked out, according to their types and sequence. One order corresponds to one picking module.


### 2.1. MPBS System

As shown in Figure4, the MPBS system is divided into a picking area and a stocking area. The stocking area has one PBS module called stocking module, and the picking area has multiple PBS modules called picking modules. Each storage module is a cyclic structure. Every picking module connected to the stocking module has an IO point in the lower left corner. Each module keeps at least one escort to guarantee the normal operation of the system. There are different types of items stored in the system.Each picking module can be used to pick items out. The whole system can deal with a batch of orders for customers simultaneously. When a picking module receives a request to bring a certain type of items out, it will search for the required type of items within itself and then move the items to the IO point. If the picking module does not contain the required type, it will send a demand signal to the stocking module. Then, the stocking module will search for the required type and move the items to the picking module. After that, the picking module will move the required type of item to its IO point.In practical application, a batch of orders tend to be assigned to individual picking modules in advance. In this case, the MPBS system works in a mode of preparing orders; in other words, each picking module that has received an order will arrange items near its IO point in accordance with the order. Thus, the items can be picked out in sequence for customers to get them in time.


### 2.2. Single Move Planning for Order Rearrangement

An order is represented byQk=qk,1,…,qk,i,…,qk,nk, where i is the serial number of the orders, qi is the type of the i-th item to be picked out, and k∈1,2,…,K is the index of the picking module, where K is the total number of picking modules.Definition 1.
Order rearrangement (for a single picking module).
Qk=qk,1,…,qk,i,…,qk,nk represents the order given to the picking module k. If the picking module k reaches the following states: the type of item in slot 1 is qk,1, the type of item in slot is qk,2, the type of item in slot nk, is qk,nk, then it can be said that the picking module fulfill its order rearrangement.
According to Definition1, the order Qk indicates a target state of picking module k. For a batch of orders Qk, if each picking module that receives an order reaches its target state, then the whole MPBS system will reach target state and complete the rearrangement of that batch of orders. The single move planning for the rearrangement problem of the MPBS system is to find a sequence of single moves of each PBS module, thus to convert the MPBS system to a target state.


### 2.3. The Merging Problem of Single Moves

Considering the generality, it is possible to use a 4× 4 PBS module as an example to describe the process of merging single moves. The words (Location, Direction) are used to indicate a move.Location means the position where the item moves during a single move. It is represented by li,j, and i and j denote the column and row of the items, respectively. Location refers to multiple positions where items move during a block move.Direction means the moving direction during a move. There are four possible values for the variable Direction: U (up), D (down), R (right), and L (left).For example, (l1,1, R) means that the item at position (1, 1) moves to the right. (l2,1, l1,1, R) means the items at position (2, 1) and (1, 1) move one step to the right at the same time during a block move.When the merged move is not considered, the PBS module performs a sequence of single moves. In this serial sequence, some single moves that may be merged into a block move or a parallel move, so they can take place simultaneously. In the single move sequence shown in Figure5, (l2,1, L) and (l3,1, L) can be merged into a block move (l2,1, l3,1, L), thereby reducing the system execution time from 4 steps to 3 steps. In the single move sequence shown in Figure 6, (l1,2, U) and (l3,2, D) can be merged into a parallel move; (l1,1, U) and (l3,1, L) can be merged into a parallel move, thereby reducing the system execution time from 5 steps to 3 steps.Figure 5
Diagram of the block move.Figure 6
Diagram of the parallel move.Given a sequence of single moves, the merging problem of single moves is to merge the sequence of single moves into block moves and parallel moves, so as to reduce the steps of movement as more as possible.


## 2.1. MPBS System

As shown in Figure4, the MPBS system is divided into a picking area and a stocking area. The stocking area has one PBS module called stocking module, and the picking area has multiple PBS modules called picking modules. Each storage module is a cyclic structure. Every picking module connected to the stocking module has an IO point in the lower left corner. Each module keeps at least one escort to guarantee the normal operation of the system. There are different types of items stored in the system.Each picking module can be used to pick items out. The whole system can deal with a batch of orders for customers simultaneously. When a picking module receives a request to bring a certain type of items out, it will search for the required type of items within itself and then move the items to the IO point. If the picking module does not contain the required type, it will send a demand signal to the stocking module. Then, the stocking module will search for the required type and move the items to the picking module. After that, the picking module will move the required type of item to its IO point.In practical application, a batch of orders tend to be assigned to individual picking modules in advance. In this case, the MPBS system works in a mode of preparing orders; in other words, each picking module that has received an order will arrange items near its IO point in accordance with the order. Thus, the items can be picked out in sequence for customers to get them in time.


## 2.2. Single Move Planning for Order Rearrangement

An order is represented byQk=qk,1,…,qk,i,…,qk,nk, where i is the serial number of the orders, qi is the type of the i-th item to be picked out, and k∈1,2,…,K is the index of the picking module, where K is the total number of picking modules.Definition 1.
Order rearrangement (for a single picking module).
Qk=qk,1,…,qk,i,…,qk,nk represents the order given to the picking module k. If the picking module k reaches the following states: the type of item in slot 1 is qk,1, the type of item in slot is qk,2, the type of item in slot nk, is qk,nk, then it can be said that the picking module fulfill its order rearrangement.
According to Definition1, the order Qk indicates a target state of picking module k. For a batch of orders Qk, if each picking module that receives an order reaches its target state, then the whole MPBS system will reach target state and complete the rearrangement of that batch of orders. The single move planning for the rearrangement problem of the MPBS system is to find a sequence of single moves of each PBS module, thus to convert the MPBS system to a target state.


## 2.3. The Merging Problem of Single Moves

Considering the generality, it is possible to use a 4× 4 PBS module as an example to describe the process of merging single moves. The words (Location, Direction) are used to indicate a move.Location means the position where the item moves during a single move. It is represented by li,j, and i and j denote the column and row of the items, respectively. Location refers to multiple positions where items move during a block move.Direction means the moving direction during a move. There are four possible values for the variable Direction: U (up), D (down), R (right), and L (left).For example, (l1,1, R) means that the item at position (1, 1) moves to the right. (l2,1, l1,1, R) means the items at position (2, 1) and (1, 1) move one step to the right at the same time during a block move.When the merged move is not considered, the PBS module performs a sequence of single moves. In this serial sequence, some single moves that may be merged into a block move or a parallel move, so they can take place simultaneously. In the single move sequence shown in Figure5, (l2,1, L) and (l3,1, L) can be merged into a block move (l2,1, l3,1, L), thereby reducing the system execution time from 4 steps to 3 steps. In the single move sequence shown in Figure 6, (l1,2, U) and (l3,2, D) can be merged into a parallel move; (l1,1, U) and (l3,1, L) can be merged into a parallel move, thereby reducing the system execution time from 5 steps to 3 steps.Figure 5
Diagram of the block move.Figure 6
Diagram of the parallel move.Given a sequence of single moves, the merging problem of single moves is to merge the sequence of single moves into block moves and parallel moves, so as to reduce the steps of movement as more as possible.


## 3. Single Move Planning

In the PBS module, each module has its own controller, and so it can carry out the internal moves independently. However, the exchange move is performed by two connected modules. The single move planning aims at finding a sequence of moves of each module which includes internal moves and exchange moves. According to the planning, the picking module that receives an order is converted to its target state. The process of single move planning is shown in Figure7.Figure 7
The process of single move planning.


### 3.1. The Order Matching

The order matching means getting part of items in an initial state of the picking module to match with part of items in a target state. As shown in Figure8, the number in the middle of each slot indicates the type of item, and 0 represents an escort. The number in the lower left corner of each slot represents its serial number. Slot 1 is the IO point, and slots 4 and 5 are the ports connected to the stocking module. In Figure 8, the items at slot 1, slot 2, slot 6, and slot 7 in the current state (the corresponding item types are [1, 2, 2, 3]) and the items at slot 1, slot 2, slot 3, and slot 4 in the target state (the corresponding item types are also [1, 2, 2, 3]) are the same in type and logic sequence. Matching items in pairs in a current state and in a target state is called the matching of the picking module (current state) with its order (target state).Figure 8
A case of matching process of the picking module.According to the matched group, a sequence of single moves can be generated to transform the picking module to the target state. The unmatched items in the target state can be moved into the picking module and the unmatched items in the current state can be moved out. Each moving-in or moving-out needs an exchange move, from which an inference is drawn: the less the number of matched items, the more the demand for exchange moves. It should be noted that the exchange move requires the coordination of the stocking module and the picking module. As there is only one stocking module in the MPBS system, the stocking module should deal with the demands of multiple picking modules one by one to avoid deadlock. Therefore, more exchange moves may lead to an increase of the steps for completing the rearrangement, which is unexpected.Based on the above description, an order matching (OM) algorithm is introduced to get an optimal matched group with the largest number of matched items. The OM is described in Algorithm 1using the notation given in Table 1. Given the order Q and the current state S of a picking module, OM returns its optimal matched group. Then, i slots are from Q and S to form a subsequence ptar and pcur, respectively (lines 2–5). If the results of checking ptar and pcur are the same, then a matched group can be obtained and added to the set M (lines 6–7). In M, the matched group with the most items is the optimal result and returned (line 13).Algorithm 1:OM(Q, S).
Input: order Q, current state SOutput: optimal matched group mopt.(1)
Initialize,N=lengthQi=N,M=∅(2)
whilei>0do(3)
getcombQ,i,combS,i(4)
foreachptar∈combQ,ido(5)
foreachpcur∈combS,ido(6)
if check ptar,pcur = true then(7)
M=M∪mptar,pcur(8)
end if(9)
end foreach(10)
end foreach(11)
i=i−1(12)
end while(13)
mopt = argmaxm∈Mlengthm(14)
returnmoptTable 1
Notation.
SymbolDeﬁnitionQ=q1,q2,…,qnAn order of a picking module, indicating a target state of the picking module.N=lengthQLength of the order.S=s1,…,sj,…,sJCurrent state of the picking module, wheresjis the type of item in slot j.combQ,iA set of subsequences composed ofi serial numbers taken from Q.ptar∈combQ,iA subsequence composed ofi serial numbers taken from Q.combS,iA set of subsequence composed ofi serial numbers taken from Spcur∈combS,iA subsequence composed ofi serial numbers selected from Sm=ptar,pcurA matched group determined only byptar and pcur.lengthmThe number of matched items, which is also the length ofptar or pcur.MA set of matched groups.


### 3.2. Single Move Planning Based on Matching

The single move planning based on matching (SMPBM) is described in Algorithm 2 with additional notation given in Table 2. The unmatched items in the target state do not exist in the current state, so it is necessary to move them from the stocking module into the picking module(lines 3–7). The unmatched items in the current state are redundant, and it is necessary to move them out from the picking module to the stocking module (lines 8–12). For the moving-in case, the picking module moves an escort to its port to wait for the stocking module to move the required items to its corresponding port and then perform an exchange move. For the moving-out case, the picking module moves the required items to its port to wait for the stocking module to move an escort to its corresponding port and then perform an exchange move. The way to move an escort or item to the target slot inside a module is realized by the move planning of cyclic structure (MPOCS) algorithm (Algorithm 3). In the cyclic structure, items can only move clockwise (lines 2–13) and anticlockwise (lines 14–26). For each shift, the moving sequence of both the directions can be obtained simultaneously. Thus, it is possible to select the shorter sequence of the two as a move plan.Algorithm 2:SMPBM (Q, S, ptar, pcur).
Input: order Q, current state S, optimal matched group ptar,pcur.Output: single move plan Π, set of exchange demands D.(1)
Initialize,N=lengthQi=1,Π=∅(2)
whilei≤Ndo(3)
ifi∉ptarthen(4)
Item typeqi in Q is unmatched, type(d) = qi(5)
π1 = MPOCS(S, ip, next(ip), 1), π2 = MPOCS(S, ip, previous(ip), -1)(6)
π=argminπ′∈π1,π2lengthπ′Aex=ip,2(7)
Π=Π∪π∪Aex, D=D∪d, update ptar, pcur(8)
elseifi∈ptarandi+1∈ptarandbetweenmatchedi,matchedi+1≠∅then(9)
foreachs∈betweenmatchedi,matchedi+1(10)
π1 = MPOCS(S, slot(s), ip, 1), π2 = MPOCS(S, slot(s), ip, −1)(11)
π=argminπ′∈π1,π2lengthπ′, distanced=lengthπ, Aex=ip,−2(12)
Π=Π∪π∪Aex, D=D∪d, update ptar, pcur(13)
end foreach(14)
end if(15)
i=i+1(16)
end while(17)
returnΠ , DTable 2
Additional notation.
SymbolDeﬁnitionA = [source(A), direction(A)]A single move, where source(A) denotes the source slot to be moved and direction(A) denotes the moving direction. For an internal move, direction(A) = 1 or -1, which means clockwise or anticlockwise, respectively; for an exchange move, direction(A) = 2 or -2, which means moving-in or moving-out, respectively.slot(s)The slot index of itemSπ = {Ak}A sequence of single moves, whereAk is a single move.Π=πjA single move plan of the module.previous(i)The previous (anticlockwise adjacent) slot index of sloti.next(i)The next (clockwise adjacent) slot index of sloti.matched(i)Slot index inpcur corresponding to slot i in ptar.between(i1, i2)A set of items between sloti1 and slot i2 in a current state Sd = [type(d), distance(d)]An exchange demand generated by the picking module, where type(d) denotes the type of required item, and distance(d) denotes the remaining steps for exchange move of d.D = {d}A set of exchange demands generated by the picking module.ipThe index of port slot.Algorithm 3:MPOCS (S, isrc, ides, dir).
Input: the current state S, the source slot isrc of item, the destination slot ides to be moved to, the moving direction dir.Output: single move sequence π that moves the item at slot isrc to slot ides.(1)
Initialize,π=∅(2)
ifdir = 1 then(3)
isrc′=isrc(4)
whileisrc′≠idesdo(5)
itemp = nextisrc′(6)
while type(itemp)≠0 do(7)
itemp = next(itemp)(8)
end while(9)
AInter=previousitemp,1, π=π∪Ainter, update S(10)
ifisrc′ = previous(itemp) then(11)
isrc′ = nextisrc′(12)
end if(13)
end while(14)
else(15)
isrc′=isrc(16)
whileisrc′≠idesdo(17)
itemp = previousisrc′(18)
while type(itemp)≠0 do(19)
itemp = previous(itemp)(20)
end while(21)
AInter=nextitemp,−1, π=π∪Ainter, update S(22)
ifisrc′ = next(itemp) then(23)
isrc′ = previous isrc′(24)
end if(25)
end while(26)
end if(27)
returnπThe process of conversion from the current state to the target state shown in Figure9 is corresponding to the matched group in Figure 8. A single move is expressed as A = (source(A), direction(A)). Refer to the first line of Table 2 about the details of A. In Figure 9, the internal move (3, 1) converts the system from the state in Figure 9(a) to the state in Figure 9(b); the exchange move (4, −2) converts the system from the state in Figure 9(b) to the state in Figure 9(c), the internal move sequence {(6, −1), (5, −1), (4, −1), (7, −1), (6, −1), (5, −1)} converts the system from the state in Figure 9(c) to the state in Figure 9(d); and the exchange move [5, 2] converts from the state in Figure 9(d) to the target state in Figure 9(e). In summary, a single move plan {(3, 1), (4, −2), (6, −1), (5, −1), (4, −1), (7, −1), (6, −1), (5, −1), (5, 2)} converts the picking module to the target state.Figure 9
The process of converting a picking module to a target state.


### 3.3. Single Move Planning Based on the Priority of Demands

The stocking module receives the exchange demands from each picking module and deals with them according to priority. The single move planning based on the priority of demands (SMPBPD) is described as Algorithm 4. The distance(d) denotes the remaining steps of the picking module for the exchange move corresponding to the demand d. The smaller the distance(d) is, the higher the priority of demand d is. In each loop, the stocking module selects the highest priority demand to handle (line 3). The process of dealing with a demand is to move the required item or escort its corresponding port, which invokes Algorithm 3, obtaining move plans in two directions and selecting the shorter one.Algorithm 4:SMPBPD (D, S).
Input: set of exchange demands D. the current state SOutput: single move plan Π of stocking module.(1)
Initialize,Π=∅, πs=∅(2)
whileD≠∅do(3)
d=argmind′∈Ddistanced′(4)
if type(d) = 0 then(5)
π1 = MPOCS(S, ip, next(ip), 1), π2 = MPOCS(S, ip, previous(ip), -1)(6)
π=argminπ′∈π1,π2lengthπ′,Π=Π∪π(7)
else(8)
foreachs∈s′|s′=typed,s′∈Sdo(9)
π1=(S, slot(s), ip, 1), π2=(S, slot(s), ip, -1)(10)
π=argminπ′∈π1,π2lengthπ′, πs=πs∪π(11)
end foreach(12)
π=argminπ′∈πslengthπ′, Π=Π∪π, πs=∅(13)
end if(14)
D=D/d(15)
end while(16)
returnΠ


## 3.1. The Order Matching

The order matching means getting part of items in an initial state of the picking module to match with part of items in a target state. As shown in Figure8, the number in the middle of each slot indicates the type of item, and 0 represents an escort. The number in the lower left corner of each slot represents its serial number. Slot 1 is the IO point, and slots 4 and 5 are the ports connected to the stocking module. In Figure 8, the items at slot 1, slot 2, slot 6, and slot 7 in the current state (the corresponding item types are [1, 2, 2, 3]) and the items at slot 1, slot 2, slot 3, and slot 4 in the target state (the corresponding item types are also [1, 2, 2, 3]) are the same in type and logic sequence. Matching items in pairs in a current state and in a target state is called the matching of the picking module (current state) with its order (target state).Figure 8
A case of matching process of the picking module.According to the matched group, a sequence of single moves can be generated to transform the picking module to the target state. The unmatched items in the target state can be moved into the picking module and the unmatched items in the current state can be moved out. Each moving-in or moving-out needs an exchange move, from which an inference is drawn: the less the number of matched items, the more the demand for exchange moves. It should be noted that the exchange move requires the coordination of the stocking module and the picking module. As there is only one stocking module in the MPBS system, the stocking module should deal with the demands of multiple picking modules one by one to avoid deadlock. Therefore, more exchange moves may lead to an increase of the steps for completing the rearrangement, which is unexpected.Based on the above description, an order matching (OM) algorithm is introduced to get an optimal matched group with the largest number of matched items. The OM is described in Algorithm 1using the notation given in Table 1. Given the order Q and the current state S of a picking module, OM returns its optimal matched group. Then, i slots are from Q and S to form a subsequence ptar and pcur, respectively (lines 2–5). If the results of checking ptar and pcur are the same, then a matched group can be obtained and added to the set M (lines 6–7). In M, the matched group with the most items is the optimal result and returned (line 13).Algorithm 1:OM(Q, S).
Input: order Q, current state SOutput: optimal matched group mopt.(1)
Initialize,N=lengthQi=N,M=∅(2)
whilei>0do(3)
getcombQ,i,combS,i(4)
foreachptar∈combQ,ido(5)
foreachpcur∈combS,ido(6)
if check ptar,pcur = true then(7)
M=M∪mptar,pcur(8)
end if(9)
end foreach(10)
end foreach(11)
i=i−1(12)
end while(13)
mopt = argmaxm∈Mlengthm(14)
returnmoptTable 1
Notation.
SymbolDeﬁnitionQ=q1,q2,…,qnAn order of a picking module, indicating a target state of the picking module.N=lengthQLength of the order.S=s1,…,sj,…,sJCurrent state of the picking module, wheresjis the type of item in slot j.combQ,iA set of subsequences composed ofi serial numbers taken from Q.ptar∈combQ,iA subsequence composed ofi serial numbers taken from Q.combS,iA set of subsequence composed ofi serial numbers taken from Spcur∈combS,iA subsequence composed ofi serial numbers selected from Sm=ptar,pcurA matched group determined only byptar and pcur.lengthmThe number of matched items, which is also the length ofptar or pcur.MA set of matched groups.


## 3.2. Single Move Planning Based on Matching

The single move planning based on matching (SMPBM) is described in Algorithm 2 with additional notation given in Table 2. The unmatched items in the target state do not exist in the current state, so it is necessary to move them from the stocking module into the picking module(lines 3–7). The unmatched items in the current state are redundant, and it is necessary to move them out from the picking module to the stocking module (lines 8–12). For the moving-in case, the picking module moves an escort to its port to wait for the stocking module to move the required items to its corresponding port and then perform an exchange move. For the moving-out case, the picking module moves the required items to its port to wait for the stocking module to move an escort to its corresponding port and then perform an exchange move. The way to move an escort or item to the target slot inside a module is realized by the move planning of cyclic structure (MPOCS) algorithm (Algorithm 3). In the cyclic structure, items can only move clockwise (lines 2–13) and anticlockwise (lines 14–26). For each shift, the moving sequence of both the directions can be obtained simultaneously. Thus, it is possible to select the shorter sequence of the two as a move plan.Algorithm 2:SMPBM (Q, S, ptar, pcur).
Input: order Q, current state S, optimal matched group ptar,pcur.Output: single move plan Π, set of exchange demands D.(1)
Initialize,N=lengthQi=1,Π=∅(2)
whilei≤Ndo(3)
ifi∉ptarthen(4)
Item typeqi in Q is unmatched, type(d) = qi(5)
π1 = MPOCS(S, ip, next(ip), 1), π2 = MPOCS(S, ip, previous(ip), -1)(6)
π=argminπ′∈π1,π2lengthπ′Aex=ip,2(7)
Π=Π∪π∪Aex, D=D∪d, update ptar, pcur(8)
elseifi∈ptarandi+1∈ptarandbetweenmatchedi,matchedi+1≠∅then(9)
foreachs∈betweenmatchedi,matchedi+1(10)
π1 = MPOCS(S, slot(s), ip, 1), π2 = MPOCS(S, slot(s), ip, −1)(11)
π=argminπ′∈π1,π2lengthπ′, distanced=lengthπ, Aex=ip,−2(12)
Π=Π∪π∪Aex, D=D∪d, update ptar, pcur(13)
end foreach(14)
end if(15)
i=i+1(16)
end while(17)
returnΠ , DTable 2
Additional notation.
SymbolDeﬁnitionA = [source(A), direction(A)]A single move, where source(A) denotes the source slot to be moved and direction(A) denotes the moving direction. For an internal move, direction(A) = 1 or -1, which means clockwise or anticlockwise, respectively; for an exchange move, direction(A) = 2 or -2, which means moving-in or moving-out, respectively.slot(s)The slot index of itemSπ = {Ak}A sequence of single moves, whereAk is a single move.Π=πjA single move plan of the module.previous(i)The previous (anticlockwise adjacent) slot index of sloti.next(i)The next (clockwise adjacent) slot index of sloti.matched(i)Slot index inpcur corresponding to slot i in ptar.between(i1, i2)A set of items between sloti1 and slot i2 in a current state Sd = [type(d), distance(d)]An exchange demand generated by the picking module, where type(d) denotes the type of required item, and distance(d) denotes the remaining steps for exchange move of d.D = {d}A set of exchange demands generated by the picking module.ipThe index of port slot.Algorithm 3:MPOCS (S, isrc, ides, dir).
Input: the current state S, the source slot isrc of item, the destination slot ides to be moved to, the moving direction dir.Output: single move sequence π that moves the item at slot isrc to slot ides.(1)
Initialize,π=∅(2)
ifdir = 1 then(3)
isrc′=isrc(4)
whileisrc′≠idesdo(5)
itemp = nextisrc′(6)
while type(itemp)≠0 do(7)
itemp = next(itemp)(8)
end while(9)
AInter=previousitemp,1, π=π∪Ainter, update S(10)
ifisrc′ = previous(itemp) then(11)
isrc′ = nextisrc′(12)
end if(13)
end while(14)
else(15)
isrc′=isrc(16)
whileisrc′≠idesdo(17)
itemp = previousisrc′(18)
while type(itemp)≠0 do(19)
itemp = previous(itemp)(20)
end while(21)
AInter=nextitemp,−1, π=π∪Ainter, update S(22)
ifisrc′ = next(itemp) then(23)
isrc′ = previous isrc′(24)
end if(25)
end while(26)
end if(27)
returnπThe process of conversion from the current state to the target state shown in Figure9 is corresponding to the matched group in Figure 8. A single move is expressed as A = (source(A), direction(A)). Refer to the first line of Table 2 about the details of A. In Figure 9, the internal move (3, 1) converts the system from the state in Figure 9(a) to the state in Figure 9(b); the exchange move (4, −2) converts the system from the state in Figure 9(b) to the state in Figure 9(c), the internal move sequence {(6, −1), (5, −1), (4, −1), (7, −1), (6, −1), (5, −1)} converts the system from the state in Figure 9(c) to the state in Figure 9(d); and the exchange move [5, 2] converts from the state in Figure 9(d) to the target state in Figure 9(e). In summary, a single move plan {(3, 1), (4, −2), (6, −1), (5, −1), (4, −1), (7, −1), (6, −1), (5, −1), (5, 2)} converts the picking module to the target state.Figure 9
The process of converting a picking module to a target state.


## 3.3. Single Move Planning Based on the Priority of Demands

The stocking module receives the exchange demands from each picking module and deals with them according to priority. The single move planning based on the priority of demands (SMPBPD) is described as Algorithm 4. The distance(d) denotes the remaining steps of the picking module for the exchange move corresponding to the demand d. The smaller the distance(d) is, the higher the priority of demand d is. In each loop, the stocking module selects the highest priority demand to handle (line 3). The process of dealing with a demand is to move the required item or escort its corresponding port, which invokes Algorithm 3, obtaining move plans in two directions and selecting the shorter one.Algorithm 4:SMPBPD (D, S).
Input: set of exchange demands D. the current state SOutput: single move plan Π of stocking module.(1)
Initialize,Π=∅, πs=∅(2)
whileD≠∅do(3)
d=argmind′∈Ddistanced′(4)
if type(d) = 0 then(5)
π1 = MPOCS(S, ip, next(ip), 1), π2 = MPOCS(S, ip, previous(ip), -1)(6)
π=argminπ′∈π1,π2lengthπ′,Π=Π∪π(7)
else(8)
foreachs∈s′|s′=typed,s′∈Sdo(9)
π1=(S, slot(s), ip, 1), π2=(S, slot(s), ip, -1)(10)
π=argminπ′∈π1,π2lengthπ′, πs=πs∪π(11)
end foreach(12)
π=argminπ′∈πslengthπ′, Π=Π∪π, πs=∅(13)
end if(14)
D=D/d(15)
end while(16)
returnΠ


## 4. Single Move Merging

### 4.1. Matrix Model of Movement

The state of a PBS module is described by a row vector. Suppose a PBS module hasn slots and its state is denoted by a 1×n row vector. Then, S=w1,…,wi,…,wn, where wi is the type of items in slot i, and i∈1,2,…,n. In particular, wi=0 indicates that slot i is an escort.The movement of PBS module can be described by a matrix. Suppose the movement of a PBS module withn slots is expressed as a matrix C∈Βn×n, where B=0,1 is the Boolean space. Then, C can be expressed as(1)C=cij,cij∈0,1.In equation (1), cij=1 means that the item of slot i is moved to slot j after the movement of C.Take a 2 × 2 PBS module for example. As shown in Figure10, the number in the lower left corner of each slot represents the slot index of the PBS module. According to the above description, the initial state of the module can be expressed as S0=w1,w2,0,w4. After the movement of C, the item at slot 2 is moved to slot 3 while the items at slot 1 and slot 4 remain unmoved. As a result, c11=1, c44=1, and c23=1. Then, C can be expressed as a 4 × 4 matrix in equation (2). Note that S1=w1,0,w2,w4 and S0C=w1,0,w2,w4; thus, S1=S0C. Through the above model, the state transition of a movement can be described by the multiplication operation of a matrix and a vector:(2)C=1000001000000001.Figure 10
The process of state transition during a movement.


### 4.2. Merging into Block Move

For a designed PBS module, all of its single moves and block moves can be enumerated. Therefore, all single moves can be listed as a finite setΘ=Ci. Furthermore, all single move that can be merged into block moves can be enumerated.Definition 2.
The longest block move.
The longest block move is a sequential set of all single moves which can be merged into a block move on a straight path (row or column) of PBS module. It is expressed asCLB=C1,…,Ci,…,Cn. For all straight paths of the PBS module, their corresponding longest block moves can be enumerated as a finite set G=CLB,1,CLB,2,…,CLB,X.
The block move merging (BMM) algorithm is described in Algorithm 5. Given a sequence of single moves Π=C1,…,Ci,…,Cm to be performed and the set of all longest block moves G, BMM returns a block move that can be performed at the current step. C1 is the first move to be performed at the current step, and its subsequent move sequence is Πs=C2,…,Ci,…,Cm. By traversing the set G, the longest block move CLB,x that contains C1 (lines 2–4) will be found. Suppose CLB,x,i=C1 and CLB,x,i+j is the j-th move after CLB,x,i in CLB,x, where CLB,x,i∈CLB,x and CLB,x,i+j∈CLB,x. Let C1+j denote the j-th move after C1 in Π. In Algorithm 5, j is initialized to 1 (line 1) and incremented in each loop. According to Definition 2, the continuous moves in CLB,x can be merged into a block move. Judging whether C1+j=CLB,x,i+j in each loop, then the block move Cblock at the current step can be obtained (lines 5–6).Algorithm 5:BMM (Π, G).
Input: sequence of single moves Π =  C1,…,Cm, a set of all the longest block moves G.Output: the block move Cblock at the current step.(1)
Initialize,x=1i=1j=1,Cblock=C1(2)
foreachCLB,x∈Gdo(3)
foreachCLB,x,i∈CLB,xdo(4)
ifC1=CLB,x,ithen(5)
whileC1+j=CLB,x,i+jdo(6)
Cblock=Cblock∪C1+j,j=j+1(7)
end while(8)
end if(9)
end foreach(10)
end foreach(11)
returnCblockAlgorithm 6:PMM.Π=C1,…,Ci,…,Cm.
Input: sequence of single moves Π=C1,…,Ci,…,Cm.Output: the parallel move Cpara at current step.(1)
Initialize,i=2, Cpara=C1(2)
whilei<mdo(3)
ifC1,…,Ci−1Ci=CiC1,…,Ci−1then(4)
Cpara=Cpara∪Ci(5)
end if(6)
endwhile(7)
returnCpara


### 4.3. Merging into Parallel Move

According to Section4.1, if a sequence of moves C1,…,Cm converts the PBS module from the initial state Sinit to the state Sm, then this process is expressed as(3)Sm=SinitC1,…,Cm.In a sequence of movesC1,…,Cm, C1 is the first move to be executed at the current step. However, in the remaining sequence of moves C2,…,Cm, there may be moves that can be executed in parallel with C1.Lemma 1.
For the two single movesC1 and C2 of a PBS system, if C2C1=C1C2, then C1 and C2 can be parallelly executed.Proof..
suppose the initial state of the PBS system isSinit. Since that C1C2=C2C1, the following equation can be derived:(4)SinitC1C2=SinitC2C1,which shows that the executive sequence of C1 and C2 does not affect the final state of the PBS system; that is, C1 and C2can be parallelly executed.Theorem 1.
For a given sequence of single movesC1,…,Ci,…,Cm, C1 is the first move to be executed at the current step and Ci is a certain move in the sequence to be executed later. A sufficient condition for Ci and C1 to be executed parallelly is(5)C1,…,Ci−1Ci=CiC1,…,Ci−1.Proof..
letC′=C1,…,Ci−1, then the formula C′Ci=CiC′ can be derived. And the move sequence C1,…,Ci−1 is considered as a whole move C′. According to Lemma 1, C' and Ci can be executed parallelly. Because C1 is the first move in C′, so C1 and Ci can be executed parallelly.Theorem 2.
Given a sequence of single movesC1,…,Ci,…,Cm, it follows that Ci,Cj, and C1 can be executed parallelly if equations (6) and (7) are satisfied:(6)C1,…,Ci−1Ci=CiC1,…,Ci−1,(7)C1,…,Cj−1Cj=CjC1,…,Cj−1.Proof:.
according to Theorem1, Ci and C1 are parallel according to (6); Cj and C1 are in parallel according to (7). Assuming that i<j, equation (7) can be written as (8). The substitution of (6) into the left and the right side of (8) leads to (9) and (10), respectively. Thus, the right side of (9) equals to the right side of (10), which is (11). According to (11) and Theorem 1, Ci and Cj can be executed in parallel. Therefore, Ci,Cj, and C1 can be executed in parallel:(8)C1,…,Ci−1CiCi+1,…,Cj−1Cj=CjC1,…,Ci−1CiCi+1,…,Cj−1,(9)C1,…,Ci−1CiCi+1,…,Cj−1Cj=CiC1,…,Ci−1Ci+1,…,Cj−1Cj,(10)CjC1,…,Ci−1CiCi+1,…,Cj−1=CjCiC1,…,Ci−1Ci+1,…,Cj−1,(11)CiC1,…,Ci−1Ci+1,…,Cj−1Cj=CjCiC1,…,Ci−1Ci+1,…,Cj−1.
A sequence of single movesΠ=C1,…,Ci…,Cm is given, according to Theorem 2, if multiple single moves satisfy the sufficient condition of equation (5) in Theorem 1, then these moves are all parallel with one another. Based on the above principle, a parallel move merging (PMM) algorithm (Algorithm 6) is proposed. C1 is the first move to be executed at the current step and its subsequent move sequence is Πs=C2,…,Ci,…,Cm. The move Ci is taken out from Πs=C2,…,Ci,…,Cm to judge whether Ci and C1 satisfy equation (5) in each loop (lines 1–4). If Ci and C1 satisfy equation (5), Ci will be added to Cpara (line 4). Finally, all parallel moves at the current step can be obtained (line 7).


## 4.1. Matrix Model of Movement

The state of a PBS module is described by a row vector. Suppose a PBS module hasn slots and its state is denoted by a 1×n row vector. Then, S=w1,…,wi,…,wn, where wi is the type of items in slot i, and i∈1,2,…,n. In particular, wi=0 indicates that slot i is an escort.The movement of PBS module can be described by a matrix. Suppose the movement of a PBS module withn slots is expressed as a matrix C∈Βn×n, where B=0,1 is the Boolean space. Then, C can be expressed as(1)C=cij,cij∈0,1.In equation (1), cij=1 means that the item of slot i is moved to slot j after the movement of C.Take a 2 × 2 PBS module for example. As shown in Figure10, the number in the lower left corner of each slot represents the slot index of the PBS module. According to the above description, the initial state of the module can be expressed as S0=w1,w2,0,w4. After the movement of C, the item at slot 2 is moved to slot 3 while the items at slot 1 and slot 4 remain unmoved. As a result, c11=1, c44=1, and c23=1. Then, C can be expressed as a 4 × 4 matrix in equation (2). Note that S1=w1,0,w2,w4 and S0C=w1,0,w2,w4; thus, S1=S0C. Through the above model, the state transition of a movement can be described by the multiplication operation of a matrix and a vector:(2)C=1000001000000001.Figure 10
The process of state transition during a movement.


## 4.2. Merging into Block Move

For a designed PBS module, all of its single moves and block moves can be enumerated. Therefore, all single moves can be listed as a finite setΘ=Ci. Furthermore, all single move that can be merged into block moves can be enumerated.Definition 2.
The longest block move.
The longest block move is a sequential set of all single moves which can be merged into a block move on a straight path (row or column) of PBS module. It is expressed asCLB=C1,…,Ci,…,Cn. For all straight paths of the PBS module, their corresponding longest block moves can be enumerated as a finite set G=CLB,1,CLB,2,…,CLB,X.
The block move merging (BMM) algorithm is described in Algorithm 5. Given a sequence of single moves Π=C1,…,Ci,…,Cm to be performed and the set of all longest block moves G, BMM returns a block move that can be performed at the current step. C1 is the first move to be performed at the current step, and its subsequent move sequence is Πs=C2,…,Ci,…,Cm. By traversing the set G, the longest block move CLB,x that contains C1 (lines 2–4) will be found. Suppose CLB,x,i=C1 and CLB,x,i+j is the j-th move after CLB,x,i in CLB,x, where CLB,x,i∈CLB,x and CLB,x,i+j∈CLB,x. Let C1+j denote the j-th move after C1 in Π. In Algorithm 5, j is initialized to 1 (line 1) and incremented in each loop. According to Definition 2, the continuous moves in CLB,x can be merged into a block move. Judging whether C1+j=CLB,x,i+j in each loop, then the block move Cblock at the current step can be obtained (lines 5–6).Algorithm 5:BMM (Π, G).
Input: sequence of single moves Π =  C1,…,Cm, a set of all the longest block moves G.Output: the block move Cblock at the current step.(1)
Initialize,x=1i=1j=1,Cblock=C1(2)
foreachCLB,x∈Gdo(3)
foreachCLB,x,i∈CLB,xdo(4)
ifC1=CLB,x,ithen(5)
whileC1+j=CLB,x,i+jdo(6)
Cblock=Cblock∪C1+j,j=j+1(7)
end while(8)
end if(9)
end foreach(10)
end foreach(11)
returnCblockAlgorithm 6:PMM.Π=C1,…,Ci,…,Cm.
Input: sequence of single moves Π=C1,…,Ci,…,Cm.Output: the parallel move Cpara at current step.(1)
Initialize,i=2, Cpara=C1(2)
whilei<mdo(3)
ifC1,…,Ci−1Ci=CiC1,…,Ci−1then(4)
Cpara=Cpara∪Ci(5)
end if(6)
endwhile(7)
returnCpara


## 4.3. Merging into Parallel Move

According to Section4.1, if a sequence of moves C1,…,Cm converts the PBS module from the initial state Sinit to the state Sm, then this process is expressed as(3)Sm=SinitC1,…,Cm.In a sequence of movesC1,…,Cm, C1 is the first move to be executed at the current step. However, in the remaining sequence of moves C2,…,Cm, there may be moves that can be executed in parallel with C1.Lemma 1.
For the two single movesC1 and C2 of a PBS system, if C2C1=C1C2, then C1 and C2 can be parallelly executed.Proof..
suppose the initial state of the PBS system isSinit. Since that C1C2=C2C1, the following equation can be derived:(4)SinitC1C2=SinitC2C1,which shows that the executive sequence of C1 and C2 does not affect the final state of the PBS system; that is, C1 and C2can be parallelly executed.Theorem 1.
For a given sequence of single movesC1,…,Ci,…,Cm, C1 is the first move to be executed at the current step and Ci is a certain move in the sequence to be executed later. A sufficient condition for Ci and C1 to be executed parallelly is(5)C1,…,Ci−1Ci=CiC1,…,Ci−1.Proof..
letC′=C1,…,Ci−1, then the formula C′Ci=CiC′ can be derived. And the move sequence C1,…,Ci−1 is considered as a whole move C′. According to Lemma 1, C' and Ci can be executed parallelly. Because C1 is the first move in C′, so C1 and Ci can be executed parallelly.Theorem 2.
Given a sequence of single movesC1,…,Ci,…,Cm, it follows that Ci,Cj, and C1 can be executed parallelly if equations (6) and (7) are satisfied:(6)C1,…,Ci−1Ci=CiC1,…,Ci−1,(7)C1,…,Cj−1Cj=CjC1,…,Cj−1.Proof:.
according to Theorem1, Ci and C1 are parallel according to (6); Cj and C1 are in parallel according to (7). Assuming that i<j, equation (7) can be written as (8). The substitution of (6) into the left and the right side of (8) leads to (9) and (10), respectively. Thus, the right side of (9) equals to the right side of (10), which is (11). According to (11) and Theorem 1, Ci and Cj can be executed in parallel. Therefore, Ci,Cj, and C1 can be executed in parallel:(8)C1,…,Ci−1CiCi+1,…,Cj−1Cj=CjC1,…,Ci−1CiCi+1,…,Cj−1,(9)C1,…,Ci−1CiCi+1,…,Cj−1Cj=CiC1,…,Ci−1Ci+1,…,Cj−1Cj,(10)CjC1,…,Ci−1CiCi+1,…,Cj−1=CjCiC1,…,Ci−1Ci+1,…,Cj−1,(11)CiC1,…,Ci−1Ci+1,…,Cj−1Cj=CjCiC1,…,Ci−1Ci+1,…,Cj−1.
A sequence of single movesΠ=C1,…,Ci…,Cm is given, according to Theorem 2, if multiple single moves satisfy the sufficient condition of equation (5) in Theorem 1, then these moves are all parallel with one another. Based on the above principle, a parallel move merging (PMM) algorithm (Algorithm 6) is proposed. C1 is the first move to be executed at the current step and its subsequent move sequence is Πs=C2,…,Ci,…,Cm. The move Ci is taken out from Πs=C2,…,Ci,…,Cm to judge whether Ci and C1 satisfy equation (5) in each loop (lines 1–4). If Ci and C1 satisfy equation (5), Ci will be added to Cpara (line 4). Finally, all parallel moves at the current step can be obtained (line 7).


## 5. Simulation and Analysis

### 5.1. Simulation Settings

The MPBS system used for simulation consists of one stocking module and ten picking modules:(i)
Fixed parameters: 50 slots of the stocking module, 10 slots of each picking module, with its slot 5 and slot 6 served as ports and connected with the stocking module, and four types of items stored in the whole system.(ii)
Variable parameters: the number of ordersα, which represents the number of orders assigned to the system, or the number of picking modules needing to be rearranged; the storage density ρ, which represents the ratio of the number of items to the total number of slots in a PBS module.The simulations on the number of ordersα and the storage density ρ are carried out, respectively. The given parameters are used to generate a series of random problem instances. For each instance, the order assigned to a picking module is generated by randomly disrupting the initial state of this picking module.The simulation results of each instance are divided into 4 cases: the results using only single move planning (denoted bySingle); the results using single move planning and block move merging (denoted by Block); the results using single move planning and parallel move merging (denoted by Para); the results using single move planning, both block move merging and parallel move merging (denoted by Both). The average steps of the above 4 cases are separately defined as (12)–(15), where T is the number of instances under each parameter configuration:(12)avgSingle=1T∑i=1TSinglei,(13)avgBlock=1T∑i=1TBlocki,(14)avgPara=1T∑i=1TParai,(15)avgBoth=1T∑i=1TBothi.Furthermore, the average optimization ratios of the latter three cases (Block, Para, and Both) relative to the single case are, respectively, defined as (16)–(18), where T is the number of instances under each parameter configuration:(16)ηBlock=1T∑i=1TSinglei−BlockiSinglei×100%,(17)ηPara=1T∑i=1TSinglei−ParaiSinglei×100%,(18)ηBoth=1T∑i=1TSinglei−BothiSinglei×100%.


### 5.2. Experimental Results concerning the Number of Orders

The storage density is set as 80%, and the length of each order is set as 8. The value of the number of ordersα is changed, and 50 instances are generated for each value of α. Table 3 gives the numerical results, and Figure 11 shows the histogram.Table 3
Experimental results of different number of orders.
Parameter configurationsResults of caseSingleResults of caseBlockResults of caseParaResults of caseBothραavgSingleavgBlockηBlockavgParaηParaavgBothηBoth80%6408.58146.940.6404255.200.3754128.440.685680%7423.00161.160.6190295.960.3003145.920.655080%8486.62173.980.6425304.580.3741154.780.681980%9587.46196.800.6650377.180.3579178.480.696280%10632.62213.900.6619398.840.3695194.020.6933Figure 11
Comparison of four cases according to different number of orders. (a) The average steps. (b) The average optimization ratio.
(a)(b)From Table3 and Figure 11, it can be seen that all the four methods (Single, Block, Para, and Both) can solve the rearrangement problem stably in different number of orders. With an increase in the number of orders, the average number of steps increases, which is approximately linear with the number of orders. The number of orders is also the number of picking modules that need to be rearranged. For each picking module, its average number of steps and average number of exchange demands tend to be similar with many random experiments. For the stocking module, many random experiments show that its average number of steps is approximately linear to the number of exchange demands. Therefore, the average number of steps increases approximately linearly with the number of orders.The relationship among the average steps of the four methods isavgBoth<avgBlock<avgPara<avgSingle, and the relationship between the average optimization ratios is ηPara<ηBlock<ηBoth. This is because the storage density of each module is set as 0.8. Thus, there are fewer escorts in the system but more items can be moved as a block. In this case, there are fewer moves that can be merged into parallel moves, while there are more moves that can be merged into block moves.In addition, the average optimization ratio of caseBoth is over 60% as far as the orders different in number are concerned. It indicates that the merged moves (including both block move and parallel move) can greatly reduce the steps and improve the execution efficiency.


### 5.3. Experimental Results concerning the Storage Density

The number of orders is set as 8. The value of storage densityρ is changed, and 50 instances are generated for each value of ρ. Table 4 gives the numerical results, and Figure 12 shows the histogram. Two simulation videos are provided in Supplementary Materials.Table 4
Experimental results of different storage densities.
Parameter configurationsResults of caseSingleResults of caseBlockResults of caseParaResults of caseBothραavgSingleavgBlockηBlockavgParaηParaavgBothηBoth50%8171.78102.940.400787.680.489681.400.526160%8241.22144.420.4013141.180.4147119.680.503970%8413.30206.660.5000216.580.4760167.260.595380%8608.48244.320.5985391.660.3563214.300.647890%8948.38310.060.6731756.260.2026275.960.7090Figure 12
Comparison of four cases according to different storage densities. (a) The average steps. (b) The average optimization ratio.
(a)(b)According to Table4 and Figure 12, all the four methods (Single, Block, Para, and Both) can be used to solve the rearrangement problem stably in different storage densities. With an increase in storage density, the average number of steps increases, and the increasing speed becomes faster and faster. The reason is that, on one hand, the increase of storage density leads to the decrease of escorts in the system, resulting in that there are more obstructive items on the moving path need to be cleared; on the other hand, the length of each order increases with the storage density, which will cause more difficulty for rearrangement.When the storage density is low, the relationship between the average steps of the four methods isavgBoth<avgPara<avgBlock<avgSingle, and the relationship between the average optimization ratios is ηBlock<ηPara<ηBoth. With an increase in storage density, the average steps increase, but avgSingle and avgPara increase faster than avgBlock and avgBoth; ηBlock decreases, but ηPara and ηBoth increase. When the storage density exceeds 0.7, the relationship between the average steps becomes avgBoth<avgBlock<avgPara<avgSingle, and the relationship between the average optimization ratios becomes ηPara<ηBlock<ηBoth. The above findings show that, with an increase in storage density, the number of stored items increases while the number of escorts decreases. Thus, the optimization effect of the block move becomes stronger and the optimization effect of the parallel move becomes weaker.In addition, the average optimization ratio of caseBoth is over 50% and can reach 70% when the storage density is increased to 0.9. This indicates that considering the merged moves (including both block move and parallel move) can greatly reduce the steps and improve the execution efficiency, and that the optimization effect is more significant under the condition of high storage density.


## 5.1. Simulation Settings

The MPBS system used for simulation consists of one stocking module and ten picking modules:(i)
Fixed parameters: 50 slots of the stocking module, 10 slots of each picking module, with its slot 5 and slot 6 served as ports and connected with the stocking module, and four types of items stored in the whole system.(ii)
Variable parameters: the number of ordersα, which represents the number of orders assigned to the system, or the number of picking modules needing to be rearranged; the storage density ρ, which represents the ratio of the number of items to the total number of slots in a PBS module.The simulations on the number of ordersα and the storage density ρ are carried out, respectively. The given parameters are used to generate a series of random problem instances. For each instance, the order assigned to a picking module is generated by randomly disrupting the initial state of this picking module.The simulation results of each instance are divided into 4 cases: the results using only single move planning (denoted bySingle); the results using single move planning and block move merging (denoted by Block); the results using single move planning and parallel move merging (denoted by Para); the results using single move planning, both block move merging and parallel move merging (denoted by Both). The average steps of the above 4 cases are separately defined as (12)–(15), where T is the number of instances under each parameter configuration:(12)avgSingle=1T∑i=1TSinglei,(13)avgBlock=1T∑i=1TBlocki,(14)avgPara=1T∑i=1TParai,(15)avgBoth=1T∑i=1TBothi.Furthermore, the average optimization ratios of the latter three cases (Block, Para, and Both) relative to the single case are, respectively, defined as (16)–(18), where T is the number of instances under each parameter configuration:(16)ηBlock=1T∑i=1TSinglei−BlockiSinglei×100%,(17)ηPara=1T∑i=1TSinglei−ParaiSinglei×100%,(18)ηBoth=1T∑i=1TSinglei−BothiSinglei×100%.


## 5.2. Experimental Results concerning the Number of Orders

The storage density is set as 80%, and the length of each order is set as 8. The value of the number of ordersα is changed, and 50 instances are generated for each value of α. Table 3 gives the numerical results, and Figure 11 shows the histogram.Table 3
Experimental results of different number of orders.
Parameter configurationsResults of caseSingleResults of caseBlockResults of caseParaResults of caseBothραavgSingleavgBlockηBlockavgParaηParaavgBothηBoth80%6408.58146.940.6404255.200.3754128.440.685680%7423.00161.160.6190295.960.3003145.920.655080%8486.62173.980.6425304.580.3741154.780.681980%9587.46196.800.6650377.180.3579178.480.696280%10632.62213.900.6619398.840.3695194.020.6933Figure 11
Comparison of four cases according to different number of orders. (a) The average steps. (b) The average optimization ratio.
(a)(b)From Table3 and Figure 11, it can be seen that all the four methods (Single, Block, Para, and Both) can solve the rearrangement problem stably in different number of orders. With an increase in the number of orders, the average number of steps increases, which is approximately linear with the number of orders. The number of orders is also the number of picking modules that need to be rearranged. For each picking module, its average number of steps and average number of exchange demands tend to be similar with many random experiments. For the stocking module, many random experiments show that its average number of steps is approximately linear to the number of exchange demands. Therefore, the average number of steps increases approximately linearly with the number of orders.The relationship among the average steps of the four methods isavgBoth<avgBlock<avgPara<avgSingle, and the relationship between the average optimization ratios is ηPara<ηBlock<ηBoth. This is because the storage density of each module is set as 0.8. Thus, there are fewer escorts in the system but more items can be moved as a block. In this case, there are fewer moves that can be merged into parallel moves, while there are more moves that can be merged into block moves.In addition, the average optimization ratio of caseBoth is over 60% as far as the orders different in number are concerned. It indicates that the merged moves (including both block move and parallel move) can greatly reduce the steps and improve the execution efficiency.


## 5.3. Experimental Results concerning the Storage Density

The number of orders is set as 8. The value of storage densityρ is changed, and 50 instances are generated for each value of ρ. Table 4 gives the numerical results, and Figure 12 shows the histogram. Two simulation videos are provided in Supplementary Materials.Table 4
Experimental results of different storage densities.
Parameter configurationsResults of caseSingleResults of caseBlockResults of caseParaResults of caseBothραavgSingleavgBlockηBlockavgParaηParaavgBothηBoth50%8171.78102.940.400787.680.489681.400.526160%8241.22144.420.4013141.180.4147119.680.503970%8413.30206.660.5000216.580.4760167.260.595380%8608.48244.320.5985391.660.3563214.300.647890%8948.38310.060.6731756.260.2026275.960.7090Figure 12
Comparison of four cases according to different storage densities. (a) The average steps. (b) The average optimization ratio.
(a)(b)According to Table4 and Figure 12, all the four methods (Single, Block, Para, and Both) can be used to solve the rearrangement problem stably in different storage densities. With an increase in storage density, the average number of steps increases, and the increasing speed becomes faster and faster. The reason is that, on one hand, the increase of storage density leads to the decrease of escorts in the system, resulting in that there are more obstructive items on the moving path need to be cleared; on the other hand, the length of each order increases with the storage density, which will cause more difficulty for rearrangement.When the storage density is low, the relationship between the average steps of the four methods isavgBoth<avgPara<avgBlock<avgSingle, and the relationship between the average optimization ratios is ηBlock<ηPara<ηBoth. With an increase in storage density, the average steps increase, but avgSingle and avgPara increase faster than avgBlock and avgBoth; ηBlock decreases, but ηPara and ηBoth increase. When the storage density exceeds 0.7, the relationship between the average steps becomes avgBoth<avgBlock<avgPara<avgSingle, and the relationship between the average optimization ratios becomes ηPara<ηBlock<ηBoth. The above findings show that, with an increase in storage density, the number of stored items increases while the number of escorts decreases. Thus, the optimization effect of the block move becomes stronger and the optimization effect of the parallel move becomes weaker.In addition, the average optimization ratio of caseBoth is over 50% and can reach 70% when the storage density is increased to 0.9. This indicates that considering the merged moves (including both block move and parallel move) can greatly reduce the steps and improve the execution efficiency, and that the optimization effect is more significant under the condition of high storage density.


## 6. Conclusions

This paper introduces an MPBS system consisting of multiple cyclic PBS modules and proposes a two-stage path planning method considering the merged moves to solve the rearrangement problem. The proposed method includes single move planning and single move merging. In the stage of single move planning, a path planning method based on the order matching and the priority of demands is proposed; in the stage of single move merging, the method of merging single moves into block moves and the method of merging single moves into parallel moves are proposed, respectively. Through the simulation and analysis in different numbers of orders and different storage densities, the effectiveness of the single move planning method and the optimization performance of single move merging method are verified.The framework of solving problems in stages may provide references for other PBS systems. For example, in the studies of the other PBS systems, there may be different methods to get a single move plan. Then, the single move plan can be merged in the second stage. The proposed method in this paper can deal with one sequence of moves, and further research may focus on the method to merge multiple sequences of moves or the planning method in stages for the other PBS systems.



---

*Source: 6626569-2021-04-23.xml*