# Large-Scale Storage/Retrieval Requests Sorting Algorithm for Multi-I/O Depots Automated Storage/Retrieval Systems

Authors: Yu Bo Song; Hai Bo Mu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

This paper addresses the sequence sorting problem of large-scale storage/retrieval (S/R) requests in multiple Input/Output (multi-I/O) depots automated storage/retrieval systems (AS/RS), in which the cargoes can enter/leave the system through multi-I/O depots, the stacker can load only one cargo, and the load travel time of stacker is fixed. The problem is to find an optimal sequence for a certain S/R requests sequence, and it is a special kind of traveling salesman problem. In this paper, a heuristic algorithm based on assignment is proposed. In order to eliminate the subloops emerged in the sorting process, the equivalent merging and minimum cost merging methods of subloops are considered, and the proposed algorithm is modified. Experimental results indicate the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

The functions of automated storage/retrieval system (AS/RS) include receiving, storing, and order fulfillment. Assignment of products to storage locations, choice of products to retrieval, and storage/retrieval (S/R) requests sequencing are important planning and operational decisions in the AS/RS operation problems [1, 2]. Since AS/RS is required to accomplish S/R requests in a timely manner, optimization of S/R requests sequence of a stacker is considered as an essential problem for efficient operation in the AS/RS [3, 4]. Especially, the optimization of S/R requests sequence becomes much more important for AS/RS, which is fully integrated with other automated industrial production line or logistical systems. Not only the optimized routing, but also the fast calculation of routing is required to be attained simultaneously. With the increasing scale of S/R requests sequence, the scale of its feasible region increases exponentially. The overall performance and efficiency of AS/RS will be limited if the optimization of routing takes considerable time [5–7].However, it is challenging to quickly optimize the execution order of large-scale S/R requests sequence. Research has gained momentum with the papers by Hausman et al. [8] and Graves et al. [9]. A lot of optimization methods of S/R requests sequence under different AS/RS layout structure are proposed. In AS/RS with single Input/Output (I/O), the optimization methods of S/R requests sequence are distributed in three operation modes, namely, single command cycle, double command cycle, and multiple command cycle. In single command cycle mode, the time to complete all S/R requests is a fixed value, and S/R requests sorting is not an optimization problem. However, after importing the permission of S/R requests, the S/R requests sequence sorting problem is transformed into a polynomial solvable problem and NP-hard problem under different optimization objectives [10, 11]. In double command cycle mode, a stacker can complete one storage request and one retrieval request in the same command cycle. Based on the feature that the S/R requests appear in pairs, Lee and Schaefer [12] constructed a bipartite assignment graph by using storage request and retrieval request as the job request nodes, respectively. Hungarian algorithm was used to pair the S/R requests in the same command cycle, and the completion time of S/R requests was minimized. Compared with single command cycle, completing the same number of S/R requests in the double command cycle mode can save about 30% of the time cost [9, 13]. But it is not always possible to have pairs of S/R requests to construct dual instruction cycles in the actual operation process. Eben-Chaime and Pliskin put forward the mixed operation mode and made the decision rules for selecting single or double command cycle [14, 15].Due to the excellent efficiency of dual command cycle, researchers proposed the concept of expanding the number of shuttle in the stacker and thus resulted in four command cycles (twin-shuttle stacker) and six command cycles (triple-shuttle stacker). Keserla and Peters [16] proposed a minimum perimeter based heuristic algorithm and realized the minimization of S/R requests operation time in a four-command cycle. To solve the same problem, Sarker et al. proposed some optimization methods based on greedy strategy to improve the throughput of AS/RS [17, 18]. Tanaka and Araki [19] established a capacitated stacker S/R requests sorting model for multishuttle AS/RS under the condition of fixed storage and retrieval locations and designed an exact algorithm to solve the model. Tanaka [20] extended their work and proposed a hybrid tabu heuristic algorithm to solve the S/R requests sequence of stacker. Popovic et al. [21] provided a general framework for the optimization of S/R requests sequence in the operation mode of a six command cycle, and heuristic algorithm and genetic algorithm were used separately to optimize the S/R requests sequence. They believed that the optimization effect of genetic algorithm was better than that of the heuristic algorithm for the optimization of S/R requests sequence in multi-command cycle. Based on shared memory strategy, Tanaka and Araki [22] and Yang et al. [23] analyzed the optimization problem of S/R requests sequence in multi-command cycle and formalized the problem into an integer programming model. Accurate algorithm and variable neighborhood search algorithm were used to solve the presented model, respectively.The optimization methods of S/R requests sequence of the above three operation modes are discussed in single I/O depot AS/RS, in which the I/O depot is located at one end of the aisle, and each S/R request has the characteristic of periodic return to the unique I/O depot. Another common layout structure of AS/RS is that I/O depot is located at both ends of the aisle. The expansion of I/O depot increases the paths for cargoes’ entering or leaving the AS/RS and also provides the possibility of separating the storage and retrieval operations. Pohl et al. consider that the decisions including AS/RS layout and aisle configuration have an impact on the efficiency of AS/RS [24]. The recent work of Schleyer and Gue [25] and Gue et al. [26] also revealed this conclusion mentioned above. Gharehgozli et al. [27] optimized the S/R requests sequence through polynomial algorithm under the following three conditions: (i) the output depot was dedicated; (ii) the input depot and the output depot were separated; and (iii) the stacker could start and end at any position, and the method was compared with the optimization method presented by Van den Berg and Gademann [28]. Researchers can refer to the summary of Roodbergen and Vis [4], and Boysen and Stephan [29] to obtain more research results related to AS/RS.The literatures mentioned above studied the optimization of S/R requests sequence for AS/RS with single and double I/O depots, and the optimization methods are all on the basis of command cycle. To the best of our knowledge, few people pay attention to the optimization of S/R requests sequence for AS/RS with no command cycle division. In this paper, the optimization problem of large-scale S/R requests sequence for AS/RS with multi-I/O depots is studied based on the logistics problem of actual air cargo terminal. The AS/RS with multi-I/O depots is composed of two rows of racks, and the I/O depot is distributed along both sides of the aisle. Each I/O depot, through which the cargo enters or leaves the system, is connected to the conveyor (the layout of AS/RS with multi-I/O depots is shown in Figure1). The stacker is located in the aisle, and its vertical lifting structure and horizontal moving structure can run simultaneously to complete S/R request of cargoes. A stacker can only hold one cargo during its operation process. Then, the optimization problem of large-scale S/R request sequence in multi-I/O depots AS/RS is to find an optimal execution sequence for a given group of S/R requests, with the purpose of minimizing the operation time of completing all S/R requests. In order to solve the problem mentioned above, we propose a fast optimization method in this paper to study the optimization problem of S/R requests sequence, especially for large-scale S/R requests sequence, in multi-I/O depots AS/RS under the condition of no command cycle division. Simulation results indicate that the algorithm is superior in the quality of optimization results and calculation time.Figure 1
Layout of multi-I/O depots AS/RS.The paper is organized as follows. Details of the optimization problem of S/R requests sequence in multi-I/O depot AS/RS are introduced in Section2. Subsequently, an assignment based heuristic algorithm to optimize large-scale S/R requests sequence is presented in Section 3. Computer simulation results and conclusions follow in Sections 4 and 5.


## 2. The R/S Requests Sequence Problem

According to the operation process of S/R requests, we divide the execution process of S/R requests into two consecutive steps. For the storage request, first, the stacker moves from the current position to the I/O depot and loads the cargo, and then the stacker moves with load to the storage location of the cargo and unloads. For the retrieval request, first, the stacker moves without load from the current position to the storage location of retrieval cargo and loads the cargo, and then the stacker moves with load to the output depot and unloads the cargo. The trajectory formed by the continuous execution of S/R requests of stacker is called a route. A route may be seen as a concatenation of loaded travels, with no-load travels in-between. If the end position of a load travel is the start position of another load travel, the no-load travel is a virtual travel, and its running time is 0. A route for the stacker to complete all S/R requests corresponds to an S/R requests sequence.Through the whole study, we considered the following assumptions. Firstly, only a group of static S/R requests is considered, which means that the scale of the S/R requests sequence remains unchanged during the whole optimization process. Secondly, the Chebyshev distance is used to represent the movement time of the stacker between any two points. Here, the Chebyshev distance refers to the maximum travel time between vertical travel time and horizontal travel time. Thirdly, the stacker moves both vertically and horizontally simultaneously at a constant speed. Fourthly, each location can store only one cargo. Finally, the initial position of the stacker is the virtual starting and ending position for the problem.We allow the cargo to enter/leave the system through any I/O depot and attempt to find an optimal or near optimal execution sequence of the stacker under the condition that the I/O depot of S/R requests and storage position are all known. It is convenient for us to define the following symbols for problem modeling.m: number of storage requestsn: number of retrieval requestsSi: the ith storage requestRj: the jth retrieval requestSIi: input depot of the ith storage requestSLi: storage position of the ith storage requestROj: retrieval depot of the jth retrieval requestRLj: retrieval position of the jth retrieval requestLk: the kth load traveltkl: the no-load movement time between load travel Lk and LlSP: start position of stackerEP: end position of stackertA,B: movement time of stacker from position A to position BFor each storage requestSi, a load travel (SIi⟶SLi) must be performed, i=1,…,m. Likewise, for each retrieval request Rj, a load travel RLj⟶ROj must be performed, j=1,…,n. The no-load travel is executed after each load travel, and its travel time is the time from the end of the previous load travel to the start of the next load travel. We want to find a sequence of load travel to minimize the completion time of the S/R requests sequence. Figure 2 depicts such a sequence. The stacker starts from the initial position SP and returns to the initial position SP after completing all S/R requests. The previous and subsequent load travels of any load travel can be selected arbitrarily, and any two load travels are connected by a no-load travel. Different connection scheme of load travel corresponds to different operation path and completion time of stacker. Since the time of load travel is fixed, the completion time of S/R requests sequence is decided by the running time of no-load travel, and the optimal sequence of no-load travel corresponds to the optimal execution sequence of S/R requests. We consider each load travel as an S/R request vertex and denote it by Lpp=1,…,m+n. Each vertex is connected by a no-load travel Eqq=1,…,m+n, and the minimization of S/R requests completion time is transformed into the minimization of time for traversing all the S/R requests vertices. In the process of traversing, each S/R request vertex can be traversed for only one time, and the stacker finally returns to the initial position. The optimal solution of traveling salesman problem (TSP) is exactly the optimal scheme of no-load travel selection and sorting. Therefore, we model the optimization problem of S/R requests sequence as a TSP.Figure 2
Stacker movement route with three storage requests and seven retrieval requests: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.It is assumed, in this model, that there arem storage requests and n retrieval requests, and the starting address and the ending location of the stacker are both SP. The decision variable xkl takes on binary values, 0 or 1, depending on whether or not the load travel Ll is performed immediately after the load travel Lk has been performed by the stacker. Let tkl be the no-load movement time between load travel Lk and Ll. The objective function minimizes the total no-load travel time. Constraints (2) and (3) ensure that each load travel is accessed once and only once. Constraint (4) ensures that, in the optimal solution, no-load travel and load travel do not constitute a subloop.(1)minT=∑l=1m+n+1∑k=1m+n+1tklxkl,k≠l,(2)∑k=1m+n+1xkl=1,∀l∈L∪SP,l≠k,(3)∑l=1m+n+1xkl=1,∀k∈L∪SP,k≠l,(4)∑l∈L′∑k∈L′xkl≤L′−1,∀L′⊂L∪SP,2≤L′≤m+n,(5)xkl∈0,1.In order to quickly solve the optimization problem of large-scale S/R requests sequence rapidly, we develop an assignment based heuristic algorithm, which will be introduced in the next section.


## 3. Heuristic Algorithms for the R/S Requests Sequence Problem

In this section, a heuristic method to solve the optimization problem of large-scale S/R requests sequence in multi-I/O depots AS/RS was presented. The presented heuristic algorithm is based on the solution idea of assignment model, and it can optimize large-scale S/R requests sequence in a near-real-time manner. It may be a useful tool for dynamic optimization of S/R requests sequence.


### 3.1. Algorithmic Idea

According to the TSP model built in Section2, each node in the model represents an S/R request. Under the condition that the start location and destination location of each S/R request are known, if the initial point returned by the stacker is assumed to be EP, then each vertex in the TSP model can be divided into two vertices, and the assignment problem (AP) we constructed is as follows. The constructed bipartite graph is represented as G=V1,V2,E. V1 is composed of the start points of m+n+1 no-load travels in the tour including the end point of the storage requests SL1,…,SLm, the end point of the retrieval requests RO1,…,ROn, and the start point of the stacker SP, and V1 is defined as the set of people in the AP. V2 is composed of the end points of m+n+1 no-load travels in the tour, including the start point of the storage request SI1,…SIm, the start point of the retrieval request RL1,…RLn, and the end point of the stacker EP, and V2 is defined as the set of tasks in the AP. The set E is composed of edges between any vertex in V1 and any vertex in V2. The cost of any edge is equal to the no-load travel time. E is defined as the time for each person to complete each task in the AP. The time of no-load travel is defined in Table 1. The edge with value ∞ represents the prohibited travel, and prohibited travel is omitted in bipartite graph.Table 1
Costs related to edges in the sequencing problem.
FromToCostSPSIitSP,SIi,i=1,…,mSPRLjtSP,RLj,j=1,…,nSPEP∞SLi′SIitSLi′,SIi,i=1,…,m,i′=1,…,m,andi≠i′SLi′RLjtSLi′,RLji′=1,…,m,j=1,…,nSLi′SIi∞,i=1,…,m,i′=1,…,mandi=i′SLi′EPtSLi′,EP,i′=1,…,mROj′SIitROj′,SIi,i=1,…,m,j′=1,…,nROj′RLjtROj′,RLj,j=1,…,n,j′=1,…,nandj≠j′ROj′RLj∞,j=1,…,n,j′=1,…,nandj=j′ROj′EPtROj′,EP,j′=1,…,nIn addition, each task in the AP can only be completed by one person, and the constraint that each person can only undertake one task is equivalent to constraints (2) and (3) in the TSP model. Then, the minimum edge cover of bipartite graph is the assignment scheme of AP.According to the above rules, we construct a bipartite graph with two storage requests and two retrieval requests (see Figure3) and arbitrarily give an assignment scheme as shown in Figure 4(a). According to the reverse rule of constructing bipartite graph, the vertices in V1 and V2 of Figure 4(a) are combined into the S/R requests node and the start point of the stacker. According to the definition of edge in Table 1, there is no edge between the start location and the destination location of the same S/R request and between SP and EP. Therefore, the edges in the assignment scheme are not lost in the process of vertex merging. Since the assignment scheme covers all the vertices in V1 and V2, and each vertex in V1 and V2 has only one edge connected, each merged S/R request node has two edges connected as shown in Figure 4(b). By merging the same edges in Figure 4(b), we can get a node coverage scheme with multiple disjoint subloops, and the covered nodes include all the S/R request nodes and the start point of the stacker as shown in Figure 4(c). The set of edges in Figure 4(c) is exactly the same as that in Figure 4(a). Therefore, a node traversal scheme with multiple disjoint subloops of TSP can be found according to the above method, and vice versa. In conclusion, our AP has the same solution space as the TSP with subloop relaxation.Figure 3
Bipartite graph with two storage requests and two retrieval requests.Figure 4
Solution of TSP with subloop relaxation transformed from assignment scheme. (a) Assignment scheme. (b) Node merging. (c) Solution of TSP problem with subloop relaxation.
(a)(b)(c)Based on the above analysis, although the optimal assignment scheme, which is a node coverage scheme with multiple disjoint subloops, may not satisfy constraint (4), if we can find the combination scheme of subloops without increasing the no-load travel time, we can obtain the optimal solution of TSP problem. Due to the same specifications of the shelf in AS/RS, and the constant running speed of the stacker in the horizontal and vertical directions, with the increase of the size of the S/R requests sequence, there is a great probability that an edge with the same no-load running time exists in different subloops. Therefore, in the large-scale S/R requests sequence, there is a great probability that an equivalent merging scheme of subloops exists. In order to show the association between the optimal solution of the AP and the optimal solution of the TSP, we give the following theory for three cases: there is no subloop, there is equivalent merging subloop, and there is no equivalent merging subloop.Definition 1.
The scale of TSP refers to the number of load travels plus 1 in the optimization problem of S/R requests sequence.Definition 2.
The scale of AP refers to the number of people or tasks.Definition 3.
In an AP, assigning a task to a person is called an assignment pair, and in the optimal solution of an AP, the number of assignment pairs is equal to the scale of the AP.Theorem 1.
If the scales of the TSP and the AP are equal, then the number of edges in the optimal solution of the TSP is equal to the number of assignment pairs of the AP.Proof.
It can be concluded from Definition1 that there are N-1load travels for the TSP with size N. Departing from the start point of the stacker, one edge is added before the first load travel is performed, and N-2 edges will be generated after the remaining load travels have been completed. Finally, another edge is needed when returning to the initial point from the position, where the loading travel is completed. Then, all feasible solutions of TSP contain N edges. Since the feasible solution contains the optimal solution, there are also N edges in the optimal solution. According to Definition 3, the number of assignment pairs is N in the optimal solution of the AP with size N. Therefore, Theorem 1 holds.Corollary 1.
For an AP and a TSP with the same scale, under the condition that one person only completes one task, the optimal solution of the AP corresponds to the optimal solution of the TSP with the same scale if the no-load travels that correspond to the assignment pairs in the optimal solution of AP and the load travels that correspond to the S/R requests sequence do not constitute a subloop.Proof.
It can be concluded from Definition3 that an assignment pair corresponds to a no-load travel, and the optimal solution of AP is the combination scheme with the minimum total time among all the combination schemes of no-load travels. One person completes only one task means that the start point and end point of each no-load travel are connected with different load travels and connected with only one load travel. It can be concluded from Theorem 1 that the numbers of no-load travels in the optimal solution of AP and TSP with the same scale are equal. If the no-load travels that correspond to the assignment pairs in the optimal solution and the load travels do not constitute a subloop, the N assignment pairs in the optimal solution of AP with scale N can connect the N load travels in series successively to form a path that begins and ends at the start location and ensure that each vertex is visited only once. Therefore, the optimal solution of AP is also the optimal solution of TSP.Corollary 2.
If the load travels corresponding to the S/R requests and the no-load travels corresponding to the assignment pairs in the optimal solution of AP constitute at least two subloops, and there exists a subloop merging scheme, which does not change the task completion time of the AP, then the optimal solution of AP is also the optimal solution of TSP.Proof.
If the load travels corresponding to the S/R requests and the no-load travels corresponding to the assignment pairs in the optimal solution of AP constitute at least two subloops, then load travels and no-load travels will constitute two types of paths. One is the subloop containing the start and end points of the stacker and another is the subloop that does not contain the start and end points of the stacker. Figure5(a) shows the subloop SC1 that contains the start and end points of the stacker and the subloop SC2 that does not contain the start and end points of the stacker. In Figure 5(b), no-load travel Ek that connects A∈EP,SL1,…SLm,RO1,…ROn and B∈SP,SI1,…SIm,RL1,…RLn and no-load travel El that connects C∈SP,SI1,…SIm,RL1,…RLn and D∈EP,SL1,…SLm,RO1,…ROn are deleted, while no-load travel Ek′ that connects A and C and no-load travel El′ that connects B and D are added. A new tour is formed by the above operation, as shown in Figure 5(c). If the sum of travel times of no-load travels Ek and El is equal to the sum of travel times of no-load travels Ek′ and El′, then the sum of no-load travel time tA,C+tD,B in the tour of Figure 5(c) is equal to the sum of no-load travel time tA,B+tD,C in Figure 5(a). The other no-load travel times in SC1 and SC2 remain unchanged. Therefore, when the subloops are merged, the sum of the no-load travel time of the new tour after merging is equal to the sum of the no-load travel time of subloop SC1 and SC2. The merger of more subloops without the start and end points of the stacker can be proved in the same way. According to the equivalent merging process of subloops, all of the load travel vertices involved in the subloop merging process can be accessed only once, and the time does not change. Therefore, the optimal solution of AP formed by merging subloops is also the optimal solution of TSP.Figure 5
Process diagram of subloops merging. (a) Examples with subloops. (b) Merging scheme of subloops. (c) Loop formed with merging.Corollary 3.
If the load travels corresponding to the S/R requests and the no-load travels corresponding to the optimal solution of the AP constitute at least two subloops, and there is no subloop merging scheme, which does not change the task completion time of the AP, then the subloop merging scheme with the smallest task completion time increment is selected to merge the subloops one by one until all subloops are merged, and the solution of AP after subloop merging is also the optimal solution or suboptimal solution of TSP.Proof.
According to the proof of Corollary2, the merging of subloops needs to delete two existing no-load travels and generate two new no-load travels at the same time. When there is no equivalent merging scheme, the no-load travel time will be increased after the merging of subloops. The increase of no-load travel time will bring two possibilities. One is that the no-load travel time of the merged loop is equal to the time of the optimal solution of TSP (as shown in Table 2). The total time of no-load travels corresponding to the optimal solution of the AP, which is constituted by the start and end points of the seven load travels in Table 2 and the start and end points of the stacker, is 162.8 seconds, and three subloops are formed (see Figure 6(a)). The three subloops are merged twice according to the minimum cost rule and form a tour (see Figure 6(b) and Figure 6(e)), and the no-load travel time is increased by 4.6 seconds and 25.8 seconds, respectively. The sum of no-load travel time of the tour is 193.2 seconds, which is equal to the time of the optimal solution of TSP obtained by enumeration method. Another is that the no-load travel time of the merged loop is larger than the time of the optimal solution of TSP (as shown in Table 3). The total time of no-load travels corresponding to the optimal solution of the AP, which is constituted by the start and end points of the nine load travels in Table 3 and the start and end points of the stacker, is 231.2 seconds, and three subloops are formed (see Figure 7(a)). The three subloops are merged by equivalent and minimum cost rules and form a tour (see Figures 7(b) and 7(e)). The minimum cost merging increases the no-load travel time by 10 seconds, and the sum of no-load travel time of the tour is 241.2 seconds, which is 1.4 seconds longer than the time of the optimal solution of TSP obtained by enumeration method. Therefore, the optimal or suboptimal solution of TSP can be found by merging the minimum cost subloops.Table 2
An example of the optimal solution of TSP obtained by minimum cost merging.
Load travelsNo-load travels determined by assignmentSubloopsNumberStart pointEnd pointColumnLayerColumnLayerSP/EP101——SP ⟶ 5SC113134015 ⟶ EPSC124845011 ⟶ 6SC233013836 ⟶ 4SC243513724 ⟶ 3SC2551933 ⟶ 1SC262324012 ⟶ 7SC373925017 ⟶ 2SC3Note. The horizontal speed and vertical speed of stacker are 1.4 s/column and 6 S/layer, respectively.Figure 6
Minimum cost merging process of subloops of the example shown in Table2. (a) Three subloops determined by assignment. (b) Minimum cost merging scheme. (c) New subloops after minimum cost merging. (d) Minimum cost merging scheme. (e) Tour after minimum cost merging.Table 3
An example of the suboptimal solution of TSP obtained by minimum cost merging.
Load travelsNo-load travels determined by assignmentSubloopsNumberStart pointEnd pointColumnLayerColumnLayerSP/EP101——SP ⟶ 6SC112944016 ⟶ 2SC12512152 ⟶ 5SC134144515 ⟶ 7SC143514937 ⟶ EPSC151722511 ⟶ 4SC26512254 ⟶ 9SC271511839 ⟶ 1SC284535013 ⟶ 8SC393754518 ⟶ 3SC3Note. The horizontal speed and vertical speed of stacker are 1.4 s/column and 6 S/layer respectively.Figure 7
Equivalent merging process of subloops of the example shown in Table3 (a) Three subloops determined by assignment. (b) Equivalent merging scheme. (c) New subloops after equivalent merging. (d) Minimum cost merging scheme. (e) Tour after minimum cost merging.


### 3.2. Algorithmic Design

The stacker starts from the start pointSP and returns to the start point after completing all S/R requests. We mark the end point as a virtual point EP. Based on Corollary 1, we propose a heuristic algorithm based on assignment. The algorithm consists of five steps: constructing bipartite graph, creating adjacency matrix, solving the optimal assignment scheme, determining the load travel corresponding to the vertex of serial S/R requests, and sorting the S/R requests sequence.Figure8 shows an example with four storage requests and three retrieval requests. The start and end points of each S/R request are the start and end points of load travel. First, we construct the bipartite graph corresponding to Figure 8 according to the bipartite graph defined in section 3.1 (see Figure 9).Figure 8
An example of four storage requests and three retrieval requests: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively.Figure 9
Bipartite graph of four storage requests and three retrieval requests.The adjacency matrix is created based on the constructed bipartite graphG and the defined no-load travel time. The column index of the matrix corresponds to the serial number of the S/R requests, and the last column is the virtual end point EP. The row vector component of the first line in the matrix represents the running time from the start point of the stacker to the start point of each load travel, and the time arrived to EP is ∞, which is expressed by a relatively large number. The component of the remaining row vector in the matrix represents the running time of the stacker from the end point of the load travel to the start point of other load travels and EP, and the time to reach the end point of the current load travel is ∞, which is represented by a relatively large number. The row index in the matrix is 1 larger than the serial number of the S/R request.Hungary algorithm is applied to solve the adjacency matrix, and the optimal assignment scheme of bipartite graph shown in Figure9 is obtained. In bipartite graph, V1 is composed of the end point of the load travel and the start point of the stacker, and V2 is composed of the start point of the load travel and the virtual end point of the stacker. Therefore, the edges determined by the optimal assignment scheme are all no-load travel, and the directions are all from the nodes of V1 to the nodes of V2. According to the corresponding relationship between the serial number of S/R requests and the row and column index in the adjacency matrix, the no-load travels determined by the optimal assignment scheme in Figure 9 are SP⟶R3, S1⟶R1, S2⟶S4, R1⟶S3, S3⟶R2, R2⟶S2, S4⟶EP, R3⟶S1.Starting from the start locationSP of the stacker, the subsequent S/R requests are determined according to definite no-load travel. At the same time, the definite S/R requests are marked in the S/R requests sequence, and then starting from the definite end location of the S/R requests, the next S/R request is found according to the definite no-load travel and marked until the virtual end of the stacker is found. If the traversal of all the S/R requests nodes is not completed after finding EP, the first unmarked S/R request is found in the S/R requests sequence and starts from the destination corresponding to this S/R request. The above process is repeated until the traversal of all the S/R request nodes is completed. If the no-load travel and S/R requests do not constitute multiple subloop, then starting from SP and finding EP according to the optimal assignment scheme, the traversal of all S/R requests nodes is completed, and the traversal order of all the S/R requests nodes is the optimal solution of the optimization problem of S/R requests sequence. The no-load travel and S/R requests determined by the corresponding optimal assignment scheme of the example shown in Figure 8 do not constitute multiple subloops, and the optimal execution sequence of S/R requests sequence determined by the optimal assignment scheme is shown in Figure 10.Figure 10
Optimal solution of execution sequence of S/R requests sequence: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.However, when the no-load travel determined by the optimal assignment scheme and the load travel constitute multiple subloops (as shown in Figure11), series connection of all load travels along determined no-load travel by the stacker cannot form a tour; that is, the sequencing of all S/R requests cannot realize. An equivalent merging algorithm of subloops based on Corollary 2 will be introduced in the next section. The algorithm is embedded in the heuristic algorithm based on assignment. The subloops are merged without changing the total time of the no-load travel, and a tour contacting all load travels is formed.Figure 11
An example with two subloops: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.When the no-load travel determined by the optimal assignment scheme is in series with the load travel, if multiple subloops are formed, then the execution order of the determined S/R requests sequence violates Constraint (4) in the given model. In order to eliminate the subloops without increasing the operation time of S/R requests sequence, we propose the subloop equivalent merging algorithm to improve the method of concatenating S/R requests nodes. This algorithm is used to consummate the method of connecting S/R request nodes in series. It is connected with the optimal assignment scheme in the assignment based heuristic algorithm and used to solve the following three problems in turn: determining the subloop, constructing the subloop merging matrix, and subloop merging. Firstly, the optimal assignment scheme is used to determine the subloop composed of no-load travel and load travel, so that each load travel (including the start point of the stacker) is connected with the no-load travel determined by the optimal assignment scheme (see Figure 11). There are two subloops in Figure 11, namely, SC1 and SC2. The subloop SC1 is S1⟶R2⟶R3⟶S1 and the subloop SC2 is SP⟶S3⟶R1⟶R4⟶S2⟶SP. We can implement the sort of S/R requests through the equivalent merging of subloops (Corollary 2 has been proved). The subloop merging matrix is used to record the merging scheme of any two subloops. Figure 12 shows the subloop merging matrix with three subloops. The element in the matrix represents the time change after the merging of the subloops that do not contain the start point of the stacker with any other subloops, and its value is the time of the no-load travel corresponding to the two newly generated edges minus the time of the no-load travel corresponding to the original two edges. Taking Figure 5(b) as an example, the time change is dkl after merging of SC1 and SC2, and its value is tA,C+tD,B−tA,B−tD,C. The element with zero value is called zero element, and the merging scheme corresponding to zero element is a subloop equivalent merging scheme. In the subloop merging matrix, it is forbidden to merge any two no-load travels in the same subloop, which is expressed as ∞. In addition, we define the dashed box in the subloop merging matrix as merging block. Each merging block corresponds to two subloops, and the number of elements in the merging block represents the number of merging schemes corresponding to the two subloops.Figure 12
Subloop merging matrix with three subloops.When the subloop merging matrix contains zero elements, the equivalent merging of two subloops corresponding to zero elements can be realized. When the matrix contains multiple zero elements, the merging blocks are taken as units firstly and are sorted according to the number of zero elements. Then, the merging block with the least zero elements is selected, in which all zero elements are picked, and the number of zero elements on the row and column of each zero element is counted and sorted. The two no-load travels corresponding to the zero element with the minimum number in the statistical results are deleted in the merging of subloops. The subsequent merging process of subloops can be found in the proof process of Corollary2. After a subloop is merged, the elements on the row and column where zero element with the minimum number in the statistical results in the merge block is located are deleted. Repeat the above steps until there are no more subloops. Figure 11 is an example with two subloops. In the merging process of SC1 and SC2, the no-load travel R2⟶R3 in SC1 and the no-load travel S2⟶SP in SC2 are deleted, and two new no-load travels S2⟶R3 and R2⟶SP are selected, and the tour formed after merging is SP⟶S3⟶R1⟶R4⟶S2⟶R3⟶S1⟶R2⟶SP (see Figure 13).Figure 13
An example of subloops after equivalent merging: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.Considering that the optimal assignment scheme may construct multiple subloops, subloop equivalent merging algorithm is introduced. By adjusting the no-load travel equivalently, multiple subloops are merged into a time invariant tour. The premise of equivalent merging of subloops is that there are zero elements in the merging matrix of subloops. However, we do not know whether the constructed subloop merging matrix contains zero elements. If the no-load travel determined by the optimal assignment scheme forms multiple subloops when concatenating with the load travel, and there are no zero elements in the subloop merging matrix, that is, there is no equivalent subloop merging scheme (as shown in the example in Figure14), then it is impossible to get the execution sequence of S/R requests that satisfy Constraint (4) through the subloop equivalent merging algorithm. To solve this problem, we propose the minimum cost heuristic rule to merge the subloops and eliminate multiple subloops without equivalent merging scheme.Figure 14
An example of minimum cost merging with four subloops: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.In the process of subloops merging, two no-load travels should be deleted, and two new no-load travels should be selected at the same time. Since the two newly selected no-load travels and the existing no-load travels may form an equivalent merging scheme, in order to avoid omitting the equivalent merging scheme, the minimum merging cost heuristic rule requires that only two subloops be merged at a time, and the two subloops with the minimum time increment of no-load travels are required. The minimum merging cost heuristic rule is a supplement to the subloop equivalent merging algorithm, and its general idea is as follows. If there is no zero element in the subloop merging matrix, all the elements in the subloop merging matrix are traversed, and the element with the smallest time increment is selected. The two subloops corresponding to the merging block, where the element is located, are determined as the two combined subloops, and the two no-load travels corresponding to the element are deleted during the subloop merging process. After the two subloops are merged, the subloop merging matrix will be rebuilt. If there are no zero elements in the matrix, continue with the above steps until there are no more subloops. For example, in the example shown in Figure14, the optimal assignment scheme determines four subloops, namely, R3⟶S1⟶R3, SC1, R2⟶R4⟶R2, SC2, S2⟶S3⟶S2, SC3, and SP⟶R1⟶SP, SC4, and there is no zero element in the subloop merging matrix constructed by these 4 subloops. According to the minimum merging cost heuristic rule, SC1 and SC3 are merged first. The deleted no-load travels are R3⟶S1 and S2⟶S3, and the merged subloop is R3⟶S3⟶S2⟶S1⟶R3SC5. Then, three subloops, namely, SC5, SC2 and SC4, construct the subloop merging matrix again, and there is still no zero element in the matrix. SC5 and SC2 are merged according to the minimum merging cost heuristic rule. The deleted no-load travels are S1⟶S2 and R2⟶R4, and the merged subloop is R3⟶S3⟶S2⟶R4⟶R2⟶S1⟶R3 (SC6). There is still no zero element in the subloop merging matrix constructed by SC6 and SC4. The last two subloops are merged according to the minimum merging cost heuristic rule. The deleted no-load travels are R1⟶SP and S1⟶R3, and the merged loop is SP⟶R1⟶R3⟶S3⟶S2⟶R4⟶R2⟶S1⟶SP (see Figure 15).Figure 15
Loops after merging with minimum merging cost heuristic rules: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.In summary, after introducing the subloop equivalent merging algorithm and the minimum merging cost heuristic rule, the steps of the assignment based heuristic algorithm are as follows:Step 0: According to the bipartite graph definition mentioned above, the vertex setsV1 and V2 including the start and end points of the stacker and the start and end points of the load travels are created.Step 1: The adjacency matrix of bipartite graph is constructed according to the no-load travel time defined in Table1.Step 2: The Hungarian algorithm is used to solve the optimal assignment scheme of adjacency matrix, and the no-load travel is selected by the optimal assignment scheme.Step 3: The load travel is connected in series according to the selected no-load travel, and the number of subloops is determined.Step 4: If there is no subloop, sort the S/R requests according to the optimal assignment scheme, and go to Step 10.Step 5: The subloop merging matrix shown in Figure12 is constructed based on the determined subloops.Step 6: Check whether there are zero elements in the subloop merging matrix.Step 7: If the subloop merging matrix contains zero elements, the merging blocks are sorted according to the number of zero elements in the merging block, and the subloops are merged equivalently according to the sorting order, and the optimal assignment scheme is updated, and go to Step 9.Step 8: After traversing all the elements in the subloop merging matrix, the element with the smallest time increment is selected, and the two subloops corresponding to the element are merged according to the minimum merging cost heuristic rule, and the optimal assignment scheme is updated.Step 9: Count the number of subloops composed of no-load travel and load travel in the updated optimal assignment scheme, and go to Step 4.Step 10: Calculate the no-load travel time of the obtained S/R requests sequence.


## 3.1. Algorithmic Idea

According to the TSP model built in Section2, each node in the model represents an S/R request. Under the condition that the start location and destination location of each S/R request are known, if the initial point returned by the stacker is assumed to be EP, then each vertex in the TSP model can be divided into two vertices, and the assignment problem (AP) we constructed is as follows. The constructed bipartite graph is represented as G=V1,V2,E. V1 is composed of the start points of m+n+1 no-load travels in the tour including the end point of the storage requests SL1,…,SLm, the end point of the retrieval requests RO1,…,ROn, and the start point of the stacker SP, and V1 is defined as the set of people in the AP. V2 is composed of the end points of m+n+1 no-load travels in the tour, including the start point of the storage request SI1,…SIm, the start point of the retrieval request RL1,…RLn, and the end point of the stacker EP, and V2 is defined as the set of tasks in the AP. The set E is composed of edges between any vertex in V1 and any vertex in V2. The cost of any edge is equal to the no-load travel time. E is defined as the time for each person to complete each task in the AP. The time of no-load travel is defined in Table 1. The edge with value ∞ represents the prohibited travel, and prohibited travel is omitted in bipartite graph.Table 1
Costs related to edges in the sequencing problem.
FromToCostSPSIitSP,SIi,i=1,…,mSPRLjtSP,RLj,j=1,…,nSPEP∞SLi′SIitSLi′,SIi,i=1,…,m,i′=1,…,m,andi≠i′SLi′RLjtSLi′,RLji′=1,…,m,j=1,…,nSLi′SIi∞,i=1,…,m,i′=1,…,mandi=i′SLi′EPtSLi′,EP,i′=1,…,mROj′SIitROj′,SIi,i=1,…,m,j′=1,…,nROj′RLjtROj′,RLj,j=1,…,n,j′=1,…,nandj≠j′ROj′RLj∞,j=1,…,n,j′=1,…,nandj=j′ROj′EPtROj′,EP,j′=1,…,nIn addition, each task in the AP can only be completed by one person, and the constraint that each person can only undertake one task is equivalent to constraints (2) and (3) in the TSP model. Then, the minimum edge cover of bipartite graph is the assignment scheme of AP.According to the above rules, we construct a bipartite graph with two storage requests and two retrieval requests (see Figure3) and arbitrarily give an assignment scheme as shown in Figure 4(a). According to the reverse rule of constructing bipartite graph, the vertices in V1 and V2 of Figure 4(a) are combined into the S/R requests node and the start point of the stacker. According to the definition of edge in Table 1, there is no edge between the start location and the destination location of the same S/R request and between SP and EP. Therefore, the edges in the assignment scheme are not lost in the process of vertex merging. Since the assignment scheme covers all the vertices in V1 and V2, and each vertex in V1 and V2 has only one edge connected, each merged S/R request node has two edges connected as shown in Figure 4(b). By merging the same edges in Figure 4(b), we can get a node coverage scheme with multiple disjoint subloops, and the covered nodes include all the S/R request nodes and the start point of the stacker as shown in Figure 4(c). The set of edges in Figure 4(c) is exactly the same as that in Figure 4(a). Therefore, a node traversal scheme with multiple disjoint subloops of TSP can be found according to the above method, and vice versa. In conclusion, our AP has the same solution space as the TSP with subloop relaxation.Figure 3
Bipartite graph with two storage requests and two retrieval requests.Figure 4
Solution of TSP with subloop relaxation transformed from assignment scheme. (a) Assignment scheme. (b) Node merging. (c) Solution of TSP problem with subloop relaxation.
(a)(b)(c)Based on the above analysis, although the optimal assignment scheme, which is a node coverage scheme with multiple disjoint subloops, may not satisfy constraint (4), if we can find the combination scheme of subloops without increasing the no-load travel time, we can obtain the optimal solution of TSP problem. Due to the same specifications of the shelf in AS/RS, and the constant running speed of the stacker in the horizontal and vertical directions, with the increase of the size of the S/R requests sequence, there is a great probability that an edge with the same no-load running time exists in different subloops. Therefore, in the large-scale S/R requests sequence, there is a great probability that an equivalent merging scheme of subloops exists. In order to show the association between the optimal solution of the AP and the optimal solution of the TSP, we give the following theory for three cases: there is no subloop, there is equivalent merging subloop, and there is no equivalent merging subloop.Definition 1.
The scale of TSP refers to the number of load travels plus 1 in the optimization problem of S/R requests sequence.Definition 2.
The scale of AP refers to the number of people or tasks.Definition 3.
In an AP, assigning a task to a person is called an assignment pair, and in the optimal solution of an AP, the number of assignment pairs is equal to the scale of the AP.Theorem 1.
If the scales of the TSP and the AP are equal, then the number of edges in the optimal solution of the TSP is equal to the number of assignment pairs of the AP.Proof.
It can be concluded from Definition1 that there are N-1load travels for the TSP with size N. Departing from the start point of the stacker, one edge is added before the first load travel is performed, and N-2 edges will be generated after the remaining load travels have been completed. Finally, another edge is needed when returning to the initial point from the position, where the loading travel is completed. Then, all feasible solutions of TSP contain N edges. Since the feasible solution contains the optimal solution, there are also N edges in the optimal solution. According to Definition 3, the number of assignment pairs is N in the optimal solution of the AP with size N. Therefore, Theorem 1 holds.Corollary 1.
For an AP and a TSP with the same scale, under the condition that one person only completes one task, the optimal solution of the AP corresponds to the optimal solution of the TSP with the same scale if the no-load travels that correspond to the assignment pairs in the optimal solution of AP and the load travels that correspond to the S/R requests sequence do not constitute a subloop.Proof.
It can be concluded from Definition3 that an assignment pair corresponds to a no-load travel, and the optimal solution of AP is the combination scheme with the minimum total time among all the combination schemes of no-load travels. One person completes only one task means that the start point and end point of each no-load travel are connected with different load travels and connected with only one load travel. It can be concluded from Theorem 1 that the numbers of no-load travels in the optimal solution of AP and TSP with the same scale are equal. If the no-load travels that correspond to the assignment pairs in the optimal solution and the load travels do not constitute a subloop, the N assignment pairs in the optimal solution of AP with scale N can connect the N load travels in series successively to form a path that begins and ends at the start location and ensure that each vertex is visited only once. Therefore, the optimal solution of AP is also the optimal solution of TSP.Corollary 2.
If the load travels corresponding to the S/R requests and the no-load travels corresponding to the assignment pairs in the optimal solution of AP constitute at least two subloops, and there exists a subloop merging scheme, which does not change the task completion time of the AP, then the optimal solution of AP is also the optimal solution of TSP.Proof.
If the load travels corresponding to the S/R requests and the no-load travels corresponding to the assignment pairs in the optimal solution of AP constitute at least two subloops, then load travels and no-load travels will constitute two types of paths. One is the subloop containing the start and end points of the stacker and another is the subloop that does not contain the start and end points of the stacker. Figure5(a) shows the subloop SC1 that contains the start and end points of the stacker and the subloop SC2 that does not contain the start and end points of the stacker. In Figure 5(b), no-load travel Ek that connects A∈EP,SL1,…SLm,RO1,…ROn and B∈SP,SI1,…SIm,RL1,…RLn and no-load travel El that connects C∈SP,SI1,…SIm,RL1,…RLn and D∈EP,SL1,…SLm,RO1,…ROn are deleted, while no-load travel Ek′ that connects A and C and no-load travel El′ that connects B and D are added. A new tour is formed by the above operation, as shown in Figure 5(c). If the sum of travel times of no-load travels Ek and El is equal to the sum of travel times of no-load travels Ek′ and El′, then the sum of no-load travel time tA,C+tD,B in the tour of Figure 5(c) is equal to the sum of no-load travel time tA,B+tD,C in Figure 5(a). The other no-load travel times in SC1 and SC2 remain unchanged. Therefore, when the subloops are merged, the sum of the no-load travel time of the new tour after merging is equal to the sum of the no-load travel time of subloop SC1 and SC2. The merger of more subloops without the start and end points of the stacker can be proved in the same way. According to the equivalent merging process of subloops, all of the load travel vertices involved in the subloop merging process can be accessed only once, and the time does not change. Therefore, the optimal solution of AP formed by merging subloops is also the optimal solution of TSP.Figure 5
Process diagram of subloops merging. (a) Examples with subloops. (b) Merging scheme of subloops. (c) Loop formed with merging.Corollary 3.
If the load travels corresponding to the S/R requests and the no-load travels corresponding to the optimal solution of the AP constitute at least two subloops, and there is no subloop merging scheme, which does not change the task completion time of the AP, then the subloop merging scheme with the smallest task completion time increment is selected to merge the subloops one by one until all subloops are merged, and the solution of AP after subloop merging is also the optimal solution or suboptimal solution of TSP.Proof.
According to the proof of Corollary2, the merging of subloops needs to delete two existing no-load travels and generate two new no-load travels at the same time. When there is no equivalent merging scheme, the no-load travel time will be increased after the merging of subloops. The increase of no-load travel time will bring two possibilities. One is that the no-load travel time of the merged loop is equal to the time of the optimal solution of TSP (as shown in Table 2). The total time of no-load travels corresponding to the optimal solution of the AP, which is constituted by the start and end points of the seven load travels in Table 2 and the start and end points of the stacker, is 162.8 seconds, and three subloops are formed (see Figure 6(a)). The three subloops are merged twice according to the minimum cost rule and form a tour (see Figure 6(b) and Figure 6(e)), and the no-load travel time is increased by 4.6 seconds and 25.8 seconds, respectively. The sum of no-load travel time of the tour is 193.2 seconds, which is equal to the time of the optimal solution of TSP obtained by enumeration method. Another is that the no-load travel time of the merged loop is larger than the time of the optimal solution of TSP (as shown in Table 3). The total time of no-load travels corresponding to the optimal solution of the AP, which is constituted by the start and end points of the nine load travels in Table 3 and the start and end points of the stacker, is 231.2 seconds, and three subloops are formed (see Figure 7(a)). The three subloops are merged by equivalent and minimum cost rules and form a tour (see Figures 7(b) and 7(e)). The minimum cost merging increases the no-load travel time by 10 seconds, and the sum of no-load travel time of the tour is 241.2 seconds, which is 1.4 seconds longer than the time of the optimal solution of TSP obtained by enumeration method. Therefore, the optimal or suboptimal solution of TSP can be found by merging the minimum cost subloops.Table 2
An example of the optimal solution of TSP obtained by minimum cost merging.
Load travelsNo-load travels determined by assignmentSubloopsNumberStart pointEnd pointColumnLayerColumnLayerSP/EP101——SP ⟶ 5SC113134015 ⟶ EPSC124845011 ⟶ 6SC233013836 ⟶ 4SC243513724 ⟶ 3SC2551933 ⟶ 1SC262324012 ⟶ 7SC373925017 ⟶ 2SC3Note. The horizontal speed and vertical speed of stacker are 1.4 s/column and 6 S/layer, respectively.Figure 6
Minimum cost merging process of subloops of the example shown in Table2. (a) Three subloops determined by assignment. (b) Minimum cost merging scheme. (c) New subloops after minimum cost merging. (d) Minimum cost merging scheme. (e) Tour after minimum cost merging.Table 3
An example of the suboptimal solution of TSP obtained by minimum cost merging.
Load travelsNo-load travels determined by assignmentSubloopsNumberStart pointEnd pointColumnLayerColumnLayerSP/EP101——SP ⟶ 6SC112944016 ⟶ 2SC12512152 ⟶ 5SC134144515 ⟶ 7SC143514937 ⟶ EPSC151722511 ⟶ 4SC26512254 ⟶ 9SC271511839 ⟶ 1SC284535013 ⟶ 8SC393754518 ⟶ 3SC3Note. The horizontal speed and vertical speed of stacker are 1.4 s/column and 6 S/layer respectively.Figure 7
Equivalent merging process of subloops of the example shown in Table3 (a) Three subloops determined by assignment. (b) Equivalent merging scheme. (c) New subloops after equivalent merging. (d) Minimum cost merging scheme. (e) Tour after minimum cost merging.


## 3.2. Algorithmic Design

The stacker starts from the start pointSP and returns to the start point after completing all S/R requests. We mark the end point as a virtual point EP. Based on Corollary 1, we propose a heuristic algorithm based on assignment. The algorithm consists of five steps: constructing bipartite graph, creating adjacency matrix, solving the optimal assignment scheme, determining the load travel corresponding to the vertex of serial S/R requests, and sorting the S/R requests sequence.Figure8 shows an example with four storage requests and three retrieval requests. The start and end points of each S/R request are the start and end points of load travel. First, we construct the bipartite graph corresponding to Figure 8 according to the bipartite graph defined in section 3.1 (see Figure 9).Figure 8
An example of four storage requests and three retrieval requests: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively.Figure 9
Bipartite graph of four storage requests and three retrieval requests.The adjacency matrix is created based on the constructed bipartite graphG and the defined no-load travel time. The column index of the matrix corresponds to the serial number of the S/R requests, and the last column is the virtual end point EP. The row vector component of the first line in the matrix represents the running time from the start point of the stacker to the start point of each load travel, and the time arrived to EP is ∞, which is expressed by a relatively large number. The component of the remaining row vector in the matrix represents the running time of the stacker from the end point of the load travel to the start point of other load travels and EP, and the time to reach the end point of the current load travel is ∞, which is represented by a relatively large number. The row index in the matrix is 1 larger than the serial number of the S/R request.Hungary algorithm is applied to solve the adjacency matrix, and the optimal assignment scheme of bipartite graph shown in Figure9 is obtained. In bipartite graph, V1 is composed of the end point of the load travel and the start point of the stacker, and V2 is composed of the start point of the load travel and the virtual end point of the stacker. Therefore, the edges determined by the optimal assignment scheme are all no-load travel, and the directions are all from the nodes of V1 to the nodes of V2. According to the corresponding relationship between the serial number of S/R requests and the row and column index in the adjacency matrix, the no-load travels determined by the optimal assignment scheme in Figure 9 are SP⟶R3, S1⟶R1, S2⟶S4, R1⟶S3, S3⟶R2, R2⟶S2, S4⟶EP, R3⟶S1.Starting from the start locationSP of the stacker, the subsequent S/R requests are determined according to definite no-load travel. At the same time, the definite S/R requests are marked in the S/R requests sequence, and then starting from the definite end location of the S/R requests, the next S/R request is found according to the definite no-load travel and marked until the virtual end of the stacker is found. If the traversal of all the S/R requests nodes is not completed after finding EP, the first unmarked S/R request is found in the S/R requests sequence and starts from the destination corresponding to this S/R request. The above process is repeated until the traversal of all the S/R request nodes is completed. If the no-load travel and S/R requests do not constitute multiple subloop, then starting from SP and finding EP according to the optimal assignment scheme, the traversal of all S/R requests nodes is completed, and the traversal order of all the S/R requests nodes is the optimal solution of the optimization problem of S/R requests sequence. The no-load travel and S/R requests determined by the corresponding optimal assignment scheme of the example shown in Figure 8 do not constitute multiple subloops, and the optimal execution sequence of S/R requests sequence determined by the optimal assignment scheme is shown in Figure 10.Figure 10
Optimal solution of execution sequence of S/R requests sequence: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.However, when the no-load travel determined by the optimal assignment scheme and the load travel constitute multiple subloops (as shown in Figure11), series connection of all load travels along determined no-load travel by the stacker cannot form a tour; that is, the sequencing of all S/R requests cannot realize. An equivalent merging algorithm of subloops based on Corollary 2 will be introduced in the next section. The algorithm is embedded in the heuristic algorithm based on assignment. The subloops are merged without changing the total time of the no-load travel, and a tour contacting all load travels is formed.Figure 11
An example with two subloops: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.When the no-load travel determined by the optimal assignment scheme is in series with the load travel, if multiple subloops are formed, then the execution order of the determined S/R requests sequence violates Constraint (4) in the given model. In order to eliminate the subloops without increasing the operation time of S/R requests sequence, we propose the subloop equivalent merging algorithm to improve the method of concatenating S/R requests nodes. This algorithm is used to consummate the method of connecting S/R request nodes in series. It is connected with the optimal assignment scheme in the assignment based heuristic algorithm and used to solve the following three problems in turn: determining the subloop, constructing the subloop merging matrix, and subloop merging. Firstly, the optimal assignment scheme is used to determine the subloop composed of no-load travel and load travel, so that each load travel (including the start point of the stacker) is connected with the no-load travel determined by the optimal assignment scheme (see Figure 11). There are two subloops in Figure 11, namely, SC1 and SC2. The subloop SC1 is S1⟶R2⟶R3⟶S1 and the subloop SC2 is SP⟶S3⟶R1⟶R4⟶S2⟶SP. We can implement the sort of S/R requests through the equivalent merging of subloops (Corollary 2 has been proved). The subloop merging matrix is used to record the merging scheme of any two subloops. Figure 12 shows the subloop merging matrix with three subloops. The element in the matrix represents the time change after the merging of the subloops that do not contain the start point of the stacker with any other subloops, and its value is the time of the no-load travel corresponding to the two newly generated edges minus the time of the no-load travel corresponding to the original two edges. Taking Figure 5(b) as an example, the time change is dkl after merging of SC1 and SC2, and its value is tA,C+tD,B−tA,B−tD,C. The element with zero value is called zero element, and the merging scheme corresponding to zero element is a subloop equivalent merging scheme. In the subloop merging matrix, it is forbidden to merge any two no-load travels in the same subloop, which is expressed as ∞. In addition, we define the dashed box in the subloop merging matrix as merging block. Each merging block corresponds to two subloops, and the number of elements in the merging block represents the number of merging schemes corresponding to the two subloops.Figure 12
Subloop merging matrix with three subloops.When the subloop merging matrix contains zero elements, the equivalent merging of two subloops corresponding to zero elements can be realized. When the matrix contains multiple zero elements, the merging blocks are taken as units firstly and are sorted according to the number of zero elements. Then, the merging block with the least zero elements is selected, in which all zero elements are picked, and the number of zero elements on the row and column of each zero element is counted and sorted. The two no-load travels corresponding to the zero element with the minimum number in the statistical results are deleted in the merging of subloops. The subsequent merging process of subloops can be found in the proof process of Corollary2. After a subloop is merged, the elements on the row and column where zero element with the minimum number in the statistical results in the merge block is located are deleted. Repeat the above steps until there are no more subloops. Figure 11 is an example with two subloops. In the merging process of SC1 and SC2, the no-load travel R2⟶R3 in SC1 and the no-load travel S2⟶SP in SC2 are deleted, and two new no-load travels S2⟶R3 and R2⟶SP are selected, and the tour formed after merging is SP⟶S3⟶R1⟶R4⟶S2⟶R3⟶S1⟶R2⟶SP (see Figure 13).Figure 13
An example of subloops after equivalent merging: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.Considering that the optimal assignment scheme may construct multiple subloops, subloop equivalent merging algorithm is introduced. By adjusting the no-load travel equivalently, multiple subloops are merged into a time invariant tour. The premise of equivalent merging of subloops is that there are zero elements in the merging matrix of subloops. However, we do not know whether the constructed subloop merging matrix contains zero elements. If the no-load travel determined by the optimal assignment scheme forms multiple subloops when concatenating with the load travel, and there are no zero elements in the subloop merging matrix, that is, there is no equivalent subloop merging scheme (as shown in the example in Figure14), then it is impossible to get the execution sequence of S/R requests that satisfy Constraint (4) through the subloop equivalent merging algorithm. To solve this problem, we propose the minimum cost heuristic rule to merge the subloops and eliminate multiple subloops without equivalent merging scheme.Figure 14
An example of minimum cost merging with four subloops: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.In the process of subloops merging, two no-load travels should be deleted, and two new no-load travels should be selected at the same time. Since the two newly selected no-load travels and the existing no-load travels may form an equivalent merging scheme, in order to avoid omitting the equivalent merging scheme, the minimum merging cost heuristic rule requires that only two subloops be merged at a time, and the two subloops with the minimum time increment of no-load travels are required. The minimum merging cost heuristic rule is a supplement to the subloop equivalent merging algorithm, and its general idea is as follows. If there is no zero element in the subloop merging matrix, all the elements in the subloop merging matrix are traversed, and the element with the smallest time increment is selected. The two subloops corresponding to the merging block, where the element is located, are determined as the two combined subloops, and the two no-load travels corresponding to the element are deleted during the subloop merging process. After the two subloops are merged, the subloop merging matrix will be rebuilt. If there are no zero elements in the matrix, continue with the above steps until there are no more subloops. For example, in the example shown in Figure14, the optimal assignment scheme determines four subloops, namely, R3⟶S1⟶R3, SC1, R2⟶R4⟶R2, SC2, S2⟶S3⟶S2, SC3, and SP⟶R1⟶SP, SC4, and there is no zero element in the subloop merging matrix constructed by these 4 subloops. According to the minimum merging cost heuristic rule, SC1 and SC3 are merged first. The deleted no-load travels are R3⟶S1 and S2⟶S3, and the merged subloop is R3⟶S3⟶S2⟶S1⟶R3SC5. Then, three subloops, namely, SC5, SC2 and SC4, construct the subloop merging matrix again, and there is still no zero element in the matrix. SC5 and SC2 are merged according to the minimum merging cost heuristic rule. The deleted no-load travels are S1⟶S2 and R2⟶R4, and the merged subloop is R3⟶S3⟶S2⟶R4⟶R2⟶S1⟶R3 (SC6). There is still no zero element in the subloop merging matrix constructed by SC6 and SC4. The last two subloops are merged according to the minimum merging cost heuristic rule. The deleted no-load travels are R1⟶SP and S1⟶R3, and the merged loop is SP⟶R1⟶R3⟶S3⟶S2⟶R4⟶R2⟶S1⟶SP (see Figure 15).Figure 15
Loops after merging with minimum merging cost heuristic rules: the horizontal axis and the vertical axis represent the column and floor, where the stacker access point is located, respectively, the solid line represents load travel, and the dotted line represents no-load travel.In summary, after introducing the subloop equivalent merging algorithm and the minimum merging cost heuristic rule, the steps of the assignment based heuristic algorithm are as follows:Step 0: According to the bipartite graph definition mentioned above, the vertex setsV1 and V2 including the start and end points of the stacker and the start and end points of the load travels are created.Step 1: The adjacency matrix of bipartite graph is constructed according to the no-load travel time defined in Table1.Step 2: The Hungarian algorithm is used to solve the optimal assignment scheme of adjacency matrix, and the no-load travel is selected by the optimal assignment scheme.Step 3: The load travel is connected in series according to the selected no-load travel, and the number of subloops is determined.Step 4: If there is no subloop, sort the S/R requests according to the optimal assignment scheme, and go to Step 10.Step 5: The subloop merging matrix shown in Figure12 is constructed based on the determined subloops.Step 6: Check whether there are zero elements in the subloop merging matrix.Step 7: If the subloop merging matrix contains zero elements, the merging blocks are sorted according to the number of zero elements in the merging block, and the subloops are merged equivalently according to the sorting order, and the optimal assignment scheme is updated, and go to Step 9.Step 8: After traversing all the elements in the subloop merging matrix, the element with the smallest time increment is selected, and the two subloops corresponding to the element are merged according to the minimum merging cost heuristic rule, and the optimal assignment scheme is updated.Step 9: Count the number of subloops composed of no-load travel and load travel in the updated optimal assignment scheme, and go to Step 4.Step 10: Calculate the no-load travel time of the obtained S/R requests sequence.


## 4. Experimental Results

Table4 shows the experimental results of assignment based heuristic sorting algorithm and enumeration sorting algorithm. The first column shows the number of S/R requests received by the system. The second column shows the no-load travel running time of the stacker for the best sequence found by the enumeration sorting algorithm. Note that the optimal sequence obtained by the algorithm is the real optimal solution of each test case. The third column shows the computation time of the enumeration sort algorithm (on a 2.5 GHz core (TM) i5 machine). The fourth column shows the no-load travel running time of the stacker of the best sequence found by the proposed assignment based heuristic sorting algorithm. The fifth column shows the computation time of the assignment based heuristic sorting algorithm (on a 2.5 GHz core (TM) i5 machine). The sixth to eighth columns show the number of subloops, the equivalent merging times of subloops, and the minimum cost merging times of subloops generated by the proposed heuristic sorting algorithm based on assignment. The ninth column shows the time difference of no-load travel running time of the stacker between the optimal sequence generated by the enumeration algorithm and the assignment based heuristic algorithm.Table 4
Comparisons of unload times between EA and proposed method for small-scale problem.
N_rEnumerationAssignmentDiff1T_NLaCPUT_NLbCPUN_SLEMTMinMT7177.80.016177.80.00620107188.20.004188.20.00300007181.80.015181.80.00331107244.80.016244.80.00421007208.20.015208.20.00400007193.20.016193.20.00430207168.60.016168.60.00331107249.60.015249.60.00320107167.40.016167.40.00430207203.00.015203.00.00221008213.00.043213.00.00420108219.80.045219.80.00400008301.40.054301.40.00421008210.40.035210.40.00741208238.40.047238.40.00231108220.80.062220.80.01600008246.40.046246.40.01632008275.80.047275.80.00200009243.20.330243.20.00831109230.60.323230.60.00442109255.60.323255.60.00220109285.80.329285.80.00400009212.00.312212.00.00632009253.40.329253.40.00331109240.40.342240.40.00200009201.80.338201.80.00321009266.00.316266.00.00300009247.80.311247.80.00532009239.80.326241.20.0043111.410229.83.385229.80.016320010292.83.229292.80.003000010232.43.245232.40.016311010349.03.198349.00.002210010271.03.213271.00.002311010332.43.229332.40.002210010291.63.230291.60.015320010272.63.229272.60.002210010280.83.182280.80.015000010241.83.244241.80.012302010251.63.354251.60.015311011317.449.134317.40.016421011243.451.510243.40.016311011286.245.344286.20.015210011267.841.389267.80.016311011283.248.496283.20.015311011267.842.226267.80.016311011283.249.931283.20.015311011294.840.909294.80.015210011300.444.486302.00.0153111.6Note. Five-layer double row shelf with 15 I/O depots, N_r: number of S/R requests; T_NL: no-load travel time of stacker (sec); CPU: computation time (sec); N_SL: the number of subloops; EMT: the equivalent merging times of subloops; MinMT: the minimum cost merging times of subloops; Diff1 = T_NLa − T_NLb.In the 49 test cases, the number of subloops is 0 for 10 cases. For the S/R requests sequence without subloops, the assignment based sorting algorithm connects all the S/R requests in series through the optimal assignment scheme, and the no-load travel time of the sorting sequence is equal to the optimal no-load travel time of the stacker found by enumeration algorithm. When the S/R requests connected in series by assignment schemes form multiple subloops, the assignment based sorting algorithm combines the subloops by equivalent merging and minimum cost merging. Among the 39 cases with nonzero subloops, 14 cases are merged into one tour only by equivalent merging, 7 cases are merged into one tour only by minimum cost merging, and 18 cases are merged into one tour by two methods. Compared with enumeration algorithm, the assignment based sorting algorithm can generate a sequence with the same no-load travel running time of stacker for each case when only equivalent merging method is used to merge subloops.When the minimum cost merging rule is used in the subloops merging process, the assignment based sorting algorithm generates two suboptimal solutions compared with enumeration algorithm in 25 test cases. In two examples of suboptimal solutions, the merging of subloops is realized by means of equivalent merging and minimum cost merging. Combined with Corollary1 and Corollary 2, the assignment based sorting algorithm can get the best sequence scheme when only the equivalent merging method is used to merge the subloops, and the number of subloops is zero. When the minimum cost rule is used to merge the subloops, the best sequence scheme can also be obtained in most cases, and the difference of no-load travel time of stacker between the suboptimal solution and the optimal solution is extremely small.In order to research the effectiveness of the proposed algorithm in large-scale S/R requests sorting problem, we increase the scale of the sequence. For the sequence with more than 15 S/R requests, the time of enumeration sorting algorithm is too long, so the experiment of enumeration sorting is not carried out. Table5 shows the experimental results of the nearest neighbor heuristic sorting algorithm and the assignment based heuristic sorting algorithm. The number of S/R requests sequences is in the first column. They are two to ten times the scale of the problems in previous experiments. The second column shows the empty running time of the stacker for the best sequence found by the nearest neighbor heuristic sorting algorithm. The third column shows the computation time of the nearest neighbor algorithm (on a 2.5 GHz core (TM) i5 machine). The ninth column and the tenth column are the performance comparison between the nearest neighbor heuristic sorting algorithm and the algorithm proposed in this paper.Table 5
Comparisons of unload times between NN and proposed method for large-scale problem.
N_rNearest neighborAssignmentDiff1Diff2 (%)T_NLaCPUT_NLbCPUN_SLEMTMinMT15458.20.0224429.20.01615458.20.0224296.3315382.00.0284366.60.01632015.44.2015355.20.0262339.40.06231115.84.6615513.60.0248444.60.0162106915.5215513.60.0268382.20.016210131.434.3815451.80.0287416.20.01600035.68.5515519.20.0291480.40.01521038.88.0815487.80.0285469.20.01632018.63.9615401.40.0279386.20.01531115.23.9415550.60.0261521.20.01600029.45.6420613.60.0268561.40.01632052.29.3020612.60.0259581.40.01621031.25.3720612.60.0268569.40.01621043.27.5920726.80.0261709.40.01500017.42.4520573.60.0223551.20.01632022.44.0620599.60.0272585.20.01621014.42.4620607.40.0249576.40.015000315.3820636.20.0259602.40.01631133.85.6130884.80.0351865.40.01621019.42.24301007.60.0335944.00.03121063.66.7430950.80.0373928.40.04721022.42.4130850.40.0395842.80.0313207.60.9030810.80.0362785.20.03132025.63.2630878.60.0332840.60.031210384.5230911.00.0387862.60.01521048.45.6130859.60.0462832.60.031210273.24501536.60.04421499.40.07832037.22.48501610.80.04181561.80.094320493.14501469.40.04241418.60.04700050.83.58501470.40.04551447.00.06321023.41.62501395.00.04481344.00.047210513.79501373.80.04721322.00.06321051.83.92501563.80.04751497.20.06221066.64.45501695.20.04561670.20.078210251.50501461.80.04291447.00.04721014.81.02501268.00.05051221.60.04721046.43.80802185.60.06112118.20.15632067.43.18802386.80.06682359.80.171311271.14802236.40.06342196.00.1421040.41.84802281.60.06022244.60.125000371.65802235.60.06362190.40.15621045.22.06802367.20.06292310.40.15621056.82.46802311.20.06952247.80.18732063.42.82802389.20.06152359.80.18732029.41.25802450.60.06582405.40.20321045.21.881002949.60.07482891.60.328320582.011003169.40.07583069.80.31221099.63.241003081.00.07463028.80.23421052.21.721002845.80.08372795.00.35932050.81.82Note. Five-layer double row shelf with 15 I/O depots; N_r: number of S/R requests; T_NL: no-load travel time of stacker (sec); CPU: computation time (sec); N_SL: the number of subloops; EMT: the equivalent merging times of subloops; MinMT: the minimum cost merging times of subloops; Diff1 = T_NLa − T_NLb; Diff2 = (T_NLa − T_NLb)/T_NLa.Among the 49 test cases, 45 cases obtained the best sequence of large-scale S/R requests by the optimal assignment scheme and equivalent merging subloops, and the remaining 4 cases were the sequences of large-scale S/R requests obtained by equivalent merging and minimum cost merging. With the increase of the scale of the S/R requests sequence, the probability of the subloops equivalent merging increases. Only a few cases do not have the subloops equivalent merging scheme. This is because, with the increase of the scale of the S/R requests sequence, the no-load travel in the subloop also increases, and the equivalent merging schemes in the constructed adjacency matrix increase correspondingly. Therefore, most of the large-scale S/R requests sequence cases can merge the subloops by equivalent merging to find the optimal sorting sequence of the S/R requests.Compared with the nearest neighbor heuristic sorting algorithm, the sorting algorithm based on assignment can generate better sorting sequence, which can save up to 34.38% of the no-load running time. When the S/R requests scale is 30 to 50, the no-load travel time can be saved by 3.23% on average. With the increase of the scale of the S/R requests, the calculation time of the assignment based sorting algorithm does not increase significantly. In the near-real-time (less than 0.4 seconds), a better sorting sequence for each test case is found.In order to make readers have a deeper understanding of the current status of related research fields, we compare the optimization method proposed in this paper with the existing optimization methods. Due to the differences of different optimization methods in storage system layout, stacker performance, and command cycle mode, it is difficult to fully reflect the advantages and disadvantages of various algorithms only through the calculation time of algorithm and the saved operation time comparing with the nearest neighbor algorithm. However, the comparison of the above performance indicators can partially or indirectly reflect the advantages and disadvantages of different algorithms. Based on this consideration, the performance comparison between the existing sorting algorithms for S/R requests and our algorithm is listed in Table6. In the scenarios of different number of I/O depot, different command cycle modes, and different scale of S/R request sequence, the completion time and the calculation time of S/R requests are compared between different algorithms and the nearest neighbor algorithm.Table 6
Comparisons of existing methods with the proposed method.
StudiesN_rN_dCRT_NNContrastive algorithmGAPAlgorithmT _ACPUGharehgozli et al. [27]201021113.10TPHA976.420.0177136.68 sGharehgozli et al. [27]501022730.60TPHA2325.70.0397404.90 sGharehgozli et al. [27]1001025406.32TPHA4650.20.1321756.12 sGharehgozli et al. [27]1501028006.24TPHA6965.10.29731041.14 sGharehgozli et al. [27]20010210692.10TPHA9190.70.54621501.4 sGharehgozli et al. [27]1001016312.60TPHA6130.30.1147182.30 sGharehgozli et al. [27]1001016219.10TPHA6197.70.094221.40 sVan den Berg and Gademann [28]10127.80PA7.3—0.5 UTVan den Berg and Gademann [28]201214.70PA14.0—0.7 UTVan den Berg and Gademann [28]401228.30PA27.1—1.2 UTVan den Berg and Gademann [28]1021or211.30PA11.1—0.2 UTVan den Berg and Gademann [28]2021or222.60PA22.4—0.2 UTVan den Berg and Gademann [28]4021or245.40PA45.0—0.4 UTGharehgozli et al. [27]1022544.69PA449.060.6195.63 sGharehgozli et al. [27]20221048.19PA820.9120.27227.28 sGharehgozli et al. [27]30221609.64PA1240.39187.04369.25 sGharehgozli et al. [27]40222146.66PA1633.73776.24512.93 sGharehgozli et al. [27]50222603.50PA2005.751811.57597.75 sPopovic et al. [21]1216343.60ISL312.84—30.76 sPopovic et al. [21]1216343.60BH307.81<135.79 sPopovic et al. [21]1216343.60GA282.21<2061.39 sPopovic et al. [21]2416660.87ISL593.20—67.67 sPopovic et al. [21]2416660.87BH588.66<1672.21 sPopovic et al. [21]2416660.87GA521.09<60139.78 sThis paper1515—800.78HA760.960.020439.82 sThis paper2015—1088.40HA1057.700.015830.70 sThis paper3015—1588.88HA1557.380.029131.50 sThis paper5015—2647.08HA2604.800.062642.28 sThis paper8015—4134.93HA4089.180.164645.76 sThis paper10015—5360.85HA5295.700.308365.15 sNote. N_r: number of S/R requests; N_d: number of I/O depots; CR: number of command cycle; T_NN: completion time obtained by nearest neighbor algorithm (sec); T_A: completion time obtained by specified algorithm (sec); CPU: computation time (sec); GAP: T_NN-T_A (sec); TPHA: Two-phase heuristic algorithm; PA: polynomial algorithm; ISL: improved shortest leg heuristic; BH: best heuristic; GA: genetic algorithm; HA: heuristic algorithm based on assignment.It can be seen from Table6 that various optimization algorithms can improve the completion time of S/R requests obtained by the nearest neighbor algorithm to varying degrees. This is because the nearest neighbor algorithm is a local optimal algorithm, while the other algorithms are global optimization algorithms, which can optimize the execution order of S/R requests from a global perspective and reduce the no-load travel time of the stacker. In addition, the heuristic algorithm has a good performance in computing time.


## 5. Conclusions

In this paper, we address the scheduling problem of large-scale S/R requests sequence in multi-I/O depots AS/RS, in which the load travel time of stacker is fixed, the goods can enter and exit the system through multi-I/O depots, and the stacker can load at most one cargo at any time. Each load travel is considered as an S/R requests vertex, and a special traveling salesman problem is constructed. By introducing the concept of assignment, the adjacency matrix for subloops merging is established, and the sorting method based on the optimal assignment scheme, the equivalent merging method of subloops, and the minimum cost merging method of subloops are proposed.Experimental results indicate their efficiency. Due to the particularity of the TSP, the sorting method based on the optimal assignment scheme can generate the best solution of the test case without subloops. The proposed equivalent merging method of subloops realizes the merging of subloops with equivalent merging scheme without increasing the no-load travel time. In the process of subloops merging, in order to merge the subloops that cannot be merged by equivalent merging method, the minimum cost merging method is also considered, and the proposed algorithm is modified according to the new subloops merging rules.



---

*Source: 6646180-2021-05-20.xml*