A scheduling optimization method for stacker path in double-ended compact storage system

Abstract

Given the low space usage rate of the traditional automated storage/retrieval system and the long aisle, it is easy for a stacker to take a long time to enter/leave the warehouse. Thus, a new type of double-ended compact storage system is proposed. This paper addresses the scheduling problem for the stacker to execute the single and dual commands mixed tasks in the system where the I/O ports are located at both ends of the aisle, and the power conveyor devices on the rack can meet the requirement of multi-depth storage and generate displacement. An improved shuffled frog leaping algorithm (ISFLA) is developed for the scheduling problem. In order to eliminate the disadvantages of local optimum and slow convergence in the standard shuffled frog leaping algorithm, a set of hybrid perturbation update methods are designed based on a role model learning strategy, and the feasibility of the improved algorithm is verified by a numerical simulation. The experimental results show that the solution quality and the convergence ability of the ISFLA are significantly improved, and it can effectively solve the stacker-scheduling problem in the double-ended compact storage system.

Keywords

Stacker warehouse double-ended compact storage system improved shuffled frog leaping algorithm storage efficiency

Introduction

As an important part of manufacturing enterprises, an automated storage/retrieval system (AS/RS) is an important factor to maintaining market competitiveness because of its accurate and fast warehousing management technology. With the continuous progress of intelligent warehousing technology, enterprises are constantly improving the work efficiency and intensity requirements of automated 3D warehouses. The increasing production demands are difficult to meet using the traditional warehousing system.¹ Moreover, the continuous expansion of urbanization has led to a continuous decline in land supply, increasing land and labor costs. All these factors prompt enterprises to seek more compact and efficient warehousing systems.² The emergence of the compact warehousing system effectively solves these limitations. The system still uses a traditional automatic stacker to complete the cargo storage/retrieval task, which is used to realize the horizontal and vertical movement of the goods. However, in the depth direction of a storage rack, there is a power conveyor device to help realize the deep displacement of the goods, which is different from the traditional AS/RS, which can only realize single-deep or double-deep storage. The compact AS/RS can realize the multi-depth storage of goods.³ This study reports a compact 3D warehouse considering a double-ended layout. Under the same space conditions, the system will have more storage units, lower cost, and higher flexibility and throughput. Therefore, it has been applied more widely.

Because of the novelty and complexity of the system, the research of many scholars at home and abroad on compact storage systems has primarily focused on model analysis^4–6 and rack design,^7,8 whereas the research on scheduling optimization is still in its infancy. As the most important transportation tool of the system out/in operation, the stacker has high practical value and research significance to optimize its scheduling to improve operational efficiency. The following can be performed by summarizing the literature on traditional AS/RS stacker scheduling to seek a research perspective for compact storage systems.

The research on stacker scheduling of traditional AS/RS primarily includes job path optimization and order task sequencing optimization. Hsu et al.⁹ established the optimization model of the job path of the stacker under the condition of different storage scales and order quantity and proposed that the order batching approach based on a genetic algorithm (GA) can effectively solve the large-scale picking optimization problem. Tanaka and Araki¹⁰ examined the routing problem for unit-load AS/RSs under the shared storage policy and proposed an algorithm based on a general mixed integer linear programming solver. Kung et al.¹¹ considered a shared aisle with multiple stackers as the primary research problem. The authors established a dynamic programming model with the shortest travel distance of the stacker. They used a fast order scheduling method to solve the problem, which improved the sorting efficiency of the system. Dornberger et al.¹² examined the optimal picking order sequence problem in AS/RS to minimize the stacker’s travel distance when performing a single command (SC) task and solved the problem by changing the selection method and introducing an elitism mechanism in the GA. Popović et al.¹³ examined an AS/RS with a triple-shuttle module in class-based storage and used GA to solve the order scheduling problem to minimize the stacker’s running time. Gharehgozli et al.¹⁴ examined the scheduling problem of out/in operations in AS/RS and adopted polynomial-time algorithms to minimize the total travel time of the stacker when performing dual command (DC) tasks. Yang et al.¹⁵ proposed a hybrid GA to solve the order task-sequencing problem in a dense mobile rack warehouse to achieve the shortest picking time for the stacker. In similar studies,^16–19 the job path optimization model of the stacker was established with the shortest travel distance or the shortest travel time as the scheduling index. The problem was solved using standard heuristic algorithms or integer linear programming solvers. The optimization process primarily considered the number of equipment configurations, order batching, and other related factors.

Although many researchers have achieved significant results in the stacker-scheduling problem and proposed many heuristic and meta-heuristic algorithms, the following issues persist:

Most research objects were traditional storage systems with single I/O ports. When the number of I/O ports is increased, the I/O ports of the materials are no longer unique, or the established model is no longer applicable when there is a new displacement in the rack depth direction.

The scheduling model only considers the SC task of the stacker or its DC task, and the operation efficiency of the stacker cannot be brought into full play when the number of tasks in the order is increased or the number of I/O tasks in the order is not equal.

The algorithms used in the study were basically standard heuristic algorithms, which can fall into “prematurity” and have poor robustness.

For the stacker-scheduling optimization problem of a double-ended compact storage system, this paper comprehensively considers the allocation of the I/O port and the displacement in the depth direction of the rack, establishes the scheduling time model for the stacker to perform the SC/DC mixed operation tasks, and designs a new shuffled frog leaping algorithm (SFLA). SFLA is a metaheuristic algorithm based on memetic evolution; its main advantages are fast convergence speed and effective algorithm structures involving local search and global information exchanges.²⁰ The algorithm has been widely applied to several optimization problems, including economic load dispatch,²¹ vehicle routing,^22,23 component sequencing,^24–26 and shop scheduling.^27–29 However, the initial solution will be distributed unevenly in the feasible region, resulting in a weaker global optimization ability, because the initial population of the SFLA is generated by a random method. In addition, only the worst individual frogs of the subpopulation are updated during the evolution process without considering the optimal frog position, and it is easy to fall into the local optimization. The wide applications of SFLA and related improvement strategies can help solve the stacker-scheduling optimization problem, which motivated us to consider the stacker-scheduling problem in a double-ended compact storage system and apply some new principles to design SFLA for the problem. Firstly, an iterative method for collectively generating new solutions is designed by introducing a model learning strategy, which generates an initial frog population with good fitness, and ensures the diversity of the population. A set of mixed perturbation update strategies are then designed by combining the model learning scheme to avoid the random updates that may occur in the worst frogs in the local search process. These strategies can improve the probability of obtaining high-quality solutions. Finally, the effectiveness and feasibility of ISFLA in time-efficiency and stacker-scheduling optimization are confirmed using simulation experiments.

The main contribution of this paper is to propose a new double-ended compact storage system and develop a new method to solve the stacker-scheduling optimization problem. The new system improves the storage space utilization and shortens the operational cycle, and the developed optimization method can accurately and quickly calculate the optimal path for the stacker to execute mixed operation tasks. The results obtained have great value and relevance in practical applications, which can guide managers to complete the layout design of the storage system and the planning of the stacker-scheduling path according to the storage environment and order information, and effectively improve storage efficiency.

The remainder of this paper is organized as follows. Section 2 describes the system model. Section 3 establishes the scheduling optimization model of the stacker. Section 4 designs an ISFLA to solve the model. Section 5 verifies simulation experiments, and the optimal scheduling path of the stacker is obtained using a numerical example. Finally, Section 6 gives a summary and further research directions.

System description and assumptions

System model

A double-ended compact AS/RS is composed of an automatic sorting subsystem (ASS), S/R machine subsystem (SMS), and compact rack subsystem (CRS). The ASS comprises RGVs, sorting platforms, and I/O ports, which are used mostly to sort outgoing unit loads or unit loads ready to be imported. The SMS responsible for storing and retrieving unit loads on the storage rack comprises an S/R machine and a straight guide rail. Finally, the CRS includes a compact storage rack and several storage units. Each storage unit has a power conveyor device, which primarily stores unit loads and moves them toward racks depth. The three subsystems work together to complete the load access tasks of the 3D warehouse. Figures 1 and 2 present this system.

Figure 1.

Overall view of a proposed double-ended compact warehouse.

Figure 2.

Top view of a proposed double-ended compact warehouse.

One aisle is produced for every two adjacent rows of racks in the system, and each end of the aisle is provided with an I/O port. The rack is designed with a compact storage unit, and each storage unit contains a power conveyor device, which can realize multi-depth storage and deep displacement of goods, as shown in Figure 3. Compared to traditional AS/RS, a double-ended compact 3D warehouse has the following advantages:

(1) High operation efficiency: The double-ended layout effectively reduces the walking time of the stacker in the aisle and improves the system’s operational efficiency.

(2) High storage density: A compact storage rack and power conveyor device design realizes multi-depth storage and expands the storage density of the system.

(3) Low input cost: The compact storage rack efficiently increases the storage density of the system while reducing the number of input stackers and the expense of using available land resources.

Figure 3.

Schematic of the power conveyor device.

Analysis of operation mode of stacker

The stacker is usually operated in two modes: SC and DC operation. The SC operation is the single operation of the stacker to complete one storage or retrieval in a single operation cycle, and the DC operation is the compound operation of completing the storage and retrieval of the warehouse.³⁰ Figures 4 and 5 show the two operation modes. The number of storage and retrieval jobs in batch I/O task orders is often not equal. Although the efficiency of DC operations is higher, the stacker inevitably has to execute some SC jobs. Therefore, to improve the operation efficiency further, it is necessary to consider planning a more appropriate DC/SC task queue to minimize the time required for the stacker to complete the task of leaving/entering the warehouse. Aiming at the double-ended compact AS/RS, this study proposes a DC/SC mixed operation mode that is more in line with actual production, establishes the stacker’s I/O job scheduling model, and conducts optimization research on the system I/O port allocation, job sequence, and scheduling path.

Figure 4.

Schematic diagram of the single command operation mode of the stacker.

Figure 5.

Schematic diagram of the dual command operation mode of the stacker.

Assumptions and explanations

Given the related problems and principles that should be followed in the operation scheduling of a stacker in a double-ended compact 3D warehouse, which is convenient for model construction and problem research, the following assumptions and explanations can be made:

(1) Considering the symmetry of the racks on both sides of the aisle, the modeling and scheduling optimization process of this study only analyzes the single side rack.

(2) The target goods take the same time to be transported from the external starting point to both I/O ports and also the same time to be transported from both I/O ports to the specified delivery point.

(3) Let $X$ denote the number of rack columns and $Y$ denote the number of rack layers. The rack has a total of $X \times Y$ grid units: let the grid unit have a column width of $l$ , layer height of $h$ , and depth length of $z$ , and each grid unit can store $k$ pieces of goods (Figure 6, $k = 5$ ). If the bottom of the left I/O port of the rack is defined as the coordinate origin, the coordinates of the left port can be expressed as $(0, 1)$ , the coordinates of the right port can be expressed as $(X + 1, 1)$ , and the coordinates of all goods spaces in the grid units of column $x$ and layer $y$ can be expressed as $(x, y)$ .

(4) The stacker is defined as a single load operation, and its horizontal running speed is $v_{x}$ , vertical running speed is $v_{y}$ , both directions are a constant speed and independent of each other, and the start/brake time and material loading/unloading time of the stacker are ignored.

(5) The running speed of the power conveyor device in the depth direction is defined as $v_{z}$ , which is also a constant speed. The stacker first arrives at the designated storage unit to perform the task, and then the conveyor device starts to transport the goods to the front of the storage unit. The stacker will produce a waiting time at this time, but the waiting time of the stacker will not be too long because the target goods are always in the front end of the storage unit or only one space behind, as shown in Figure 6; this time can be considered as the minimal fixed value.

Figure 6.

Schematic of the location of loads to be sorted.

From the above assumptions and explanations, the time required for the stacker to run from a storage unit location $P_{1} (x_{1}, y_{1})$ to a location $P_{2} (x_{2}, y_{2})$ can be expressed as

t (P_{1} P_{2}) = max {\frac{| x_{1} - x_{2} | l}{v_{x}}, \frac{| y_{1} - y_{2} | h}{v_{y}}}

(1)

The waiting time for the stacker after arriving at the designated storage unit is

t_{W} = \frac{z}{k v_{z}}

(2)

Optimization model of stacker-scheduling

Although there is a port at both ends of the warehouse for the stacker to access the material or cargo space, the corresponding I/O port is determined by the shorter travel time consumed by the stacker to perform the task, whether it is an SC or DC operation. Therefore, the total working time for the system to complete all order tasks can be defined as the sum of all SC and DC tasks completed by the stacker:

T = T_{SC} + T_{DC}

(3)

where $T$ is the total time it takes for the stacker to perform all ordered tasks; $T_{SC}$ is the time it takes for the stacker to perform all the SC tasks in order; and $T_{DC}$ is the time required for the stacker to perform all the DC tasks in order.

The time it takes for a stacker to complete an SC task can be expressed as

t_{SC} = t (P_{IOa} P_{1}) + t (P_{1} P_{IOb}) + t_{W}

(4)

where $t (P_{IOa} P_{1})$ is the time for the stacker to run from port $P_{IOa}$ to the $P_{1}$ storage unit; $t (P_{1} P_{IOb})$ is the time for the stacker to run to port $P_{IOb}$ after completing the storage or retrieval of materials from the $P_{1}$ location; and $t_{W}$ is the waiting time after the stacker reaches the $P_{1}$ location.

The time it takes for a stacker to complete a DC task can be expressed as follows:

t_{DC} = t (P_{IOa} P_{1}) + t (P_{1} P_{2}) + t (P_{2} P_{IOb}) + 2 t_{W}

(5)

where $t (P_{IOa} P_{1})$ is the time the stacker runs from the $P_{IOa}$ port to the $P_{1}$ storage unit; $t (P_{1} P_{2})$ is the time the stacker runs from the $P_{1}$ location to the $P_{2}$ location; and $t (P_{2} P_{IOb})$ is the time the stacker runs from the $P_{2}$ location to the $P_{IOb}$ port.

Assume there are m storage and n retrieval operations in a batch of order tasks, and $m \neq n$ then the stacker has $| m - n |$ SC tasks and $min {m, n}$ DC tasks, respectively. If $Z_{1} = | m - n |$ and $Z_{2} = min {m, n}$ , the time it takes for the stacker to perform all SC tasks can be expressed as

T_{SC} = \sum_{i = 1}^{Z_{1}} [t (P_{IOa} P_{i}) + t (P_{i} P_{IOb})] + Z_{1} t_{W}

(6)

where $t (P_{IOa} P_{i})$ is the time the stacker runs from the $P_{IOa}$ port to the $P_{i}$ storage unit; and $t (P_{i} P_{IOb})$ is the time the stacker runs to the $P_{IOb}$ port after completing the storage or retrieval of materials from the $P_{i}$ location.

Similarly, the time required for the stacker to complete all the DC tasks can be expressed as follows:

T_{DC} = \sum_{j = 1}^{Z_{2}} [t (P_{IOa} P_{2 j - 1}) + t (P_{2 j - 1} P_{2 j}) + t (P_{2 j} P_{IOb})] + 2 Z_{2} t_{W}

(7)

where $t (P_{IOa} P_{2 j - 1})$ is the time the stacker runs from the $P_{IOa}$ port to the $P_{2 j - 1}$ storage unit; $t (P_{2 j - 1} P_{2 j})$ is the time the stacker runs from the $P_{2 j - 1}$ location to the $P_{2 j}$ location; and $t (P_{2 j} P_{IOb})$ is the time the stacker runs from the $P_{2 j}$ location to the $P_{IOb}$ port.

To summarize, the stacker’s overall working time to complete all order tasks in batches is

\begin{matrix} T = T_{SC} + T_{DC} = \sum_{i = 1}^{Z_{1}} [t (P_{IOa} P_{i}) + t (P_{i} P_{IOb})] \\ + \sum_{j = 1}^{Z_{2}} [t (P_{IOa} P_{2 j - 1}) + t (P_{2 j - 1} P_{2 j}) + t (P_{2 j} P_{IOb})] \\ + (Z_{1} + 2 Z_{2}) t_{W} \end{matrix}

(8)

Therefore, when the double-ended compact 3D warehouse completes a batch of I/O orders, the optimal scheduling model of the stacker is as follows:

g (T) = min T

(9)

Subject to:

\begin{matrix} a = {\begin{matrix} 1, if \frac{x_{i}}{v_{x}} \leq \frac{lX}{2 v_{x}} \\ 2, if \frac{x_{i}}{v_{x}} \geq \frac{lX}{2 v_{x}} \end{matrix} \forall i \in {1, 2, \dots, Z_{1} + 2 Z_{2}} \end{matrix}

(10)

\begin{matrix} b = {\begin{matrix} 1, if \frac{x_{i}}{v_{x}} \leq \frac{lX}{2 v_{x}} \\ 2, if \frac{x_{i}}{v_{x}} \geq \frac{lX}{2 v_{x}} \end{matrix} \forall i \in {1, 2, \dots, Z_{1} + 2 Z_{2}} \end{matrix}

(11)

t_{w} \leq \frac{l}{v_{x}}

(12)

Z_{1} + 2 Z_{2} \leq kXY

(13)

Among them, equations (10) and (11) are the port selection constraints of the stacker, which indicates that the stacker performs the task from the left port when $a = 1$ or $b = 1$ , and the stacker performs the task from the right port when $a = 2$ or $b = 2$ . Equation (12) is the time constraint for the depth displacement of the power conveyor device, and equation (13) is the maximum number constraint of SC tasks and DC tasks.

Design of scheduling optimization algorithm for stacker

When examining the path optimization problem of the stacker in the double-ended compact storage system, the computational complexity increases with the existence of both SC and DC operation modes and the increase in the number of related equipment. Finding the optimal solution in such a search space is difficult using conventional methods. Some standard heuristic algorithms proposed for the traditional stacker system do not guarantee solution accuracy and optimization effect. Therefore, based on the established stacker-scheduling optimization model, the ISFLA is designed to solve the problem and combined with the system process simulation to identify the optimal path scheme of the stacker.

Shuffled frog leaping algorithm

SFLA imitates the communication mechanism within the frog population in the process of foraging and finds the best location of food through information sharing among groups to obtain the optimal solution to the optimization problem. After generating the initial population, all frog individuals are sorted according to the order of fitness values, and the optimal individuals in the population are recorded. The population is then divided into multiple subpopulations according to the grouping strategy, and the best and worst individuals in each subpopulation are simultaneously recorded. The local search strategy of the subpopulation uses the leapfrog update formula to optimize the worst individuals. When the number of local iterations is updated, all frog individuals in the population are reshuffled and sorted, and the subpopulations are divided again according to the grouping strategy. The cycle is alternated and finally realizes the global information exchange.

The grouping strategy of subpopulations is as follows:

JI = X (j + n * (i - 1)), i \in (1, 2, \dots, N), j \in (1, 2, \dots, n)

(14)

where JI is the frog individuals belonging to the i subpopulation; N is the number of subpopulations; n is the number of frogs in each subpopulation; $X = {X_{1}, X_{2}, \dots, X_{n \times N}}$ .

The worst individual update strategies in the subpopulation are as follows:

D_{i} = rand () * (X_{b} - X_{w})

(15)

D_{i} = rand () * (X_{g} - X_{w})

(16)

X_{w}' = X_{w} + D_{i}

(17)

X_{w}' = s_{min} + rand () * (s_{max} - s_{min})

(18)

where $D_{i}$ is the frog jump step length; $rand ()$ is a random real number evenly distributed between 0 and 1; $X_{b}$ is the best individual of the subpopulation; $X_{w}$ is the worst individual of the subpopulation; $X_{g}$ is the best individual of the whole population; $X_{w}'$ is the updated frog; and $s_{max}$ and $s_{min}$ are the maximum and minimum of fitness value, respectively. The worst frog individual is first updated according to equations (15) and (17), and if the fitness of the worst frog individual is not improved, it is updated according to equations (16) and (17). If the fitness of the worst frog individual is still not improved, a frog individual is randomly generated to replace the worst frog individual according to the equations (18).

Figure 7 presents the step flow of SFLA. The key steps include population initialization, subpopulation division, local search, and global information exchange.

Figure 7.

Flowchart of the shuffled frog leaping algorithm.

ISFLA

Based on the above description, the SFLA has a advantages of simple principle and exhibits ease of implementation. However, it has certain disadvantages such as slow convergence and easily falling into local optimization. The lack of a variation mechanism leads to a decrease in population diversity and reducing the probability of obtaining high-quality solutions. The local search only updates the worst individual frogs, and it needs to constantly adjust the number of iterations, resulting in the problem of slow convergence. To avoid these shortcomings, the ISFLA is proposed in this section. Furthermore, specific improvement strategies are presented.

Model learning strategy

The main principle of the model learning strategy is to allow poor individuals to learn from relatively better individuals to obtain an optimal fitness value. When considering several individuals in a population, the individuals with higher fitness value than that of the i individual are known as the role models of the i individual; all such role models together constitute the model group of the i individual. Consequently, the best individual in the population has no role model. The second-best individual has only one model in the population, and the worst individual cannot become a model. A frog individual $X_{i}$ randomly selects a role model from the model group to learn, which can have a beneficial impact on its own renewal. The selection of the model frog is shown below:

SI = ceil (rand () * (i - 1))

(19)

where $ceil ()$ is an upward rounding operation.

Differential perturbation update strategy

The introduction of the model learning scheme in the previous section shows that there is no model for the frog individuals with the best performance in the population. Therefore, this paper uses a differential perturbation update strategy (shown below) to update the optimal frogs in the subpopulation.

X_{b}' = X_{b} + rand () * (X_{g} - X_{b} + X_{rn 1} - X_{rn 2})

(20)

where $X_{b}'$ denotes the updated optimal frogs in the subpopulation, and $X_{m 1}$ and $X_{m 2}$ are two frogs randomly selected from the current subpopulation that satisfy $b \neq m 1 \neq m 2$ .

In equation (20), for the optimal frog in each subpopulation to assume a better position, using the mutation operator of differential evolution for reference, a differential vector related to the global optimal frog is added to the optimal frog feature vector in the subpopulation to form two groups of search methods based on differential mutations, one of which is guided by the global optimal frog $X_{g}$ . This can accelerate the convergence speed and improve the global search ability of the algorithm. The other group is guided by two frogs $X_{m 1}$ and $X_{m 2}$ , randomly selected from the current subpopulation. Their positions are used to map the optimal position of frogs in the subpopulation to improve the local search ability of the algorithm.

Direct perturbation update strategy

For the other frogs in the subpopulation, there are other models to learn from; thus, the direct perturbation update method shown below is used to update their position.

X_{i}' = X_{i} + (ran d_{1 \to d} () - 0.5) * (X_{g} - X_{i} + X_{SI} - X_{i})

(21)

where $X_{i}'$ is the updated nonoptimal frogs in the subpopulation, and $ran d_{1 \to d} ()$ is a random d-dimensional vector, wherein each dimension is a random number distributed uniformly between 0 and 1, and $X_{SI}$ stands for the model frog.

The direct perturbation update strategy is the fusion of two update methods based on local and global optimization in the standard SFLA. Based on equation (21), that the nonoptimal frog $X_{i}$ in the subpopulation is affected by itself, the global optimal frog $X_{g}$ and a model frog $X_{SI}$ selected from the current subpopulation. Through the direct weighting calculations of $X_{g}$ and $X_{SI}$ , $X_{i}$ is perturbed to search near $X_{g}$ and $X_{SI}$ in the solution space, enhancing the local search ability of the algorithm. The use of the model learning scheme ensures that $X_{i}$ can obtain the frog information which is better than its fitness value, avoid solely receiving the local or global optimal location information in the basic SFLA, and improve the population diversity, which is beneficial to the global search of the algorithm. Furthermore, $(ran d_{1 \to d} () - 0.5)$ can obtain a random vector whose values of all dimensions lie between −0.5 and 0.5. Using this value as a weight in the direct perturbation update strategy also increases the randomness of the frog updates; thus, the frogs can search for more locations in the solution space for each update.

Application of ISFLA in the stacker-scheduling optimization problem

Compared with the basic SFLA, the ISFLA creates a new way to generate new solutions within the subpopulation, thereby compensating for the defect wherein SFLA only updates the worst frog individuals in the local search, solving the problem of tedious updating steps, and increasing the probability of obtaining high-quality solutions. Simultaneously, as ISFLA does not need to set the number of iterations in the subpopulation or sort the frogs in the subpopulation, it reduces the computational complexity of the algorithm and improves its maneuverability.

Coding and decoding

When the above ISFLA is applied to the scheduling optimization problem of the stacker in the double-ended compact storage system, the task type must be coded before solving the problem. In this paper, the integer coding structure based on task number sorting is adopted, the storage tasks received by the stacker are numbered to form a coding section, and the retrieval tasks received by the stacker are numbered based on the storage task number to form another coding section. Any bit in the coding sequence represents a frog gene, and each gene consists of a set of numbers $(x, y, x')$ , where x, y, and z represents the rack column, rack layer, and I/O port of the rack, respectively, and $x' \in {1, 2}$ . The reasonable arrangement of coding sequences constitutes the solution space of the problem; thus, every state in the evolution of frogs corresponds to a scheduling scheme of the stacker, and each group of coding sequences is also a reflection of the advantages and disadvantages of stacker-scheduling schemes. Assuming that currently three storage tasks and two retrieval tasks must be performed, (1, 1, 1) indicates transporting the storage task numbered 1 from the left port to the storage unit with coordinates (1, 1); (6, 2, 2) indicates that the retrieval task numbered 4 will be transported from the storage unit (6, 2) to the right port, as shown in Figure 8.

Figure 8.

Coding mode.

Decoding is the process of finding a reasonable sequence of I/O tasks according to their numbering order and the coding information corresponding to each I/O task. First, the number “0” is used to constitute the number of retrieval tasks; all storage and retrieval tasks are then paired according to the port information, and a set of continuous I/O task numbers are formed. As shown in Figure 9, 1→4→3→5→2 is a reasonable sequence of operations for I/O tasks.

Figure 9.

Decoding mode.

Determine the fitness function

When ISFLA is used to solve the scheduling optimization problem of the stacker, the selection of a fitness function is made to evaluate the algorithm results simply and effectively. The fitness function is set to

f (i) = \frac{1}{g (T)}

(22)

Algorithm discrete operation

The stacker-scheduling problem of a double-ended compact storage system is a combinatorial optimization problem, and the solution space is discrete; thus, it is necessary to perform discrete operations on the update process of the algorithm when using ISFLA to solve the problem. The permutation sequences $(x_{k}, y_{k})$ , $k \in Z_{1}$ , and $(x_{l}, y_{l})$ , $l \in Z_{2}$ are introduced into the frog individual update formula, where $Z_{1}$ and $Z_{2}$ represent the number of SC and DC tasks, respectively, that the stacker must perform. The operation in the location update is given a new definition, and the following individual update formulas are obtained:

X_{b}' = X_{b} \oplus rand () * (X_{g} - X_{b}) \oplus rand () * (X_{rn 1} - X_{rn 2})

(23)

\begin{matrix} X_{i}' = X_{i} \oplus (ran d_{1 \to d} () - 0.5) * (X_{g} - X_{i}) \oplus \\ (ran d_{1 \to d} () - 0.5) (X_{SI} - X_{i}) \end{matrix}

(24)

where “⊕” is the combination of several permutation sequences; “−” is the position subtraction of two frogs, and the result is a set of permutation sequences; $rand ()$ and $ran d_{1 \to d} () \in [0, 1]$ are the truncation of permutation sequences of length d.

Steps of ISFLA for solving stacker scheduling

The steps of the ISFLA for solving the stacker-scheduling optimization problem are as follows:

Step 1: Set the parameters; initialize the coordinates of all I/O tasks; calculate the running time between the two coordinates of the stacker performing any set of incoming and outgoing tasks; generate the time matrix.

Step 2: Initialize the frog population, and each frog is a reasonable coding sequence of integers consisting of (m+n) I/O tasks.

Step 3: The fitness values $f (i)$ of all frogs are evaluated and arranged in descending order according to the fitness values.

Step 4: The frog population is divided into N subpopulations according to equation (14).

Step 5: The best individual $X_{b}$ and worst individual $X_{w}$ in the subpopulation are marked, and the frog individuals with the best fitness value are updated using equation (23).

Step 6: Establish the model group of all nonoptimal frog individuals; select the model frog by Formula (19), and update the nonoptimal frog in the subpopulation by equation (24).

Step 7: Cross-boundary limits are imposed on each frog according to the time matrix in Step 1.

Step 8: Evaluate the fitness of each frog and replace other frogs in the subpopulation with elite frogs.

Step 9: Re-shuffle all the updated frogs into the frog population.

Step 10: All frogs in the population are arranged in descending order according to the fitness value.

Step 11: Output the optimal solution.

Simulation experiment research

The simulation experiment was conducted by taking the 3D warehouse used in a carton factory as an example. The 3D warehouse adopts the above double-ended compact layout design, and each row of racks was composed of 12 floors, 60 columns, and a total of $12 \times 60 = 720$ storage units. There were five spaces on the power conveyor device of the storage units; that is, $720 \times 5 = 3600$ spaces can be stored in each row of racks. To verify the performance of the ISFLA, the location coordinates of 50 cargo sites were generated randomly to simulate the stacker-scheduling problem. The results were compared with the results of standard SFLA and GA. Table 1 lists the operating parameters of the double-ended compact storage system. Table 2 presents the coordinate information of the storage unit corresponding to the location of the goods. The coordinate attribute value: 0 is the storage operation command, and 1 is the retrieval operation command.

Table 1.

System operating parameters.

Parameter	Numerical value
l (m)	1
h (m)	1
z (m)	6
v_x (m/s)	2
v_y (m/s)	1
v_z (m/s)	1

Table 2.

Order task sequence and corresponding location coordinates.

No.	Coordinate	Command	No.	Coordinate	Command
12	(18, 8)	0	48	(11, 2)	1
36	(55, 11)	1	18	(46, 10)	0
9	(51, 7)	0	11	(58, 12)	0
24	(38, 4)	0	23	(26, 1)	0
1	(16, 7)	0	37	(37, 12)	1
45	(48, 5)	1	14	(3, 4)	0
29	(21, 4)	0	15	(17, 6)	0
38	(40, 7)	1	20	(30, 2)	0
7	(57, 5)	0	34	(58, 6)	1
40	(36, 6)	1	32	(29, 5)	0
33	(7, 3)	1	43	(39,9)	1
49	(29, 11)	1	17	(12, 9)	0
10	(55, 2)	0	30	(49, 3)	0
31	(44, 7)	0	8	(21, 8)	0
27	(32, 7)	0	6	(1, 12)	0
41	(29, 8)	1	42	(35, 8)	1
5	(9, 2)	0	13	(40, 6)	0
47	(9, 10)	1	46	(33, 3)	1
16	(39, 5)	0	50	(18, 2)	1
44	(18, 4)	1	28	(41, 6)	0
21	(25, 12)	0	2	(3, 8)	0
39	(15, 3)	1	22	(19, 5)	0
3	(50, 2)	0	35	(8, 6)	1
26	(43, 10)	0	19	(10, 8)	0
25	(22, 9)	0	4	(43, 7)	0

Optimal solution analysis

The experiments were conducted on 10, 20, 30, 40, and 50 order tasks an average of 30 times to explain the solving performance of ISFLA. The computer hardware configuration of the experimental platform is Intel Core i5-8300h 2.3 GHz 16 GB memory, which is performed under the Windows 10 operating system using the Matlab2018a development environment. The parameters of all algorithms are set as follows: population size was $F = 80$ and the number of iterations of population evolution was $η = 500$ . For ISFLA and standard SFLA, the number of subpopulations was $N = 8$ ; the maximum jump step size of a frog was $D_{max} = 2$ , and the number of iterations of the subpopulation was $η_{-} sub = 10$ . For GA, the crossover probability and mutation probability were $p_{c} = 0.95$ and $p_{m} = 0.05$ , respectively. Table 3 lists the experimental results, including the average picking time, optimal picking time, and average running time of each algorithm with different picking numbers.

Table 3.

Experimental results of the three algorithms under different numbers of tasks.

No. of tasks	Algorithm	Average picking time (s)	Optimal picking time (s)	Average running time (s)
10	GA	183.50	183.50	6.27
	SFLA	183.50	183.50	8.68
	ISFLA	183.50	183.50	5.15
20	GA	398.33	396.08	13.31
	SFLA	392.62	390.13	18.22
	ISFLA	377.74	377.02	9.79
30	GA	657.93	651.48	24.35
	SFLA	631.87	629.44	30.49
	ISFLA	585.01	584.39	19.27
40	GA	884.02	878.21	41.30
	SFLA	839.40	836.54	52.31
	ISFLA	774.08	773.26	30.62
50	GA	1113.15	1107.64	62.44
	SFLA	1042.41	1038.23	75.03
	ISFLA	949.92	948.80	43.19

Table 2 shows that the storage and retrieval operations are six and four, respectively, when the number of tasks is 10. That is, the batch of I/O tasks contains four DC and two SC tasks. The corresponding numbers of all storage and retrieval operations are ${12, 9, 24, 1, 29, 7}$ and ${36, 45, 38, 40}$ , respectively. The stacker-scheduling path under the batch I/O tasks is optimized, and the average and optimal picking times of the three algorithms are all 183.5 s.

However, as the scale of solving problems is increased, the solution quality of ISFLA is higher than that of SFLA and GA. When the number of tasks is 30, the average picking time of ISFLA is 46.86 s less than that of SFLA and 72.92 s less than that of GA (Table 3). When the number of tasks is 50, the average picking time of ISFLA is 92.49 s less than that of SFLA and 163.23 s less than that of GA. This shows that ISFLA has more advantages than SFLA and GA in solving the problem.

Furthermore, the running times of the three algorithms were compared. The running time of the algorithm is optimized because ISFLA overcomes the problem of tedious individual update steps in the standard SFLA and does not need to sort the frogs in the subpopulation. The average running time of ISFLA is shorter than that of SFLA and GA (Table 3), which shows that it can enhance the accuracy of the solution and ensure the speed of operation.

Convergence verification

To explain the solving characteristics of the ISFLA algorithm in more detail, the above scheduling optimization problem with 50 tasks was selected, and the number of iterations was 500. Figure 10 compares the operating processes of ISFLA, SFLA, and GA and the corresponding algorithm convergence diagram is drawn; $η$ is the number of iterations of the algorithm.

Figure 10.

Iterative curves of the three algorithms.

Compared to SFLA and GA, ISFLA has great advantages in the iterative rate and quality of the solution (Figure 10). The GA gets the optimal solution after 247 iterations, which isis 1108.32 s. The optimal solution of SFLA is 1039.09 s after 286 times of execution. The optimal solution of the ISFLA is 949.07 s after 187 s execution, and the fitness value is no longer reduced. ISFLA has a faster convergence speed, higher convergence accuracy, and higher quality solution than the other two algorithms.

Optimal scheduling path of stacker

Figure 11 shows the scheduling path of the stacker in random access mode and solved by three algorithms. The sequence of I/O tasks and ports corresponding to the path obtained by ISFLA is the optimal scheduling scheme, as shown in Table 4.

Figure 11.

Scheduling path diagram of the stacker: (a) scheduling path in the random access state, (b) scheduling path solved by GA, (c) scheduling path solved by SFLA, and (d) scheduling path solved by ISFLA.

Table 4.

I/O task sequence and its corresponding I/O port sequence.

I/O tasks sequence	I port	O port	I/O tasks sequence	I port	O port
21	1*		45		2*
37		2*	27	2*
11	2*		42		2*
36		2*	13	2*
26	2*		40		2*
49		1*	4	2*
5	1*		38		2*
48		1*	7	2*
22	1*		34		2*
39		1*	10	2*
29	1*		28		2*
44		1*	30	2*
14	1*		3	2*
33		1*	31	2*
2	1*		18	2*
35		1*	9	2*
17	1*		20	2*
47		1*	50		1*
8	1*		6	1*
41		1*	19	1*
25	1*		1	1*
43		2*	15	1*
24	2*		12	1*
46		2*	23	1*
16	2*		32	1*

1* and 2* in the table represent the left and right I/O ports, respectively.

After obtaining the optimal scheduling path of the stacker, the running sequence of the order task can be determined:

1*→21→37→2*→11→36→2*→26→49→1*→5→48→1*

→22→39→1*→29→44→1*→14→33→1*→2→35→1*→

17→47→1*→8→41→1*→25→43→2*→24→46→2*→16

→45→2*→27→42→2*→13→40→2*→4→38→2*→7→34

→2*→10→28→2*→30→2*→3→2*→31→2*→18→2*→9

→2*→20→50→1*→6→1*→19→1*→1→1*→15→1*→12

→1*→23→1*→32→1*.

The operation results of numerical simulation demonstrate that the stacker-scheduling optimization model established in this paper is suitable for the double-ended compact storage system, and the ISFLA can effectively solve the optimal task sequence problem for the stacker-scheduling path in the mixed operation mode.

Conclusions

This paper mainly presents a double-ended compact storage system and examines the stacker-scheduling optimization problem in the system. A scheduling optimization model for the stacker to execute DC/SC mixed tasks is established by analyzing the operation characteristics and actual workflow of related equipment, and the selection of the I/O port and the depth displacement of goods are comprehensively considered in the scheduling model, making the path optimization process of the stacker more reasonable. The ISFLA was designed to solve the existing problems, the update mode of only the worst frog individuals is changed in the standard SFLA, and a set of hybrid perturbation update methods are designed by combining a role model learning scheme; these changes improved the optimization performance and running efficiency of the algorithm. The simulation results show that ISFLA can get a satisfactory solution when considering different order scales, with good robustness. The superiority of ISFLA over SFLA and GA becomes increasingly prominent with the increasing scale of solving the problem, indicating that the improved algorithm can better meet the requirements of the stacker-scheduling tasks in the double-ended compact storage system.

Future research may be conducted on the following aspects. First, general cases with energy consumption and operating costs in the double-ended compact storage system may be worthy of consideration. Second, considering the acceleration and deceleration characteristics of related operating equipment in the scheduling model may get more accurate results. Third, a more effective solution can be further investigated for a more production task and batch I/O task sequence.

Footnotes

Handling editor: Chenhui Liang

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This article is supported by Zhejiang Science and Technology Plan Project (Grant No. 2018C01003), Natural Science Foundation of Zhejiang Province (Grant No. LQ22E050017), Postdoctoral Science Foundation of China (Grant No. 2021M702894) and Zhejiang Provincial Postdoctoral Science Foundation (Grant No. ZJ2021119).

ORCID iDs

Qing Yan

Yiping Shao

References

Boysen

Stephan

. A survey on single crane scheduling in automated storage/retrieval systems. Eur J Oper Res 2016; 254: 691–704.

Kou

. Belt-conveyor based efficient parallel storage system design and travel time model analysis. Int J Prod Res 2018; 56: 7142–7159.

De Koster

Le-Duc

. Optimal storage rack design for a 3-dimensional compact as/rs. Int J Prod Res 2008; 46: 1495–1514.

Gong

Fan

, et al. Travel-time model of dual-command cycles in a 3D compact as/rs with lower mid-point i/o dwell point policy. Int J Prod Res 2017; 56: 1620–1641.

Zhao

Zou

, et al. Travel time models for a three-dimensional compact as/rs considering different i/o point policies. Int J Prod Res 2019; 58: 5432–5455.

Yang

Jin

Duan

. Modelling and analysis for multi-deep compact robotic mobile fulfilment system. Int J Prod Res 2021; 3: 1–16.

Yang

Miao

Xue

, et al. Optimal storage rack design for a multi-deep compact as/rs considering the acceleration/deceleration of the storage and retrieval machine. Int J Prod Res 2015; 53: 929–943.

Hao

Zhang

. Optimal design of a 3D compact storage system with the i/o port at the lower mid-point of the storage rack. Int J Prod Res 2015; 53: 5153–5173.

Hsu

Chen

. Batching orders in warehouses by minimizing travel distance with genetic algorithms. Comput Ind 2005; 56: 169–178.

10.

Tanaka

Araki

. Routing problem under the shared storage policy for unit-load automated storage and retrieval systems with separate input and output points. Int J Prod Res 2009; 47: 2391–2408.

11.

Kung

Kobayashi

Higashi

, et al. Order scheduling of multiple stacker cranes on common rails in an automated storage/retrieval system. Int J Prod Res 2014; 52: 1171–1187.

12.

Dornberger

Hanne

Ryter

, et al. Optimization of the picking sequence of an automated storage and retrieval system (AS/RS). In: Proceedings of the 2014 IEEE Congress on Evolutionary Computation (CEC), Beijing, China, 6–11 July 2014, pp.2817–2824. New York, NY: IEEE.

13.

Popović

Vidović

Bjelić

. Application of genetic algorithms for sequencing of as/rs with a triple-shuttle module in class-based storage. Flex Serv Manuf J 2014; 26: 432–453.

14.

Gharehgozli

Zhang

, et al. Polynomial time algorithms to minimize total travel time in a two-depot automated storage/retrieval system. Transport Sci 2017; 51: 19–33.

15.

Yang

Zhou

Liu

. Hybrid genetic algorithm-based optimisation of the batch order picking in a dense mobile rack warehouse. PLoS One 2021; 16: e0249543.

16.

Keserla

Peters

. Analysis of dual-shuttle automated storage/retrieval systems. J Manuf Syst 1994; 13: 424–434.

17.

Rubrico

Higashi

Tamura

, et al. Online rescheduling of multiple picking agents for warehouse management. Robot Cim-Int Manuf 2011; 27: 62–71.

18.

Santis

Montanari

Vignali

, et al. An adapted ant colony optimization algorithm for the minimization of the travel distance of pickers in manual warehouses. Eur J Oper Res 2018; 267: 120–137.

19.

Song

. Large-scale storage/retrieval requests sorting algorithm for multi-i/o depots automated storage/retrieval systems. Discrete Dyn Nat Soc 2021;4: 1–16.

20.

Eusuff

Lansey

Pasha

. Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Eng Optimiz 2006; 38: 129–154.

21.

Roy

Chakrabarti

. Modified shuffled frog leaping algorithm with genetic algorithm crossover for solving economic load dispatch problem with valve-point effect. Appl Soft Comput 2013; 13: 4244–4252.

22.

Luo

Chen

, et al. A novel hybrid shuffled frog leaping algorithm for vehicle routing problem with time windows. Inf Sci 2015; 316: 266–292.

23.

Duan

Niu

Huang

. An improved shuffled frog leaping algorithm and its application in dynamic emergency vehicle dispatching. Math Probl Eng 2018; 2: 1–34.

24.

Ebrahimi

Hosseinian

Gharehpetian

. Unit commitment problem solution using shuffled frog leaping algorithm. IEEE Trans Power Syst 2011; 26: 573–581.

25.

Zhu

Zhang

. An improved shuffled frog-leaping algorithm to optimize component pick-and-place sequencing optimization problem. Expert Syst Appl 2014; 41: 6818–6829.

26.

Hsu

Yang

. Optimization of component sequencing and feeder assignment for a chip shooter machine using shuffled frog-leaping algorithm. IEEE Trans Autom Sci Eng 2020; 17: 56–71.

27.

Pan

Wang

Gao

, et al. An effective shuffled frog-leaping algorithm for lot-streaming flow shop scheduling problem. Int J Adv Manuf Tech 2011; 52: 699–713.

28.

Lei

Wang

. Solving distributed two-stage hybrid flowshop scheduling using a shuffled frog-leaping algorithm with memeplex grouping. Eng Optim 2020; 52: 1461–1474.

29.

Cai

Lei

. A cooperated shuffled frog-leaping algorithm for distributed energy-efficient hybrid flow shop scheduling with fuzzy processing time. Complex Intell Syst 2021; 7: 2235–2253.

30.

Basile

Chiacchio

Coppola

. A hybrid model of complex automated warehouse systems-part i: modeling and simulation. IEEE Trans Autom Sci Eng 2012; 9: 640–653.

I/O tasks sequence	I port	O port	I/O tasks sequence	I port	O port
21	1*		45		2*
37		2*	27	2*
11	2*		42		2*
36		2*	13	2*
26	2*		40		2*
49		1*	4	2*
5	1*		38		2*
48		1*	7	2*
22	1*		34		2*
39		1*	10	2*
29	1*		28		2*
44		1*	30	2*
14	1*		3	2*
33		1*	31	2*
2	1*		18	2*
35		1*	9	2*
17	1*		20	2*
47		1*	50		1*
8	1*		6	1*
41		1*	19	1*
25	1*		1	1*
43		2*	15	1*
24	2*		12	1*
46		2*	23	1*
16	2*		32	1*

I/O tasks sequence	I port	O port	I/O tasks sequence	I port	O port
21	1*		45		2*
37		2*	27	2*
11	2*		42		2*
36		2*	13	2*
26	2*		40		2*
49		1*	4	2*
5	1*		38		2*
48		1*	7	2*
22	1*		34		2*
39		1*	10	2*
29	1*		28		2*
44		1*	30	2*
14	1*		3	2*
33		1*	31	2*
2	1*		18	2*
35		1*	9	2*
17	1*		20	2*
47		1*	50		1*
8	1*		6	1*
41		1*	19	1*
25	1*		1	1*
43		2*	15	1*
24	2*		12	1*
46		2*	23	1*
16	2*		32	1*

I/O tasks sequence	I port	O port	I/O tasks sequence	I port	O port
21	1*		45		2*
37		2*	27	2*
11	2*		42		2*
36		2*	13	2*
26	2*		40		2*
49		1*	4	2*
5	1*		38		2*
48		1*	7	2*
22	1*		34		2*
39		1*	10	2*
29	1*		28		2*
44		1*	30	2*
14	1*		3	2*
33		1*	31	2*
2	1*		18	2*
35		1*	9	2*
17	1*		20	2*
47		1*	50		1*
8	1*		6	1*
41		1*	19	1*
25	1*		1	1*
43		2*	15	1*
24	2*		12	1*
46		2*	23	1*
16	2*		32	1*