# Integrated Optimization of Input/Output Point Assignment and Twin Stackers Scheduling in Multi-Input/Output Points Automated Storage and Retrieval System by Ant Colony Algorithm

Authors: Yubo Song; Haibo Mu
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

This paper researches the problem of operational optimization in the multiple-input/output (multi-I/O) points automated storage and retrieval system (AS/RS), where the destination addresses of the retrieval requests are unknown, twin stackers work simultaneously in the same aisle and cannot cross each other, and each stacker can carry two cargo units at the same time. The problem is formalized as an integrated optimization problem with noncrossing constraint for the I/O point assignment and the storage/retrieval (S/R) requests grouping and scheduling. The complexity of the problem is analyzed without considering the I/O point assignment and double units transport (DUT). In order to adapt to the integrated optimization characteristics of the problem, a node structure with multi-I/O points is considered, and the probability selection formula of ant colony algorithm is improved for multiple pheromones. Various numerical experiments show that the average deviation of the objective function value between the proposed method and CPLEX is no more than 0.4%, and the maximum deviation is only 1.22%. Although the phased algorithm avoids the waiting of stacker in operation, the average value of its objective function is 12.14% higher than that of the proposed method, and the maximum deviation is more than 30%.


---

## Body

## 1. Introduction

The functions of automated storage and retrieval system (AS/RS) include storage and retrieval. Assigning storage locations to cargoes, choice of cargoes to retrieval, assignment of I/O points for retrieval requests, and stacker scheduling are important planning and operational decisions in the AS/RS problems [1, 2]. Since AS/RS is required to accomplish storage/retrieval (S/R) requests in time, the operational efficiency of AS/RS is a key problem [3, 4]. In order to reduce the makespan of S/R requests, we can choose to add more stackers in the aisle [5]. A typical multi-I/O points AS/RS (Figure 1(a)) is equipped with twin stackers in the same aisle. The I/O points are located at the bottom of the high-rise shelves and distributed along both sides of the aisle. A conveyor is set in each I/O point, and it transfers the cargoes enter/depart the system through roller rotation. The stacker operates in the aisle, moves the loading platform to the determinant position through the simultaneous movement in both horizontal and vertical directions, and completes the pickup/dropdown cargo by the means of roller rotation. The cooperative operation of conveyor and stacker completes the S/R requests. The cargoes for storage are transported by the conveyor and enter the system from the input point. The conveyor transports the cargoes horizontally to the side of aisle and the cargoes wait for being picked up by stacker. After the stacker moves to the cargo input point and aligns the loading platform with the conveyor, the conveyor transmits the cargo to the loading platform of the stacker by roller rotation. After picking up the cargoes, the stacker controls the loading platform to align with the determinant storage location through the movement in the horizontal and vertical directions, and then the cargoes are dropdown in the storage location through roller rotation. The retrieval process is opposite to the storage process. The cargoes are transported from the storage location to the output point. Each stacker can loading two cargo units at the same time in the process of cargo transporting, which is called double units transport (DUT), as shown in Figure 2.Figure 1
Layout of AS/RS: (a) multi-I/O points AS/RS and (b) single I/O points AS/RS.
(a)(b)Figure 2
Double units transport.Compared with traditional AS/RS (Figure1(b)), multi-I/O points AS/RS can achieve less makespan [6, 7]. However, when twin stackers operate simultaneously in the same aisle, the operation collision is inevitable. If the twin stackers cannot be scheduled reasonably, the makespan will increase. In addition, the DUT will alter the access sequence of the stacker operational location (Figure 3), and shorten the makespan of the stacker. Figure 3 describes the travel routes of storage request L1 and retrieval request R1 in single cargo unit mode and DUT mode, respectively. Figure 3(a) shows the travel route of single cargo unit where the stacker first completes the storage request S1, and then executes the retrieval request R1. Figure 3(b) shows the travel route of DUT. After picking up the cargo at I/O1, the stacker does not access the storage location L2 of S1, but accesses the storage location L1 of R1, then carries two cargo units at the same time and moves to L2 to complete the storage request S1, and then accesses I/O3 to complete the retrieval request R1. Intuitively, the operation distance of DUT mode is shorter than that of single cargo unit mode. Without an efficient operation scheme, the overall performance and efficiency of multi-I/O points AS/RS are limited [8–10]. The best strategy for the optimization of organizational operation management depends on the best application of equipment [11].Figure 3
Operation location access sequence of stacker: (a) The mode of single unit transport. (b) The mode of double units transport.
(a)(b)However, it is challenging to achieve the integrated optimization of the I/O point assignment and the stacker scheduling with the noncrossing constraint and DUT. The complexity of the problem is that the uncertainty of the I/O point brings the uncertainty of the judgment of DUT and the uncertainty of noncrossing constraint. The three factors mentioned above affect the decision-making of stacker scheduling scheme. The characteristic that the optimization objectives are affected by multiple factors is similar to the product portfolio problem under risk uncertainty [12]. The research on operational optimization for AS/RS has been widely concerned by scholars at home and abroad with the papers by Hausman [13] and Graves [14]. Many operational optimization methods have been proposed for different layout structures of AS/RS, in which, a large number of researches focus on the operational optimization problem of single I/O point AS/RS. The operational mode of stacker in single I/O point AS/RS can be divided into single command cycle and dual command cycle [4]. The makespan under the two operational modes can be obtained through the stacker motion model [15]. Whether the stacker can execute the dual command cycle depends on whether the S/R requests are paired. If both are present, the makespan can be reduced by alternating storage request and retrieval request [14]. Based on the feature that the S/R requests appear in pairs, the bipartite graph of S/R request node [16] and cost matrix are constructed [17]. The Hungarian algorithm and the greedy algorithm are used, respectively, to pair the S/R requests in the same command cycle to minimize the makespan. Compared with single command cycle, completing the same number of S/R requests in the double command cycle can save about 30% of the makespan [18]. But it is not always possible to have pairs of S/R requests to construct dual command cycles in the actual operation process. Eben-Chaime and Pliskin [19, 20] put forward the mixed operating mode and made the decision rules for selecting single command cycle or double command cycle. In such mixed mode, the operating mode is selected according to the S/R request matching, which effectively reduces the storage queuing time.Due to the excellent efficiency of dual command cycle, researchers proposed the concept of expanding the number of shuttle for stacker, and thus resulted in dual-shuttle stacker and triple-shuttle stacker. The expansion of stacker capacity effectively improves the operational efficiency of AS/RS in the aspect of structural design [21]. Meanwhile, the operational efficiency has been improved further by optimizing the sequence of S/R requests [3]. Under the operation mode of multi-aisles shared stacker, Yan et al. established the scheduling optimization model of multi-aisles AS/RS with multi-shuttle stacker, and designed an improved artificial bee colony algorithm to solve the model [22]. From there, Yan et al. established a multiobjective scheduling optimization model for multi-aisle AS/RS with the objective of minimizing the makespan and the delay penalty. A nondominated sorting artificial bee colony algorithm is proposed to solve the problem, which combines the multiobjective handling framework of NSGA-II and the neighborhood search of the ABC algorithm [23]. It provides an effective approach to solve the AS/RS scheduling optimization problem of multi-shuttle stacker. Since the multi-shuttle stacker can complete multiple S/R requests in each command cycle, in order to make full use of the capacity of the stacker, Kazemi et al. and Habibi Tostani et al. studied the scheduling problem of the multi-shuttle stacker under the shared storage strategy and the class-based storage strategy, respectively, and proposed the mathematical model based on the assignment problem and the bilevel optimization model, respectively, and designed the algorithm with the intention of solving the proposed model. It provides a solution for the application of multi-shuttle stacker under specific storage strategy [24, 25]. The scheduling problem of multi-shuttle stacker is more complex and has a larger space of feasible scheduling scheme than the single-shuttle stacker. Main algorithm to solve this problem includes nearest-neighbor heuristics [26], the genetic algorithm [27], neural networks [28], particle swarm algorithm [29], Petri Net [30], and artificial intelligence [31]. The artificial intelligence algorithm can be improved by the newest metaheuristic algorithms, such as grey wolf algorithm, cultural algorithm, and particle swarm optimization, so as to improve the accuracy of calculation results [32].The above literature is about the operational optimization of the single stacker, which are different from the operational optimization of multiple stackers with noncrossing constraint [33]. The noncrossing constraint requires that the stacker cannot cross another stacker in the same aisle. Although the simultaneous stackers can effectively improve the operational efficiency of AS/RS, due to the impact of potential operation collisions, and the operational efficiency of AS/RS is at the cost of more complex stacker scheduling. Erdogan et al. [34] defined the twin robot scheduling problem (TRSP) for the first time and proved that the problem is NP-hard. Integer programming formulas are constructed based on time index and priority index, respectively, to avoid the S/R requests with collisional paths are executed simultaneously. And the branch and bound algorithm and the heuristic algorithm are designed to solve the problem. They consider that the branch and bound algorithm and the heuristic algorithm are complementary in solving TRSP within the specified time limit. Boysen et al. [35] extended TRSP by introducing the concept of bottleneck robot, and proposed the TRSP-F. The dynamic programming method is applied to determine the scheme of another robot with the noncrossing constraint. Jaehn and Wiehl [36] further extended the TRSP by considering the types of S/R requests and the makespan (d > 0), meanwhile designed the accurate algorithm and approximate algorithm to solve the problem. The construction of the problem is closer to the actual application scenarios. Based on the characteristics of potential overlapping paths in the time domain of S/R requests, Briskorn et al. [37] and Carlo and Martínez-Acevedo [38] avoided operation collisions by the method of judging the distance between twin stackers at the same moment. The former analyzed the complexity of preemptive crane scheduling problem, and proposed a mixed-integer programming model for cooperative operation optimization of twin stackers, and designed a heuristic algorithm to solve the model. The latter evaluated 14 kinds of priority rules for twin stackers operation, which were used to solve potential collisions in the process of operation, and realized the cooperative operation by transferring containers from one stacker to another at the exchange point. The solutions of collisions in the above literature are based on the premise of determining the operation sequence of one stacker first, and then optimize the operation sequence of another stacker combining with noncrossing constraint, so as to minimize the makespan on the premise of avoiding collisions. When Kung et al. [39, 40] solved the stacker operational optimization problem with noncrossing constraint, they divided the problem into two stages: grouping and sorting. In the first stage, the clustering method was applied to group S/R requests. The S/R requests with nonconflict path and close makespan are clustered, and the number of S/R requests in each cluster equals to the number of stackers. In the second stage, dynamic programming is applied to obtain the best sequence of clustering. This method avoids the potential collisions in the operating process by clustering, and it is suitable for solving the operational conflict problem of more than two stackers. For more research about the optimization solutions of stacker operation with noncrossing constraints refer to the summary of Bierwirth and Meisel [41], Carlo et al. [42], and Boysen et al. [33].Layout of AS/RS is another important attribute related to operational efficiency [43]. For AS/RS with the same layout, the scheduling strategy vitally affects the performance indicators such as the makespan, storage queuing time, and stacker operational distance, and the performance of AS/RS is different under different scheduling strategies [44, 45]. Scheduling strategies such as first-come-first-served, nearest-neighbor, and shortest legs can quickly sort S/R requests, but the scheduling effect is not as good as heuristic algorithm [46] and polynomial algorithms [47], and the solution quality is not as good as biogeography-based optimization algorithm and variable neighborhood search algorithm [48]. The above studies invariably focused on the AS/RS with tow I/O points which are distributed at both ends of the aisle; AS/RS with three or more I/O points have been rarely studied. Except the research on the optimization of picking in multi-I/O points AS/RS, some theoretical opinions have appeared in the literature. For example, Briskorn et al. [37] proved that the stacker scheduling problem in multi-I/O points AS/RS was NP-hard. Xu et al. found the optimal system structure of AS/RS with four I/O points in theory, and compared these I/O point strategies according to the expected travel time of stacker [49]. Song and Mu transformed the scheduling problem of large-scale S/R requests in multi-I/O points AS/RS into a special traveling salesman problem, and proposed an assignment-based heuristic algorithm for stacker scheduling [50]. The execution order of picking is usually obtained by solving a mathematical model, typical solution methods are heuristic algorithms, clustering-based efficient algorithms, genetic algorithms, ant colony algorithms, artificial immune algorithms, and other intelligent algorithms [51, 52]. The picking optimization problem is transformed into the picking path optimization problem, and the model can be solved by the harmony search algorithm [53, 54].The literature mentioned above studied on the operational optimization of the single stacker and multiple stackers, and provided the operational optimization schemes for the single I/O point AS/RS and two I/O points AS/RS. However, as far as we know, few people pay attention to the operational optimization problem of multiple stackers in multi-I/O points AS/RS. Based on the logistics problem of actual air cargo terminal, the problem of operation optimization for multi-I/O points AS/RS is studied in this paper. The multi-I/O points AS/RS is composed of two rows of racks, and the I/O points are distributed along both sides of the aisle. The twin stackers in the aisle share the same roadway and cannot cross each other. Each stacker can perform DUT. Then, the operational optimization problem in multi-I/O points AS/RS is to optimize the I/O point assignment and the scheduling of twin stackers with the purpose of minimizing the makespan of stackers. In order to solve the problem mentioned above, two optimization aspects that are the I/O points assignment and the schedule of twin stackers with noncrossing constraint are consider comprehensively, and the schedule optimization problem of multiple stackers under the condition that the destinations of the retrieval requests is uncertain is researched. Computational experiments results indicate the correctness of the model and the efficiency of the proposed algorithm.The paper is organized as follows. Details of the integrated optimization problem of the I/O point assignment and the scheduling of twin stackers with noncrossing constraint and the complexity of the problem are introduced in Section2. Solution procedures and computational experiments follow in Sections 3 and 4. Conclusion is presented in Section 5.


## 2. Problem Description and Complexity

### 2.1. Problem Description

In this section, we will describe multi-I/O points AS/RS in detail. The system is derived from air logistics industry and is used to complete the automatic transportation of containers between the rack cell and the I/O points. The system is composed of high racks, stackers, roller conveyors, I/O points, aisle, and control system. The spatial layout is shown in Figure1(a). Each rack cell has same size and can store one cargo unit. Each stacker can transport two cargo units at the same time through DUT, and the loading mode of DUT on the loading platform of stacker is shown in Figure 2. The stacker needs to meet the conditions of DUT when performing DUT. That is, when the stacker unloads the cargo unit, the other cargo units on the loading platform will not interfere with the unloaded cargo unit. When the operation task does not meet the conditions of DUT, the stacker completes the operation task through single-unit transport. There are two types of requests in the air cargo production plan: storage request and retrieval request. Stored container enters the system through the I/O point and is transported to the side of aisle by the roller conveyor, and then the container is transported to the rack cell by the stacker to complete the storage request. The I/O point and rack cell of the storage request are known. The process of retrieval request is opposite to the storage request. The stacker first picks up the container at the storage rack cell, then transports the container along the aisle to the roller conveyor corresponding to the I/O point and dropped down it. The roller conveyor transports the container from the aisle side to the I/O point to complete the retrieval request. In the retrieval request, the storage rack cell is known and the I/O point of retrieval is unknown. Since the number of I/O points is far more than that of the stacker in the multi-I/O points AS/RS, the goal is to minimize the makespan of all the S/R requests as much as possible while keeping the safe distance between the twin stackers.In this scenario, we have five major decisions to make in order to improve the operation efficiency from the perspective of operational optimization. (1) Assign an I/O point to each retrieval request. (2) Assign all S/R requests to both stackers. (3) Sort the S/R requests assigned to each stacker. (4) Determine the adjacent S/R requests perform DUT or not. (5) Keep the safe distance between twin stackers. These five decisions are interrelated and all affect the efficiency of the system. Our problem is described as follows. The S/R requests constitute a sequence of S/R requests in which the input points and storage locations of the storage requests are known, and the storage locations of the retrieval requests are known, but the output points of the retrieval requests are unknown. The S/R requests are completed by twin stackers that cannot cross each other, and must remain separated by a safe working distance. Each stacker can transport two containers at the same time. Once the S/R request starts to be executed, the containers must be transported from the source address to the destination address without unloading midway. The horizontal and vertical dimensions of the rack cells are fixed. Whether loaded or unloaded, the stacker is assumed to move at constant known speed in both the horizontal and vertical directions. The pick-up and drop-down times of the stacker are ignored. The Chebyshev distance is used to represent the makespan between two locations. Here the Chebyshev distance refers to the maximum travel time between vertical travel time and horizontal travel time. The makespan of S/R requests is obtained by accumulating the Chebyshev distance between the source address and destination address of S/R requests continuously accessed by the stacker. The objective is to minimize the makespan for the stackers to complete all S/R requests.


### 2.2. Complexity of the Problem

If the DUT and output point assignment are ignored, the problem can be reduced to a twin stackers scheduling problem in multi-I/O points AS/RS. It is known that the scheduling problem of twin stackers in the AS/RS with two points is a strong NP-hard problem [34, 35]. It can be estimated that the problem we studied is at least a strong NP-hard problem. The complexity of the simplification problem is analyzed by reduction from 3-Partition. The first step of the reduction process is to construct a problem instance, then reduce the instance to the equal partition problem, and finally prove that the number of elements in each partition is 3.A 3-Partition problem is described as follows. Given a setH=a1,a2,…,a3h with 3h elements and a positive integer a, and the set H satisfies a/4<aj<a/2, ∑j=13haj=ha. Does there exist a partition of set H=1,2,3h into h disjoint subsets H1,H1,…,Hh with 3 elements, such that ∑aj∈Hiaj=a,i=1,2,…,h?Theorem 1.
The twin stackers scheduling problem in multi-I/O points AS/RS is a strong NP-hard problem even without considering DUT and output point assignment.Proof.
we construct an instance of the twin stackers scheduling problem in multi-I/O points AS/RS as follows.B: There are B columns rack cells along the aisle in the AS/RS.P=0, the pick-up and dropdown time of the stacker are 0.The setJ1 contains m+1 S/R requests Aj with makespan δj=3B/2 for each j=3m+3,3m+4,…,4m+3.The setJ2 contains 3m+2 S/R requests Aj with makespan δj=aj for each j=1,2,…,3m and δ3m+1=δ3m+2=3B/4.Thresholdy=3Bm+1/2.
We will prove that if and only if the 3-Partition problem has a solution, we can find a schedulingS∗ whose optimum makespan is 3Bm+1/2 for the instance we constructed.
If the 3-Partition problem has a solution, and it is expressed asH1,H2,…,Hm. The scheduling problem instance scheduling that we construct is depicted in Figure 4. The given S/R requests set J1 is executed by stacker 1, and stacker 1 has to constantly move back and forth between columns B/4+1 and B without waiting, otherwise the makespan will exceed 3Bm+1/2. Stacker 2 completes the S/R requests through multi-I/O points. Considering that the makespan of stacker 2 is at most 3Bm+1/2, we can conclude that stacker 2 must work without any waiting also. Stacker 1’s equidistance continuous operational process divides the makespan into m+1 cycles with a length of 3B/2. Between time interval 3B2j−1/4,3B2j+1/4 stacker 1 completes the S/R request Aj and starts to execute the S/R request Aj+1, stacker 2 executes the S/R request subset Hj, j=1,2,…,m. In the time interval 0,3B/4, stacker 1 starts to execute the S/R request A1, and stacker 2 executes the S/R request A3m+1. Between time interval 3B2m+1/4,3Bm+1/2, stacker 1 completes the S/R request Am+1 and stacker 2 executes the S/R request A3m+2. The above scheduling scheme is feasible and the total makespan is 3Bm+1/2.
Conversely, if the constructed instance has a scheduleS∗ whose makespan is 3Bm+1/2, then the 3-PARTITION is proved to be solvable. For the schedule S∗ depicted in Figure 4, the makespan for stacker 1 to complete any S/R request is 3B/2, and the makespan for stacker 2 to complete H1,H2,…,Hm cannot exceed 3B/2, otherwise the makespan for schedule S∗ will exceed 3Bm+1/2, it is contradictory.
Next, it is proved that the subsetHj completed by stacker 2 contains three S/R requests, j=1,2,…,m. In the 3-Partition problem, when a=3B/2, the makespan of each S/R request satisfies 3B/8<Ai<3B/4,i=1,2,⋯,3m. If Hj contains four S/R requests, the makespan of Hj is larger than 3B/2, and it is contradictory. H1,H2,…,Hm contains 3m S/R requests. If Hj contains 2 S/R requests, then Hi=4,i≠j must be present, and it is contradictory. Therefore, Hj is the solution of the 3-Partition problem.
The above theorem shows that it is impossible to find the optimal scheduling of the simplified problem in polynomial time. This means that it is less likely for us to find the optimal solution of the original problem in polynomial time.Figure 4
The schedule structure of the constructed instance.


## 2.1. Problem Description

In this section, we will describe multi-I/O points AS/RS in detail. The system is derived from air logistics industry and is used to complete the automatic transportation of containers between the rack cell and the I/O points. The system is composed of high racks, stackers, roller conveyors, I/O points, aisle, and control system. The spatial layout is shown in Figure1(a). Each rack cell has same size and can store one cargo unit. Each stacker can transport two cargo units at the same time through DUT, and the loading mode of DUT on the loading platform of stacker is shown in Figure 2. The stacker needs to meet the conditions of DUT when performing DUT. That is, when the stacker unloads the cargo unit, the other cargo units on the loading platform will not interfere with the unloaded cargo unit. When the operation task does not meet the conditions of DUT, the stacker completes the operation task through single-unit transport. There are two types of requests in the air cargo production plan: storage request and retrieval request. Stored container enters the system through the I/O point and is transported to the side of aisle by the roller conveyor, and then the container is transported to the rack cell by the stacker to complete the storage request. The I/O point and rack cell of the storage request are known. The process of retrieval request is opposite to the storage request. The stacker first picks up the container at the storage rack cell, then transports the container along the aisle to the roller conveyor corresponding to the I/O point and dropped down it. The roller conveyor transports the container from the aisle side to the I/O point to complete the retrieval request. In the retrieval request, the storage rack cell is known and the I/O point of retrieval is unknown. Since the number of I/O points is far more than that of the stacker in the multi-I/O points AS/RS, the goal is to minimize the makespan of all the S/R requests as much as possible while keeping the safe distance between the twin stackers.In this scenario, we have five major decisions to make in order to improve the operation efficiency from the perspective of operational optimization. (1) Assign an I/O point to each retrieval request. (2) Assign all S/R requests to both stackers. (3) Sort the S/R requests assigned to each stacker. (4) Determine the adjacent S/R requests perform DUT or not. (5) Keep the safe distance between twin stackers. These five decisions are interrelated and all affect the efficiency of the system. Our problem is described as follows. The S/R requests constitute a sequence of S/R requests in which the input points and storage locations of the storage requests are known, and the storage locations of the retrieval requests are known, but the output points of the retrieval requests are unknown. The S/R requests are completed by twin stackers that cannot cross each other, and must remain separated by a safe working distance. Each stacker can transport two containers at the same time. Once the S/R request starts to be executed, the containers must be transported from the source address to the destination address without unloading midway. The horizontal and vertical dimensions of the rack cells are fixed. Whether loaded or unloaded, the stacker is assumed to move at constant known speed in both the horizontal and vertical directions. The pick-up and drop-down times of the stacker are ignored. The Chebyshev distance is used to represent the makespan between two locations. Here the Chebyshev distance refers to the maximum travel time between vertical travel time and horizontal travel time. The makespan of S/R requests is obtained by accumulating the Chebyshev distance between the source address and destination address of S/R requests continuously accessed by the stacker. The objective is to minimize the makespan for the stackers to complete all S/R requests.


## 2.2. Complexity of the Problem

If the DUT and output point assignment are ignored, the problem can be reduced to a twin stackers scheduling problem in multi-I/O points AS/RS. It is known that the scheduling problem of twin stackers in the AS/RS with two points is a strong NP-hard problem [34, 35]. It can be estimated that the problem we studied is at least a strong NP-hard problem. The complexity of the simplification problem is analyzed by reduction from 3-Partition. The first step of the reduction process is to construct a problem instance, then reduce the instance to the equal partition problem, and finally prove that the number of elements in each partition is 3.A 3-Partition problem is described as follows. Given a setH=a1,a2,…,a3h with 3h elements and a positive integer a, and the set H satisfies a/4<aj<a/2, ∑j=13haj=ha. Does there exist a partition of set H=1,2,3h into h disjoint subsets H1,H1,…,Hh with 3 elements, such that ∑aj∈Hiaj=a,i=1,2,…,h?Theorem 1.
The twin stackers scheduling problem in multi-I/O points AS/RS is a strong NP-hard problem even without considering DUT and output point assignment.Proof.
we construct an instance of the twin stackers scheduling problem in multi-I/O points AS/RS as follows.B: There are B columns rack cells along the aisle in the AS/RS.P=0, the pick-up and dropdown time of the stacker are 0.The setJ1 contains m+1 S/R requests Aj with makespan δj=3B/2 for each j=3m+3,3m+4,…,4m+3.The setJ2 contains 3m+2 S/R requests Aj with makespan δj=aj for each j=1,2,…,3m and δ3m+1=δ3m+2=3B/4.Thresholdy=3Bm+1/2.
We will prove that if and only if the 3-Partition problem has a solution, we can find a schedulingS∗ whose optimum makespan is 3Bm+1/2 for the instance we constructed.
If the 3-Partition problem has a solution, and it is expressed asH1,H2,…,Hm. The scheduling problem instance scheduling that we construct is depicted in Figure 4. The given S/R requests set J1 is executed by stacker 1, and stacker 1 has to constantly move back and forth between columns B/4+1 and B without waiting, otherwise the makespan will exceed 3Bm+1/2. Stacker 2 completes the S/R requests through multi-I/O points. Considering that the makespan of stacker 2 is at most 3Bm+1/2, we can conclude that stacker 2 must work without any waiting also. Stacker 1’s equidistance continuous operational process divides the makespan into m+1 cycles with a length of 3B/2. Between time interval 3B2j−1/4,3B2j+1/4 stacker 1 completes the S/R request Aj and starts to execute the S/R request Aj+1, stacker 2 executes the S/R request subset Hj, j=1,2,…,m. In the time interval 0,3B/4, stacker 1 starts to execute the S/R request A1, and stacker 2 executes the S/R request A3m+1. Between time interval 3B2m+1/4,3Bm+1/2, stacker 1 completes the S/R request Am+1 and stacker 2 executes the S/R request A3m+2. The above scheduling scheme is feasible and the total makespan is 3Bm+1/2.
Conversely, if the constructed instance has a scheduleS∗ whose makespan is 3Bm+1/2, then the 3-PARTITION is proved to be solvable. For the schedule S∗ depicted in Figure 4, the makespan for stacker 1 to complete any S/R request is 3B/2, and the makespan for stacker 2 to complete H1,H2,…,Hm cannot exceed 3B/2, otherwise the makespan for schedule S∗ will exceed 3Bm+1/2, it is contradictory.
Next, it is proved that the subsetHj completed by stacker 2 contains three S/R requests, j=1,2,…,m. In the 3-Partition problem, when a=3B/2, the makespan of each S/R request satisfies 3B/8<Ai<3B/4,i=1,2,⋯,3m. If Hj contains four S/R requests, the makespan of Hj is larger than 3B/2, and it is contradictory. H1,H2,…,Hm contains 3m S/R requests. If Hj contains 2 S/R requests, then Hi=4,i≠j must be present, and it is contradictory. Therefore, Hj is the solution of the 3-Partition problem.
The above theorem shows that it is impossible to find the optimal scheduling of the simplified problem in polynomial time. This means that it is less likely for us to find the optimal solution of the original problem in polynomial time.Figure 4
The schedule structure of the constructed instance.


## 3. Solution Procedures

In this section, we will discuss the method of solving the problem of the I/O point assignment and scheduling of twin stackers. In the above section, we explained that the problem we studied is strong NP-hard, and it is impossible to solve a real-world instance in acceptable time through an exact procedure. Therefore, we introduce a mixed-integer programming (MIP) model and a heuristic algorithm to get near optimal solutions of large-sized problems in a satisfactory time.


### 3.1. MIP Mode

Applying the notation summarized in Table1, we constructed the MIP model for the problem of the I/O point assignment and the scheduling of two stackers, which consists of objective function (1) and constraints (2)–(6).(1)T=minmaxTk,Tk′kandk′are elements of setM,s.t.∑p∈PYip=1∀i∈R,∑k∈MZik=1∀i∈J,∑j∈JkXijk≤1∀,i∈Jkandi≠j,∀k∈M,0≤qk≤2∀k∈M,Ckt−Ck′t≥Dk,k′∈M,t∈0,T.Table 1
Notation definition.
NotationNotation meaningJSet of S/R requestsRSet of retrieval requestsMSet of stackersPSet of I/O pointsTMinimum makespan of the S/R requests sequenceDSafe operational distance between twin stackersJkThe set of S/R requests assigned to stackerkTkThe makespan to complete the S/R requests assigned to the stackerkqkLoad capacity of stackerkCktAddress of stackerk at time tXijkXijkis an element of0,1, 1 indicates that stacker k completes S/R request i before executing S/R request j, and 0 otherwiseYipYipis an element of0,1, 1 indicates that retrieval request i selects I/O point p as the destination address, and 0 otherwiseZikZikis an element of0,1, 1 indicates that S/R request i is assigned to stacker k, and 0 otherwiseThe objective function (1) minimizes the S/R requests sequence makespan which is the longer makespan of the twin stackers. Constraint (2) ensures that only one output point can be assigned as the destination address for each retrieval request. Constraint (3) ensures that each S/R request can be executed by only one stacker. Constraint (4) ensures that each S/R requests assigned to each stacker is executed in the order of sorting. Constraint (5) ensures that the stacker capacity does not exceed the maximum load, and constraint (6) ensures that the working distance between two stackers is not less than the minimum safe operational distance (noncrossing constraint).


### 3.2. Algorithm

Suppose that the output point has been assigned to each retrieval request, if each S/R request is considered as a node without considering the DUT and noncrossing constraint, the sorting and grouping problem of the S/R requests becomes the problem that twin stackers traverse all the nodes and each node can only traverse once. This problem is similar to the open multiple traveling salesman problem (MTSP) after simplification. Ant colony algorithm (ACA) is often used to solve TSP problem. The key of using ACA to solve the traveling salesman problem is to be able to transform the problem into a graph with nodes and edges [55]. The ACA solves the MTSP with higher precision within a shorter time frame than the exact algorithm [56]. If the S/R requests are regarded as nodes, and the sum of the makespan from the destination address of any S/R request to the source address of any other S/R request and the makespan to complete the current S/R request is taken as the weight of each edge between two nodes, then all S/R requests can be transformed into a graph with nodes and edges. In order to avoid the drawback that ACA is easy to fall into local optima, a weight pheromone and a disturbance strategy are introduced into the algorithm [57, 58]. This section designs an improved ACA for solving the proposed integrated optimization problem.


#### 3.2.1. Weight Pheromone

Different from ordinary pheromones, the weight pheromone is used to describe the weight of each subpath in the optimal path, and its update is based on the global information. Letξijt represent the weight pheromone value from node i to node j. The weight pheromone is neither volatilized nor superimposed, and its value is updated after traversal by ants. The update formula is given by(2)ξijt+n=CTkCTk>ξijt,ξijtotherwise,where C is a constant, and Tk is the makespan for the kth pair of ant to complete traversal. As indicated in equation (2), the weight pheromone of the longer subpath in the shorter path can get the second enhancement, increasing the probability of selecting that subpath and hence improving the global convergence of the algorithm.


#### 3.2.2. Transfer Strategies

The ordinary pheromone indicates the selection probability of the local path, whereas the weight pheromone reflects the global information. Although the two pheromones play a positive feedback role on the optimal information in the process of path search, they should have different heuristic factors in the probability selection formula. The ordinary pheromone indicates the transition probability of the local path, whereas the weight pheromone reflects the global information. Although the two pheromones play a positive feedback role on the optimal information in the process of path search, they should have different heuristic factors in the probability selection formula. Ants will be affected by the transition probability when it searches path. The path with higher transition probability will be selected by more ants With the action of positive feedback, if ants continue to select the path with high transition probability, the pheromone on the current optimal path will be more than that on the undetected optimal path, and the probability of selecting the undetected optimal path will be smaller and smaller, resulting in the phenomenon of falling into local optimization. In order to avoid this situation, the disturbance factor is added in the process of ant selecting path. Through the interference of disturbance factor, the transformation of the transfer probability formula in the process of path selection is completed, so that the different combinations of ordinary pheromone, weight pheromone, and expected information urge ants to choose the path whose pheromone is not the most with a certain probability. The introduction of disturbance factor realizes the dynamic adjustment of transition probability in the process of searching path and improves the diversity of path selection. Moreover, the probability of the path with the largest residual pheromone is calculated individually to prevent the optimal path from being missed. These ideas are combined into the following probability selection formula with a random mutation rate.(3)pijkt=τijαtηijβtξijγt∑j∈Okτijαtηijβtξijγt,τijt=maxτijt,i∈O;,τijαtηijtξijγt∑j∈Okτijαtηijβtξijγt,τijt≠maxτijt,pm≤p1,i∈O;,τijtηijβtξijγt∑j∈Okτijαtηijβtξijγt,τijt≠maxτijt,p1<pm<p2,i∈O;,τijtηijtξijγt∑j∈Okτijαtηijβtξijγt,τijt≠maxτijt,p2≤pm,i∈O;,0,otherwise.In equation (3), τijt denotes the residual value of the ordinary pheromone between nodes i and j at time t, the calculation formula is equation (4). ηijt is the reciprocal of τijt, indicating the expected degree of transfer from node i to node j, and ξijt is the weight pheromone value at time t between nodes i and j, the calculation formula is equation (2). α denotes the importance degree of the residual ordinary pheromone in the process of path selection, β denotes the role played by the heuristic information in the process of path selection, and γ is the importance degree of the weight pheromone in the process of path selection. Ok denotes the node set currently accessible by ant k. The random mutation rate pm is uniformly distributed on interval 0,1, p1 and p2 are constants.(4)τijt=1−ρτijt−n.In equation (4), ρ is pheromone volatilization coefficient between time periods (t − n, t). After ants complete the traversal of all nodes, enhance the ordinary pheromone of the path passed by ants, the calculation of the enhancement is shown in the following equation:(5)△τij=∑k=1m△τijk.In equation (5), △τijk is the amount of ordinary pheromone left by the kth ant between node i and j in this iteration, the calculation of △τijk is shown in the following equation:(6)△τijk=QLkif thekth ant gose fromitoj,0otherwise.In equation (6), Q is a constant, and Lk is the makespan for the kth pair of ants to complete all S/R requests.


#### 3.2.3. Algorithm Procedure

Because the DUT can change the access sequence of the stacker operation address (as shown in Figure3), thus shortening the makespan of the stacker. Whether the two S/R requests can perform DUT is judged by the following conditions.(1)
The two S/R requests are adjacent, and the transport paths of the two S/R requests are in the same direction along the aisle and overlapping;(2)
Both S/R requests satisfy any of the conditions listed in Table2.The four operational conditions listed in Table2 are demonstrated in Figure 5.Table 2
Working conditions of the DUT.
YUnloading sequenceLoading methodsRelation between source addresses and destination addresses1First load first unloadOne side loadingSource addresses and destination addresses of the “first unload” container are on opposite sides of the loading platform2First load first unloadBoth side loadingSource addresses and destination addresses of the “first unload” container are on the same side of the loading platform3Last load first unloadOne side loadingSource addresses and destination addresses of the “first unload” container are on the same side of the loading platform4Last load first unloadBoth side loadingSource addresses and destination addresses of the “first unload” container are on opposite sides of the loading platformFigure 5
Position relation of the double units transport.Under the decision conditions of the DUT, when the destination address of the retrieval request is unknown, we can change the front–back and left–right positions of the destination address relative the source address to construct the DUT. If the search neighborhood of the I/O point assignment is classified by its positional relationship (front, back, left, and right) relative the source address, the I/O point assignment becomes the selection of the location relationship. Since the objective function is minimize the makespan, the set of I/O points in the optimal solution can be composed of the I/O points closest to the source address in the four directions.In summary, the retrieval request node contains the source address and four optional destination addresses. Each destination address and source address constitute a retrieval request, and one edge connected to the destination address points to the source address of other nodes. The weight of the edge is the sum of the makespan of the current retrieval request and the makespan from the current I/O point to the source address of other nodes. The number of edges pointing to the retrieval request node depends on the type of node. The number of edges is 4 if it is a retrieval request node, and the number of edges is 1 if it is a storage request node. The structure and connection with other nodes of the retrieval request node are shown in Figure6. The structure of the storage request node is relatively simple, having only the source address and destination address, and both of them are known. This node has only one edge pointing to other nodes, and the weight of the edge is the sum of the makespan from the destination address of the current node to the source address of other nodes and the makespan to complete the current storage request. The number of edges pointing to the storage request node depends on the type of node. If it is a retrieval request node, the number of edges is 4. If it is a storage request node, the number of edges is 1. The structure and connection with other nodes of the storage request node are shown in Figure 7. Except the above two types of nodes, there are dwell-point nodes. This kind of node represents the dwell-point address of the stacker. It has only the edge pointing to other nodes, and the weight of the edge is the makespan from the current address to the source address of other nodes.Figure 6
S/R request nodes.Figure 7
Storage request nodes.The graph of search space for ant colony algorithm proposed in this paper consists of the above three types of nodes. In the graph, each S/R request node corresponds to an S/R request. The number of S/R request nodes depends on the number of S/R requests, while the number of dwell-point nodes depends on the number of stackers. In this paper, the number of stackers is 2. The graph of search space with 6 S/R requests is shown in Figure8. The graph includes two retrieval request nodes R1 and R2, four storage request nodes S1, S2, S3, S4 and two dwell-point nodes ST1 and ST2. Both R1 and R2 have 20 edges pointing to other nodes in the graph, and there are 4 edges for other nodes except ST1 and ST2. There are 10 edges pointing to R1 and R2, respectively, of which S1, S2, S3, S4, ST1, and ST2 have one edge pointing to R1 and R2, respectively, and the edges from R1 to R2 and from R2 to R1 are all 4. Each storage node has 5 edges pointing to other nodes (except ST1 and ST2) and 13 edges pointing to each storage node. For example, S1 has five edges pointing to nodes S2, S3, S4, R1, and R2, respectively. Each node in S2, S3, S4, ST1, and ST2 has one edge pointing to S1, and each node in R1 and R2 has four edges pointing to S1, with a total of 13 edges. ST1 and ST2 have only 6 edges pointing to other nodes, respectively, and there are no edges pointing to ST1 or ST2.Figure 8
Path optimization graph of algorithm.The basic idea of ant colony algorithm is to first generate the path optimization graph of the S/R requests set. The path nodes in the graph are divided into retrieval request node, storage request node, and dwell-point node. The storage request node includes the source address and destination address, the retrieval request node includes the source address and four optional destination addresses, and the dwell-point node only includes the dwell-point address of stacker. The initial value of the weight pheromone between any two nodes in the graph is 0, and the initial value of the ordinary pheromone between any two nodes is the reciprocal of the makespan required for the stacker to complete the S/R request represented by the current node and move to the source address of the next node. The number of ants generated is double the number of S/R requests, each ant representing a stacker, and two ants form a group. Nodes that are not accessed by the current ant and its group partner constitute the set of candidate nodes that the current ant can access, and the selection probability of the current node to each node in the candidate node set is calculated through the probability selection equation (3). If the current node is a retrieval request node with unknown destination address, the selection probabilities of the retrieval request composed of four optional destination addresses to each accessible node needs to be calculated, respectively. If the current node is a storage request node, we only need to calculate the selection probability of the storage request node to each accessible path node. After calculating the selection probability from the current node to each node in the candidate node set, the roulette method is used to select the next access node of the current ant. Repeat the path node selection operation until the two ants have accessed all nodes exactly once, a solution is obtained. The nodes passed through by ant constitute the S/R requests assigned to the stacker represented by the ant, and the sequence of each ant passing through the nodes is the S/R request execution sequence. Finally, the selected destination address of the retrieval request node is the output point of that retrieval request. Record the current optimal solution and judge whether it meets the termination conditions of the algorithm. If not, enhance the ordinary pheromone according to equation (5) and update the weight pheromone according to equation (2). Otherwise, the current optimal solution is output and exit.Based on the above search process, a feasible solution of the graph for searching space shown in Figure8 is depicted in Figure 9. Departing from ST1 and ST2, respectively, ant1 and ant2 select the next node accessed by itself through probability selection formula (3) and roulette method. When the ant is in the dwell-point node or storage request node, the ant selects the next node in the same way. For example, if ant1 is at node S2, its accessible node set is {R1, R2, S3, S4}, the selection probability from S2 to R1, R2, S3, S4 is calculated by formula (3), respectively, and then the roulette method is used to select the next node accessed by ant1. When the ant is at the retrieval request node, it completes the selection of the next node and the destination address of the retrieval request simultaneously. For example, when ant1 is at node R1, its accessible node set is {S3, S4}. Formula (3) is applied to calculate the selection probability of the four destination addresses of R1 to S3 and S4, respectively, and then the roulette method is used to select the next accessed node of ant1. After the edge from R1 to S3 is determined, the I/O point corresponding to this edge is the destination address of R1. Repeat the above two node selection methods until all nodes are traversed, a feasible solution is obtained. The feasible solution shown in Figure 9 means that the S/R request sequence executed by stacker 1 is: S2 ⟶ R1 ⟶ S3, the S/R request sequence executed by Stacker 2 is: S1 ⟶ R2 ⟶ S4, and the destination addresses of R1 and R2 are the I/O point corresponding to the edge of R1 ⟶ S3 and R2 ⟶ S4, respectively. The detailed steps of the algorithm are as follows. The algorithm flowchart is shown in Figure 10.Figure 9
Feasible solution of algorithm.Figure 10
Algorithm flowchart.Step 1.
Define the path node setO, whose size is the number of the S/R requests plus 2. The source address and destination address of the storage request are assigned to the storage request node, the source address of the retrieval request and the I/O points closest to the source address in 4 directions are assigned to the retrieval request node, and the two stackers dwell-points are assigned to the stacker dwell-point nodes. Calculate the makespan between any two nodes, and the initial value of ordinary pheromone between any two nodes is the reciprocal of the makespan. The initial value of weight pheromone between any two nodes is 0. Set tabuk1=ϕ, tabuk2=ϕ (the set of nodes already accessed by each pair of ants), neighbork=ϕ (the set of nodes that each pair of ants may access in the next step), WorkTimek1=0, WorkTimek2=0 (the cumulative makespan of each pair of ants), N=0 (the repeat umber of the current optimal solution).Step 2.
Generate ants which number is double the number of S/R requests, two ants form a group. The initial address of the dwell-point node is assigned to each pair of ants, respectively, meanwhile the dwell-point node is added totabuk1 and tabuk2 respectively.Step 3.
Setneighbork=O−tabuk1−tabuk2 (the set of nodes that each pair of ants can access), meanwhile generate random number between 0,1 and assign to pm. Equation (3) is applied to calculate the selection probability of the dwell-point to each accessible node in the set neighbork, and then the roulette method is applied to determine the next accessed node for the current ant, then the determined node is added to the set of the current ant has accessed nodes.Step 4.
According to the noncrossing constraint (equation (6)) judge whether there is an operation collision between the two S/R requests which are represented by the node currently accessed by each pair of ants. If the noncrossing constraint is violated, add the avoidance time to the cumulative makespan. Calculate the makespan of the current S/R request and accumulate it to the cumulative makespan of the current ant. Repeat Steps 3 and 4 to determine the first access node for each ant.Step 5.
Judge which of the S/R requests corresponding to the node currently accessed by each pair of ants is completed first, and set the ant corresponding to the S/R requests completed first asantk, Set neighbork=O−tabuk1−tabuk2 (the set of nodes that the antk can access), and the random number between 0,1 is assigned to pm. If the current node accessed by antk is the storage request node, go to Step 6, otherwise, go to Step 7.Step 6.
Equation (3) is applied to calculate the selection probability of the storage request node to each accessible node in set neighbork, and then the roulette method is applied to determine the next accessed node for antk, then the determined node is added to the set of antk has accessed nodes, go to Step 8.Step 7.
The source address of the retrieval request and the four nearest I/O points constitute four retrieval requests. Equation (3) is applied to calculate the selection probability of the four retrieval requests to each node in set neighbork, respectively. And then the roulette method is applied to determine the next accessed node for antk, then the determined node is added to the set of antk has accessed nodes.Step 8.
According to the noncrossing constraint (equation (6)), judge whether there is an operation collision between the two S/R requests which are represented by the node currently accessed by each pair of ants. If the noncrossing constraint is violated, add the avoidance time to the cumulative makespan. Calculate the makespan of the current S/R request and accumulate it to the cumulative makespan of the current ant.Step 9.
Repeat Steps5 to 8 to determine the next node for each ant to access until each pair of ants complete the traversal of all nodes, i.e., neighbork=ϕ, record all scheduling schemes obtained in this cycle.Step 10.
The shortest time scheduling scheme is selected as the optimal solution of this cycle, and compared with the current optimal solution to update. If the current optimal solution is not changed, thenN=N+1, otherwise N=1.Step 11.
If the repeat number of the current optimal solution is greater thanN, the current optimal solution is output and the algorithm stops. Otherwise, equations (4) and (5) shall be applied to update the weight pheromone and ordinary pheromone respectively, clear the node set that the ants have accessed, the dwell-point node of two stackers is assigned to each pair of ants, meanwhile the node is added to the set of the ant has accessed nodes, go to Step 3.


## 3.1. MIP Mode

Applying the notation summarized in Table1, we constructed the MIP model for the problem of the I/O point assignment and the scheduling of two stackers, which consists of objective function (1) and constraints (2)–(6).(1)T=minmaxTk,Tk′kandk′are elements of setM,s.t.∑p∈PYip=1∀i∈R,∑k∈MZik=1∀i∈J,∑j∈JkXijk≤1∀,i∈Jkandi≠j,∀k∈M,0≤qk≤2∀k∈M,Ckt−Ck′t≥Dk,k′∈M,t∈0,T.Table 1
Notation definition.
NotationNotation meaningJSet of S/R requestsRSet of retrieval requestsMSet of stackersPSet of I/O pointsTMinimum makespan of the S/R requests sequenceDSafe operational distance between twin stackersJkThe set of S/R requests assigned to stackerkTkThe makespan to complete the S/R requests assigned to the stackerkqkLoad capacity of stackerkCktAddress of stackerk at time tXijkXijkis an element of0,1, 1 indicates that stacker k completes S/R request i before executing S/R request j, and 0 otherwiseYipYipis an element of0,1, 1 indicates that retrieval request i selects I/O point p as the destination address, and 0 otherwiseZikZikis an element of0,1, 1 indicates that S/R request i is assigned to stacker k, and 0 otherwiseThe objective function (1) minimizes the S/R requests sequence makespan which is the longer makespan of the twin stackers. Constraint (2) ensures that only one output point can be assigned as the destination address for each retrieval request. Constraint (3) ensures that each S/R request can be executed by only one stacker. Constraint (4) ensures that each S/R requests assigned to each stacker is executed in the order of sorting. Constraint (5) ensures that the stacker capacity does not exceed the maximum load, and constraint (6) ensures that the working distance between two stackers is not less than the minimum safe operational distance (noncrossing constraint).


## 3.2. Algorithm

Suppose that the output point has been assigned to each retrieval request, if each S/R request is considered as a node without considering the DUT and noncrossing constraint, the sorting and grouping problem of the S/R requests becomes the problem that twin stackers traverse all the nodes and each node can only traverse once. This problem is similar to the open multiple traveling salesman problem (MTSP) after simplification. Ant colony algorithm (ACA) is often used to solve TSP problem. The key of using ACA to solve the traveling salesman problem is to be able to transform the problem into a graph with nodes and edges [55]. The ACA solves the MTSP with higher precision within a shorter time frame than the exact algorithm [56]. If the S/R requests are regarded as nodes, and the sum of the makespan from the destination address of any S/R request to the source address of any other S/R request and the makespan to complete the current S/R request is taken as the weight of each edge between two nodes, then all S/R requests can be transformed into a graph with nodes and edges. In order to avoid the drawback that ACA is easy to fall into local optima, a weight pheromone and a disturbance strategy are introduced into the algorithm [57, 58]. This section designs an improved ACA for solving the proposed integrated optimization problem.


### 3.2.1. Weight Pheromone

Different from ordinary pheromones, the weight pheromone is used to describe the weight of each subpath in the optimal path, and its update is based on the global information. Letξijt represent the weight pheromone value from node i to node j. The weight pheromone is neither volatilized nor superimposed, and its value is updated after traversal by ants. The update formula is given by(2)ξijt+n=CTkCTk>ξijt,ξijtotherwise,where C is a constant, and Tk is the makespan for the kth pair of ant to complete traversal. As indicated in equation (2), the weight pheromone of the longer subpath in the shorter path can get the second enhancement, increasing the probability of selecting that subpath and hence improving the global convergence of the algorithm.


### 3.2.2. Transfer Strategies

The ordinary pheromone indicates the selection probability of the local path, whereas the weight pheromone reflects the global information. Although the two pheromones play a positive feedback role on the optimal information in the process of path search, they should have different heuristic factors in the probability selection formula. The ordinary pheromone indicates the transition probability of the local path, whereas the weight pheromone reflects the global information. Although the two pheromones play a positive feedback role on the optimal information in the process of path search, they should have different heuristic factors in the probability selection formula. Ants will be affected by the transition probability when it searches path. The path with higher transition probability will be selected by more ants With the action of positive feedback, if ants continue to select the path with high transition probability, the pheromone on the current optimal path will be more than that on the undetected optimal path, and the probability of selecting the undetected optimal path will be smaller and smaller, resulting in the phenomenon of falling into local optimization. In order to avoid this situation, the disturbance factor is added in the process of ant selecting path. Through the interference of disturbance factor, the transformation of the transfer probability formula in the process of path selection is completed, so that the different combinations of ordinary pheromone, weight pheromone, and expected information urge ants to choose the path whose pheromone is not the most with a certain probability. The introduction of disturbance factor realizes the dynamic adjustment of transition probability in the process of searching path and improves the diversity of path selection. Moreover, the probability of the path with the largest residual pheromone is calculated individually to prevent the optimal path from being missed. These ideas are combined into the following probability selection formula with a random mutation rate.(3)pijkt=τijαtηijβtξijγt∑j∈Okτijαtηijβtξijγt,τijt=maxτijt,i∈O;,τijαtηijtξijγt∑j∈Okτijαtηijβtξijγt,τijt≠maxτijt,pm≤p1,i∈O;,τijtηijβtξijγt∑j∈Okτijαtηijβtξijγt,τijt≠maxτijt,p1<pm<p2,i∈O;,τijtηijtξijγt∑j∈Okτijαtηijβtξijγt,τijt≠maxτijt,p2≤pm,i∈O;,0,otherwise.In equation (3), τijt denotes the residual value of the ordinary pheromone between nodes i and j at time t, the calculation formula is equation (4). ηijt is the reciprocal of τijt, indicating the expected degree of transfer from node i to node j, and ξijt is the weight pheromone value at time t between nodes i and j, the calculation formula is equation (2). α denotes the importance degree of the residual ordinary pheromone in the process of path selection, β denotes the role played by the heuristic information in the process of path selection, and γ is the importance degree of the weight pheromone in the process of path selection. Ok denotes the node set currently accessible by ant k. The random mutation rate pm is uniformly distributed on interval 0,1, p1 and p2 are constants.(4)τijt=1−ρτijt−n.In equation (4), ρ is pheromone volatilization coefficient between time periods (t − n, t). After ants complete the traversal of all nodes, enhance the ordinary pheromone of the path passed by ants, the calculation of the enhancement is shown in the following equation:(5)△τij=∑k=1m△τijk.In equation (5), △τijk is the amount of ordinary pheromone left by the kth ant between node i and j in this iteration, the calculation of △τijk is shown in the following equation:(6)△τijk=QLkif thekth ant gose fromitoj,0otherwise.In equation (6), Q is a constant, and Lk is the makespan for the kth pair of ants to complete all S/R requests.


### 3.2.3. Algorithm Procedure

Because the DUT can change the access sequence of the stacker operation address (as shown in Figure3), thus shortening the makespan of the stacker. Whether the two S/R requests can perform DUT is judged by the following conditions.(1)
The two S/R requests are adjacent, and the transport paths of the two S/R requests are in the same direction along the aisle and overlapping;(2)
Both S/R requests satisfy any of the conditions listed in Table2.The four operational conditions listed in Table2 are demonstrated in Figure 5.Table 2
Working conditions of the DUT.
YUnloading sequenceLoading methodsRelation between source addresses and destination addresses1First load first unloadOne side loadingSource addresses and destination addresses of the “first unload” container are on opposite sides of the loading platform2First load first unloadBoth side loadingSource addresses and destination addresses of the “first unload” container are on the same side of the loading platform3Last load first unloadOne side loadingSource addresses and destination addresses of the “first unload” container are on the same side of the loading platform4Last load first unloadBoth side loadingSource addresses and destination addresses of the “first unload” container are on opposite sides of the loading platformFigure 5
Position relation of the double units transport.Under the decision conditions of the DUT, when the destination address of the retrieval request is unknown, we can change the front–back and left–right positions of the destination address relative the source address to construct the DUT. If the search neighborhood of the I/O point assignment is classified by its positional relationship (front, back, left, and right) relative the source address, the I/O point assignment becomes the selection of the location relationship. Since the objective function is minimize the makespan, the set of I/O points in the optimal solution can be composed of the I/O points closest to the source address in the four directions.In summary, the retrieval request node contains the source address and four optional destination addresses. Each destination address and source address constitute a retrieval request, and one edge connected to the destination address points to the source address of other nodes. The weight of the edge is the sum of the makespan of the current retrieval request and the makespan from the current I/O point to the source address of other nodes. The number of edges pointing to the retrieval request node depends on the type of node. The number of edges is 4 if it is a retrieval request node, and the number of edges is 1 if it is a storage request node. The structure and connection with other nodes of the retrieval request node are shown in Figure6. The structure of the storage request node is relatively simple, having only the source address and destination address, and both of them are known. This node has only one edge pointing to other nodes, and the weight of the edge is the sum of the makespan from the destination address of the current node to the source address of other nodes and the makespan to complete the current storage request. The number of edges pointing to the storage request node depends on the type of node. If it is a retrieval request node, the number of edges is 4. If it is a storage request node, the number of edges is 1. The structure and connection with other nodes of the storage request node are shown in Figure 7. Except the above two types of nodes, there are dwell-point nodes. This kind of node represents the dwell-point address of the stacker. It has only the edge pointing to other nodes, and the weight of the edge is the makespan from the current address to the source address of other nodes.Figure 6
S/R request nodes.Figure 7
Storage request nodes.The graph of search space for ant colony algorithm proposed in this paper consists of the above three types of nodes. In the graph, each S/R request node corresponds to an S/R request. The number of S/R request nodes depends on the number of S/R requests, while the number of dwell-point nodes depends on the number of stackers. In this paper, the number of stackers is 2. The graph of search space with 6 S/R requests is shown in Figure8. The graph includes two retrieval request nodes R1 and R2, four storage request nodes S1, S2, S3, S4 and two dwell-point nodes ST1 and ST2. Both R1 and R2 have 20 edges pointing to other nodes in the graph, and there are 4 edges for other nodes except ST1 and ST2. There are 10 edges pointing to R1 and R2, respectively, of which S1, S2, S3, S4, ST1, and ST2 have one edge pointing to R1 and R2, respectively, and the edges from R1 to R2 and from R2 to R1 are all 4. Each storage node has 5 edges pointing to other nodes (except ST1 and ST2) and 13 edges pointing to each storage node. For example, S1 has five edges pointing to nodes S2, S3, S4, R1, and R2, respectively. Each node in S2, S3, S4, ST1, and ST2 has one edge pointing to S1, and each node in R1 and R2 has four edges pointing to S1, with a total of 13 edges. ST1 and ST2 have only 6 edges pointing to other nodes, respectively, and there are no edges pointing to ST1 or ST2.Figure 8
Path optimization graph of algorithm.The basic idea of ant colony algorithm is to first generate the path optimization graph of the S/R requests set. The path nodes in the graph are divided into retrieval request node, storage request node, and dwell-point node. The storage request node includes the source address and destination address, the retrieval request node includes the source address and four optional destination addresses, and the dwell-point node only includes the dwell-point address of stacker. The initial value of the weight pheromone between any two nodes in the graph is 0, and the initial value of the ordinary pheromone between any two nodes is the reciprocal of the makespan required for the stacker to complete the S/R request represented by the current node and move to the source address of the next node. The number of ants generated is double the number of S/R requests, each ant representing a stacker, and two ants form a group. Nodes that are not accessed by the current ant and its group partner constitute the set of candidate nodes that the current ant can access, and the selection probability of the current node to each node in the candidate node set is calculated through the probability selection equation (3). If the current node is a retrieval request node with unknown destination address, the selection probabilities of the retrieval request composed of four optional destination addresses to each accessible node needs to be calculated, respectively. If the current node is a storage request node, we only need to calculate the selection probability of the storage request node to each accessible path node. After calculating the selection probability from the current node to each node in the candidate node set, the roulette method is used to select the next access node of the current ant. Repeat the path node selection operation until the two ants have accessed all nodes exactly once, a solution is obtained. The nodes passed through by ant constitute the S/R requests assigned to the stacker represented by the ant, and the sequence of each ant passing through the nodes is the S/R request execution sequence. Finally, the selected destination address of the retrieval request node is the output point of that retrieval request. Record the current optimal solution and judge whether it meets the termination conditions of the algorithm. If not, enhance the ordinary pheromone according to equation (5) and update the weight pheromone according to equation (2). Otherwise, the current optimal solution is output and exit.Based on the above search process, a feasible solution of the graph for searching space shown in Figure8 is depicted in Figure 9. Departing from ST1 and ST2, respectively, ant1 and ant2 select the next node accessed by itself through probability selection formula (3) and roulette method. When the ant is in the dwell-point node or storage request node, the ant selects the next node in the same way. For example, if ant1 is at node S2, its accessible node set is {R1, R2, S3, S4}, the selection probability from S2 to R1, R2, S3, S4 is calculated by formula (3), respectively, and then the roulette method is used to select the next node accessed by ant1. When the ant is at the retrieval request node, it completes the selection of the next node and the destination address of the retrieval request simultaneously. For example, when ant1 is at node R1, its accessible node set is {S3, S4}. Formula (3) is applied to calculate the selection probability of the four destination addresses of R1 to S3 and S4, respectively, and then the roulette method is used to select the next accessed node of ant1. After the edge from R1 to S3 is determined, the I/O point corresponding to this edge is the destination address of R1. Repeat the above two node selection methods until all nodes are traversed, a feasible solution is obtained. The feasible solution shown in Figure 9 means that the S/R request sequence executed by stacker 1 is: S2 ⟶ R1 ⟶ S3, the S/R request sequence executed by Stacker 2 is: S1 ⟶ R2 ⟶ S4, and the destination addresses of R1 and R2 are the I/O point corresponding to the edge of R1 ⟶ S3 and R2 ⟶ S4, respectively. The detailed steps of the algorithm are as follows. The algorithm flowchart is shown in Figure 10.Figure 9
Feasible solution of algorithm.Figure 10
Algorithm flowchart.Step 1.
Define the path node setO, whose size is the number of the S/R requests plus 2. The source address and destination address of the storage request are assigned to the storage request node, the source address of the retrieval request and the I/O points closest to the source address in 4 directions are assigned to the retrieval request node, and the two stackers dwell-points are assigned to the stacker dwell-point nodes. Calculate the makespan between any two nodes, and the initial value of ordinary pheromone between any two nodes is the reciprocal of the makespan. The initial value of weight pheromone between any two nodes is 0. Set tabuk1=ϕ, tabuk2=ϕ (the set of nodes already accessed by each pair of ants), neighbork=ϕ (the set of nodes that each pair of ants may access in the next step), WorkTimek1=0, WorkTimek2=0 (the cumulative makespan of each pair of ants), N=0 (the repeat umber of the current optimal solution).Step 2.
Generate ants which number is double the number of S/R requests, two ants form a group. The initial address of the dwell-point node is assigned to each pair of ants, respectively, meanwhile the dwell-point node is added totabuk1 and tabuk2 respectively.Step 3.
Setneighbork=O−tabuk1−tabuk2 (the set of nodes that each pair of ants can access), meanwhile generate random number between 0,1 and assign to pm. Equation (3) is applied to calculate the selection probability of the dwell-point to each accessible node in the set neighbork, and then the roulette method is applied to determine the next accessed node for the current ant, then the determined node is added to the set of the current ant has accessed nodes.Step 4.
According to the noncrossing constraint (equation (6)) judge whether there is an operation collision between the two S/R requests which are represented by the node currently accessed by each pair of ants. If the noncrossing constraint is violated, add the avoidance time to the cumulative makespan. Calculate the makespan of the current S/R request and accumulate it to the cumulative makespan of the current ant. Repeat Steps 3 and 4 to determine the first access node for each ant.Step 5.
Judge which of the S/R requests corresponding to the node currently accessed by each pair of ants is completed first, and set the ant corresponding to the S/R requests completed first asantk, Set neighbork=O−tabuk1−tabuk2 (the set of nodes that the antk can access), and the random number between 0,1 is assigned to pm. If the current node accessed by antk is the storage request node, go to Step 6, otherwise, go to Step 7.Step 6.
Equation (3) is applied to calculate the selection probability of the storage request node to each accessible node in set neighbork, and then the roulette method is applied to determine the next accessed node for antk, then the determined node is added to the set of antk has accessed nodes, go to Step 8.Step 7.
The source address of the retrieval request and the four nearest I/O points constitute four retrieval requests. Equation (3) is applied to calculate the selection probability of the four retrieval requests to each node in set neighbork, respectively. And then the roulette method is applied to determine the next accessed node for antk, then the determined node is added to the set of antk has accessed nodes.Step 8.
According to the noncrossing constraint (equation (6)), judge whether there is an operation collision between the two S/R requests which are represented by the node currently accessed by each pair of ants. If the noncrossing constraint is violated, add the avoidance time to the cumulative makespan. Calculate the makespan of the current S/R request and accumulate it to the cumulative makespan of the current ant.Step 9.
Repeat Steps5 to 8 to determine the next node for each ant to access until each pair of ants complete the traversal of all nodes, i.e., neighbork=ϕ, record all scheduling schemes obtained in this cycle.Step 10.
The shortest time scheduling scheme is selected as the optimal solution of this cycle, and compared with the current optimal solution to update. If the current optimal solution is not changed, thenN=N+1, otherwise N=1.Step 11.
If the repeat number of the current optimal solution is greater thanN, the current optimal solution is output and the algorithm stops. Otherwise, equations (4) and (5) shall be applied to update the weight pheromone and ordinary pheromone respectively, clear the node set that the ants have accessed, the dwell-point node of two stackers is assigned to each pair of ants, meanwhile the node is added to the set of the ant has accessed nodes, go to Step 3.


## 3.2.1. Weight Pheromone

Different from ordinary pheromones, the weight pheromone is used to describe the weight of each subpath in the optimal path, and its update is based on the global information. Letξijt represent the weight pheromone value from node i to node j. The weight pheromone is neither volatilized nor superimposed, and its value is updated after traversal by ants. The update formula is given by(2)ξijt+n=CTkCTk>ξijt,ξijtotherwise,where C is a constant, and Tk is the makespan for the kth pair of ant to complete traversal. As indicated in equation (2), the weight pheromone of the longer subpath in the shorter path can get the second enhancement, increasing the probability of selecting that subpath and hence improving the global convergence of the algorithm.


## 3.2.2. Transfer Strategies

The ordinary pheromone indicates the selection probability of the local path, whereas the weight pheromone reflects the global information. Although the two pheromones play a positive feedback role on the optimal information in the process of path search, they should have different heuristic factors in the probability selection formula. The ordinary pheromone indicates the transition probability of the local path, whereas the weight pheromone reflects the global information. Although the two pheromones play a positive feedback role on the optimal information in the process of path search, they should have different heuristic factors in the probability selection formula. Ants will be affected by the transition probability when it searches path. The path with higher transition probability will be selected by more ants With the action of positive feedback, if ants continue to select the path with high transition probability, the pheromone on the current optimal path will be more than that on the undetected optimal path, and the probability of selecting the undetected optimal path will be smaller and smaller, resulting in the phenomenon of falling into local optimization. In order to avoid this situation, the disturbance factor is added in the process of ant selecting path. Through the interference of disturbance factor, the transformation of the transfer probability formula in the process of path selection is completed, so that the different combinations of ordinary pheromone, weight pheromone, and expected information urge ants to choose the path whose pheromone is not the most with a certain probability. The introduction of disturbance factor realizes the dynamic adjustment of transition probability in the process of searching path and improves the diversity of path selection. Moreover, the probability of the path with the largest residual pheromone is calculated individually to prevent the optimal path from being missed. These ideas are combined into the following probability selection formula with a random mutation rate.(3)pijkt=τijαtηijβtξijγt∑j∈Okτijαtηijβtξijγt,τijt=maxτijt,i∈O;,τijαtηijtξijγt∑j∈Okτijαtηijβtξijγt,τijt≠maxτijt,pm≤p1,i∈O;,τijtηijβtξijγt∑j∈Okτijαtηijβtξijγt,τijt≠maxτijt,p1<pm<p2,i∈O;,τijtηijtξijγt∑j∈Okτijαtηijβtξijγt,τijt≠maxτijt,p2≤pm,i∈O;,0,otherwise.In equation (3), τijt denotes the residual value of the ordinary pheromone between nodes i and j at time t, the calculation formula is equation (4). ηijt is the reciprocal of τijt, indicating the expected degree of transfer from node i to node j, and ξijt is the weight pheromone value at time t between nodes i and j, the calculation formula is equation (2). α denotes the importance degree of the residual ordinary pheromone in the process of path selection, β denotes the role played by the heuristic information in the process of path selection, and γ is the importance degree of the weight pheromone in the process of path selection. Ok denotes the node set currently accessible by ant k. The random mutation rate pm is uniformly distributed on interval 0,1, p1 and p2 are constants.(4)τijt=1−ρτijt−n.In equation (4), ρ is pheromone volatilization coefficient between time periods (t − n, t). After ants complete the traversal of all nodes, enhance the ordinary pheromone of the path passed by ants, the calculation of the enhancement is shown in the following equation:(5)△τij=∑k=1m△τijk.In equation (5), △τijk is the amount of ordinary pheromone left by the kth ant between node i and j in this iteration, the calculation of △τijk is shown in the following equation:(6)△τijk=QLkif thekth ant gose fromitoj,0otherwise.In equation (6), Q is a constant, and Lk is the makespan for the kth pair of ants to complete all S/R requests.


## 3.2.3. Algorithm Procedure

Because the DUT can change the access sequence of the stacker operation address (as shown in Figure3), thus shortening the makespan of the stacker. Whether the two S/R requests can perform DUT is judged by the following conditions.(1)
The two S/R requests are adjacent, and the transport paths of the two S/R requests are in the same direction along the aisle and overlapping;(2)
Both S/R requests satisfy any of the conditions listed in Table2.The four operational conditions listed in Table2 are demonstrated in Figure 5.Table 2
Working conditions of the DUT.
YUnloading sequenceLoading methodsRelation between source addresses and destination addresses1First load first unloadOne side loadingSource addresses and destination addresses of the “first unload” container are on opposite sides of the loading platform2First load first unloadBoth side loadingSource addresses and destination addresses of the “first unload” container are on the same side of the loading platform3Last load first unloadOne side loadingSource addresses and destination addresses of the “first unload” container are on the same side of the loading platform4Last load first unloadBoth side loadingSource addresses and destination addresses of the “first unload” container are on opposite sides of the loading platformFigure 5
Position relation of the double units transport.Under the decision conditions of the DUT, when the destination address of the retrieval request is unknown, we can change the front–back and left–right positions of the destination address relative the source address to construct the DUT. If the search neighborhood of the I/O point assignment is classified by its positional relationship (front, back, left, and right) relative the source address, the I/O point assignment becomes the selection of the location relationship. Since the objective function is minimize the makespan, the set of I/O points in the optimal solution can be composed of the I/O points closest to the source address in the four directions.In summary, the retrieval request node contains the source address and four optional destination addresses. Each destination address and source address constitute a retrieval request, and one edge connected to the destination address points to the source address of other nodes. The weight of the edge is the sum of the makespan of the current retrieval request and the makespan from the current I/O point to the source address of other nodes. The number of edges pointing to the retrieval request node depends on the type of node. The number of edges is 4 if it is a retrieval request node, and the number of edges is 1 if it is a storage request node. The structure and connection with other nodes of the retrieval request node are shown in Figure6. The structure of the storage request node is relatively simple, having only the source address and destination address, and both of them are known. This node has only one edge pointing to other nodes, and the weight of the edge is the sum of the makespan from the destination address of the current node to the source address of other nodes and the makespan to complete the current storage request. The number of edges pointing to the storage request node depends on the type of node. If it is a retrieval request node, the number of edges is 4. If it is a storage request node, the number of edges is 1. The structure and connection with other nodes of the storage request node are shown in Figure 7. Except the above two types of nodes, there are dwell-point nodes. This kind of node represents the dwell-point address of the stacker. It has only the edge pointing to other nodes, and the weight of the edge is the makespan from the current address to the source address of other nodes.Figure 6
S/R request nodes.Figure 7
Storage request nodes.The graph of search space for ant colony algorithm proposed in this paper consists of the above three types of nodes. In the graph, each S/R request node corresponds to an S/R request. The number of S/R request nodes depends on the number of S/R requests, while the number of dwell-point nodes depends on the number of stackers. In this paper, the number of stackers is 2. The graph of search space with 6 S/R requests is shown in Figure8. The graph includes two retrieval request nodes R1 and R2, four storage request nodes S1, S2, S3, S4 and two dwell-point nodes ST1 and ST2. Both R1 and R2 have 20 edges pointing to other nodes in the graph, and there are 4 edges for other nodes except ST1 and ST2. There are 10 edges pointing to R1 and R2, respectively, of which S1, S2, S3, S4, ST1, and ST2 have one edge pointing to R1 and R2, respectively, and the edges from R1 to R2 and from R2 to R1 are all 4. Each storage node has 5 edges pointing to other nodes (except ST1 and ST2) and 13 edges pointing to each storage node. For example, S1 has five edges pointing to nodes S2, S3, S4, R1, and R2, respectively. Each node in S2, S3, S4, ST1, and ST2 has one edge pointing to S1, and each node in R1 and R2 has four edges pointing to S1, with a total of 13 edges. ST1 and ST2 have only 6 edges pointing to other nodes, respectively, and there are no edges pointing to ST1 or ST2.Figure 8
Path optimization graph of algorithm.The basic idea of ant colony algorithm is to first generate the path optimization graph of the S/R requests set. The path nodes in the graph are divided into retrieval request node, storage request node, and dwell-point node. The storage request node includes the source address and destination address, the retrieval request node includes the source address and four optional destination addresses, and the dwell-point node only includes the dwell-point address of stacker. The initial value of the weight pheromone between any two nodes in the graph is 0, and the initial value of the ordinary pheromone between any two nodes is the reciprocal of the makespan required for the stacker to complete the S/R request represented by the current node and move to the source address of the next node. The number of ants generated is double the number of S/R requests, each ant representing a stacker, and two ants form a group. Nodes that are not accessed by the current ant and its group partner constitute the set of candidate nodes that the current ant can access, and the selection probability of the current node to each node in the candidate node set is calculated through the probability selection equation (3). If the current node is a retrieval request node with unknown destination address, the selection probabilities of the retrieval request composed of four optional destination addresses to each accessible node needs to be calculated, respectively. If the current node is a storage request node, we only need to calculate the selection probability of the storage request node to each accessible path node. After calculating the selection probability from the current node to each node in the candidate node set, the roulette method is used to select the next access node of the current ant. Repeat the path node selection operation until the two ants have accessed all nodes exactly once, a solution is obtained. The nodes passed through by ant constitute the S/R requests assigned to the stacker represented by the ant, and the sequence of each ant passing through the nodes is the S/R request execution sequence. Finally, the selected destination address of the retrieval request node is the output point of that retrieval request. Record the current optimal solution and judge whether it meets the termination conditions of the algorithm. If not, enhance the ordinary pheromone according to equation (5) and update the weight pheromone according to equation (2). Otherwise, the current optimal solution is output and exit.Based on the above search process, a feasible solution of the graph for searching space shown in Figure8 is depicted in Figure 9. Departing from ST1 and ST2, respectively, ant1 and ant2 select the next node accessed by itself through probability selection formula (3) and roulette method. When the ant is in the dwell-point node or storage request node, the ant selects the next node in the same way. For example, if ant1 is at node S2, its accessible node set is {R1, R2, S3, S4}, the selection probability from S2 to R1, R2, S3, S4 is calculated by formula (3), respectively, and then the roulette method is used to select the next node accessed by ant1. When the ant is at the retrieval request node, it completes the selection of the next node and the destination address of the retrieval request simultaneously. For example, when ant1 is at node R1, its accessible node set is {S3, S4}. Formula (3) is applied to calculate the selection probability of the four destination addresses of R1 to S3 and S4, respectively, and then the roulette method is used to select the next accessed node of ant1. After the edge from R1 to S3 is determined, the I/O point corresponding to this edge is the destination address of R1. Repeat the above two node selection methods until all nodes are traversed, a feasible solution is obtained. The feasible solution shown in Figure 9 means that the S/R request sequence executed by stacker 1 is: S2 ⟶ R1 ⟶ S3, the S/R request sequence executed by Stacker 2 is: S1 ⟶ R2 ⟶ S4, and the destination addresses of R1 and R2 are the I/O point corresponding to the edge of R1 ⟶ S3 and R2 ⟶ S4, respectively. The detailed steps of the algorithm are as follows. The algorithm flowchart is shown in Figure 10.Figure 9
Feasible solution of algorithm.Figure 10
Algorithm flowchart.Step 1.
Define the path node setO, whose size is the number of the S/R requests plus 2. The source address and destination address of the storage request are assigned to the storage request node, the source address of the retrieval request and the I/O points closest to the source address in 4 directions are assigned to the retrieval request node, and the two stackers dwell-points are assigned to the stacker dwell-point nodes. Calculate the makespan between any two nodes, and the initial value of ordinary pheromone between any two nodes is the reciprocal of the makespan. The initial value of weight pheromone between any two nodes is 0. Set tabuk1=ϕ, tabuk2=ϕ (the set of nodes already accessed by each pair of ants), neighbork=ϕ (the set of nodes that each pair of ants may access in the next step), WorkTimek1=0, WorkTimek2=0 (the cumulative makespan of each pair of ants), N=0 (the repeat umber of the current optimal solution).Step 2.
Generate ants which number is double the number of S/R requests, two ants form a group. The initial address of the dwell-point node is assigned to each pair of ants, respectively, meanwhile the dwell-point node is added totabuk1 and tabuk2 respectively.Step 3.
Setneighbork=O−tabuk1−tabuk2 (the set of nodes that each pair of ants can access), meanwhile generate random number between 0,1 and assign to pm. Equation (3) is applied to calculate the selection probability of the dwell-point to each accessible node in the set neighbork, and then the roulette method is applied to determine the next accessed node for the current ant, then the determined node is added to the set of the current ant has accessed nodes.Step 4.
According to the noncrossing constraint (equation (6)) judge whether there is an operation collision between the two S/R requests which are represented by the node currently accessed by each pair of ants. If the noncrossing constraint is violated, add the avoidance time to the cumulative makespan. Calculate the makespan of the current S/R request and accumulate it to the cumulative makespan of the current ant. Repeat Steps 3 and 4 to determine the first access node for each ant.Step 5.
Judge which of the S/R requests corresponding to the node currently accessed by each pair of ants is completed first, and set the ant corresponding to the S/R requests completed first asantk, Set neighbork=O−tabuk1−tabuk2 (the set of nodes that the antk can access), and the random number between 0,1 is assigned to pm. If the current node accessed by antk is the storage request node, go to Step 6, otherwise, go to Step 7.Step 6.
Equation (3) is applied to calculate the selection probability of the storage request node to each accessible node in set neighbork, and then the roulette method is applied to determine the next accessed node for antk, then the determined node is added to the set of antk has accessed nodes, go to Step 8.Step 7.
The source address of the retrieval request and the four nearest I/O points constitute four retrieval requests. Equation (3) is applied to calculate the selection probability of the four retrieval requests to each node in set neighbork, respectively. And then the roulette method is applied to determine the next accessed node for antk, then the determined node is added to the set of antk has accessed nodes.Step 8.
According to the noncrossing constraint (equation (6)), judge whether there is an operation collision between the two S/R requests which are represented by the node currently accessed by each pair of ants. If the noncrossing constraint is violated, add the avoidance time to the cumulative makespan. Calculate the makespan of the current S/R request and accumulate it to the cumulative makespan of the current ant.Step 9.
Repeat Steps5 to 8 to determine the next node for each ant to access until each pair of ants complete the traversal of all nodes, i.e., neighbork=ϕ, record all scheduling schemes obtained in this cycle.Step 10.
The shortest time scheduling scheme is selected as the optimal solution of this cycle, and compared with the current optimal solution to update. If the current optimal solution is not changed, thenN=N+1, otherwise N=1.Step 11.
If the repeat number of the current optimal solution is greater thanN, the current optimal solution is output and the algorithm stops. Otherwise, equations (4) and (5) shall be applied to update the weight pheromone and ordinary pheromone respectively, clear the node set that the ants have accessed, the dwell-point node of two stackers is assigned to each pair of ants, meanwhile the node is added to the set of the ant has accessed nodes, go to Step 3.


## 4. Computational Experiments

To verify the effectiveness of the proposed optimization method, computational experiments are conducted in this section. Firstly, we generate different scenarios with small-sized and large-sized instances, and apply different optimization methods to do computational experiments. Secondly, the calculation results are compared and analyzed. The experimental software is Matlab R2014a and run on a personal computer with a 2.5 GHz processor and 8 GHz RAM. Since metaheuristic algorithms are sensitive to their input parameters [59], the values of parameters in the algorithm are obtained by sensitivity analysis. Due to the large number of parameters in the algorithm, to take into account the diversity of parameter value combination schemes and the rapidity of parameter value combination process, the uniform design method is introduced in the analysis process [60]. The steps of this method are as follows. Firstly, the uniform design table is established to determine the range of each parameter. Then, the experimental calculation is carried out according to the uniform design table. Finally, the parameter values are determined according to the calculation results. Based on the statistical results of the above experiments, the algorithm parameter value is further adjusted by the method of single parameter sensitivity analysis. The parameter values determined by two-stage statistical analysis are shown in Table 3.Table 3
Initial parameters of the algorithm.
Algorithm parametersParameter valueThe repeat number of the current optimal solutionN30Influence factors of residual pheromoneα2Influence factors of heuristic informationβ1.5Influence factors of weight pheromoneγ10Pheromone volatilization coefficientρ0.1Selection probabilityp1,p2p1=1/4,p2=2/3Ordinary pheromone enhancement constantQ1Weight pheromone update constantC1


### 4.1. Calculation Instances

We consider that the layout of multi-I/O points AS/RS with different quantity I/O points is similar to Figure1(a). Two stackers operate simultaneously in the aisle. The horizontal speed of the stacker is 2 m/s, and the vertical speed of the stacker is 0.4 m/s. The size of rack is 2 rows, 5 layers, and 45 columns, with a width of 2.8 m and a height of 2.4 m. The details on instances generation are presented as follows.For small-sized instances, the number of I/O points (left I/O point-right I/O point) is set to 4 (2–2), 5 (2–3), and 6 (3–3), and the number of S/R requests is 5, 6, and 8. The S/R requests are generated randomly. In large-sized instances, the number of I/O points is 15 (7–8), 18 (9–9), and 23 (11–12), and the number of S/R requests is 20, 25, 30, 35, 40, and 50, respectively.


### 4.2. Computational Results and Analysis

#### 4.2.1. Small-Sized Instances

The computational results for small-sized instances are shown in Table4. For small-sized instances, ant colony algorithm can obtain the optimal solution or suboptimal solution of the problem with high probability. The average makespan is quite near to that of the optimal solution. With the increase in the number of I/O points and S/R requests, the solution space of the feasible solution of the problem increases sharply, and the CPU time of CPLEX also increases greatly. The number of I/O points and the number of S/R requests have great influence on the CPU time of CPLEX. However, the CPU time of ant colony algorithm is less affected by the size of the problem, and the difference between the maximum CPU time and the average CPU time is less than 2 seconds. In the instance of n = 8, the average value of the objective function and average value of CPU time of CPLEX and ant colony algorithm are illustrated in Figure 11. It is intuitively shown that the average value gap of the objective function between CPLEX and ant colony algorithm is very small, whereas the CPU time gap becomes larger with the increase of I/O point scale. The computational results for small-sized instances indicate that the ant colony algorithm is effective for small-sized randomly generated instances.Table 4
Computational results for small-sized instances.
mnCPLEXAnt colonyGAPaobj1CPU1obj2SUBOPTAVGNUM_OPTCPU24588.848.606188.89088.9294.23210.1346100.8104.1242100.8100.8100.80106.35590.0048114.0743.2382114.0115.2114.2485.98570.214585.253.283285.287.685.4496.38800.2846126.0100.6682126.0130.8126.4898.02540.3848111.6816.3781111.6115.2114.6876.58902.694576.854.366176.876.876.80106.02450.0046130.8102.2810130.8139.2131.6494.35290.6448160.8742.0237160.8162166.2866.32903.305568.480.712968.474.469.0097.25640.8756108.0165.9259108.0115.2109.4487.56681.3258138.01705.3464138.0144146.6056.59025.875568.479.340468.470.868.8887.85400.7056126.0162.2359126.0126126.00108.06500.0058129.61699.1107129.6130.8134.9675.62143.975572.085.955472.076.872.4895.21040.6656141.6165.3859141.6142.8141.7295.86240.0858134.41699.1107134.4139.2139.4066.16143.596554.0120.498554.055.254.1295.36210.226684.0244.962884.091.285.4486.32261.6968141.63147.0655141.6144148.6046.97514.716576.8122.248176.87876.9295.02160.166697.2241.930297.299.697.6886.18990.4968105.63087.8198105.6109.8115.7057.32648.736586.4121.315086.486.486.40106.28510.006698.4239.130898.4100.298.7686.85120.3668115.22839.4768115.2122.4126.2437.25608.75m: the number of I/O points, n: the number of S/R requests, obj: objective function value (s), SUBOPT: suboptimal solution (s), CPU: computation time (s), AVG: Average of 10 calculations, NUM_OPT: the number of optimal solution plus the number of suboptimal solution in 10 calculations, GAPa = (AVG − obj1)/AVG∗100% (%).Figure 11
Objective function value and CPU time for small-sized instances.


#### 4.2.2. Large-Sized Instances

For large-sized instances, we solve the problem by CPLEX, phased algorithm, and ant colony algorithm, respectively. We set the computation time threshold limit to 18000 s for CPLEX, and then we record the incumbent solution and its corresponding lower bound. In the phased algorithm, firstly, the I/O point is assigned for the retrieval request under the nearest-neighbor strategy, then group the S/R requests through the cluster method proposed by Kung et al. [40], and sorts the clusters by the dynamic programming finally. The computational results are shown in Table 5.Table 5
Computational results for large-sized instances.
mnCPLEXPAACAGAPaGAPbobj1dust1cwt1obj2dust2cwt2obj3dust3cwt31520247.267.22.4284.426.40.0247.270.86.00.0013.081525350.486.40.0399.644.40.0351.692.44.80.3412.311530462.036.09.6516.016.80.0462.037.212.00.0010.471535525.681.66.0584.445.60.0528.081.69.60.4510.061540562.8120.012.0634.863.60.0567.6126.08.40.8511.341550640.8210.09.6717.6118.80.0642.0194.410.80.1910.701520295.228.80.0332.413.20.0295.225.22.40.0011.191525372.057.60.0410.433.60.0373.252.80.00.329.361530488.418.014.4577.20.00.0489.618.014.40.2515.381535514.881.66.0572.445.60.0517.279.22.40.4610.061540572.496.07.2644.449.20.0576.099.63.60.6311.171550682.8150.013.2774.078.00.0685.2153.614.40.3511.781820256.848.04.8316.89.60.0256.851.66.00.0018.941825356.443.27.2513.60.00.0356.439.67.20.0030.611830463.218.014.4519.60.00.0464.426.412.00.2610.851835471.681.610.8529.243.20.0475.270.810.80.7610.881840547.272.08.4610.838.40.0550.875.68.40.6510.411850694.890.06.0776.448.00.0697.297.24.80.3410.511820286.819.23.6320.48.40.0286.821.66.00.0010.491825328.872.02.4370.838.40.0328.869.60.00.0011.331830438.036.00.0498.013.20.0442.850.47.21.0812.051835486.081.66.0558.036.00.0492.069.60.01.2212.901840501.6120.010.8582.055.20.0504.0134.414.40.4813.811850649.2120.09.6740.457.60.0650.4123.612.00.1812.322320291.69.63.6331.20.00.0294.09.63.60.8211.962325333.657.69.6372.031.20.0333.654.04.80.0010.322330429.618.01.2499.20.00.0433.225.26.00.8313.942335504.040.84.8561.620.40.0504.040.83.60.0010.262340523.272.03.6583.238.40.0523.280.47.20.0010.292350632.4120.06.0708.066.00.0637.2110.40.00.7510.682320283.29.60.0314.44.80.0283.29.60.00.009.922325315.672.04.8361.234.80.0316.862.42.40.3812.622330428.418.04.8495.60.00.0429.621.69.60.2813.562335475.261.22.4528.033.60.0476.460.00.00.2510.002340529.272.01.2685.246.80.0529.278.00.00.0022.772350607.2150.00.0674.486.40.0609.6156.08.40.399.96m: the number of I/O points, n: the number of S/R requests, PA: Phased algorithm, ACA: Ant colony algorithm, obj: objective function value (s), dust: saving time of DUT (s), cwt: waiting time of collisions (s), GAPa = (obj3 − obj1)/obj3∗100 (%), GAPb = (obj2 − obj1)/obj2∗100 (%).The objective function value, saving time of DUT, and waiting time of avoiding for each method are recorded in Table5. The results show that the objective function value obtained by ant colony algorithm is quite near to CPLEX, the average gap between CPLEX and ant colony algorithm is not more than 0.4%, the maximum value gap is only 1.22%, and the quality of the solution does not decline with the increase of the sized of the instance. Due to the cluster method, the phased algorithm avoids the waiting time of avoiding completely; however, the average gap between CPLEX and phased algorithm is 12.45%, and the maximum value gap is more than 30%. From the perspective of waiting time of stacker avoidance, the phased optimization method is better than CPLEX and ant colony algorithm. Most of the solutions obtained by CPLEX and ant colony algorithm have waiting time of stacker avoidance, and the average waiting time of stacker avoidance is 5.73 s and 6.20 s, respectively. However, as far as the saving time of DUT is concerned, the saving time of DUT in the solutions obtained by CPLEX and ant colony algorithm accounts for 15.32% and 15.47% of the total makespan, and saves more than 35.83 s and 36.76 s on average compares with the phased algorithm, respectively.


#### 4.2.3. Analysis

The computer experimental instances of small-sized and large-sized examples show that the ant colony algorithm can get high-quality solutions. We obtain I/O point assignment and the scheduling of two stackers by applying equation (3) to determine the access order of S/R request nodes which is effective. Because the stacker can save operation time through DUT, and the DUT is related to the location of destination address of the retrieval request, the I/O point assignment scheme affects the grouping and sorting of the S/R requests, and the problem we discussing is an integrated optimization problem with noncrossing constraints. The phased algorithm is a three-stage solution process. The I/O point assignment phase only minimizes the makespan between the source address and the output point of the retrieval request, whereas the grouping and sorting phase only minimizes the makespan between the destination address of the current request and the source address of the next request. The single decision-making rationale of each phase separates the relationship among the I/O points assignment and the grouping and sorting S/R requests, ignores the nesting relationships between the I/O points assignment and the DUT and between the I/O points assignment and the noncrossing constraint, and does not consider the impact of DUT and noncrossing constraint on the makespan of the S/R requests. The results in Table 5 show that the waiting time of avoiding collision of stacker in the phased algorithm is 0, but the saving time of DUT is far less than that of ant colony algorithm. The results are caused by being unable to compare DUT schemes and allocate the grouping results through adjusting I/O points assignment, which leads to the decrease of saving time through DUT and the increase of makespan. In the proposed algorithm, we design a retrieval request node structure that integrate multiple I/O points and a parallel search method in which two ants can access the nodes at the same time, which realizes the integrated optimization of I/O point assignment and the grouping and sorting of the S/R requests. The process of ant’s path selection not only determines the executing order of the S/R requests, but also determines the I/O point of the retrieval request. The parallel search method of two ants determines the group of S/R requests while selecting the node. The solving process of the algorithm fully reflects the integrated optimization requirements of the I/O point assignment and the grouping and sorting of the S/R requests. Among them, the structure of the retrieval request node reflects the influence of the selection of the I/O point on the DUT, and the deterministic selection rules of ant colony algorithm reflect the influence of the DUT and noncrossing constraint on the makespan. Meanwhile, the introduction of weight pheromone provides an important guarantee for restraining search stagnation and avoiding premature falling into local optimum.


## 4.1. Calculation Instances

We consider that the layout of multi-I/O points AS/RS with different quantity I/O points is similar to Figure1(a). Two stackers operate simultaneously in the aisle. The horizontal speed of the stacker is 2 m/s, and the vertical speed of the stacker is 0.4 m/s. The size of rack is 2 rows, 5 layers, and 45 columns, with a width of 2.8 m and a height of 2.4 m. The details on instances generation are presented as follows.For small-sized instances, the number of I/O points (left I/O point-right I/O point) is set to 4 (2–2), 5 (2–3), and 6 (3–3), and the number of S/R requests is 5, 6, and 8. The S/R requests are generated randomly. In large-sized instances, the number of I/O points is 15 (7–8), 18 (9–9), and 23 (11–12), and the number of S/R requests is 20, 25, 30, 35, 40, and 50, respectively.


## 4.2. Computational Results and Analysis

### 4.2.1. Small-Sized Instances

The computational results for small-sized instances are shown in Table4. For small-sized instances, ant colony algorithm can obtain the optimal solution or suboptimal solution of the problem with high probability. The average makespan is quite near to that of the optimal solution. With the increase in the number of I/O points and S/R requests, the solution space of the feasible solution of the problem increases sharply, and the CPU time of CPLEX also increases greatly. The number of I/O points and the number of S/R requests have great influence on the CPU time of CPLEX. However, the CPU time of ant colony algorithm is less affected by the size of the problem, and the difference between the maximum CPU time and the average CPU time is less than 2 seconds. In the instance of n = 8, the average value of the objective function and average value of CPU time of CPLEX and ant colony algorithm are illustrated in Figure 11. It is intuitively shown that the average value gap of the objective function between CPLEX and ant colony algorithm is very small, whereas the CPU time gap becomes larger with the increase of I/O point scale. The computational results for small-sized instances indicate that the ant colony algorithm is effective for small-sized randomly generated instances.Table 4
Computational results for small-sized instances.
mnCPLEXAnt colonyGAPaobj1CPU1obj2SUBOPTAVGNUM_OPTCPU24588.848.606188.89088.9294.23210.1346100.8104.1242100.8100.8100.80106.35590.0048114.0743.2382114.0115.2114.2485.98570.214585.253.283285.287.685.4496.38800.2846126.0100.6682126.0130.8126.4898.02540.3848111.6816.3781111.6115.2114.6876.58902.694576.854.366176.876.876.80106.02450.0046130.8102.2810130.8139.2131.6494.35290.6448160.8742.0237160.8162166.2866.32903.305568.480.712968.474.469.0097.25640.8756108.0165.9259108.0115.2109.4487.56681.3258138.01705.3464138.0144146.6056.59025.875568.479.340468.470.868.8887.85400.7056126.0162.2359126.0126126.00108.06500.0058129.61699.1107129.6130.8134.9675.62143.975572.085.955472.076.872.4895.21040.6656141.6165.3859141.6142.8141.7295.86240.0858134.41699.1107134.4139.2139.4066.16143.596554.0120.498554.055.254.1295.36210.226684.0244.962884.091.285.4486.32261.6968141.63147.0655141.6144148.6046.97514.716576.8122.248176.87876.9295.02160.166697.2241.930297.299.697.6886.18990.4968105.63087.8198105.6109.8115.7057.32648.736586.4121.315086.486.486.40106.28510.006698.4239.130898.4100.298.7686.85120.3668115.22839.4768115.2122.4126.2437.25608.75m: the number of I/O points, n: the number of S/R requests, obj: objective function value (s), SUBOPT: suboptimal solution (s), CPU: computation time (s), AVG: Average of 10 calculations, NUM_OPT: the number of optimal solution plus the number of suboptimal solution in 10 calculations, GAPa = (AVG − obj1)/AVG∗100% (%).Figure 11
Objective function value and CPU time for small-sized instances.


### 4.2.2. Large-Sized Instances

For large-sized instances, we solve the problem by CPLEX, phased algorithm, and ant colony algorithm, respectively. We set the computation time threshold limit to 18000 s for CPLEX, and then we record the incumbent solution and its corresponding lower bound. In the phased algorithm, firstly, the I/O point is assigned for the retrieval request under the nearest-neighbor strategy, then group the S/R requests through the cluster method proposed by Kung et al. [40], and sorts the clusters by the dynamic programming finally. The computational results are shown in Table 5.Table 5
Computational results for large-sized instances.
mnCPLEXPAACAGAPaGAPbobj1dust1cwt1obj2dust2cwt2obj3dust3cwt31520247.267.22.4284.426.40.0247.270.86.00.0013.081525350.486.40.0399.644.40.0351.692.44.80.3412.311530462.036.09.6516.016.80.0462.037.212.00.0010.471535525.681.66.0584.445.60.0528.081.69.60.4510.061540562.8120.012.0634.863.60.0567.6126.08.40.8511.341550640.8210.09.6717.6118.80.0642.0194.410.80.1910.701520295.228.80.0332.413.20.0295.225.22.40.0011.191525372.057.60.0410.433.60.0373.252.80.00.329.361530488.418.014.4577.20.00.0489.618.014.40.2515.381535514.881.66.0572.445.60.0517.279.22.40.4610.061540572.496.07.2644.449.20.0576.099.63.60.6311.171550682.8150.013.2774.078.00.0685.2153.614.40.3511.781820256.848.04.8316.89.60.0256.851.66.00.0018.941825356.443.27.2513.60.00.0356.439.67.20.0030.611830463.218.014.4519.60.00.0464.426.412.00.2610.851835471.681.610.8529.243.20.0475.270.810.80.7610.881840547.272.08.4610.838.40.0550.875.68.40.6510.411850694.890.06.0776.448.00.0697.297.24.80.3410.511820286.819.23.6320.48.40.0286.821.66.00.0010.491825328.872.02.4370.838.40.0328.869.60.00.0011.331830438.036.00.0498.013.20.0442.850.47.21.0812.051835486.081.66.0558.036.00.0492.069.60.01.2212.901840501.6120.010.8582.055.20.0504.0134.414.40.4813.811850649.2120.09.6740.457.60.0650.4123.612.00.1812.322320291.69.63.6331.20.00.0294.09.63.60.8211.962325333.657.69.6372.031.20.0333.654.04.80.0010.322330429.618.01.2499.20.00.0433.225.26.00.8313.942335504.040.84.8561.620.40.0504.040.83.60.0010.262340523.272.03.6583.238.40.0523.280.47.20.0010.292350632.4120.06.0708.066.00.0637.2110.40.00.7510.682320283.29.60.0314.44.80.0283.29.60.00.009.922325315.672.04.8361.234.80.0316.862.42.40.3812.622330428.418.04.8495.60.00.0429.621.69.60.2813.562335475.261.22.4528.033.60.0476.460.00.00.2510.002340529.272.01.2685.246.80.0529.278.00.00.0022.772350607.2150.00.0674.486.40.0609.6156.08.40.399.96m: the number of I/O points, n: the number of S/R requests, PA: Phased algorithm, ACA: Ant colony algorithm, obj: objective function value (s), dust: saving time of DUT (s), cwt: waiting time of collisions (s), GAPa = (obj3 − obj1)/obj3∗100 (%), GAPb = (obj2 − obj1)/obj2∗100 (%).The objective function value, saving time of DUT, and waiting time of avoiding for each method are recorded in Table5. The results show that the objective function value obtained by ant colony algorithm is quite near to CPLEX, the average gap between CPLEX and ant colony algorithm is not more than 0.4%, the maximum value gap is only 1.22%, and the quality of the solution does not decline with the increase of the sized of the instance. Due to the cluster method, the phased algorithm avoids the waiting time of avoiding completely; however, the average gap between CPLEX and phased algorithm is 12.45%, and the maximum value gap is more than 30%. From the perspective of waiting time of stacker avoidance, the phased optimization method is better than CPLEX and ant colony algorithm. Most of the solutions obtained by CPLEX and ant colony algorithm have waiting time of stacker avoidance, and the average waiting time of stacker avoidance is 5.73 s and 6.20 s, respectively. However, as far as the saving time of DUT is concerned, the saving time of DUT in the solutions obtained by CPLEX and ant colony algorithm accounts for 15.32% and 15.47% of the total makespan, and saves more than 35.83 s and 36.76 s on average compares with the phased algorithm, respectively.


### 4.2.3. Analysis

The computer experimental instances of small-sized and large-sized examples show that the ant colony algorithm can get high-quality solutions. We obtain I/O point assignment and the scheduling of two stackers by applying equation (3) to determine the access order of S/R request nodes which is effective. Because the stacker can save operation time through DUT, and the DUT is related to the location of destination address of the retrieval request, the I/O point assignment scheme affects the grouping and sorting of the S/R requests, and the problem we discussing is an integrated optimization problem with noncrossing constraints. The phased algorithm is a three-stage solution process. The I/O point assignment phase only minimizes the makespan between the source address and the output point of the retrieval request, whereas the grouping and sorting phase only minimizes the makespan between the destination address of the current request and the source address of the next request. The single decision-making rationale of each phase separates the relationship among the I/O points assignment and the grouping and sorting S/R requests, ignores the nesting relationships between the I/O points assignment and the DUT and between the I/O points assignment and the noncrossing constraint, and does not consider the impact of DUT and noncrossing constraint on the makespan of the S/R requests. The results in Table 5 show that the waiting time of avoiding collision of stacker in the phased algorithm is 0, but the saving time of DUT is far less than that of ant colony algorithm. The results are caused by being unable to compare DUT schemes and allocate the grouping results through adjusting I/O points assignment, which leads to the decrease of saving time through DUT and the increase of makespan. In the proposed algorithm, we design a retrieval request node structure that integrate multiple I/O points and a parallel search method in which two ants can access the nodes at the same time, which realizes the integrated optimization of I/O point assignment and the grouping and sorting of the S/R requests. The process of ant’s path selection not only determines the executing order of the S/R requests, but also determines the I/O point of the retrieval request. The parallel search method of two ants determines the group of S/R requests while selecting the node. The solving process of the algorithm fully reflects the integrated optimization requirements of the I/O point assignment and the grouping and sorting of the S/R requests. Among them, the structure of the retrieval request node reflects the influence of the selection of the I/O point on the DUT, and the deterministic selection rules of ant colony algorithm reflect the influence of the DUT and noncrossing constraint on the makespan. Meanwhile, the introduction of weight pheromone provides an important guarantee for restraining search stagnation and avoiding premature falling into local optimum.


## 4.2.1. Small-Sized Instances

The computational results for small-sized instances are shown in Table4. For small-sized instances, ant colony algorithm can obtain the optimal solution or suboptimal solution of the problem with high probability. The average makespan is quite near to that of the optimal solution. With the increase in the number of I/O points and S/R requests, the solution space of the feasible solution of the problem increases sharply, and the CPU time of CPLEX also increases greatly. The number of I/O points and the number of S/R requests have great influence on the CPU time of CPLEX. However, the CPU time of ant colony algorithm is less affected by the size of the problem, and the difference between the maximum CPU time and the average CPU time is less than 2 seconds. In the instance of n = 8, the average value of the objective function and average value of CPU time of CPLEX and ant colony algorithm are illustrated in Figure 11. It is intuitively shown that the average value gap of the objective function between CPLEX and ant colony algorithm is very small, whereas the CPU time gap becomes larger with the increase of I/O point scale. The computational results for small-sized instances indicate that the ant colony algorithm is effective for small-sized randomly generated instances.Table 4
Computational results for small-sized instances.
mnCPLEXAnt colonyGAPaobj1CPU1obj2SUBOPTAVGNUM_OPTCPU24588.848.606188.89088.9294.23210.1346100.8104.1242100.8100.8100.80106.35590.0048114.0743.2382114.0115.2114.2485.98570.214585.253.283285.287.685.4496.38800.2846126.0100.6682126.0130.8126.4898.02540.3848111.6816.3781111.6115.2114.6876.58902.694576.854.366176.876.876.80106.02450.0046130.8102.2810130.8139.2131.6494.35290.6448160.8742.0237160.8162166.2866.32903.305568.480.712968.474.469.0097.25640.8756108.0165.9259108.0115.2109.4487.56681.3258138.01705.3464138.0144146.6056.59025.875568.479.340468.470.868.8887.85400.7056126.0162.2359126.0126126.00108.06500.0058129.61699.1107129.6130.8134.9675.62143.975572.085.955472.076.872.4895.21040.6656141.6165.3859141.6142.8141.7295.86240.0858134.41699.1107134.4139.2139.4066.16143.596554.0120.498554.055.254.1295.36210.226684.0244.962884.091.285.4486.32261.6968141.63147.0655141.6144148.6046.97514.716576.8122.248176.87876.9295.02160.166697.2241.930297.299.697.6886.18990.4968105.63087.8198105.6109.8115.7057.32648.736586.4121.315086.486.486.40106.28510.006698.4239.130898.4100.298.7686.85120.3668115.22839.4768115.2122.4126.2437.25608.75m: the number of I/O points, n: the number of S/R requests, obj: objective function value (s), SUBOPT: suboptimal solution (s), CPU: computation time (s), AVG: Average of 10 calculations, NUM_OPT: the number of optimal solution plus the number of suboptimal solution in 10 calculations, GAPa = (AVG − obj1)/AVG∗100% (%).Figure 11
Objective function value and CPU time for small-sized instances.


## 4.2.2. Large-Sized Instances

For large-sized instances, we solve the problem by CPLEX, phased algorithm, and ant colony algorithm, respectively. We set the computation time threshold limit to 18000 s for CPLEX, and then we record the incumbent solution and its corresponding lower bound. In the phased algorithm, firstly, the I/O point is assigned for the retrieval request under the nearest-neighbor strategy, then group the S/R requests through the cluster method proposed by Kung et al. [40], and sorts the clusters by the dynamic programming finally. The computational results are shown in Table 5.Table 5
Computational results for large-sized instances.
mnCPLEXPAACAGAPaGAPbobj1dust1cwt1obj2dust2cwt2obj3dust3cwt31520247.267.22.4284.426.40.0247.270.86.00.0013.081525350.486.40.0399.644.40.0351.692.44.80.3412.311530462.036.09.6516.016.80.0462.037.212.00.0010.471535525.681.66.0584.445.60.0528.081.69.60.4510.061540562.8120.012.0634.863.60.0567.6126.08.40.8511.341550640.8210.09.6717.6118.80.0642.0194.410.80.1910.701520295.228.80.0332.413.20.0295.225.22.40.0011.191525372.057.60.0410.433.60.0373.252.80.00.329.361530488.418.014.4577.20.00.0489.618.014.40.2515.381535514.881.66.0572.445.60.0517.279.22.40.4610.061540572.496.07.2644.449.20.0576.099.63.60.6311.171550682.8150.013.2774.078.00.0685.2153.614.40.3511.781820256.848.04.8316.89.60.0256.851.66.00.0018.941825356.443.27.2513.60.00.0356.439.67.20.0030.611830463.218.014.4519.60.00.0464.426.412.00.2610.851835471.681.610.8529.243.20.0475.270.810.80.7610.881840547.272.08.4610.838.40.0550.875.68.40.6510.411850694.890.06.0776.448.00.0697.297.24.80.3410.511820286.819.23.6320.48.40.0286.821.66.00.0010.491825328.872.02.4370.838.40.0328.869.60.00.0011.331830438.036.00.0498.013.20.0442.850.47.21.0812.051835486.081.66.0558.036.00.0492.069.60.01.2212.901840501.6120.010.8582.055.20.0504.0134.414.40.4813.811850649.2120.09.6740.457.60.0650.4123.612.00.1812.322320291.69.63.6331.20.00.0294.09.63.60.8211.962325333.657.69.6372.031.20.0333.654.04.80.0010.322330429.618.01.2499.20.00.0433.225.26.00.8313.942335504.040.84.8561.620.40.0504.040.83.60.0010.262340523.272.03.6583.238.40.0523.280.47.20.0010.292350632.4120.06.0708.066.00.0637.2110.40.00.7510.682320283.29.60.0314.44.80.0283.29.60.00.009.922325315.672.04.8361.234.80.0316.862.42.40.3812.622330428.418.04.8495.60.00.0429.621.69.60.2813.562335475.261.22.4528.033.60.0476.460.00.00.2510.002340529.272.01.2685.246.80.0529.278.00.00.0022.772350607.2150.00.0674.486.40.0609.6156.08.40.399.96m: the number of I/O points, n: the number of S/R requests, PA: Phased algorithm, ACA: Ant colony algorithm, obj: objective function value (s), dust: saving time of DUT (s), cwt: waiting time of collisions (s), GAPa = (obj3 − obj1)/obj3∗100 (%), GAPb = (obj2 − obj1)/obj2∗100 (%).The objective function value, saving time of DUT, and waiting time of avoiding for each method are recorded in Table5. The results show that the objective function value obtained by ant colony algorithm is quite near to CPLEX, the average gap between CPLEX and ant colony algorithm is not more than 0.4%, the maximum value gap is only 1.22%, and the quality of the solution does not decline with the increase of the sized of the instance. Due to the cluster method, the phased algorithm avoids the waiting time of avoiding completely; however, the average gap between CPLEX and phased algorithm is 12.45%, and the maximum value gap is more than 30%. From the perspective of waiting time of stacker avoidance, the phased optimization method is better than CPLEX and ant colony algorithm. Most of the solutions obtained by CPLEX and ant colony algorithm have waiting time of stacker avoidance, and the average waiting time of stacker avoidance is 5.73 s and 6.20 s, respectively. However, as far as the saving time of DUT is concerned, the saving time of DUT in the solutions obtained by CPLEX and ant colony algorithm accounts for 15.32% and 15.47% of the total makespan, and saves more than 35.83 s and 36.76 s on average compares with the phased algorithm, respectively.


## 4.2.3. Analysis

The computer experimental instances of small-sized and large-sized examples show that the ant colony algorithm can get high-quality solutions. We obtain I/O point assignment and the scheduling of two stackers by applying equation (3) to determine the access order of S/R request nodes which is effective. Because the stacker can save operation time through DUT, and the DUT is related to the location of destination address of the retrieval request, the I/O point assignment scheme affects the grouping and sorting of the S/R requests, and the problem we discussing is an integrated optimization problem with noncrossing constraints. The phased algorithm is a three-stage solution process. The I/O point assignment phase only minimizes the makespan between the source address and the output point of the retrieval request, whereas the grouping and sorting phase only minimizes the makespan between the destination address of the current request and the source address of the next request. The single decision-making rationale of each phase separates the relationship among the I/O points assignment and the grouping and sorting S/R requests, ignores the nesting relationships between the I/O points assignment and the DUT and between the I/O points assignment and the noncrossing constraint, and does not consider the impact of DUT and noncrossing constraint on the makespan of the S/R requests. The results in Table 5 show that the waiting time of avoiding collision of stacker in the phased algorithm is 0, but the saving time of DUT is far less than that of ant colony algorithm. The results are caused by being unable to compare DUT schemes and allocate the grouping results through adjusting I/O points assignment, which leads to the decrease of saving time through DUT and the increase of makespan. In the proposed algorithm, we design a retrieval request node structure that integrate multiple I/O points and a parallel search method in which two ants can access the nodes at the same time, which realizes the integrated optimization of I/O point assignment and the grouping and sorting of the S/R requests. The process of ant’s path selection not only determines the executing order of the S/R requests, but also determines the I/O point of the retrieval request. The parallel search method of two ants determines the group of S/R requests while selecting the node. The solving process of the algorithm fully reflects the integrated optimization requirements of the I/O point assignment and the grouping and sorting of the S/R requests. Among them, the structure of the retrieval request node reflects the influence of the selection of the I/O point on the DUT, and the deterministic selection rules of ant colony algorithm reflect the influence of the DUT and noncrossing constraint on the makespan. Meanwhile, the introduction of weight pheromone provides an important guarantee for restraining search stagnation and avoiding premature falling into local optimum.


## 5. Conclusion

This article provides an efficient solution procedure for the integrated optimization problem of AS/RS operations with multi-I/O points. We consider how to improve the operational efficiency of the twin stackers with DUT capability when the I/O point is unknown, rather than the widely discussed operational optimization of the twin stacker in the AS/RS with two I/O points. Because the DUT can save the makespan of the S/R request, and the assignment of the I/O point is related to whether the stacker can execute the DUT, when considering the assignment of the I/O point and sorting the execution sequence of the S/R requests, we need to consider not only the noncrossing constraint, but also how to improve the operational efficiency by adding the DUT. The resulting problem is formalized as an integrated optimization problem of the I/O point assignment and stacker scheduling. By reducing the problem to a 3-PARTITION problem, the complexity of the problem is proved. Then the ant colony algorithm is proposed to solve the problem, and it is proved that the method can effectively obtain the approximate optimal solution, even the optimal solution under different sized, the following messages can be derived from our computational experiments.As for the multi-I/O points AS/RS to storage cargoes with different dimensions, DUT (see Section1) can greatly improve the efficiency of storage and retrieval. At the peak time when many S/R requests arrive, the DUT mode greatly improves the performance of AS/RS. In typical large-sized example, the scheduling scheme optimized by the method proposed in this paper almost reduces the makespan by 30% compared with the scheduling scheme obtained by the phased optimization method.Under the nearest-neighbor strategy for I/O point assignment, the clustered S/R requests determine the operational sequence of the stacker through dynamic programming, which can perfectly avoid the collisions of the stacker caused by twin stackers working simultaneously in the same aisle. It seems that it is very suitable for the efficient scheduling of twin stackers in multi-I/O points AS/RS. However, the decision results of the I/O point assignment and the grouping and sorting of S/R requests affect each other, and jointly affect the makespan of the S/R requests. It is not wholly satisfactory to solve the integrated optimization problem with the idea of solving by phased method. Our research shows that the integrated optimization of the I/O point assignment and the grouping and sorting of the S/R requests is realized by the means that ants select the retrieval request node which integrates multiple I/O points.Finally, minimizing the waiting time for avoiding collision in the process of simultaneous stacker operation can improve the performance of multi-I/O points AS/RS indeed, but often not to a very considerable extent. Thus, in the process of multi-I/O points AS/RS operation optimization, on the basis of minimizing the avoidance waiting time, it is also necessary to comprehensively consider the impact of I/O point assignment and DUT on operational efficiency. Future research should consider the update of the model and algorithm when the storage location and the I/O point are uncertain. Additionally, the scheduling of stacker with deterministic constraints of S/R requests in the multi-I/O points AS/RS is also a promising research subject.



---

*Source: 5997095-2022-05-21.xml*