# Research on Cooperative Scheduling of Automated Quayside Cranes and Automatic Guided Vehicles in Automated Container Terminal

Authors: Qianru Zhao; Shouwen Ji; Dong Guo; Xuemin Du; Hongxuan Wang
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

According to previous research studies, automated quayside cranes (AQCs) and automated guided vehicles (AGVs) in automated container terminals have a high potential synergy. In this paper, a collaborative scheduling model for AQCs and AGVs is established and the capacity limitation of the transfer platform on AQCs is considered in the model. The minimum total energy consumption of automated quayside cranes (AQCs) and Automatic Guided Vehicles (AGVs) is taken as the objective function. A two-stage taboo search algorithm is adopted to solve the problem of collaborative scheduling optimization. This algorithm integrates AQC scheduling and AGV scheduling. The optimal solution to the model is obtained by feedback from the two-stage taboo search process. Finally, the Qingdao Port is taken as an example of a data experiment. Ten small size test cases are solved to evaluate the performance of the proposed optimization methods. The results show the applicability of the two-stage taboo search algorithm since it can find near-optimal solutions, precisely and accurately.


---

## Body

## 1. Introduction and Literature Review

With the deepening of economic globalization, the status of automated container terminals is becoming increasingly prominent. Reasonable scheduling for loading and unloading machinery and equipment has become the key to improve the efficiency of terminal operations. On the contrary, with the increasingly serious problem of climate change, low carbon and energy saving have become an urgent issue in container terminals production. In the automated container terminal operating system, automated quayside cranes (AQCs) and automated guided vehicles (AGVs) are the main operating equipment. At the same time, they are also energy-intensive equipment. Therefore, the energy consumption factor should be considered in the research. The total energy consumption of handling equipment was chosen as the research objective, not the operating time for this paper.Figure1 shows the operating system of the automated container terminal. Taking the unloading operation as an example, the automated quayside cranes (AQCs) unloads the container from the ship, and then the containers are transported to the container yard by automated guided vehicles (AGVs). The automated yard cranes (AYCs) are responsible for stocking and retrieving containers. The loading process is reversed.Figure 1
Schematic representation of the container terminal operating system.This paper mainly wants to do three aspects of research. Firstly, this paper studies the coordination problem of AGV and AQC. A two-stage taboo search algorithm is applied to solve the problem. The first stage is AQC scheduling, the searching for unloading sequence, and the second stage is AGV scheduling, the searching for the AGV walking path. The optimal solution to the model is obtained by feedback from the two-stage taboo search process. Secondly, the capacity limitation of the transfer platform of the AQCs is considered when constructing the cooperative scheduling model. This problem is often overlooked, but it is very important. Because once the capacity limit of the transfer platform is reached, it will cause AGV congestion and AQC operation waiting. This will not only reduce the operating efficiency of the automated terminal, but also increase unnecessary energy consumption. Finally, unlike other literature studies, this paper does not take the minimum operating time as the objective function, but takes the minimum total energy consumption of equipment as the research objective.At present, the research scenarios of loading and unloading equipment collaboration are divided into traditional container terminals and automated container terminals. Hu and Hu [1] considered cooperative scheduling mechanisms among the three types of devices, a full freedom optimization problem with integrated quay crane, yard crane, and yard truck are studied, and a mixed-integer program model is built. By simulation, the sequence and operating time of tasks in different combinations of quay cranes, yard cranes, and yard trucks are analyzed. This study provides a basic model to coordinate the allocation and dispatch of critical operating resources in container terminals. He et al. [2] proposed the reasonable scheduling of quay cranes (QCs), internal trucks (ITs), and yard cranes (YCs), especially coordinated scheduling for the three types of handling equipment, plays an important role in the service level and energy saving of container terminal. In 2018, Roy and de Koster [3] established a new integrated stochastic model for analyzing the performance of overlapping loading and unloading operations to capture the interaction between complex processes of docks, vehicles, and stacks processes. Homayouni et al. [4] proposed a hybrid integer programming model for the integrated dispatch (including SP-AS/RS) of automated container terminal handling equipment. At the same time, a simulated annealing algorithm was developed to solve this problem in 2012. In 2011, Homayouni et al. [5] proposed a comprehensive scheduling scheme based on a mixed-integer linear programming model for dock cranes and automatic guided vehicles. Homayouni et al. [6, 7] proposed a genetic algorithm (GA) to solve this problem more accurately in 2013. In 2014, Sadeghian et al. [8] proposed a mixed-integer programming model that considers the integration of ALVs, quayside cranes, and yard cranes. In 2015, Le and Zhang [9] established a joint scheduling model of automated quayside cranes, automated guided vehicles, and gantry cranes that could achieve the optimal scheduling of the entire horizontal transportation system of container terminals. In 2017, Yu et al. [10] proposed a new integrated scheduling framework of an automated terminal that includes automated guidance vehicles for lifting functions and a buffer bracket system. In 2016, Huo and Hu [11, 12] established a mixed-integer programming model for the multiloaded AGV scheduling problem. Its planning goal was to minimize the total cost of operations, and its constraints were job restriction, time window length, and load balancing. This research method is an event-driven scheduling strategy. A mixed-integer linear programming model of a multiload AGV scheduling problem was established and solved by a genetic algorithm.In addition to cooperative scheduling, single scheduling and real-time scheduling are also very helpful to this paper. In 2018, Xie et al. [13] investigated the problem of relaxed real-time scheduling stabilization of T-S fuzzy systems by proposing a new alterable-weights-based ranking switching mechanism. They proposed a new fuzzy switching controller with a set of activated modes which can be adjusted by the real-time joint distribution of the normalized fuzzy weighting functions. In 2018, Liang et al. [14] studied the AGV scheduling problem and considered the capacity limits of the transfer platform for double-trolley quayside cranes. The delay time of the front trolley and the waiting time between the back trolley and AGVs were taken as an objective function, and an AGV scheduling mixed-integer programming model with a time window constraint was built. A heuristic algorithm was designed to solve the back trolley’s time window, and the model was solved by a genetic algorithm. Then, an AGV scheduling optimization scheme based on the time window of the QC’s back dolly was obtained.The research on handling equipment scheduling for container terminal considering energy consumption is very much. Huang et al. [15] considered three sources of carbon emission during the moving process, loading and unloading process, and preparing process, based on the feature of RTGs that they cannot cross each other. A mathematical model of route programming for RTGs is developed to minimize the carbon emissions. For the computational complexity of a mixed-integer programming model, a path strategy for RTGs is designed. A simulated annealing algorithm is applied to find the near-optimal solution. Xin et al. [16, 17] proposed a hybrid model predictive control (MPC) to optimize the operation performance of container terminals and balance the efficiency and energy consumption of transport equipment. In addition, an event-driven horizontal back controlled method is proposed to reduce the energy consumption of automated container terminals. Besides, they used discrete event dynamics and continuous-time dynamics to represent two different levels of automated container terminal operation. Given the actual operation time, the optimal control is used to control the lower-level dynamics, and the energy consumption of the wharf operation is minimized while considering the time constraints. In 2016, Mei et al. [18] proposed an overall planning model to optimize the scheduling of container terminal yard cranes and minimize the total energy consumption of tire-type gantry crane. In 2013, Yang and Lin [19] studied the selection of equipment for automated container yards on the basis of energy conservation and emission reduction.In addition, the minimum total energy consumption issue has been widely studied in other respects. In 2019, Wang et al. [20] proposed a novel small-signal modeling approach based on the characteristic equation for converter-dominated ac microgrids to assess the system low-frequency stability. Sun et al. [21] investigated the residential energy management problems of the power-heat coupling system. They presented an R-WE frame to solve the residential energy management problems of the power-heat coupling system considering the intermittency and variability features in renewable energy resources.Based on the previous research of taboo algorithm, this paper proposes a new two-stage taboo search algorithm to solve the scheduling problem. Lang and Hu [22] designed taboo search algorithms for solving vehicle routing problems. In 2013, Du et al. [23] studied the work process of AGV material transportation and established a mathematical model of the multiparameter scheduling problem of AGV material transportation with multiple complexes and multiple constraints. The taboo search algorithm was introduced into the genetic algorithm to form the mixed genetic taboo search algorithm. The algorithm was designed and simulated based on a mathematical model. The results showed that the algorithm improved the results of the genetic algorithm and made the AGV take the shortest time to complete the material transport task. In 2016, Yu et al. [24] proposed a hybrid genetic taboo search algorithm for the flexible job-shop scheduling problem, considering defects such as the premature convergence of the genetic algorithm and strong initial solution dependence of the taboo search algorithm. He used the method of dividing target multiplication to guide the evolution of the algorithm, established a multiobjective optimization model, and implemented it with MATLAB simulation.There are other aspects of research related to this article. Kong et al. [25] established a simulation model for the operation of a three-trolley quayside crane and analyzed its efficiency under different speed parameters. Tian [26] introduced the advantages and disadvantages of a double 40 ft double-trolley quayside crane in 2005. In 2011, Zhou et al. [27] utilized advanced electronic information technology to achieve the automatic control of anticollision, antishake, automatic alignment, and recognition, through the application of an optical positioning system SPSS, TDS, and SDS in an automated double-trolley quayside crane. Gu et al. [28] successfully realized the positioning of the spreader and the target container and achieved automatic grasping and releasing functions of the spreader in 2016. Wang et al. [29] introduced a composite heuristic for stacks scheduling on a hatch by integrating the Johnson rule for a developed gap-shifting strategy in 2011.An overview of this literature review is shown in Table1.Table 1
Literature classification of automated container terminals.
Citation
AQC
AGV/ALV
Loading and unloading synchronization
Model and algorithm
Working resource coordination
Xin et al. [16]
Single trolley
AGV
No
Hierarchical control
Yes
Xin et al. [17]
Single trolley
AGV
Unloading
Hierarchical control mixed-integer programming
No
Roy and de Koster [3]
Single trolley
ALV
Yes
An iterative algorithm for parametric decomposition approximation
No
Homayouni et al. [6]
Single trolley
AGV
Yes
Mixed-integer programming simulated annealing algorithm
Yes
Homayouni et al. [5]
Single trolley
AGV
No
Mixed-integer programming simulated annealing algorithm
Yes
Homayouni and Tang [7]
Single trolley
AGV
No
Genetic algorithm
Yes
Sadeghian et al. [8]
Single trolley
ALV
No
Mixed-integer programming model
Yes
Liang et al. [14]
Double trolley
AGV
No
Mixed-integer programming, heuristic algorithm genetic algorithm
No
Huo and Hu [11]
Single trolley
Multiloading AGV
Yes
Mixed-integer programming genetic algorithm
No
Le and Zhang [9]
Single trolley
AGV
No
Genetic algorithm
No
This paper
Double trolley
AGV
Yes
Two-stage taboo search algorithm
Yes


## 2. Description of the Problem

In the loading and unloading operations of automated container terminals, an AQC undertakes loading and unloading operations, and an AGV undertakes horizontal transportation from the container terminal quayside to the yard. During the unloading process, the front trolley of the AQC lifts the container from the ship to the transfer platform, and the rear trolley of the AQC then lifts the container from the transfer platform to the AGV. Figure2 is the working flow chart of the AQCs with double trolleys. Finally, the AGV transports the container to the import yard. The loading process is the opposite of the unloading process.Figure 2
Flow chart of double-trolley AQC [14].Figure3 depicts three scenarios of collaborative operation between AQC and AGV in the automated container terminal. (a) AQC unloads the container from the ship and delivers it to the AGV. The AGV transports the unloaded container to the import container yard and then returns to the AQC. (b) AQC unloads the containers from the ship and delivers them to AGV. AGV transports containers to the import container yard. After unloading the containers, AGV drives to the export container yard. After loading the containers, AGV transports them to AQC, and AQC completes the loading operation. (c) After loading containers at the export container yard, AGV transports containers to AQC, which completes the loading operation.Figure 3
(a) Unloading operation, (b) synchronized loading and unloading operation, and (c) loading operation.
(a)
(b)
(c)This paper assumes that there are three automated quay cranes (AQC1, AQC2, and AQC3). Table2 depicts the loading and unloading operations of AQC at different time periods. The x-axis represents time, and all three AQCs simultaneously unload containers from the ship at times zero. At t1, AQC1 completes the unloading operation and begins to load a container, while AQC2 and AQC3 are still unloading their containers. At t2, AQC2 begins to load a container, AQC3 continues to unload its container, and at t3, AQC3 also begins to load. At t4, AQC3 completes the loading operation and is assigned to another ship for unloading, while AQC2 and AQC1 are still loading.Table 2
Loading and unloading operations of AQC at different time periods.
Time
AQC
[0,t1)
[t1, t2)
[t2, t3)
[t3, t4)
[t4, t5)
AQC1
Unload
Unload and load
Unload and load
Load
Load
AQC2
Unload
Unload
Unload and load
Load
Load
AQC3
Unload
Unload
Unload
Load
—Due to the capacity limitation of the transfer platform for the AQC, the front trolley or the rear trolley can no longer place the container on the transfer platform, when the number of containers on the transfer platform is equal to the capacity of the transfer platform. In the process of scheduling, the AGV transportation time and the AQC waiting time are reduced by the reasonable scheduling of the AGV, thereby reducing the energy consumption of the AGV and the AQC.This paper builds an automated dock configuration model that corresponds to the job time interval. During each working period, some AQCs specialize in unloading operations, while others carry out loading operations. Once the loading and unloading from one ship are completed, another ship arrives, and loading and unloading operations are repeated again. Although the basic nodes of the queuing model remain the same for different time periods, the walking path of the AGV in the network varies depending on the operational phase. Its objective function consists of two parts, the first is that the AQC has the least delay time, and the second is that the AGV and the rear trolley have the smallest two-way waiting time. The scheduling scheme for the AGV needs to be coordinated on the basis of the time window constraint. Therefore, this article seeks to establish an integrated scheduling model.


## 3. Modeling of Joint Scheduling

This paper establishes a collaborative model of AQC and AGV operation and considers the simultaneous loading and unloading of a ship. The objective of the model is to minimize the total energy consumption of AQC and AGV operations for loading and unloading operations. In this paper, the dynamic scheduling method based on the “job surface” is adopted for AGV scheduling. After the AGV transports the imported containers to the yard, it is not empty to return to the shore; the export containers are carried to the shore. An AGV can be dynamically distributed among different “job lines.” The purpose of AGV scheduling is to minimize the distance from empty traffic by matching each import container with the export container. At the same time, due to the capacity limitations of the AQC transit platform, this paper further improves the operational coordination model to avoid AGV congestion during export container loading and waiting for the AQC after importing the container unloading. Thus, the final coordinated scheduling scheme for the AQC and the AGV is obtained.


### 3.1. Symbol Definitions

Table3 contains the definitions of all symbols for the model.Table 3
Symbol definitions.
Symbol
Definition
DP
The number of periods of loading and unloading a ship (DP = 5)
t
Each period
k
AQC (k∈K)
q
Number of AQCs
v
AGV (v∈V)
p
Number of AGVs
i
Import container
n
Number of imported containers (i∈N)
j
Export container
m
Number of export containers (j∈M)
l
i
Storage location of imported containers at the import container yard
l
j
Storage location of an export container at the export container yard
L
i
Collection of import container storage locations (li∈Li)
L
j
Collection of export container storage locations (lj∈Lj)
t
k
l
i
The time when an AGV carries an import container from AQCk to location li
t
l
j
k
The time when an AGV carries an export container from AQCk to location lj
t
l
i
l
j
The idle time of an AGV from storage locationli to storage location lj
t
k
k
+
1
The idle time of an AGV from loading AQCk to unloading AQC k+1
η
k
The average efficiency of an AQC, the average time for an AQC completing a container loading and unloading in periodt
C
k
Energy consumption per unit time of AQCk (unit: kWh)
n
k
t
The number of AQCs loading and unloading containers during periodt
C
v
f
Energy consumption per unit time when each AGVv is full (unit: kWh)
C
v
o
Energy consumption per unit time when each AGVv is empty (unit: kWh)
T
v
t
i
Total time of AGVv transporting the import container i during period t
T
v
t
j
Total time of AGVv transporting the export container j during period t
T
v
t
o
Total time when an AGV is empty during periodt
s
i
k
The planned time of import containeri being put on the transfer platform by the front trolley of AQC k
h
i
k
The actual time of the import containeri being put on the transfer platform by the front trolley of AQC k
r
i
k
The planned time of import containeri being picked up from the transfer platform by the rear trolley of AQC k
u
i
k
The actual time of import containeri being picked up from the transfer platform by the rear trolley of AQC k
s
j
k
The planned time of export containerj being picked up from the transfer platform by the front trolley of AQC k
h
j
k
The actual time of export containerj being picked up from the transfer platform by the front trolley of AQC k
r
j
k
The planned time of export containerj being put on the transfer platform by the rear trolley of AQC k
u
j
k
The actual time of export containerj being put on the transfer platform by the rear trolley of AQC k
B
k
The number of containers that the AQC’s transfer platform can accommodate
O
A large integerTherefore, the following problems can be solved by the hybrid scheduling optimization model:(1)
The loading and unloading ship operation sequence of an AQC(2)
In the synchronous period of ship loading and unloading, the matching import containers and export containers that are carried by the same AGV(3)
Optimizing the AGV’s walking path to achieve the lowest total energy consumption when the AGV and the AQC work together


### 3.2. Decision Variables

The decision variables that define the model are as follows:xik if the operation of import container i is completed by AQC k, xik=1 otherwise, xik=0xjk if the operation of export container j is completed by AQC k, xjk=1 otherwise, xjk=0yiv if the operation of import container i is completed by AGV v, yiv=1 otherwise, yiv=0yjv if the operation of export container j is completed by AGV v, yjv=1 otherwise, yjv=0Zab if an AGV passes the path a,b, Zab=1 otherwise, Zab=0yijv if both import container i and export container j are completed by AGV v, and i is the preorder task of j, yijv=1 otherwise, yijv=0


### 3.3. Objective Function

The decision goal of coordinated scheduling is to minimize the sum of the total energy consumption of the AQC and AGV during the entire loading and unloading period.(1)minf1=∑t=1D∑k=1qnkt∗ηk∗Ck,(2)minf2=∑t=1D∑v=1p∑i=1nTvti+∑j=1mTvtj∗Cvf+Tvto∗Cvo,(3)minf=f1+f2.Equation (1) represents the minimum handling energy consumption of AQC, and equation (2) represents the minimum transportation energy consumption of AGV. Equation (3) represents the minimum total energy consumption. In the container terminal, the AQC’s cart walking mechanism consumes energy only when it is moving, so its energy consumption is mainly the trolley walking mechanism. In the cooperative operation of the AQC and AGV, the main energy consumption is from the AGV’s trolley walks, which includes the energy consumption of full load and no load.The following are the constraints:(4)∑k∈Kxik=1,∀i=N,(5)∑k∈Kxjk=1,∀j=M,(6)∑v∈Vyiv=1,∀i=N,(7)∑v∈Vyjv=1,∀i=M.Equations (4) through (7) ensure that each container is assigned to an AQC and an AGV.(8)tvto=∑li∈Li∑lj∈Ljtlilj+∑k∈Ktkk+1.Equation (8) indicates the idle time of the AGV.(9)tvti=∑li∈Litkli,(10)tvtj=∑lj∈Ljtljk.Equation (9) indicates the time of an AGV carrying a container to the import yard, and (10) indicates the time of an AGV transporting an export container to the AQC.(11)Tvti+ηk≤Tvti′,∀i,i′∈N,∀k∈K,(12)Tvtj+ηk≤Tvtj′,∀j,j′∈N,∀k∈K.Equation (11) defines the relationship between the completion time of each import container operation from the perspective of AQC k, in which import containers i and i′ are all completed by the same AQC k, and i′ is the preorder task i. Equation (12) defines the relationship between the completion time of each export container operation from the perspective of AQC k, in which export containers j and j′ are all completed by the same AQC k, and j′ is the preorder task of j.(13)∑i∈Lizlilj=1,∀j∈Lj,(14)∑j∈Ljzlilj=1,∀i∈Li.Equations (13) and (14) are variable value constraints. During the period of synchronous loading and unloading, the pairs of imported containers and exported containers shall be matched and each container is served once. After the container pair is formed, once the unloading sequence is given, the shipping sequence is determined. Then, the container pairs are assigned to the AGV to minimize the total energy consumption.(15)∑yijv≤zij,∀i∈N,∀j∈M,∀v∈V.Equation (15) indicates the constraint of a container pair, ensuring that the import container and the export container are transported by the same AGV during the loading and unloading synchronization.(16)hik≥sik,∀k∈K,i=1,…,n,(17)hjk≥sjk,∀k∈K,j=1,…,m.Equations (16) and (17), respectively, indicate that the actual time for the AQC’s front trolley to drop (unload) or pick up (load) from the transfer platform is after the planned time.(18)hi+1k−hik≥si+1k−sik,∀k∈K,i=1,…,n,(19)hj+1k−hjk≥sj+1k−sjk,∀k∈K,j=1,…,m.Equations (18) and (19) indicate that the actual time interval for the same AQC’s front trolley to drop or pick up two consecutive containers on the transfer platform is greater than the planned time interval.(20)sik≤hik≤rik≤uik,∀k∈K,i∈N,(21)ujk≤rjk≤hjk≤sjk,∀k∈K,j∈M.Equations (20) and (21) indicate that the loading and unloading times of an AQC’s front and rear trolleys for import and export containers should conform to the actual situation.(22)t−hik<o∗eikt,∀k∈K,∀i∈N,t∈hik,(23)t−hjk>o∗eikt−1,∀k∈K,∀j∈M,t∈hjk,(24)t−ujk<o∗fjkt,∀k∈K,∀j∈M,t∈ujk,(25)t−uik>o∗fikt−1,∀k∈K,∀i∈N,t∈hik,(26)eikt,fikt=0,1,∀k=K,i=1,…,n,(27)ejkt,fjkt=0,1,∀k=K,j=1,…,m.Equation (22) indicates that for an unloading operation when t<hik, eikt=0, the AQC’s front trolley has placed a container on the transfer platform. Equation (23) indicates that for a loading operation, when t>hjk, ejkt=1, the AQC’s front trolley has picked up a container from the transfer platform. Equation (24) indicates that for a loading operation, when t<ujk, fjkt=0, the AQC’s rear trolley has placed a container on the transfer platform. Equation (25) indicates that for an unloading operation, when t>uik, fikt=1, the AQC’s rear trolley has picked up a container from the transfer platform. Equations (26) and (27) indicate that the ranges of a set of variables are 0, 1.(28)∑i∈Neikt−∑i∈Nfikt+∑j∈Mfjkt−∑j∈Mejkt≤Bk,∀k∈K,t∈hik,uik,i∈N,hjk,ujk,j∈M.Equation (28) indicates that the number of containers on the transit platform at each moment should meet the capacity limit of the transit platform.


## 3.1. Symbol Definitions

Table3 contains the definitions of all symbols for the model.Table 3
Symbol definitions.
Symbol
Definition
DP
The number of periods of loading and unloading a ship (DP = 5)
t
Each period
k
AQC (k∈K)
q
Number of AQCs
v
AGV (v∈V)
p
Number of AGVs
i
Import container
n
Number of imported containers (i∈N)
j
Export container
m
Number of export containers (j∈M)
l
i
Storage location of imported containers at the import container yard
l
j
Storage location of an export container at the export container yard
L
i
Collection of import container storage locations (li∈Li)
L
j
Collection of export container storage locations (lj∈Lj)
t
k
l
i
The time when an AGV carries an import container from AQCk to location li
t
l
j
k
The time when an AGV carries an export container from AQCk to location lj
t
l
i
l
j
The idle time of an AGV from storage locationli to storage location lj
t
k
k
+
1
The idle time of an AGV from loading AQCk to unloading AQC k+1
η
k
The average efficiency of an AQC, the average time for an AQC completing a container loading and unloading in periodt
C
k
Energy consumption per unit time of AQCk (unit: kWh)
n
k
t
The number of AQCs loading and unloading containers during periodt
C
v
f
Energy consumption per unit time when each AGVv is full (unit: kWh)
C
v
o
Energy consumption per unit time when each AGVv is empty (unit: kWh)
T
v
t
i
Total time of AGVv transporting the import container i during period t
T
v
t
j
Total time of AGVv transporting the export container j during period t
T
v
t
o
Total time when an AGV is empty during periodt
s
i
k
The planned time of import containeri being put on the transfer platform by the front trolley of AQC k
h
i
k
The actual time of the import containeri being put on the transfer platform by the front trolley of AQC k
r
i
k
The planned time of import containeri being picked up from the transfer platform by the rear trolley of AQC k
u
i
k
The actual time of import containeri being picked up from the transfer platform by the rear trolley of AQC k
s
j
k
The planned time of export containerj being picked up from the transfer platform by the front trolley of AQC k
h
j
k
The actual time of export containerj being picked up from the transfer platform by the front trolley of AQC k
r
j
k
The planned time of export containerj being put on the transfer platform by the rear trolley of AQC k
u
j
k
The actual time of export containerj being put on the transfer platform by the rear trolley of AQC k
B
k
The number of containers that the AQC’s transfer platform can accommodate
O
A large integerTherefore, the following problems can be solved by the hybrid scheduling optimization model:(1)
The loading and unloading ship operation sequence of an AQC(2)
In the synchronous period of ship loading and unloading, the matching import containers and export containers that are carried by the same AGV(3)
Optimizing the AGV’s walking path to achieve the lowest total energy consumption when the AGV and the AQC work together


## 3.2. Decision Variables

The decision variables that define the model are as follows:xik if the operation of import container i is completed by AQC k, xik=1 otherwise, xik=0xjk if the operation of export container j is completed by AQC k, xjk=1 otherwise, xjk=0yiv if the operation of import container i is completed by AGV v, yiv=1 otherwise, yiv=0yjv if the operation of export container j is completed by AGV v, yjv=1 otherwise, yjv=0Zab if an AGV passes the path a,b, Zab=1 otherwise, Zab=0yijv if both import container i and export container j are completed by AGV v, and i is the preorder task of j, yijv=1 otherwise, yijv=0


## 3.3. Objective Function

The decision goal of coordinated scheduling is to minimize the sum of the total energy consumption of the AQC and AGV during the entire loading and unloading period.(1)minf1=∑t=1D∑k=1qnkt∗ηk∗Ck,(2)minf2=∑t=1D∑v=1p∑i=1nTvti+∑j=1mTvtj∗Cvf+Tvto∗Cvo,(3)minf=f1+f2.Equation (1) represents the minimum handling energy consumption of AQC, and equation (2) represents the minimum transportation energy consumption of AGV. Equation (3) represents the minimum total energy consumption. In the container terminal, the AQC’s cart walking mechanism consumes energy only when it is moving, so its energy consumption is mainly the trolley walking mechanism. In the cooperative operation of the AQC and AGV, the main energy consumption is from the AGV’s trolley walks, which includes the energy consumption of full load and no load.The following are the constraints:(4)∑k∈Kxik=1,∀i=N,(5)∑k∈Kxjk=1,∀j=M,(6)∑v∈Vyiv=1,∀i=N,(7)∑v∈Vyjv=1,∀i=M.Equations (4) through (7) ensure that each container is assigned to an AQC and an AGV.(8)tvto=∑li∈Li∑lj∈Ljtlilj+∑k∈Ktkk+1.Equation (8) indicates the idle time of the AGV.(9)tvti=∑li∈Litkli,(10)tvtj=∑lj∈Ljtljk.Equation (9) indicates the time of an AGV carrying a container to the import yard, and (10) indicates the time of an AGV transporting an export container to the AQC.(11)Tvti+ηk≤Tvti′,∀i,i′∈N,∀k∈K,(12)Tvtj+ηk≤Tvtj′,∀j,j′∈N,∀k∈K.Equation (11) defines the relationship between the completion time of each import container operation from the perspective of AQC k, in which import containers i and i′ are all completed by the same AQC k, and i′ is the preorder task i. Equation (12) defines the relationship between the completion time of each export container operation from the perspective of AQC k, in which export containers j and j′ are all completed by the same AQC k, and j′ is the preorder task of j.(13)∑i∈Lizlilj=1,∀j∈Lj,(14)∑j∈Ljzlilj=1,∀i∈Li.Equations (13) and (14) are variable value constraints. During the period of synchronous loading and unloading, the pairs of imported containers and exported containers shall be matched and each container is served once. After the container pair is formed, once the unloading sequence is given, the shipping sequence is determined. Then, the container pairs are assigned to the AGV to minimize the total energy consumption.(15)∑yijv≤zij,∀i∈N,∀j∈M,∀v∈V.Equation (15) indicates the constraint of a container pair, ensuring that the import container and the export container are transported by the same AGV during the loading and unloading synchronization.(16)hik≥sik,∀k∈K,i=1,…,n,(17)hjk≥sjk,∀k∈K,j=1,…,m.Equations (16) and (17), respectively, indicate that the actual time for the AQC’s front trolley to drop (unload) or pick up (load) from the transfer platform is after the planned time.(18)hi+1k−hik≥si+1k−sik,∀k∈K,i=1,…,n,(19)hj+1k−hjk≥sj+1k−sjk,∀k∈K,j=1,…,m.Equations (18) and (19) indicate that the actual time interval for the same AQC’s front trolley to drop or pick up two consecutive containers on the transfer platform is greater than the planned time interval.(20)sik≤hik≤rik≤uik,∀k∈K,i∈N,(21)ujk≤rjk≤hjk≤sjk,∀k∈K,j∈M.Equations (20) and (21) indicate that the loading and unloading times of an AQC’s front and rear trolleys for import and export containers should conform to the actual situation.(22)t−hik<o∗eikt,∀k∈K,∀i∈N,t∈hik,(23)t−hjk>o∗eikt−1,∀k∈K,∀j∈M,t∈hjk,(24)t−ujk<o∗fjkt,∀k∈K,∀j∈M,t∈ujk,(25)t−uik>o∗fikt−1,∀k∈K,∀i∈N,t∈hik,(26)eikt,fikt=0,1,∀k=K,i=1,…,n,(27)ejkt,fjkt=0,1,∀k=K,j=1,…,m.Equation (22) indicates that for an unloading operation when t<hik, eikt=0, the AQC’s front trolley has placed a container on the transfer platform. Equation (23) indicates that for a loading operation, when t>hjk, ejkt=1, the AQC’s front trolley has picked up a container from the transfer platform. Equation (24) indicates that for a loading operation, when t<ujk, fjkt=0, the AQC’s rear trolley has placed a container on the transfer platform. Equation (25) indicates that for an unloading operation, when t>uik, fikt=1, the AQC’s rear trolley has picked up a container from the transfer platform. Equations (26) and (27) indicate that the ranges of a set of variables are 0, 1.(28)∑i∈Neikt−∑i∈Nfikt+∑j∈Mfjkt−∑j∈Mejkt≤Bk,∀k∈K,t∈hik,uik,i∈N,hjk,ujk,j∈M.Equation (28) indicates that the number of containers on the transit platform at each moment should meet the capacity limit of the transit platform.


## 4. Two-Stage Taboo Search Algorithm

According to the characteristics of the model, a two-stage taboo search algorithm is designed to solve the cooperative scheduling problem of AQCs and AGVs in an automated container terminal. This algorithm integrates the decision on two stages for AQC scheduling and AGV scheduling. The first stage is the scheduling of the AQCs. The taboo search algorithm is used to search the loading and unloading sequences according to the different requirements of a ship in different time periods. The second stage is AGV dispatching. Based on the first stage of the loading and unloading sequence, the optimal AGV dispatching scheme (AGV traveling path) is searched, the AQC loading and unloading sequence is constantly revised, the total energy consumption of the different loading and unloading periods is calculated, and the results are fed back to the first stage to determine the taboo search process of the first stage. Simultaneously, the capacity constraint of the AQC’s transfer platform is added to determine if the AQC operation delay time is too long or if the two-way waiting time of the AGV and the rear trolley is too long. Thus, the coordinated scheduling scheme for the AQC and the AGV is further optimized. The optimal solution to the integrated scheduling model is obtained by feedback from two-stage taboo search processes.In the two-stage taboo search algorithm, the unloading sequence of the import containers is given first, that is, the AQC’s unloading sequence in the initial time. During the period [0,t1], the number of AGVs is increased. Due to the capacity limitation of the AQC transfer platform, when the number of AGVs increases to a certain value, there will be two-way waiting between the AGV and the rear trolley. At this time, it is necessary to stop increasing the number of AGV until the f3 minimum. Then, during the periods [t1, t2) and [t2, t3), when the loading and unloading are synchronized, the AGV obtains the import and export container pairs. Calculating the AGV energy consumption of each pair of import and export containers, in ascending order, n container pairs will be allocated to AGV k. Due to the capacity limitation of the AQC transfer platform, the containers loaded onto the AGV will change their original pairing and reselect the matching scheme. During the period [t3, t4], the number of AGVs is reduced. Due to the capacity limitation of the AQC transfer platform, the speed of the AGV reduction should be adjusted according to the change in the loading operation time for the AQC front trolley until the f3 minimum. In the AQC dispatching stage, two imported containers are exchanged with the operation sequence, that is, the optimal operation sequence is searched for the basis of the task allocated by each quayside bridge. When the improved cycle reaches the upper limit, the exchange movement terminates. Figure 4 is the two-stage taboo search flow chart.Figure 4
Flow chart of the algorithm.


### 4.1. Initialization

In the two-stage taboo search algorithm, the unloading sequence is first given. The loading sequence is determined by the matching scheme for import and export containers obtained by formulas (4)—(7). The initial unloading sequence of AQC is given in the initial stage of AQC dispatching.One is to assign tasks to each AQC; the other is to sort the tasks of each AQC. The greedy search method is used to obtain the initial unloading sequence. The specific steps are as follows:Step 1. All unloading AQCs are sorted from small to large according to the energy consumption Ck, and the AQC that consumes minimum Ck is selected.Step 2. A represents the set of containers allocated to the AQC, and the containers satisfying equation (29) are removed from A, where mka represents AQC k completes the last container in the current container sequence and mb represents an unassigned container.(29)1mka−mbrmax1mka−mb,m∈M.Step 3. The container mb is assigned to AQC k according to the probability calculated by equation (30).(30)P=1/mka−mb∑m∈M1/mka−mb.Step 4. Cyclically execute step 1–step 3 until all containers are allocated to AQCs.Step 5. Perform optimization operations for each AQC sequence.The initial solution of AGV scheduling is obtained by a greedy algorithm. First, the container pairs are obtained, and then the total AGV delivery time of each container pair is calculated. In ascending order,n container pairs are allocated to p AGVs successively.


### 4.2. Mobile Strategy

In the collaborative scheduling stage of AQC and AGV, the neighborhood of the current solution is constructed by using two kinds of movements: “increase or decrease” and “exchange.”The way of “increase or decrease” mobility is to increase or decrease the number of AGVs according to the capacity limitation of the transfer platform, so as to minimize the total energy consumption of AQC and AGV operations. When the unimproved cycle reaches the upper limit, the “increase or decrease” mobility terminates.The method of exchanging movement is to first exchange the positions of two imported containers in the operation sequence. In other words, on the basis of the containers assigned by each AQC, searching for the optimal containers sequence and terminating the exchange movement when no improved cycle reaches the upper limit.


### 4.3. Taboo Attributes

For the taboo search process of the collaborative scheduling stage of AQC and AGV, there are two different types of taboo attributes: “exchange” movement and “increasing or decreasing” movement. The taboo attribute of the exchange movement is the two import containers after the exchange position status. The taboo attribute of “increase or decrease” movement is to increase or decrease the amount of AGV according to the capacity limit of transit platform.The choice of taboo term depends on the scale of the problem. The taboo term of AQC and AGV in the collaborative scheduling stage isaqlogq and aplogp, respectively, where q and p are the number of AQC and AGV, respectively, and aq and ap are fixed parameters.


## 4.1. Initialization

In the two-stage taboo search algorithm, the unloading sequence is first given. The loading sequence is determined by the matching scheme for import and export containers obtained by formulas (4)—(7). The initial unloading sequence of AQC is given in the initial stage of AQC dispatching.One is to assign tasks to each AQC; the other is to sort the tasks of each AQC. The greedy search method is used to obtain the initial unloading sequence. The specific steps are as follows:Step 1. All unloading AQCs are sorted from small to large according to the energy consumption Ck, and the AQC that consumes minimum Ck is selected.Step 2. A represents the set of containers allocated to the AQC, and the containers satisfying equation (29) are removed from A, where mka represents AQC k completes the last container in the current container sequence and mb represents an unassigned container.(29)1mka−mbrmax1mka−mb,m∈M.Step 3. The container mb is assigned to AQC k according to the probability calculated by equation (30).(30)P=1/mka−mb∑m∈M1/mka−mb.Step 4. Cyclically execute step 1–step 3 until all containers are allocated to AQCs.Step 5. Perform optimization operations for each AQC sequence.The initial solution of AGV scheduling is obtained by a greedy algorithm. First, the container pairs are obtained, and then the total AGV delivery time of each container pair is calculated. In ascending order,n container pairs are allocated to p AGVs successively.


## 4.2. Mobile Strategy

In the collaborative scheduling stage of AQC and AGV, the neighborhood of the current solution is constructed by using two kinds of movements: “increase or decrease” and “exchange.”The way of “increase or decrease” mobility is to increase or decrease the number of AGVs according to the capacity limitation of the transfer platform, so as to minimize the total energy consumption of AQC and AGV operations. When the unimproved cycle reaches the upper limit, the “increase or decrease” mobility terminates.The method of exchanging movement is to first exchange the positions of two imported containers in the operation sequence. In other words, on the basis of the containers assigned by each AQC, searching for the optimal containers sequence and terminating the exchange movement when no improved cycle reaches the upper limit.


## 4.3. Taboo Attributes

For the taboo search process of the collaborative scheduling stage of AQC and AGV, there are two different types of taboo attributes: “exchange” movement and “increasing or decreasing” movement. The taboo attribute of the exchange movement is the two import containers after the exchange position status. The taboo attribute of “increase or decrease” movement is to increase or decrease the amount of AGV according to the capacity limit of transit platform.The choice of taboo term depends on the scale of the problem. The taboo term of AQC and AGV in the collaborative scheduling stage isaqlogq and aplogp, respectively, where q and p are the number of AQC and AGV, respectively, and aq and ap are fixed parameters.


## 5. Case Study

This paper uses MATLAB R2016a programming to implement the fourth chapter two-stage taboo search algorithm, and it runs on an Intel (R) Core (TM) i5-7200U CPU@2. 50 GHz processor and 8 GB RAM computer.Taking the Qianwan automated terminal of Qingdao Port as an example, a container ship carries out synchronous loading and unloading operations. The cooperative operation of the AQC and the AGV is shown in Figure5.Figure 5
Cooperative operation of AQCs and AGVs in an intelligent container terminal.The average operating efficiency of an AQC is 43 containers per hour, and the operational energy consumption per container is 3 kWh/TEU. The capacity limit of the AQC transfer platform is 4. AGVs travel at a speed of 60 m/min and consume 2 kWh at full load and 0.7 kWh at no load. The distance from the front of the terminal to the import and export container yard is approximately 200 m.The container ships are required to unload 1400TEU imported containers and 1030TEU exported containers at the same time. There are 16 container areas, including 8 import container areas and 8 export container areas. Three AQCs coordinates, 16 container area coordinates, and container stock quantity are shown in Table4.Table 4
Coordinates of each node and the number of containers.
Node type
X coordinate (m)
Y coordinate (m)
Importing and exporting container quantity
AQC1
415
AQC2
455
AQC3
495
E1
525
2
160
E2
575
6
120
E3
625
6
100
E4
675
6
150
E5
725
4
120
E6
775
1
100
E7
825
2
120
E8
875
9
160
I1
25
6
150
I2
75
7
180
I3
125
8
200
I4
175
8
200
I5
225
5
150
I6
275
4
170
I7
325
6
200
I8
375
5
150It is required to arrange the AGV route reasonably so as to minimize the total energy consumption of the equipment. In order to simplify the calculation, the distance between each container area and between AQC and container area are assumed to be straight line distance, which can be calculated according to the coordinates of AQC and container area. According to the characteristics of the problem, the following parameters are used in solving the problem with taboo search algorithm: the penalty weight of the unfeasible path is 1150 km, the number of iteration steps is 400, the 40 neighbors of the current solution are searched in each iteration, and the taboo length is 10. Taboo search algorithm is used to solve 10 times randomly, and the calculated results are shown in Table5. N stands for computing order. TD stands for AGV total mileage. TN represents AGV quantity change. Ni represents the number of iteration steps. Ct stands for computation time. TT stands for the total time of loading and unloading operations. TEC represents the total energy consumption of loading and unloading equipment.Table 5
Calculation results of the taboo search algorithm.
N
TD (km)
TN
N
i
C
t (s)
TT (min)
TEC (kWh)
1
202.36
39-36-18-36-25
268
1.7
125.17
707.53
2
204.11
39-36-16-38-26
320
1.7
125.67
710.27
3
204.22
39-35-16-38-25
358
1.7
124.55
709.36
4
198.56
39-31-18-37-24
345
1.7
120.77
697.52
5
200.62
39-35-20-34-24
303
1.7
124.67
704.79
6
203.99
39-37-16-38-26
146
1.65
125.78
711.175
7
209.88
39-38-14-39-26
232
1.7
126.33
721.2
8∗
196.505
39-26-15-39-23
312
1.7
116.87
690.252
9
197.25
39-33-24-30-22
383
1.76
123.55
698.4
10
198.1
39-37-17-38-26
313
1.7
125.23
701.15
∗stands for optimal solution.It can be seen from Table5 that the taboo search algorithm was used to solve the case of 10 times, high-quality solutions have been obtained. Among them, the eighth solution has the highest quality, the total loading and unloading time is 116.87 min, and the total energy consumption of the equipment is 690.252 kWh. The calculation results of taboo search algorithm are also relatively stable. In the 10 solutions, the energy consumption of the worst solution is only 4.48% higher than that of the best solution. In terms of computational efficiency, the average computational time of 10 solutions is only 1.7 s, which is relatively high.Table6 shows the optimal transport routes and loading and unloading operations solved by the loading and unloading cooperation model and taboo search algorithm.Table 6
Optimized walking route of AGV and loading and unloading quantity.
Path number
Walking path
Unloading
Loading
1
AQC1-I1-AQC1
150
0
2
AQC2-I2-AQC2
180
0
3
AQC3-I3-AQC3
200
0
4
AQC1-I4-AQC1
160
0
5
AQC2-I5-AQC2
150
0
6
AQC3-I6-AQC3
110
0
7
AQC1-I4-E1-AQC1
40
40
9
AQC1-I6-E1-AQC1
60
60
10
AQC2-I7-AQC2
100
0
11
AQC3-I8-AQC3
110
0
12
AQC1-I7-E1-AQC1
60
60
14
AQC2-I8-E2-AQC2
40
40
15
AQC3-I7-AQC3
40
0
16
AQC1-E2-AQC1
0
70
17
AQC2-E3-AQC2
0
100
18
AQC3-E4-AQC3
0
150
19
AQC1-E5-AQC1
0
120
20
AQC2-E6-AQC2
0
100
21
AQC3-E7-AQC3
0
50
22
AQC1-E7
0
70
23
AQC1-E8
0
60
24
AQC2-E8
0
100
Total unloading and loading
1400
1030In order to facilitate comparison, the author also solves the case of 10 times by using hill-climbing algorithm, genetic algorithm, and simulated annealing algorithm. On the premise that the number of searches for the solution is 16000 times, the results of the four algorithms are compared as shown in Table6. ATD stands for AGV average total mileage. ANi represents the average number of iteration steps. ACt stands for average computation time. ATT stands for the average total time of loading and unloading operations. ATEC represents the average total energy consumption of loading and unloading equipment. SD stands for standard deviation from solution.From Table7, it can be seen that the results of the two-stage taboo search algorithm are slightly better than simulated annealing algorithm and obviously better than the hill-climbing algorithm and genetic algorithm. In terms of computational efficiency, the two-stage taboo search algorithm is less than hill-climbing algorithm, but higher than genetic algorithm and simulated annealing algorithm. From the robustness of the algorithm, the taboo search algorithm is better than genetic algorithm, simulated annealing algorithm, and hill-climbing algorithm.Table 7
Comparison of calculation results of the hill-climbing algorithm, simulated annealing algorithm, genetic algorithm, and taboo search algorithm.
Algorithm type
Hill-climbing algorithm
Genetic algorithm
Simulated annealing algorithm
Two-stage taboo search algorithm
ATD (km)
234.62
222.61
203.66
201.56
ANi
13000
10760
12240
11920
ACt (s)
1.66
2.44
1.76
1.7
ATT (min)
189.98
165.96
128.06
123.86
ATEC (kwh)
721.69
715.69
706.21
705.16
SD (kwh)
10.42
8.07
6.38
4.97Using a taboo search algorithm to solve the model, the initial optimal ratio of AQC and AGV is 1/13. The optimum ratio of the two kinds of equipment is constantly changing into different time periods of loading and unloading operation. Due to the capacity limitation of AQC transfer platform, the number of AGV should be adjusted according to the “increase or decrease” mobile strategy. During the synchronization period of loading and unloading operations, an AGV can complete the dual tasks of carrying import and export containers, and realize cross-containers operation. This also greatly reduces the empty driving rate of AGV and reducing energy consumption. In [t4, t5], AQC3 was transferred. The quantitative ratio of AQC and AGV in different time periods is shown in Figure 6, where the vertical axis represents the number of AGVs and the horizontal axis represents 5 time periods.Figure 6
Quantity ratio of AQC and AGV in different periods.The capacity limit of the transfer platform is set as 4 in the experiment. In unloading operations, the number of AQC unloading containers can be greater than the number of AGV transporting containers, thus reducing the number of AGV. In loading operation, the number of AGV transporting containers can be greater than the number of AQC loading containers, thus speeding up the operation efficiency of AGV. Through calculation, Figures7–9 show the comparison between the actual loading and unloading quantity of AQC1, AQC2, and AQC3 and the actual transportation quantity of AGV in different time periods, respectively.Figure 7
Quantity comparison between AQC1 and AGV in different periods.Figure 8
Quantity comparison between AQC2 and AGV in different periods.Figure 9
Quantity comparison between AQC3 and AGV in different periods.In addition, the capacity of the transfer platform and the number of AGVs should be coordinated. When the number of AGVs is constant, the total energy consumption of the equipment decreases with the increase of the capacity of the transfer platform. For the unloading task, the front trolley can unload more containers to the transfer platform, AGV does not have to wait for the rear trolley. For the loading task, the rear trolley can put more containers from AGV to the transfer platform; AGV does not have to wait for the rear trolley. This shows that the transfer platform can effectively reduce the waiting time for devices, thereby reducing the energy consumption of equipment.The energy consumption of AQC and AGV cooperative operation is compared with independent operation. The results are shown in Table8. In the collaborative model, the number ratio of AQC and AGV changes in real-time, which mainly depends on two factors: (1) capacity limitation of the transfer platform; (2) no waiting time. In the noncooperative model, the ratio of AQC and AGV is determined, so the waiting time of AQC occurs in each operation period, which leads to the increase of energy consumption. The percentage of deviation from Table 8 is calculated by(31)deviation%=nonsynergistic−synergisticnonsynergistic×100%.Table 8
Synergistic and nonsynergistic comparison between AQC and AGV.
Synergistic
Nonsynergistic
Deviation (%)
Time
123.55 min
150.04 min
17.66
Mileage of AGV
197.25 km
210.95 km
6.49
Energy consumption of AGV
283.9 kWh
304.8 kWh
6.86
Energy consumption of AQC
364.5 kW
441 kWh
17.35
Total energy consumption
648.4 kWh
745.8 kWh
13.06The results show that the total energy consumption of cooperative scheduling is 13.06% lower than independent scheduling. According to the calculation results from Table8, it can be found that collaborative scheduling plays a significant role in reducing the energy consumption of AQC. The percentage of AGV energy consumption decrease is 6.86%, which is greater than the percentage of mileage. It shows that cooperative scheduling can better reduce the AGV no-load rate.


## 6. Conclusions and Future Research

In this paper, the problem of the cooperative scheduling of the AQC and the AGV is studied under the synchronized loading and unloading conditions of a single ship in an automated container terminal. The main conclusions of this paper include three aspects. (1) Most of the existing research studies focus on the time of loading and unloading. This paper chooses energy consumption as the goal, which can highlight the necessity of scheduling. (2) The new two-stage taboo search algorithm strategy designed in this paper is easy to understand. Using this algorithm to solve AGV scheduling problem, not only can get high-quality solutions, but also the convergence speed of the algorithm is faster, the calculation efficiency is higher, and the calculation results are more stable, showing good optimization performance. (3) The cooperative scheduling model considering the capacity limitation of dual-trolley AQC transfer platform is constructed in this paper, which can provide reference to the optimal scheduling of AGV in automated container terminal and fill the research gap.Future research directions mainly include two aspects. (1) New model and algorithm are designed to solve the problem of container terminal operation resource scheduling. (2) Expanding the cooperative scheduling of two types of operation resources to the comprehensive scheduling of three or four types of operation resources.



---

*Source: 6574582-2019-11-03.xml*