# Cooperative Scheduling of AGV and ASC in Automation Container Terminal Relay Operation Mode

Authors: Qinglei Zhang; Weixin Hu; Jianguo Duan; Jiyun Qin
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The key problem of operation optimization for automated container terminal is the coordinated scheduling of automated quay crane (QC), automated guided vehicle (AGV), and automated stacking crane (ASC). In order to solve this problem, this paper proposed a new method to optimize the scheduling of ASC and AGV. In the automated container terminal, each container block is equipped with twin ASCs. At the same time, buffer zones are set at both ends of the container block to achieve the decoupling operation among ASC, AGV, and container truck. Considering the buffer capacity constraint and twin ASC operation interference, and introducing the design of handshake area, this paper developed a collaborative scheduling model of AGV and ASC in automatic terminal relay operation mode. This model is designed based on the genetic algorithm. The model aims to minimize the AGV waiting time and the ASC running time. The results indicated that the introduction of handshake area can effectively reduce the ASC operation interference by 10.56% on average. Also, it can be found that increasing buffer capacity can reduce the waiting time of AGV by about 4.25% on average, and the effect of relay operation is more obvious in large-scale operation. It was proved that buffer zone and handshake area can reduce task delay time and improve coordination between AGV and ASC.


---

## Body

## 1. Introduction

In recent years, with rapid increase in container tasks and continuous expansion of ship scale, the limited handling capacity of traditional container terminals can hardly meet the growing business demand. Therefore, safe, intelligent, and green automated terminals are becoming a trend in the development of container terminals.Figure1 presents a schematic diagram of an automated container terminal. As shown in Figure 1, the automated container terminal includes three types of automated operation equipment: quay cranes (QCs), automated guided vehicles (AGVs), and automated stacking cranes (ASCs). In the automatic terminal, the QCs are located at the quayside, used for loading containers onto ships and unloading containers from ships. The AGVs are assigned the path by the vehicle control system (VCS) to transfer containers between the quayside and the container yard. ASCs are used for handling containers in the container yard.Figure 1
Typical layout of automation container terminal, mainly including berth, automated guide vehicle (AGV) transportation area, seaside buffer zone, yard blocks, and landside buffer zone.In addition, the automated container terminal usually sets a buffer zone (i.e., I/O point support area or container exchange area) on both sides of the container block. The buffer zone is used for loading and unloading the target container with the AGVs and container trucks. This area can avoid the AGVs and the container trucks entering the container block, which help to reduce the operation time.Figure2 presents the transport process of the container at the port. In the automatic container terminal, containers stored in the yard can be divided into three categories: import containers, export containers, and transfer containers. There are two operation modes for containers: the loading process and the unloading process.Figure 2
Flowchart of a port import and export operation process. The blue font represents the unloading process, and the brown font represents the loading process.In the unloading process, the containers are first arrived at the destination port along with the container ships. After receiving the unloading instruction, the QC grabs the container and places it on the surface of AGV firstly. Then, the target container is transported to I/O point by the AGV and temporarily stored on the AGV-mate. The AGV-mate is an auxiliary equipment of AGVs and located in the buffer zone. This equipment is used for reducing the waiting times associated with ASC and AGV. When the ASC receives the instruction, it grabs the container from the AGV-mate and places it on the designated location of the yard, waiting for customers to pick up.In contrast, in the loading process, the containers are first transported to the storage yard by the container truck arranged by the customer, and then stored. After the destination ship arrives at the port for docking, ASC receives the shipping instruction, grabs the container from the storage yard, and places it on the AGV-mate. Then, the container is waiting for the AGV taking away, transporting to the corresponding berth. Finally, the container is loaded onto the ship by the QC.The loading and unloading operation of the automated container terminal is important links in the operation management of the automated terminal. The efficiency of the loading and unloading operation largely depends on the efficiency of collaboration between various kinds of equipment. At the same time, unreasonable allocation and scheduling plan will cause low utilization rate of container terminal resources and operation delay. The aim of the research on collaborative scheduling optimization of loading and unloading resources in container terminals is to schedule and allocate resources for each ship in a reasonable and efficient method. This can help to accomplish containers loading and unloading tasks on ships in a coordinated manner, effectively avoid the waiting time between equipment, and finally improve the utilization rate of container terminal resources.In recent years, the storage yard, limited by operation resources such as storage space, yard crane (YC), AGV, etc., is becoming a new bottle neck in port operation. For ASCs and AGVs, how to achieve the cooperative scheduling between ASCs and AGVs is of great significance for reducing equipment waiting time of and improving terminal operation efficiency. Therefore, combined with the actual situation of automated terminals, this paper studies the cooperative scheduling problem of AGVs and twin ASCs in automation container terminal relay operation mode. The purpose is to improve the coordination between different devices and optimize the job sequence of AGV and ASC, so as to minimize the waiting time of AGV and the running time of ASC.The main contribution of this study is to provide an optimization method to deal with ASC and AGV synthetically for the cooperative scheduling problem of AGVs and ASCs, which considers the loading and unloading operations and the interferences between the ASCs. In addition, we also provide a three-stage genetic algorithm to solve the collaborative scheduling problem.


## 2. Literature Review

After the AGV was put into application in 1955, there are lots of previous research studies about AGV scheduling. Durrant-Whyte [1] firstly studied the application of AGV in container terminals, and proposed an AGV system for port transportation of the International Organization for Standardization (ISO) standard cargo containers. Kim and Bae [2] proposed a look-ahead dispatching method for AGVs reducing the delay of ship operation. Bish et al. [3] developed an inverse greed algorithm to optimize the travel path for AGVs importing and exporting containers. Angeloudis and Bell [4] studied the allocation of automatic navigation operations at container terminals under various uncertain conditions (such as emergency maintenance operation, safety stop, mislabeling, and container loss), and proposed an AGV scheduling method, which can carry out real-time control under uncertain conditions. Cai et al. [5] proposed a Rescheduling New arrival Jobs (RNJ) policy and a Rescheduling Combination of new and unexecuted Jobs (RCJ) policy to solve the problem of autonomous straddle carriers scheduling under the background of uncertainty (such as arrival of new tasks at automated terminals or occurrence of emergencies). Radhia et al. [6] proposed a hybrid method based on Dijkstra algorithm, genetic algorithm, and heuristic algorithm to study the task assignment problem of AGVs. Malopolski [7] developed a new method to describe one-way, two-way or multilane flow field for AGV collision and deadlock problems.For the twin ASC scheduling study, Nguyen and Kim [8] established a mixed integer programming model to solve the priority loading and unloading order of the target container based on the buffer capacity constraint and time window constraint. Saini et al. [9] constructed a two-level random model to analyze the performance of twin YCs. It was found that the interference effect between cranes would reduce the handling capacity of cranes by about 35%, and the interference delay increase with the number of shelves in the stack. Briskorn and Angeloudis [10] developed an effective graphic model and strong polynomial algorithm to solve the scheduling problem of twin cranes and cross cranes in the automatic terminal. Lu and Wang [11] established an interference model by analyzing the time overlap among different container handling tasks, and designed a particle swarm optimization algorithm based on the graph theory model to solve the scheduling problem of twin ASCs. Hu et al. [12] developed an interference relationship matrix between twin ASCs by analyzing the minimum time interval among different container handling tasks. Based on this matrix, two mixed integer linear programming (MILP) models and a nonlinear model are developed to solve the scheduling problem of twin ASCs without interference.With the deepening of the research on each subsystem of the port, the demand for collaborative scheduling is becoming more and more obvious in both the academic circle and port enterprises. Integrated scheduling takes the optimization of each link as a part of the whole system, and improves the operation efficiency of the whole system through the seamless connection between links. Different from integrated scheduling, the core of collaborative scheduling is to consider the interaction between different systems, and to achieve the overall system efficiency through the coordination among subsystems. Meersmans and Wagelmans [13] tried to integrate the scheduling of AGVs, QCs, and YCs into the automatic container terminal. A branch and bound algorithm and a beam search algorithm were developed to minimize the total scheduling span. Xinet al. [14] proposed a method of dispatching QCs, AGVs, and YCs to improve the loading and unloading capacity of automated container terminals through energy saving. Luo and Wu [15] proposed an evolutionary heuristic algorithm (the genetic algorithm) to solve the large-scale problem. Luo et al. [16] studied the integration of AGV scheduling and container storage to optimize the unloading process of the automated container terminal. Hu et al. [17] developed two MILP models and developed a three-stage decomposition method based on particle swarm optimization to solve the joint problem of vehicle scheduling and storage distribution in automated container terminal. Zhong et al. [18] developed the integrated scheduling of the QCs, AGVs, and ASCs in automated terminals. Various basic metaheuristic and improved hybrid algorithms were developed to optimize service level. Zhao et al. [19] considered the capacity limitation of the transfer platform on QCs, established collaborative scheduling model for QCs and AGV. The optimal solution to the model is obtained by feedback from the two-stage taboo search process.For the research of integrated scheduling of traditional terminals, it is mainly the coordinated scheduling of container trucks, QCs, and YCs. Kim et al. [20] grouped the truck in dynamic situation, so as to cooperate with YC operation, improve the working efficiency of YCs, and reduce the interference among different YCs. Lee et al. [21] studied the joint scheduling problem of YCs and container trucks, and solved this problem by the simulated annealing algorithm. Petersing et al. [22] considered the working efficiency of the whole system, implemented a global expansion of local problems, and made the research of the problem more integrated. In addition, some previous studies focus on the collaborative scheduling of quayside resources. Imai et al. [23] studied the joint scheduling problem of berth allocation and QC allocation. By using the genetic algorithm, a satisfactory solution has been obtained. Liang et al. [24] established a joint optimization model of berth allocation and QC scheduling to minimize the processing time, waiting time, and delay time of each ship.From previous studies, it was found that the cooperative scheduling of the ASC and the AGV in the automated terminal has not been fully explored. Previous studies mainly focus on the collaborative problem of vehicle scheduling, storage allocation in the automated terminal, and collaborative problem of berth allocation and QC scheduling. In most of the existing literatures on cooperative scheduling of QCs, AGVs, and ASCs, the cooperation between the ASCs is ignored, and the landside ASC passively caters to the operation of the seaside ASC.In addition, previous studies on collaborative scheduling of loading and unloading equipment in automated container terminals have the following problems. Firstly, the operation requirements of landside ASC have not been considered, which separated the cooperative relationship between the twin ASCs, resulting in the operation delay of landside ASC. Secondly, ASCs are often regarded as a kind of auxiliary equipment, which requires the ASCs to follow the operation order of QCs and give priority to the quayside operation requirements, while ignoring the ability of ASC reasonable scheduling to improve the operation efficiency of the whole terminal.Therefore, this paper will take ASC as the main research object, focusing on the cooperative scheduling of ASC and AGV under the condition of limited buffer capacity, and twin ASCs interfere with each other. Combined with the actual situation of the automatic terminal, this paper adopts the dual-cycle strategy (loading operation and unloading operation are considered at the same time) and establishes the cooperative scheduling model of AGV and ASC under the ASC relay operation mode of automatic container terminal.


## 3. Mathematical Model

### 3.1. Problem Description

Yard, as the place for container changing, plays the key role in the automatic terminal. The storage yard consists of several blocks, and a buffer zone is set on both sides of the storage yard, which is used for the container handover between AGVs and ASCs. In the loading operation, the AGVs can be allowed to leave, after AGVs arrive at the buffer zone and are loaded the container by the AGV-mate. In the unloading operation, the AGVs can be allowed to leave without waiting for ASCs, after AGVs arrive at the buffer zone and unloaded the container by the AGV-mate. However, when there is no free buffer area, AGVs must wait outside the buffer. This would have a negative effect on the completion of tasks and the service time of subsequent tasks.In the automatic container terminal, the loading and unloading processes are carried out simultaneously. In order to ensure that the model proposed is more accurate and closer to the reality, the dual-cycle strategy is adopted in this paper. In the dual-cycle operations, there are four transportation modes for an AGV completing two consecutive deliveries:(i)
Mode 1: the AGV performs the import container after completing the import container(ii)
Mode 2: the AGV performs the export container after completing the import container(iii)
Mode 3: the AGV transports the import container after completing the export container(iv)
Mode 4: the AGV transports the export container after completing the export containerFigure3 presents the preparation process between two consecutive deliveries of AGV under different operation modes. In Figure 3, the solid line represents the heavy-load process of AGV, the dotted line represents the no-load process of AGV, and the horizontal line represents the moving process of AGV between the two QCs or two container blocks.Figure 3
Continuous operation flowchart of AGV in the dual-cycle operations: (a) mode 1; (b) mode 2; (c) mode 3; (d) mode 4.
(a)(b)(c)(d)Having described the operation process of the AGV, the ASC operation process is needed to be discussed. In the automatic container terminal, each container block usually has two ASCs, and each ASC can only operate in its own half container area. Since twin ASCs of the same model (mechanical performance, specification, and size) are running on the same track, twin ASCs often interfere with each other. For example, when the container near the landside needs to be exited, the landside ASC needs to wait outside the safety zone. After the seaside ASC completes its loading work, the landside ASC can continue its work. This would greatly reduce the work efficiency of twin ASCs. Therefore, the operation of some remote containers usually needs twin ASC relay to complete.In order to further effectively alleviate the operation interference of twin ASCs, handshake area design is introduced in this paper. The handshake area is attached to the rails of the cranes, which is shown in Figure4. In addition, the following rules are adopted in the scheduling process of twin ASCs: with the yard center as the boundary, container tasks near the seaside are independently completed by the seaside ASC, and container tasks near the landside are independently completed by the landside ASC. For container task needed to cross over handshake area, this container task is split into the main task and the secondary task according to the sequence of operation. This task is completed by the ASC relay on both sides.Figure 4
Schematic diagram of ASC relay operation.Figure4 presents the ASC relay operation process. In this study, the relay operation mode is divided into two stages. The first stage is that one ASC transports the container from the initial position to the temporary position in the handshake area. The second stage is that the other ASC transports the container from the temporary position in the handshake area to the target position of the container. When the AGV carries the container into the buffer zone, the seaside ASC loads the container from the buffer zone and unloads it to the temporary location of the handshake area. Then, the landside ASC loads the container from the temporary location in the handshake area and unloads it to the storage location of the container.The dual-cycle operations are considered in this paper. In the dual-cycle operation, unloading and loading operations are not necessary taken place at the same time in the same cycle. During the unloading process, the container is first unloaded on the AGV by the QC, and the container is transported to the buffer zone by the AGV. If the buffer zone capacity is not full, the AGV enters the buffer zone and unloads the container; otherwise, the AGV waits. After the AGV completes the import container, if the container needs relay operation, first, the seaside ASC will load the container from the buffer zone and unload it to the handshake area. Then, the landside ASC will load the container from the handshake area and unload it to the designated storage location. Otherwise, the seaside ASC will complete the container independently. At this time, AGV performs the next container until all containers have been completed. The loading process is executed in the reverse order of the unloading process.


### 3.2. Model Hypothesis

Considering the actual situation of the automated terminal, each container to be operated is regarded as a task, and the following assumptions are proposed:(1)
AGVs travel in the same direction at a constant speed and choose a variety of routes, without considering the mutual interference in AGV transport(2)
Storage yard location of each task container has been given(3)
AGVs can only transport one container at a time(4)
Loading and unloading time of ASC in buffer zone is ignored, and the processing time of container task remains constant(5)
The AGV does not have to wait for the quayside crane operation, which can be operated immediately upon the arrival of the AGV transporting container(6)
Twin ASCs cannot cross each other, and the case of overturning has not been considered


### 3.3. Model Parameters

To facilitate modelling, the following parameters are defined:SetsLThe set of import containersUThe set of export containersNThe set of all the containers, i.e.,N=L∪UR1The set of main tasks requiring relay operationR2The set of secondary tasks requiring relay operationRThe set of tasks requiring relay operationBThe set of bays,B=1,2,⋯BGtiThe set of tasks waiting for operation in the buffer at the timet in i taskKThe set of AGVsAThe set of ASCs in container block,A=1,2VariablesTisThe start time of taski, when the QC unloads the container onto the AGVTihThe arrival time of AGV transporting taski to bufferTiEThe time when taski is unloaded to the AGV-mateWiThe time window of taski is stored in the bufferdijThe preparation time for loading taskj to the buffer after the AGV completes task iqThe loading and unloading time of a container by the QCd0The no-load driving time of the AGVd1The heavy-load driving time of the AGVTgiThe waiting time of the AGVg in the i taskTmaxAGV maximum waiting timeCiRemaining available capacity of buffer ini taskciA 0-1 variable, which equals 1 when there is no remaining available capacity ini task, otherwise 0miA 0-1 variable, during the loading process, which equals 1 when AGVs arrive at buffer zone and wait for ASC to complete taski, otherwise 0hi1Target loading and unloading bay of seaside ASC ini taskhi2Target loading and unloading bay of landside ASC ini taskVsNumber of bays passed by ASC per unit timetiThe dropping container or picking container time of ASC ini tasktijThe ASC moving time from the end position of taski to the start position of task jZiaThe completion time of ASCa in i taskutiaA 0-1 variable, which equals 1 when the container is loaded and unloaded by ASCa at the time t in the i task, otherwise 0gtibaIn thei task, at time t, ASCa is in the bay bτSafe distance between twin ASCsMA large enough positive numberαA 0-1 variable, which equals 1 whena=1, otherwise 0niA 0-1 variable, which equals 1 when relay operation is selected in taski, otherwise 0Decision variablesXijA 0-1 variable, which equals 1 when the same AGV executes the next taskj after the AGV completed task i, otherwise 0YijaA 0-1 variable, which equals 1 when the same ASC executes the next taskj after the ASC completed task i, otherwise 0


### 3.4. Objective Function

The job scheduling of AGV is the key problem for the terminal operation system. Its scheduling will be restricted by other (such as QC and ASC) links and factors in the system. In the research of the AGV scheduling optimization for the automatic terminal, it usually aims to achieve the shortest waiting time. At the same time, in the operation of automatic terminal, the waiting time of the AGV is also the key factor for the twin ASC scheduling. Therefore, this paper chooses the AGV waiting time and the ASC running time as optimization objectives to improve the overall efficiency of the automation terminal.In the unloading operation, when the AGV reaches the buffer zone, it needs to judge whether there is residual capacity in the buffer. If there is no residual capacity, the AGV needs to wait in the queue. Similarly, in the loading operation, when ASC completes the task, it needs to judge whether there is residual capacity in the buffer. If there is no residual capacity, ASC needs to wait. However, the waiting of AGV and ASC will affect the completion of the task and the subsequent task service time; if AGV-mate is reserved for each task in the buffer zone, the waiting time of other AGVs will be increased. Therefore, this paper calculates the time window of each container in the buffer zone, and schedules AGV flexibly through the time window to ensure the efficient operation of AGV.Equation (1) is the objective function for minimizing the waiting time of AGV and the running time of ASC:(1)minF=f1+f2,where f1 represents the sum of the AGV waiting times for each task phase, including the waiting time of AGV at the time of import and export; f2 indicates the longest running time in twin ASCs to ensure all tasks of ASC are completed.Equation (2) shows the sum of the differences between the time when all AGVs leave the I/O point support area in the planned time and the time when they arrive at the seaside I/O point support area. This is the sum of the waiting time of AGVs in the whole planned time:(2)f1=∑i=1Umiuti2Zi−Tih+∑i=1Lciuti1TiE−Tih,where ∑i=1Umiuti2Zi−Tih indicates the waiting time of AGV at the time of export and ∑i=1Lciuti1TiE−Tih indicates the waiting time of AGV at the time of import:(3)f2=maxa∈A∑i=1n2ti+ti−1i+αniB+1/2−hia+1−nihiaVs+1−αnihia−B+1/2+1−niB−hiaVs.Equation (3) shows ASC scheduling time. When relay operation is required in i task, the running time of ASC is determined by the sum of ASC loading and unloading time, ASC moving time from the end position of the previous task to the starting position of the current task, and ASC loading running time from the starting position to the relay position or ASC loading running time from the relay position to the starting position. If task i does not require relay operation, the ASC running time is determined by the sum of the ASC loading and unloading time in the task, the ASC moving time from the end position of the previous task to the starting position of the current task, and the running time when the ASC loads the task to the target location. In the model, we call the starting position and the end position as the target loading and unloading bay of ASC.


### 3.5. Constraint Condition

(4)∑i=1nXij=1,∀j∈N,(5)∑j=1nXij=1,∀i∈N,(6)∑i=1nYija=1,∀j∈N,∀a∈A,(7)∑j=1nYija=1,∀i∈N,∀a∈A,(8)Tgi≤Tmax,∀i∈N,(9)Tjh−Tih+dij≥MXij−1,i,j∈N,(10)dij=d0+d1+q,mode1,0,mode2,q+d1,mode3,d0,mode4,(11)∑NZi1≥N,i∈N,(12)Tgi≥MCi,Tgi>0,i∈L,(13)Tgi≥Mmi,Tgi>0,i∈U,(14)M1−ci≥Ci,i∈N,(15)TiE∈Wi=ciminZj−1+tj−1+1−ciTih,Zi−1,j<i,j∈Gti,i∈L,(16)TiE∈Wi=Zi,minZj,Tih,i<j,j∈L∪U,i∈U,(17)gtib1<gtib′2,b′≠b,b,b′∈B,i∈N,a∈A,(18)∑Nutia≤N,i∈N,a∈A,(19)gtiba≠gtib′a,b′≠b,b,b′∈B,i∈N,a∈A,(20)M1−gtiba≤utia,b∈B,i∈N,a∈A,(21)Zj1≥∑j=1n2tj+tij+njB+1/2−hj1+1−njhj1Vs,i,j∈N,(22)Zj2≥∑j=1n2tj+tij+njhj2−B+1/2+1−njB−hj2Vs,i,j∈N,(23)Zj1≥2tj+Zi1+tij+M1−Yij1+njB+1/2−hj1+1−njhj1Vs,i,j∈N,(24)Zj2≥2tj+Zi2+tij+M1−Yij2+njhj2−B+1/2+1−njB−hj2Vs,i,j∈N,(25)Zi1≤Zj2−2tj+tlj+hj2−B+1/2Vs,i∈R1,j∈R2,i,j∈R1∩R2,l∈N,(26)Zi2≤Zj1−2tj+tlj+B+1/2−hj1Vs,i∈R1,j∈R2,i,j∈R1∩R2,l∈N,(27)∑Nni≤N,i∈N.Constraint (4) indicates that AGV has one container transportation task before starting the container transportation task. Constraint (5) indicates that AGV has one container transportation task after completing one container transportation task. Constraint (6) indicates that ASC has one container loading or unloading task before starting to perform the container loading or unloading task. Constraint (7) indicates that ASC has one container loading or unloading task after completing one container loading or unloading task. Constraint (8) indicates that the waiting time of AGV is less than the maximum waiting time. Constraint (9) shows the time relationship between two consecutive tasks transported by the same AGV and arriving at the buffer. Constraint (10) indicates the preparation time for loading task j to the buffer after the AGV completed task i, and there are four cases. Constraint (11) ensures that the target container in the unloading operation of the marine vessel can be unloaded and enter the target shell position. Constraint (12) ensures that the remaining available capacity of the support area must be 0 at the current time when the AGV is waiting in the seaside I/O point support area during the unloading operation. Constraint (13) ensures that the current task is not completed when the AGV is waiting in the seaside I/O point support area during the packing operation. Equation (14) constrains the set 0-1 variable and shows that when there is no residual available capacity in the seaside I/O point support area, ci=1. Constraint (15) indicates that, during unloading operation, the earliest start time of the time window of task i is the earliest time when the task i is unloaded in the buffer by AGV, and the latest start time is the time when the task i is loaded from the buffer by ASC. Constraint (16) indicates that, during loading operation, the earliest start time of the time window of task i is the earliest time when the task i is unloaded in the buffer by ASC, and the latest start time is the time when the task i is loaded from the buffer by AGV. Constraint (17) ensures that ASCs do not collide with each other and there is a safe distance τ between the twin ASCs. Constraint (18) indicates that ASCs can only perform loading and unloading tasks once at most. Constraint (19) indicates that ASCs can only be in one bay at a certain time. Constraint (20) ensures that the ASC is in the target bay corresponding to the task during loading and unloading. Constraints (21) and (22), respectively, indicate that the actual time for seaside and landside ASC to complete task i must be greater than or equal to the current task planned completion time. Constraints (23) and (24) show the time sequence relationship of the two adjacent tasks of the seaside and the landside ASC, respectively. Constraints (25) and (26) indicate the time sequence relationship between the main task and the secondary task of the container requiring relay operation. Constraint (27) indicates that the number of relay operations will not be greater than the total number of loading and unloading tasks.


## 3.1. Problem Description

Yard, as the place for container changing, plays the key role in the automatic terminal. The storage yard consists of several blocks, and a buffer zone is set on both sides of the storage yard, which is used for the container handover between AGVs and ASCs. In the loading operation, the AGVs can be allowed to leave, after AGVs arrive at the buffer zone and are loaded the container by the AGV-mate. In the unloading operation, the AGVs can be allowed to leave without waiting for ASCs, after AGVs arrive at the buffer zone and unloaded the container by the AGV-mate. However, when there is no free buffer area, AGVs must wait outside the buffer. This would have a negative effect on the completion of tasks and the service time of subsequent tasks.In the automatic container terminal, the loading and unloading processes are carried out simultaneously. In order to ensure that the model proposed is more accurate and closer to the reality, the dual-cycle strategy is adopted in this paper. In the dual-cycle operations, there are four transportation modes for an AGV completing two consecutive deliveries:(i)
Mode 1: the AGV performs the import container after completing the import container(ii)
Mode 2: the AGV performs the export container after completing the import container(iii)
Mode 3: the AGV transports the import container after completing the export container(iv)
Mode 4: the AGV transports the export container after completing the export containerFigure3 presents the preparation process between two consecutive deliveries of AGV under different operation modes. In Figure 3, the solid line represents the heavy-load process of AGV, the dotted line represents the no-load process of AGV, and the horizontal line represents the moving process of AGV between the two QCs or two container blocks.Figure 3
Continuous operation flowchart of AGV in the dual-cycle operations: (a) mode 1; (b) mode 2; (c) mode 3; (d) mode 4.
(a)(b)(c)(d)Having described the operation process of the AGV, the ASC operation process is needed to be discussed. In the automatic container terminal, each container block usually has two ASCs, and each ASC can only operate in its own half container area. Since twin ASCs of the same model (mechanical performance, specification, and size) are running on the same track, twin ASCs often interfere with each other. For example, when the container near the landside needs to be exited, the landside ASC needs to wait outside the safety zone. After the seaside ASC completes its loading work, the landside ASC can continue its work. This would greatly reduce the work efficiency of twin ASCs. Therefore, the operation of some remote containers usually needs twin ASC relay to complete.In order to further effectively alleviate the operation interference of twin ASCs, handshake area design is introduced in this paper. The handshake area is attached to the rails of the cranes, which is shown in Figure4. In addition, the following rules are adopted in the scheduling process of twin ASCs: with the yard center as the boundary, container tasks near the seaside are independently completed by the seaside ASC, and container tasks near the landside are independently completed by the landside ASC. For container task needed to cross over handshake area, this container task is split into the main task and the secondary task according to the sequence of operation. This task is completed by the ASC relay on both sides.Figure 4
Schematic diagram of ASC relay operation.Figure4 presents the ASC relay operation process. In this study, the relay operation mode is divided into two stages. The first stage is that one ASC transports the container from the initial position to the temporary position in the handshake area. The second stage is that the other ASC transports the container from the temporary position in the handshake area to the target position of the container. When the AGV carries the container into the buffer zone, the seaside ASC loads the container from the buffer zone and unloads it to the temporary location of the handshake area. Then, the landside ASC loads the container from the temporary location in the handshake area and unloads it to the storage location of the container.The dual-cycle operations are considered in this paper. In the dual-cycle operation, unloading and loading operations are not necessary taken place at the same time in the same cycle. During the unloading process, the container is first unloaded on the AGV by the QC, and the container is transported to the buffer zone by the AGV. If the buffer zone capacity is not full, the AGV enters the buffer zone and unloads the container; otherwise, the AGV waits. After the AGV completes the import container, if the container needs relay operation, first, the seaside ASC will load the container from the buffer zone and unload it to the handshake area. Then, the landside ASC will load the container from the handshake area and unload it to the designated storage location. Otherwise, the seaside ASC will complete the container independently. At this time, AGV performs the next container until all containers have been completed. The loading process is executed in the reverse order of the unloading process.


## 3.2. Model Hypothesis

Considering the actual situation of the automated terminal, each container to be operated is regarded as a task, and the following assumptions are proposed:(1)
AGVs travel in the same direction at a constant speed and choose a variety of routes, without considering the mutual interference in AGV transport(2)
Storage yard location of each task container has been given(3)
AGVs can only transport one container at a time(4)
Loading and unloading time of ASC in buffer zone is ignored, and the processing time of container task remains constant(5)
The AGV does not have to wait for the quayside crane operation, which can be operated immediately upon the arrival of the AGV transporting container(6)
Twin ASCs cannot cross each other, and the case of overturning has not been considered


## 3.3. Model Parameters

To facilitate modelling, the following parameters are defined:SetsLThe set of import containersUThe set of export containersNThe set of all the containers, i.e.,N=L∪UR1The set of main tasks requiring relay operationR2The set of secondary tasks requiring relay operationRThe set of tasks requiring relay operationBThe set of bays,B=1,2,⋯BGtiThe set of tasks waiting for operation in the buffer at the timet in i taskKThe set of AGVsAThe set of ASCs in container block,A=1,2VariablesTisThe start time of taski, when the QC unloads the container onto the AGVTihThe arrival time of AGV transporting taski to bufferTiEThe time when taski is unloaded to the AGV-mateWiThe time window of taski is stored in the bufferdijThe preparation time for loading taskj to the buffer after the AGV completes task iqThe loading and unloading time of a container by the QCd0The no-load driving time of the AGVd1The heavy-load driving time of the AGVTgiThe waiting time of the AGVg in the i taskTmaxAGV maximum waiting timeCiRemaining available capacity of buffer ini taskciA 0-1 variable, which equals 1 when there is no remaining available capacity ini task, otherwise 0miA 0-1 variable, during the loading process, which equals 1 when AGVs arrive at buffer zone and wait for ASC to complete taski, otherwise 0hi1Target loading and unloading bay of seaside ASC ini taskhi2Target loading and unloading bay of landside ASC ini taskVsNumber of bays passed by ASC per unit timetiThe dropping container or picking container time of ASC ini tasktijThe ASC moving time from the end position of taski to the start position of task jZiaThe completion time of ASCa in i taskutiaA 0-1 variable, which equals 1 when the container is loaded and unloaded by ASCa at the time t in the i task, otherwise 0gtibaIn thei task, at time t, ASCa is in the bay bτSafe distance between twin ASCsMA large enough positive numberαA 0-1 variable, which equals 1 whena=1, otherwise 0niA 0-1 variable, which equals 1 when relay operation is selected in taski, otherwise 0Decision variablesXijA 0-1 variable, which equals 1 when the same AGV executes the next taskj after the AGV completed task i, otherwise 0YijaA 0-1 variable, which equals 1 when the same ASC executes the next taskj after the ASC completed task i, otherwise 0


## 3.4. Objective Function

The job scheduling of AGV is the key problem for the terminal operation system. Its scheduling will be restricted by other (such as QC and ASC) links and factors in the system. In the research of the AGV scheduling optimization for the automatic terminal, it usually aims to achieve the shortest waiting time. At the same time, in the operation of automatic terminal, the waiting time of the AGV is also the key factor for the twin ASC scheduling. Therefore, this paper chooses the AGV waiting time and the ASC running time as optimization objectives to improve the overall efficiency of the automation terminal.In the unloading operation, when the AGV reaches the buffer zone, it needs to judge whether there is residual capacity in the buffer. If there is no residual capacity, the AGV needs to wait in the queue. Similarly, in the loading operation, when ASC completes the task, it needs to judge whether there is residual capacity in the buffer. If there is no residual capacity, ASC needs to wait. However, the waiting of AGV and ASC will affect the completion of the task and the subsequent task service time; if AGV-mate is reserved for each task in the buffer zone, the waiting time of other AGVs will be increased. Therefore, this paper calculates the time window of each container in the buffer zone, and schedules AGV flexibly through the time window to ensure the efficient operation of AGV.Equation (1) is the objective function for minimizing the waiting time of AGV and the running time of ASC:(1)minF=f1+f2,where f1 represents the sum of the AGV waiting times for each task phase, including the waiting time of AGV at the time of import and export; f2 indicates the longest running time in twin ASCs to ensure all tasks of ASC are completed.Equation (2) shows the sum of the differences between the time when all AGVs leave the I/O point support area in the planned time and the time when they arrive at the seaside I/O point support area. This is the sum of the waiting time of AGVs in the whole planned time:(2)f1=∑i=1Umiuti2Zi−Tih+∑i=1Lciuti1TiE−Tih,where ∑i=1Umiuti2Zi−Tih indicates the waiting time of AGV at the time of export and ∑i=1Lciuti1TiE−Tih indicates the waiting time of AGV at the time of import:(3)f2=maxa∈A∑i=1n2ti+ti−1i+αniB+1/2−hia+1−nihiaVs+1−αnihia−B+1/2+1−niB−hiaVs.Equation (3) shows ASC scheduling time. When relay operation is required in i task, the running time of ASC is determined by the sum of ASC loading and unloading time, ASC moving time from the end position of the previous task to the starting position of the current task, and ASC loading running time from the starting position to the relay position or ASC loading running time from the relay position to the starting position. If task i does not require relay operation, the ASC running time is determined by the sum of the ASC loading and unloading time in the task, the ASC moving time from the end position of the previous task to the starting position of the current task, and the running time when the ASC loads the task to the target location. In the model, we call the starting position and the end position as the target loading and unloading bay of ASC.


## 3.5. Constraint Condition

(4)∑i=1nXij=1,∀j∈N,(5)∑j=1nXij=1,∀i∈N,(6)∑i=1nYija=1,∀j∈N,∀a∈A,(7)∑j=1nYija=1,∀i∈N,∀a∈A,(8)Tgi≤Tmax,∀i∈N,(9)Tjh−Tih+dij≥MXij−1,i,j∈N,(10)dij=d0+d1+q,mode1,0,mode2,q+d1,mode3,d0,mode4,(11)∑NZi1≥N,i∈N,(12)Tgi≥MCi,Tgi>0,i∈L,(13)Tgi≥Mmi,Tgi>0,i∈U,(14)M1−ci≥Ci,i∈N,(15)TiE∈Wi=ciminZj−1+tj−1+1−ciTih,Zi−1,j<i,j∈Gti,i∈L,(16)TiE∈Wi=Zi,minZj,Tih,i<j,j∈L∪U,i∈U,(17)gtib1<gtib′2,b′≠b,b,b′∈B,i∈N,a∈A,(18)∑Nutia≤N,i∈N,a∈A,(19)gtiba≠gtib′a,b′≠b,b,b′∈B,i∈N,a∈A,(20)M1−gtiba≤utia,b∈B,i∈N,a∈A,(21)Zj1≥∑j=1n2tj+tij+njB+1/2−hj1+1−njhj1Vs,i,j∈N,(22)Zj2≥∑j=1n2tj+tij+njhj2−B+1/2+1−njB−hj2Vs,i,j∈N,(23)Zj1≥2tj+Zi1+tij+M1−Yij1+njB+1/2−hj1+1−njhj1Vs,i,j∈N,(24)Zj2≥2tj+Zi2+tij+M1−Yij2+njhj2−B+1/2+1−njB−hj2Vs,i,j∈N,(25)Zi1≤Zj2−2tj+tlj+hj2−B+1/2Vs,i∈R1,j∈R2,i,j∈R1∩R2,l∈N,(26)Zi2≤Zj1−2tj+tlj+B+1/2−hj1Vs,i∈R1,j∈R2,i,j∈R1∩R2,l∈N,(27)∑Nni≤N,i∈N.Constraint (4) indicates that AGV has one container transportation task before starting the container transportation task. Constraint (5) indicates that AGV has one container transportation task after completing one container transportation task. Constraint (6) indicates that ASC has one container loading or unloading task before starting to perform the container loading or unloading task. Constraint (7) indicates that ASC has one container loading or unloading task after completing one container loading or unloading task. Constraint (8) indicates that the waiting time of AGV is less than the maximum waiting time. Constraint (9) shows the time relationship between two consecutive tasks transported by the same AGV and arriving at the buffer. Constraint (10) indicates the preparation time for loading task j to the buffer after the AGV completed task i, and there are four cases. Constraint (11) ensures that the target container in the unloading operation of the marine vessel can be unloaded and enter the target shell position. Constraint (12) ensures that the remaining available capacity of the support area must be 0 at the current time when the AGV is waiting in the seaside I/O point support area during the unloading operation. Constraint (13) ensures that the current task is not completed when the AGV is waiting in the seaside I/O point support area during the packing operation. Equation (14) constrains the set 0-1 variable and shows that when there is no residual available capacity in the seaside I/O point support area, ci=1. Constraint (15) indicates that, during unloading operation, the earliest start time of the time window of task i is the earliest time when the task i is unloaded in the buffer by AGV, and the latest start time is the time when the task i is loaded from the buffer by ASC. Constraint (16) indicates that, during loading operation, the earliest start time of the time window of task i is the earliest time when the task i is unloaded in the buffer by ASC, and the latest start time is the time when the task i is loaded from the buffer by AGV. Constraint (17) ensures that ASCs do not collide with each other and there is a safe distance τ between the twin ASCs. Constraint (18) indicates that ASCs can only perform loading and unloading tasks once at most. Constraint (19) indicates that ASCs can only be in one bay at a certain time. Constraint (20) ensures that the ASC is in the target bay corresponding to the task during loading and unloading. Constraints (21) and (22), respectively, indicate that the actual time for seaside and landside ASC to complete task i must be greater than or equal to the current task planned completion time. Constraints (23) and (24) show the time sequence relationship of the two adjacent tasks of the seaside and the landside ASC, respectively. Constraints (25) and (26) indicate the time sequence relationship between the main task and the secondary task of the container requiring relay operation. Constraint (27) indicates that the number of relay operations will not be greater than the total number of loading and unloading tasks.


## 4. Algorithm Design

The optimization of comprehensive scheduling of container handling and transportation equipment is critical for port operation management. However, the integrated scheduling is an NP-hard problem. With the problem size increases, the computational complexity will increase exponentially. The genetic algorithm can control the collection process adaptively to obtain the approximate optimal solution. It has obvious advantages in solving such NP-hard problems. Therefore, a meta heuristic algorithm (i.e., the genetic algorithm) is proposed to find the best solution of the integrated scheduling problem. The flow of the genetic algorithm is as shown in Figure5.Figure 5
Flowchart of the genetic algorithm.In the cooperative scheduling problem of ASC and AGV, the following problems need to be solved: the problem of ASC job interference, the determination of the time window for each unloading and loading task, and the problem of job sequence conflict between ASC and AGV. Based on the above problems, a three-stage genetic algorithm is designed to solve the cooperative scheduling problem of AGV and ASC in automatic container terminals.The first stage is the scheduling of ASC, which mainly solves the job interference in the plan by avoiding, and obtains a group of feasible ASC scheduling schemes. The second stage is the scheduling of AGV. According to the scheduling plan of the first stage, the optimal AGV scheduling scheme and the time window of each unloading and loading task are searched. The upper limit of the time window is the time when the task is stored in the AGV-mate, and the lower limit is the time when the task is loaded out of the buffer zone. Due to the limited buffer capacity, AGV may need to wait in queue. IfTgi≥Tmax, the job sequence of ASC will be adjusted, and the time window of this task and subsequent tasks will be rearranged. The third stage is the calculation of fitness function. Due to the conflict between ASCs and AGVs, not every chromosome can provide a feasible solution. Therefore, in this stage, the infeasible solution is repaired through cycle iteration. As shown in Figure 6, first of all, the scheduling plans of ASC in the first and second stages are compared to judge whether it is feasible solution. If not, it finds the conflict task i through triple detection, gets the feasible scheme of the task i and the preceding task through cyclic iteration, and then traverses all the subsequent tasks to get the final feasible solution. The coordinated scheduling scheme of ASC and AGV is further optimized through the search process of the three-stage genetic algorithm.Figure 6
The operation flow of repairing infeasible solution.


### 4.1. Chromosome Encoding and Decoding

In this paper, multilayer chromosome and real number coding are used for coding. An arrangement and combination of all task numbers are taken as the first-layer chromosome which represents the operation sequence of the tasks. The second-layer chromosome is an ASC segment, and the gene in the ASC segment corresponds to the ASC number. The third-layer chromosome is an AGV segment, and the gene in the AGV segment corresponds to the AGV number.Figure7 shows an example of this coding system, where the chromosome length is N+R1. When numbering the task sequence, it is necessary to split the tasks that need relay operation according to the splitting principle. Assuming that the initial task scale is n, task i and n+i represent the primary and secondary task separated from the same initial task i. For example, when n=4, task 2 and 3 are relay tasks, and handshake bay is 11, then task sequence after splitting is (1, 2, 3, 4, 6, 7), as shown in Table 1.Figure 7
Chromosome encoding and decoding diagram.Table 1
Example of the task number.
Original taskTask after splittingTask sequence1234126374Origin00189001118119Destination51600511161100In present paper, it is assumed that there are 2 ASCs, and each ASC has 6 container tasks. It is also made an assumption that there are 8 relay tasks, and 3 AGVs are used for horizontal transportation. In the chromosome coding system, the gene of ASC and AGV segments corresponds to the initial task, and the corresponding container operation sequence of ASC and AGV can be obtained by decoding in turn according to the task sequence in the task segment. According to Figure7, the decoding results show that the job sequence of seaside ASC is (1, 3, 4, 6, 8, 10, 14, 17, 19, 23); the job sequence of landside ASC is (2, 5, 7, 9, 11, 12, 13, 16, 20, 22); the job sequence of agv1 is (4, 14, 23); the job sequence of agv2 is (3, 10, 17, 19); and the job sequence of agv3 is (1, 6, 8).


### 4.2. Initial Population

In this paper, the heuristic method is used to generate the initial population, which makes the generated individuals closer to the optimal solution and the evolutionary effect is better:(i)
Step 1: an initial solution is generated randomly, the seaside ASC gene segmenty11,y21,…,yj1and landside ASC gene segment y12,y22,…,yv2 are proposed, and then the gene position of the first and second stages of the relay task and the difference d between two positions are calculated.(ii)
Step 2: it is judged that whether the differenced is greater than θ, θ∈2,N−R. If d<θ, the first stage of the relay task is searched forward, and a gene locus is randomly selected and exchanged. The second stage of the relay task is searched backward. A gene locus is randomly selected and exchanged until d>θ.(iii)
Step 3: the remaining relay tasks were selected in turn until all relay tasks meet the conditions, and then a chromosome can be obtained. The above steps are repeated forNP times to generate an initial population of size of NP. The generation process of initial population is shown in Figure 8, where θ=2, and task 4 and task 16 are the first and second phases of the relay task, respectively.Figure 8
The generation process of initial population.


### 4.3. Fitness Function and Selection

In this paper, the sum of the minimum waiting time of AGV and the completion time of twin ASCs is used as the fitness value, and the better individuals are selected by the roulette wheel sampling method for crossover and mutation. Generally speaking, the fitness function is transformed from the objective function, and the selection of fitness function directly affects the convergence speed of the genetic algorithm and whether the optimal solution can be found. The fitness function is given as(28)Fitfx=cmax−fx,fx<cmax,0,others,where cmaxis the maximum estimate of fx.


### 4.4. Crossover and Mutation

This paper uses a two-point crossover method to cross the chromosome population. Since the tasks served by ASC are known after task splitting, the whole chromosome is first decomposed into 2 parts according to the ASC number to determine the parent chromosome of crossover operation, and then crossover is performed in two groups. This means that only the AGV segment and task segment need to be crossed. It can be seen from Figure9 that the number of tasks for seaside ASC after chromosome grouping is 10. According to the crossing principle, two random integers r1 and r2 in the 1,10 interval are generated. The data between r1 and r2 are cross processed, and the unreasonable chromosome after cross is genetically repaired. The process of chromosome crossing is shown in Figure 9, where r1 and r2 are 4 and 7, respectively.Figure 9
The process of seaside ASC chromosome crossing.After crossing, the numbers being not repeated in the same chromosome are retained, and the repeated numbers are mapped with the corresponding relationship of the middle segment to eliminate the duplicate numbers.Mutation operation is an auxiliary method to generate new individuals, which determines the local search ability of the genetic algorithm to a certain extent, maintains the diversity of population, and prevents premature convergence. Because the result of mutation is uncertain, mutation probabilitypm is usually set to a very small number. In this paper, we use the basic mutation method, based on the mutation probability. A parent chromosome is randomly selected, two integers of 1,10 are randomly selected as mutation points, and the gene values on the two mutation points are mutated. The mutation operation is shown in Figure 10.Figure 10
The process of seaside ASC chromosome mutating.


### 4.5. Simulated Annealing Operation

Because the traditional genetic algorithm is easy to fall into the local optimal problem, this paper introduces the idea of simulated annealing in the genetic algorithm. After mutation, the new individuals are judged through the metropolis criterion to decide whether to accept it or not:(29)pii⟶j=1,Fitj≤Fiti,expFiti−FitjT,else,where Fiti is the fitness before cross mutation, Fitj is the fitness after cross mutation, T is the current temperature, and Tdecreases according to the cooling rate with the evolution.


## 4.1. Chromosome Encoding and Decoding

In this paper, multilayer chromosome and real number coding are used for coding. An arrangement and combination of all task numbers are taken as the first-layer chromosome which represents the operation sequence of the tasks. The second-layer chromosome is an ASC segment, and the gene in the ASC segment corresponds to the ASC number. The third-layer chromosome is an AGV segment, and the gene in the AGV segment corresponds to the AGV number.Figure7 shows an example of this coding system, where the chromosome length is N+R1. When numbering the task sequence, it is necessary to split the tasks that need relay operation according to the splitting principle. Assuming that the initial task scale is n, task i and n+i represent the primary and secondary task separated from the same initial task i. For example, when n=4, task 2 and 3 are relay tasks, and handshake bay is 11, then task sequence after splitting is (1, 2, 3, 4, 6, 7), as shown in Table 1.Figure 7
Chromosome encoding and decoding diagram.Table 1
Example of the task number.
Original taskTask after splittingTask sequence1234126374Origin00189001118119Destination51600511161100In present paper, it is assumed that there are 2 ASCs, and each ASC has 6 container tasks. It is also made an assumption that there are 8 relay tasks, and 3 AGVs are used for horizontal transportation. In the chromosome coding system, the gene of ASC and AGV segments corresponds to the initial task, and the corresponding container operation sequence of ASC and AGV can be obtained by decoding in turn according to the task sequence in the task segment. According to Figure7, the decoding results show that the job sequence of seaside ASC is (1, 3, 4, 6, 8, 10, 14, 17, 19, 23); the job sequence of landside ASC is (2, 5, 7, 9, 11, 12, 13, 16, 20, 22); the job sequence of agv1 is (4, 14, 23); the job sequence of agv2 is (3, 10, 17, 19); and the job sequence of agv3 is (1, 6, 8).


## 4.2. Initial Population

In this paper, the heuristic method is used to generate the initial population, which makes the generated individuals closer to the optimal solution and the evolutionary effect is better:(i)
Step 1: an initial solution is generated randomly, the seaside ASC gene segmenty11,y21,…,yj1and landside ASC gene segment y12,y22,…,yv2 are proposed, and then the gene position of the first and second stages of the relay task and the difference d between two positions are calculated.(ii)
Step 2: it is judged that whether the differenced is greater than θ, θ∈2,N−R. If d<θ, the first stage of the relay task is searched forward, and a gene locus is randomly selected and exchanged. The second stage of the relay task is searched backward. A gene locus is randomly selected and exchanged until d>θ.(iii)
Step 3: the remaining relay tasks were selected in turn until all relay tasks meet the conditions, and then a chromosome can be obtained. The above steps are repeated forNP times to generate an initial population of size of NP. The generation process of initial population is shown in Figure 8, where θ=2, and task 4 and task 16 are the first and second phases of the relay task, respectively.Figure 8
The generation process of initial population.


## 4.3. Fitness Function and Selection

In this paper, the sum of the minimum waiting time of AGV and the completion time of twin ASCs is used as the fitness value, and the better individuals are selected by the roulette wheel sampling method for crossover and mutation. Generally speaking, the fitness function is transformed from the objective function, and the selection of fitness function directly affects the convergence speed of the genetic algorithm and whether the optimal solution can be found. The fitness function is given as(28)Fitfx=cmax−fx,fx<cmax,0,others,where cmaxis the maximum estimate of fx.


## 4.4. Crossover and Mutation

This paper uses a two-point crossover method to cross the chromosome population. Since the tasks served by ASC are known after task splitting, the whole chromosome is first decomposed into 2 parts according to the ASC number to determine the parent chromosome of crossover operation, and then crossover is performed in two groups. This means that only the AGV segment and task segment need to be crossed. It can be seen from Figure9 that the number of tasks for seaside ASC after chromosome grouping is 10. According to the crossing principle, two random integers r1 and r2 in the 1,10 interval are generated. The data between r1 and r2 are cross processed, and the unreasonable chromosome after cross is genetically repaired. The process of chromosome crossing is shown in Figure 9, where r1 and r2 are 4 and 7, respectively.Figure 9
The process of seaside ASC chromosome crossing.After crossing, the numbers being not repeated in the same chromosome are retained, and the repeated numbers are mapped with the corresponding relationship of the middle segment to eliminate the duplicate numbers.Mutation operation is an auxiliary method to generate new individuals, which determines the local search ability of the genetic algorithm to a certain extent, maintains the diversity of population, and prevents premature convergence. Because the result of mutation is uncertain, mutation probabilitypm is usually set to a very small number. In this paper, we use the basic mutation method, based on the mutation probability. A parent chromosome is randomly selected, two integers of 1,10 are randomly selected as mutation points, and the gene values on the two mutation points are mutated. The mutation operation is shown in Figure 10.Figure 10
The process of seaside ASC chromosome mutating.


## 4.5. Simulated Annealing Operation

Because the traditional genetic algorithm is easy to fall into the local optimal problem, this paper introduces the idea of simulated annealing in the genetic algorithm. After mutation, the new individuals are judged through the metropolis criterion to decide whether to accept it or not:(29)pii⟶j=1,Fitj≤Fiti,expFiti−FitjT,else,where Fiti is the fitness before cross mutation, Fitj is the fitness after cross mutation, T is the current temperature, and Tdecreases according to the cooling rate with the evolution.


## 5. Results and Discussion

In this paper, the genetic algorithm was used to solve the problem of the ASC and the AGV cooperative scheduling under the condition of limited buffer capacity and twin ASC job interference. The superiority of the model and the effectiveness of the algorithm were verified through the comparative analysis of with and without handshake area, and the performance comparison of the algorithm and a sensitivity experiment. The related parameters are set as follows: the no-load running speed of AGV is set to be 4 m/s, and the heavy-load running speed is set to be 2 m/s; the start time of AGV tasks follows the sequence with the first term of 0 and tolerance of 50; the loading and unloading time of a container by ASC is set to be 200 s, the moving speed of ASC is set to be 3.5 s/bay.


### 5.1. Comparative Analysis of with and without Handshake Area

According to the operating experience of existing automatic terminals, the handshake area or temporary storage area is widely used. The handshake area design is often an efficient scheduling scheme for the twin YC of the automatic container terminal. Therefore, in the cooperative scheduling of AGV and ASC under the relay operation mode, this paper compared cooperative scheduling with and without a handshake area to verify the feasibility of handshake area.In this paper, according to the actual operation tasks of the relay gantry crane in the automatic container terminal of the Yangshan deepwater port phase IV project, which is located in Shanghai, China, an experimental example of 20 tasks had been designed. It is assumed that there are 39 bays in each block of the yard, and bay 20 is initially assumed to be handshake area. The seaside I/O point lies in the 0th bay, while the landside I/O point lies in the 40th bay. The distribution of specific tasks is shown in Table 2. The results of the simulation are shown in Tables 3 and 4. The result of Table 3 showed that the scheduling scheme without handshake area design is better under a small number of tasks. The result of Table 4 showed that the scheduling scheme with or without handshake area design.Table 2
Bay-location distribution of tasks.
Task numberInitial positionTarget locationTask typeRelay or not1010LNo22540LNo3029LRelay4360URelay5027LRelay6190UNo72240LNo8030LRelay9350URelay10026LRelay11150UNo12320URelay13390URelay14038LRelay15150UNo164025UNo172840LNo18340URelay19025LRelay20290URelayTable 3
Solution results of two schemes for design with or without handshake area under relay operation mode.
Schemesf1 (s)f2 (s)Objective function value (s)With handshake area design495144239374Without handshake area design395750038960Table 4
Operation process of each kind of equipment under the two schemes with or without handshake area design.
SchemesEquipmentWork sequenceWith handshake area designAGV115-8-1-10-5AGV213-20-4-9-12AGV36-18-11-19-3-14ASC115-6-8-18-1-11-10-13-19-2-0-5-4-3-9-14-12ASC214-13-7-8-20-2-17-16-10-4-19-9-5-12-3-18Without handshake area designAGV16-15-11-10-19AGV21-8-14-3-5AGV39-4-20-12-18-13ASC16-15-11-1-8-10-14-19-9-3-4-5-20-12-18-13ASC216-12-19-20-7-9-8-4-10-3-2-17-18-14-13-5Figures11 and 12 show ASC operation path diagrams under two schemes, in which the horizontal axis represents bay and the vertical axis represents time. With handshake area, ASC workload on both sides is relatively balanced. The seaside ASC takes 4423 s, and the landside ASC takes 4360 s. Without handshake area, the seaside ASC takes 4413 s and landside ASC takes 5003.5 s. There is approximately 12% difference in task completion time between ASCs on both sides. This would cause the workload of ASCs on both sides to be mismatched.Figure 11
ASC scheduling with handshake area design.Figure 12
ASC scheduling without handshake area design.According to the scheduling results in Table3, for the same 20 task data, the scheduling scheme without handshake area design is much better than that with handshake area design. The reason is that the ASC workload on both sides is unbalanced under the design of no handshake area, and the seaside ASC completes the task too early, resulting in the AGV waiting time far less than the former. In the case of with handshake area design, the maximum time consumption of ASC is 4423 s, while in the case of without handshake area design, the maximum time consumption of ASC is 5003.5 s, and it is 11.60% higher than the former. However, the waiting time of AGV under the case of without handshake area design is about 20% less than the former, which leads to better scheduling scheme in the case of without handshake area design. In summary, the design of without handshake area saves 4.42% of the time.Figure13 presents a comparison of the results of two scheduling schemes under different task numbers. It can be seen that, without considering other factors, when the number of tasks is small, the result of the scheduling scheme without handshake area design is better. With the increase of the number of containers, the difference between the two scheduling schemes becomes smaller. When the number of tasks exceeds 90, the scheduling scheme with handshake area design is better than the latter. The main reason is that with the increase in task size, the delay time caused by the interference between the ASCs increases gradually, while the waiting time of AGV tends to be equal. When the buffer capacity is increased, the scheduling scheme under the handshake area design will be better than the latter earlier, which verified the feasibility of introducing handshake area into the cooperative scheduling model of AGV and ASC under the relay operation mode.Figure 13
Comparison of two scheduling schemes.


### 5.2. GA Parameter Experiment

In the genetic algorithm, the parameters have an important influence on the performance of the algorithm. We study the search results of the genetic algorithm under different parameter settings, so as to select the appropriate parameter combination for the problem. Here, we used the data in Table2. The parameter values of GA are as follows:Crossover ratepc=0.6,0.7,0.8,0.9Mutation ratepm=0.3,0.4,0.5,0.6,0.7Population sizePop=100,200,300,400,500Table5 show the mean of obtained solutions under various crossover rate and mutation rate in 20 size test case. It can be seen that the setting with crossover rate pc=0.9 and mutation rate pm=0.5 outperforms others for this problem. Figure 14 presents the mean objective values for different population size under pc=0.9 and pm=0.5 in 20 size test cases. With the increase of population size, it was found that the value of the objective function gradually decreases, but when the population size reaches 500, the decline range is small, so that the setting with crossover rate pc=0.9, mutation rate pm=0.5, and population size Pop=500 is the most suitable for this problem.Table 5
Mean of obtained solutions under various crossover and mutation rates.
pcpm0.3 (min)0.4 (min)0.5 (min)0.6 (min)0.7 (min)0.6176.23179.68171.89173.84179.390.7179.59182.49171.07176.84173.250.8177.46176.72171.29175.62172.450.9177.01170.63168.45170.05170.95Figure 14
Mean objective values for different population size underpc=0.9 and pm=0.5 in 20 size test cases obtained by the proposed GA.


### 5.3. Algorithm Contrast

In order to verify the effectiveness and stability of the algorithm, this paper set up two kinds of scale examples for the impact of different numbers of tasks, buffer capacity, and number of AGVs on the objective function. In the small-scale case, we used the genetic algorithm and CPLEX to solve 10 groups of examples, respectively. In the large-scale case, we used the genetic algorithm and particle swarm optimization algorithm to solve 14 groups of examples, respectively. Because there are random errors in the results of the genetic algorithm and particle swarm optimization, in order to reduce the random errors, each case runs 20 times, and its average operation time and average optimal fitness value were recorded. The specific results are shown in Table6 and 7. The parameters of PSO are set as follows: the population size of PSO is 500, the maximum iteration times is 100, c1=c2=1.1496, and ω=0.7298.Table 6
Comparison of CPLEX and GA result.
SequenceN ∗ B ∗ KCPLEXGADeviation (%)F (min)Time (s)F (min)Time (s)15∗ 3 ∗ 333.130.2733.9625.612.42210∗ 3 ∗ 367.77754.3669.0850.251.91315∗ 3 ∗ 385.38203586.7672.621.59420∗ 3 ∗ 3117.554319124.0290.205.25525∗ 4 ∗ 4158.856900163.34122.255.07630∗ 4 ∗ 5201.3511520212.94165.235.43740∗ 4 ∗ 5245.3014999256.78198.804.47850∗ 5 ∗ 5348.2818000363.12240.564.09980∗ 6 ∗ 6740.40>20000794.08510.266.76(30)Deviation%=GA−CPLEXGA×100.Table 7
Comparison of algorithm results.
SequenceN ∗ B ∗ KGAPSODeviation (%)F (min)Time (s)F (min)Time (s)110∗ 3 ∗ 268.5747.5069.3448.601.11210∗ 3 ∗ 369.6148.5070.1249.700.73320∗ 3 ∗ 3125.2787.60128.3291.102.37420∗ 4 ∗ 4131.9986.90154.0092.3014.29550∗ 3 ∗ 5482.31206.40507.41210.9010.11650∗ 4 ∗ 5377.78212.50487.81289.6022.00780∗ 4 ∗ 5823.04496.60857.06564.204.00880∗ 5 ∗ 5797.46480.90833.73494.404.359100∗ 4 ∗ 61014.18718.301098.09749.007.6410100∗ 5 ∗ 6987.43795.001079.72819.007.7811150∗ 5 ∗ 61385.711673.001655.831676.5016.3212150∗ 5 ∗ 81438.431720.001708.341741.0015.8013200∗ 4 ∗ 101896.82950.002051.522994.007.5414200∗ 5 ∗ 101784.42992.001888.163007.005.50(31)Deviation%=PSO−GAPSO×100.It can be seen from Table6 that when the task size is small, CPLEX can quickly calculate the exact solution. However, with the increase of the number of tasks, the solution time of CPLEX becomes longer and longer. When the number of tasks reaches 25, CPLEX cannot get the exact solution in an acceptable time. The average difference between the optimal fitness value obtained by GA and that by CPLEX is 4.11%. The above results show that the GA is effective for small-scale calculation. From Table 7, it can be seen that, in the large-scale case, with the increase in tasks, the solution obtained by each group of the genetic algorithm has obvious advantages compared with particle swarm optimization. It also found that the running time of the genetic algorithm is relatively short, and the convergence speed is faster. The results verified the stability and effectiveness of the genetic algorithm in solving the collaborative scheduling model of port handling equipment in this paper.


### 5.4. Buffer Capacity Analysis

In this paper, five groups of experiments were set for the effects of different numbers of tasks and buffer size on the objective function, corresponding to the number of tasks at different scales of 10, 20, 30, 40, and 50, respectively. At the same time, four subexamples were set for each experiment, corresponding to different buffer capacities of 3, 4, 5, 6, and 7, respectively. The genetic algorithm was used to solve 5 groups of experiments, and the average value of 10 experiments was taken. The specific results are shown in Table8.Table 8
Buffer capacity analysis.
Task quantityBuffer capacity/objective function3 (min)4 (min)5 (min)6 (min)7 (min)1079.2973.0570.9370.0269.5320163.60156.47153.65151.79150.2930273.40263.10257.67254.70252.3040376.95363.40354.73348.72345.0250491.95475.53462.80454.57449.27The result of Table8 showed that when buffer capacity is small, increasing the buffer capacity can reduce the total operation time of each task. This effect is becoming more obvious with the increase in tasks for relay operation. Figure 15 presents the trend of total delay time of different buffer capacities. By comparing the total operation time of different buffers in each group, it was found that increasing the buffer capacity has a decreasing effect on reducing the total operation time.Figure 15
Trend of total operation time of different buffers.


## 5.1. Comparative Analysis of with and without Handshake Area

According to the operating experience of existing automatic terminals, the handshake area or temporary storage area is widely used. The handshake area design is often an efficient scheduling scheme for the twin YC of the automatic container terminal. Therefore, in the cooperative scheduling of AGV and ASC under the relay operation mode, this paper compared cooperative scheduling with and without a handshake area to verify the feasibility of handshake area.In this paper, according to the actual operation tasks of the relay gantry crane in the automatic container terminal of the Yangshan deepwater port phase IV project, which is located in Shanghai, China, an experimental example of 20 tasks had been designed. It is assumed that there are 39 bays in each block of the yard, and bay 20 is initially assumed to be handshake area. The seaside I/O point lies in the 0th bay, while the landside I/O point lies in the 40th bay. The distribution of specific tasks is shown in Table 2. The results of the simulation are shown in Tables 3 and 4. The result of Table 3 showed that the scheduling scheme without handshake area design is better under a small number of tasks. The result of Table 4 showed that the scheduling scheme with or without handshake area design.Table 2
Bay-location distribution of tasks.
Task numberInitial positionTarget locationTask typeRelay or not1010LNo22540LNo3029LRelay4360URelay5027LRelay6190UNo72240LNo8030LRelay9350URelay10026LRelay11150UNo12320URelay13390URelay14038LRelay15150UNo164025UNo172840LNo18340URelay19025LRelay20290URelayTable 3
Solution results of two schemes for design with or without handshake area under relay operation mode.
Schemesf1 (s)f2 (s)Objective function value (s)With handshake area design495144239374Without handshake area design395750038960Table 4
Operation process of each kind of equipment under the two schemes with or without handshake area design.
SchemesEquipmentWork sequenceWith handshake area designAGV115-8-1-10-5AGV213-20-4-9-12AGV36-18-11-19-3-14ASC115-6-8-18-1-11-10-13-19-2-0-5-4-3-9-14-12ASC214-13-7-8-20-2-17-16-10-4-19-9-5-12-3-18Without handshake area designAGV16-15-11-10-19AGV21-8-14-3-5AGV39-4-20-12-18-13ASC16-15-11-1-8-10-14-19-9-3-4-5-20-12-18-13ASC216-12-19-20-7-9-8-4-10-3-2-17-18-14-13-5Figures11 and 12 show ASC operation path diagrams under two schemes, in which the horizontal axis represents bay and the vertical axis represents time. With handshake area, ASC workload on both sides is relatively balanced. The seaside ASC takes 4423 s, and the landside ASC takes 4360 s. Without handshake area, the seaside ASC takes 4413 s and landside ASC takes 5003.5 s. There is approximately 12% difference in task completion time between ASCs on both sides. This would cause the workload of ASCs on both sides to be mismatched.Figure 11
ASC scheduling with handshake area design.Figure 12
ASC scheduling without handshake area design.According to the scheduling results in Table3, for the same 20 task data, the scheduling scheme without handshake area design is much better than that with handshake area design. The reason is that the ASC workload on both sides is unbalanced under the design of no handshake area, and the seaside ASC completes the task too early, resulting in the AGV waiting time far less than the former. In the case of with handshake area design, the maximum time consumption of ASC is 4423 s, while in the case of without handshake area design, the maximum time consumption of ASC is 5003.5 s, and it is 11.60% higher than the former. However, the waiting time of AGV under the case of without handshake area design is about 20% less than the former, which leads to better scheduling scheme in the case of without handshake area design. In summary, the design of without handshake area saves 4.42% of the time.Figure13 presents a comparison of the results of two scheduling schemes under different task numbers. It can be seen that, without considering other factors, when the number of tasks is small, the result of the scheduling scheme without handshake area design is better. With the increase of the number of containers, the difference between the two scheduling schemes becomes smaller. When the number of tasks exceeds 90, the scheduling scheme with handshake area design is better than the latter. The main reason is that with the increase in task size, the delay time caused by the interference between the ASCs increases gradually, while the waiting time of AGV tends to be equal. When the buffer capacity is increased, the scheduling scheme under the handshake area design will be better than the latter earlier, which verified the feasibility of introducing handshake area into the cooperative scheduling model of AGV and ASC under the relay operation mode.Figure 13
Comparison of two scheduling schemes.


## 5.2. GA Parameter Experiment

In the genetic algorithm, the parameters have an important influence on the performance of the algorithm. We study the search results of the genetic algorithm under different parameter settings, so as to select the appropriate parameter combination for the problem. Here, we used the data in Table2. The parameter values of GA are as follows:Crossover ratepc=0.6,0.7,0.8,0.9Mutation ratepm=0.3,0.4,0.5,0.6,0.7Population sizePop=100,200,300,400,500Table5 show the mean of obtained solutions under various crossover rate and mutation rate in 20 size test case. It can be seen that the setting with crossover rate pc=0.9 and mutation rate pm=0.5 outperforms others for this problem. Figure 14 presents the mean objective values for different population size under pc=0.9 and pm=0.5 in 20 size test cases. With the increase of population size, it was found that the value of the objective function gradually decreases, but when the population size reaches 500, the decline range is small, so that the setting with crossover rate pc=0.9, mutation rate pm=0.5, and population size Pop=500 is the most suitable for this problem.Table 5
Mean of obtained solutions under various crossover and mutation rates.
pcpm0.3 (min)0.4 (min)0.5 (min)0.6 (min)0.7 (min)0.6176.23179.68171.89173.84179.390.7179.59182.49171.07176.84173.250.8177.46176.72171.29175.62172.450.9177.01170.63168.45170.05170.95Figure 14
Mean objective values for different population size underpc=0.9 and pm=0.5 in 20 size test cases obtained by the proposed GA.


## 5.3. Algorithm Contrast

In order to verify the effectiveness and stability of the algorithm, this paper set up two kinds of scale examples for the impact of different numbers of tasks, buffer capacity, and number of AGVs on the objective function. In the small-scale case, we used the genetic algorithm and CPLEX to solve 10 groups of examples, respectively. In the large-scale case, we used the genetic algorithm and particle swarm optimization algorithm to solve 14 groups of examples, respectively. Because there are random errors in the results of the genetic algorithm and particle swarm optimization, in order to reduce the random errors, each case runs 20 times, and its average operation time and average optimal fitness value were recorded. The specific results are shown in Table6 and 7. The parameters of PSO are set as follows: the population size of PSO is 500, the maximum iteration times is 100, c1=c2=1.1496, and ω=0.7298.Table 6
Comparison of CPLEX and GA result.
SequenceN ∗ B ∗ KCPLEXGADeviation (%)F (min)Time (s)F (min)Time (s)15∗ 3 ∗ 333.130.2733.9625.612.42210∗ 3 ∗ 367.77754.3669.0850.251.91315∗ 3 ∗ 385.38203586.7672.621.59420∗ 3 ∗ 3117.554319124.0290.205.25525∗ 4 ∗ 4158.856900163.34122.255.07630∗ 4 ∗ 5201.3511520212.94165.235.43740∗ 4 ∗ 5245.3014999256.78198.804.47850∗ 5 ∗ 5348.2818000363.12240.564.09980∗ 6 ∗ 6740.40>20000794.08510.266.76(30)Deviation%=GA−CPLEXGA×100.Table 7
Comparison of algorithm results.
SequenceN ∗ B ∗ KGAPSODeviation (%)F (min)Time (s)F (min)Time (s)110∗ 3 ∗ 268.5747.5069.3448.601.11210∗ 3 ∗ 369.6148.5070.1249.700.73320∗ 3 ∗ 3125.2787.60128.3291.102.37420∗ 4 ∗ 4131.9986.90154.0092.3014.29550∗ 3 ∗ 5482.31206.40507.41210.9010.11650∗ 4 ∗ 5377.78212.50487.81289.6022.00780∗ 4 ∗ 5823.04496.60857.06564.204.00880∗ 5 ∗ 5797.46480.90833.73494.404.359100∗ 4 ∗ 61014.18718.301098.09749.007.6410100∗ 5 ∗ 6987.43795.001079.72819.007.7811150∗ 5 ∗ 61385.711673.001655.831676.5016.3212150∗ 5 ∗ 81438.431720.001708.341741.0015.8013200∗ 4 ∗ 101896.82950.002051.522994.007.5414200∗ 5 ∗ 101784.42992.001888.163007.005.50(31)Deviation%=PSO−GAPSO×100.It can be seen from Table6 that when the task size is small, CPLEX can quickly calculate the exact solution. However, with the increase of the number of tasks, the solution time of CPLEX becomes longer and longer. When the number of tasks reaches 25, CPLEX cannot get the exact solution in an acceptable time. The average difference between the optimal fitness value obtained by GA and that by CPLEX is 4.11%. The above results show that the GA is effective for small-scale calculation. From Table 7, it can be seen that, in the large-scale case, with the increase in tasks, the solution obtained by each group of the genetic algorithm has obvious advantages compared with particle swarm optimization. It also found that the running time of the genetic algorithm is relatively short, and the convergence speed is faster. The results verified the stability and effectiveness of the genetic algorithm in solving the collaborative scheduling model of port handling equipment in this paper.


## 5.4. Buffer Capacity Analysis

In this paper, five groups of experiments were set for the effects of different numbers of tasks and buffer size on the objective function, corresponding to the number of tasks at different scales of 10, 20, 30, 40, and 50, respectively. At the same time, four subexamples were set for each experiment, corresponding to different buffer capacities of 3, 4, 5, 6, and 7, respectively. The genetic algorithm was used to solve 5 groups of experiments, and the average value of 10 experiments was taken. The specific results are shown in Table8.Table 8
Buffer capacity analysis.
Task quantityBuffer capacity/objective function3 (min)4 (min)5 (min)6 (min)7 (min)1079.2973.0570.9370.0269.5320163.60156.47153.65151.79150.2930273.40263.10257.67254.70252.3040376.95363.40354.73348.72345.0250491.95475.53462.80454.57449.27The result of Table8 showed that when buffer capacity is small, increasing the buffer capacity can reduce the total operation time of each task. This effect is becoming more obvious with the increase in tasks for relay operation. Figure 15 presents the trend of total delay time of different buffer capacities. By comparing the total operation time of different buffers in each group, it was found that increasing the buffer capacity has a decreasing effect on reducing the total operation time.Figure 15
Trend of total operation time of different buffers.


## 6. Conclusion

This paper analysed the cooperative scheduling of automated guided vehicle and automated stacking crane in the automated container terminal, and optimized the operation characteristics of the new loading and unloading technology for the automated terminal. By combining the AGV and ASC scheduling problems, the collaborative scheduling model of AGV and ASC under ASC relay operation mode was developed, and a genetic algorithm was designed to solve the problem.The results showed that, compared without handshake area, the handshake area design can effectively reduce the interference between the twin ASC operations, and has obvious advantages in large-scale operations. The results indicated that the handshake area design can reduce the ASC operation interference time by an average of 10.56%. It was also found that increasing the buffer capacity can reduce the total operation time of each task, and the effect is more obvious with the increase in the number of tasks. It was found that the average operation time decreases by about 2.27% for each buffer increase, where the waiting time of the AGV can be reduced by 4.35% on average. Generally speaking, the setting of buffer zone and handshake area can effectively reduce the operation delay, which can help to improve the overall operation efficiency of the terminal.



---

*Source: 5764012-2021-01-18.xml*