Computers & Industrial Engineering 126 (2018) 482–493

Contents lists available at ScienceDirect

Computers & Industrial Engineering

journal homepage: www.elsevier.com/locate/caie

An integrated scheduling method for AGV routing in automated container T

terminals
Yongsheng Yanga, , Meisu Zhonga, Yasser Dessoukyb, Octavian Postolachec
⁎

a
Shanghai Maritime University, Shanghai 201306, China
b
San Jose State University, USA
c
Instituto de Telecomunicacões/ISCTE-IUL, Lisboa, Portugal

ARTICLE INFO ABSTRACT

Keywords: The simultaneous scheduling of quay cranes (QCs), automated guided vehicles (AGVs), and yard cranes (YCs) in
Automated container terminal automated container terminals (ACTs) has been a critical problem. This paper proposes an integrated scheduling
AGVs path planning for handling equipment coordination and AGV routing. With the goal of minimising makespan, we set up a bi-
Container handling level programming model. To solve the model, we investigate and compare the rolling horizon procedure (RHP)
Integrated scheduling
and Congestion Prevention Rule-based Bi-level Genetic Algorithm (CPR-BGA). It is shown that the CPR-BGA
algorithm is highly effective for the integrated scheduling in ACTs. We conclude that the CPR-BGA is effective.

1. Introduction labour costs, decreased the probability of personal injury accidents, and
proved to be safer for the terminal environment. Automated terminals
The continuous development of global trade as well as logistics possess many advantages in terms of labour cost, improved operation
technologies has been pushing up the demand for container terminals, efficiency and economic benefit, reduced energy consumption, and
including loading and unloading operations, and the storage area. improved levels of safe operation and the port’s reputation (Le, Yassine,
Automated Container Terminals (ACTs) have appeared to meet this & Riadh, 2012; Zhang, Ioannou, & Chassiakos, 2006; Martín-Soberón,
ever-increasing demand and contribute to the higher efficiency and Monfort, Sapiña, Monterde, & Calduch, 2014). While an ACT offers
productivity of port operations as well as reduction in the cost of human such crucial benefits, more research should be conducted to further
resources and emissions at a port. More than 20 ACTs have taken off rationalize its use.
around the world but how to continue to improve their efficiency is still The operation mode of automated container terminal can be divided
one of the most frequently discussed topics on port operations and into a loading process and unloading process. In the loading process,
management. containers from the storage location are transferred from the yard by
The research in the literature on this topic can be categorized into YCs to AGVs, which then transport containers to the port to be loaded
three groups. One is concerned with the methodology of how to de- onto ships by QCs. In the unloading process, containers are removed by
scribe operations of an ACT. Liu, Jula, and Ioannou (2002) presented a QCs and transferred to AGVs, which transport the containers to the YCs
setup and analysis of a microcosmic simulation model for the operation that place containers to the corresponding storage location in the yard
mode of AC. They showed that the model significantly improved the (Gharehgozli, Roy, & Koster, 2016). The operation of container term-
performance of the traditional terminal and reduced costs. Hu, Lee, inals is shown in Fig. 1. In this work, we considered actual circum-
Huang, Lee, and Chew (2013) considered an automated terminal stances in automated terminals where the automatic rail-mounted
system that was decomposed into three subsystems through the Markov gantry (ARMG) unloads the container from AGVs to the AGV-mate in
chain model to analyse and forecast the capacity of containers in ACT. the front of a yard or from the AGV-mate to AGVs. The AGV-mate is an
The sensitivity analysis illustrated the high efficiency of ACT in the auxiliary equipment of AGVs that is used to reduce the waiting times
latter study. Yang et al. (2015) analysed two kinds of microscopic associated with ARMG and AGV, which can optimise the cycle of con-
parameter models to assess the performance of ACT based on automatic tainer loading and unloading and improve the efficiency of ACT.
stacking cranes (ASCs) or AGVs. The implemented models revealed Due to the development of large containers and rising labour costs,
advantages, such as higher efficiency and stability, effectively reduced many overseas and domestic researchers have investigated the

⁎
Corresponding author.
E-mail address: yangys_smu@126.com (Y. Yang).

https://doi.org/10.1016/j.cie.2018.10.007
Received 12 July 2018; Received in revised form 2 October 2018; Accepted 4 October 2018
Available online 06 October 2018
0360-8352/ © 2018 Elsevier Ltd. All rights reserved.
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

Fig. 1. The operation of container terminals.

scheduling problem of AGVs for decades. Since the container- minimise the interference between the QCs and improve the utilization
throughput in Chinese ports have taken a great leap forward, the of QCs by dividing the task allocation of QCs through the Ant Colony
scheduling problem of AGVs has become more urgent. In many studies, Optimisation Algorithm to increase efficient scheduling of QC projects.
AGVs and QCs are considered independently. However, AGVs and QCs Li et al. (2016) considered the interference among QCs and fixed the
work in a close relationship and should be studied dependently for two distance between the QCs, taking full account of the acceleration and
reasons: (1) AGVs play an important role in the quayside and yard-side deceleration of QCs in real-time operating. The latter research used
operations, which restricts and influences the operation of the other heuristics and a rolling horizon algorithm to improve the efficiency and
two parts, and (2) the scheduling of AGVs affects the time needed for reduce the waiting time of QCs, which is a key to improve the
every container to be handled by AGVs. AGVs, as the carrier to connect throughput of container terminals.
QCs with YCs, can influence the operation system of QCs and YCs, While the above-mentioned methods merely focus on QCs in loading
which is directly related to the working efficiency of terminals, and or unloading operation mode, we consider the actual port operation
affect the capacity of a container terminal. In addition, owing to the mode for loading and unloading of QCs in this work. Previous research
high cost of QCs or other factors like the quantitative restriction, an that only focused on the QCs does not match the actual situation of
inefficient operation will cause delays in container terminals and in- automation terminals without considering the AGVs and the yards,
crease the transportation cost of containers. Therefore, studying the which cannot improve the overall operating efficiency. The use of AGVs
problem of integrated scheduling of QCs, AGVs, and YCs is the key to first appeared in 1950s, and now there are many researches on the AGV
automated terminal efficiency. Moreover, a series of problems still ex- scheduling method. Grunow, Günther, and Lehmann (2006) first found
ists, including AGV congestion and conflict, especially in the practical that AGVs could handle two 20-ft containers or one large 40-ft con-
operation of automated terminals. Considering that there are many tainer. The randomness of the off-line heuristic model was proposed to
indefinite factors in current running environments, realizing dynamic improve the efficiency of the AGVs. Nguyen and Kim (2009) discussed
scheduling based on the conditions of AGV path planning is of great scheduling the automatic lifting vehicle (ALV) based on the time
significance in solving the practical problems in automated terminal. In window constraints and analysed the number of ALVs and buffer ca-
this work, we put forward integrated scheduling of QCs, AGVs, and pacity. Gupta, Roy, Koster, and Parhi (2017), using an integrated
ARMG and path planning for AGVs to reduce the problems of AGV queuing network model to analyse the scheduling of ALVs and storage
conflict and congestion, which has yet to be done in previous literature. yard, find out that the parallel stack layout has a better performance.
Therefore, we studied path planning to achieve the integrated sche- Pap, Bojanić, Georgijević, and Bojanić (2011) reduced the complexity
duling of QCs and AGVs and the ARMG optimisation method in the of the container terminal operations and presented a new hypothesis of
automation terminal. We also propose a bi-level programming model a simulation model based on the unloading mode and task allocation of
and Congestion Prevention Rule-based Bi-level Genetic Algorithm containers to minimise the number of AGVs.
(CPR-BGA). However, the above researchers do not consider QCs and AGVs
This paper is structured as follows. Section 2 provides a review of scheduling simultaneously. When AGVs wait for a long time in the
the existing literature on AGV path planning and handling equipment actual operation, congestion and conflict arise; thus, both QC and AGV
scheduling. Section 3 presents a bi-level programming model for- scheduling should be examined together. No research presently exists
mulated for the problem of interest. Section 4 proposes a bi-level Ge- on the optimal path planning, which greatly reduces the working effi-
netic Algorithm to solve the formulated model handling a large-sized ciency of AGVs.
problem. Section 5 shows and analyses the numerical results to show As mentioned before, there are numerous studies on AGVs in-
the performance of the formulated model and proposed algorithm. dependently, but they ignore the impact of QCs and the yard on AGVs.
Section 6 presents the conclusion and offers suggestions for further Meersmans and Wagelmans (2006) used the Branch and Bound algo-
research. rithm with the goal of minimising the completion time to solve the
scheduling problem of equipment in automated container terminals,
2. Literature review which was the first attempt of integrated scheduling of AGVs, QCs, and
YCs. Chen, Bostel, Dejax, Cai, and Xi (2007) set up a Hybrid Flow Shop
In recent years, there has been numerous researches on the equip- Scheduling problem with precedence and Blocking constraints (HFSS-B)
ment of automation terminals, especially focused on improving the to analyse the integrated scheduling method of QCs and Yard Vehicles
efficiency of QCs. For example, Meisel and Bierwirth (2009, 2013), (YVs). Lau and Zhao (2008) used the multi-level genetic algorithm
combined berth allocation with QCs assignment, by the heuristic al- (MLGA) to solve the mixed integer programming model by reducing the
gorithm to get the solution, and then they build a framework with three berth time of ships and increasing the productivity of terminal to im-
stages to finish the integrated planning, which has improved the re- plement the effective scheduling of QCs, AGVs, and YCs. Liang, Lu, and
source utilization and reduced costs in terminals. Park, Choe, Ok, and Zhou (2009) analysed the unloading and loading mode to minimise the
Ryu (2010) used the heuristic-based and local-search-based real-time working time in order to take advantage of the heuristic algorithm
scheduling methods and analysed the reason for the delay when oper- based on Johnson’s rule for scheduling. This algorithm implements the
ating QCs and AGVs to better increase QC utilization and reduce costs. integrated scheduling of QCs, trucks, and YCs and has proven to be
Wen, Ekşioğlu, Greenwood, and Zhang (2010) also attempted to effective through the large-scale calculations. Wu, Luo, Zhang, and

483
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

Dong (2013) proposed the mixed integer programming (MIP) model method based on Johnson’s rule, and the results demonstrated the va-
with a minimum berth time and optimised the operating times of cranes lidity of the optimisation. Zhang, Zeng, and Yang (2016) analysed the
through the non-linear mixed integer program (NIMIP) method to re- driving distance of trucks, YCs, and the required number of trucks and
duce the number of constraints and computing time. Skinner et al. adopted the mixed intermediate storage policy. They combined the
(2013) put forward an optimisation method based on a genetic algo- periodic queuing theory model, which minimises the driving distance of
rithm by comparing the different schemes used for integrated sche- trucks and YC operation, improving the efficiency of the terminal. Luo
duling of QCs, trucks, and Straddle Carriers (SCs) to determine an op- and Wu (2015) achieved integrated scheduling of AGVs and YCs based
timised scheduling scheme. Dhingra, Roy, and Koster (2015), to achieve on the loading and unloading mode and established an integer pro-
planning and scheduling of QCs and AGVs, combined the continuous- gramming model by implementing the Genetic Algorithm for crossover
time Markov chain (CTMC) with the multi-class closed queuing network and mutation; the results proved the effectiveness of the algorithm.
to get the solution of a two-level stochastic model, it proved that the Zhang, Jin, Ma, and Luan (2015) initially optimised the hatch of each
vessel handling time was influenced by QCs operation and AGVs path. berthing ship and the loading and unloading order of containers in
Although much published literature exists on the scheduling of QCs, hatch stacking by considering the loading and unloading mode to re-
AGVs (or trucks), YCs, problems remain with determining the optimal duce QC operation time. Then, they optimised the cargo planning of
route choice for path planning. According to the uncertainty of the export containers to further reduce the QC operation times, which was
actual operation, real-time dynamic planning has not been achieved, realised by using the Bi-level Genetic Algorithm to eventually prove the
which is a highly important factor that influences the efficiency of effectiveness of the scheduling method and improve the loading and
automation terminals. unloading efficiency of the container terminal. Hu, Sheu and Luo
In regards to the AGV path planning problem, numerous studies (2016) investigated the background of the Yang Shan port in Shanghai
have focused on the dynamic scheduling of AGVs, which motivated the to realise the integrated scheduling of the automatic stacker crane
basis of our study. For instance, Nishi, Ando, and Konishi (2006) rea- (ASC) and the automatic lifting vehicle (ALV). It was determined that
lized the dynamic scheduling of AGVs by establishing 143 nodes of a full use of the yard space to improve the terminal’s capacity, and
transportation system to choose the optimal path of AGVs, which re- practical application of the CPLEX and genetic algorithm was demon-
duced lost time and improved scheduling efficiency. Su, Samuel, and strated. Roy and Koster (2015), developed the new integrated stochastic
Chong (2000) investigated AGV path planning as an NP-complete model based on the interactions among QCs, ALVs, and ASCs, using the
asymmetric traveling salesman problem with the minimum path as the iterative convergence algorithm to obtain reasonable methods and
goal. The researchers used an artificial neural network algorithm, layouts of seaside operations.
known to be the basic characteristic of self-organizing, to solve the path As is evident, there are many studies on the integrated scheduling of
planning of AGVs. Nishi, Hiranaka, and Grossmann (2011) minimised QCs, trucks, and YCs in traditional container terminals (Boysen, 2010;
the delay time for finishing tasks as an objective by adopting the upper Zhao and Tang, 2011; Boysen, Briskorn, & Tschöke, 2013), but they
and lower levels of an algorithm for task allocation and focusing on only focus on a single cycle of loading or unloading. Thus, the in-
scheduling as a higher level problem and path planning as a sub-pro- tegrated scheduling of QCs, AGVs, and YCs for two or more cycles of
blem. Results provided a feasible solution for AGV scheduling and loading and unloading need to be studied. Herein, considering the dy-
avoided congestion of path planning at the same time. Liang, Lin, Gen namic path planning of AGVs, we realised the integrated scheduling of
and Chien (2012) considered the AGV in the flexible manufacturing QCs, AGVs, and ARMG simultaneously to develop a bi-level model for
system (FMS) by network model to implement the integrated sche- optimised planning.
duling and AGVs path planning using a random key-based particle
swarm optimization (PSO) for crossover and mutation. Results proved 3. Model formulation
that this algorithm was superior to the traditional genetic algorithm.
Miyamoto and Inoue (2016) realized AGVs scheduling and conflict-free The presented research focused on the loading and unloading op-
path planning by considering factors like the capacity constraints of eration modes with the aim to minimise the handling time of ships in
vehicles, machine buffer, and so on, it is an integer programming port. The problem was divided into two parts: one as the integrated
problem, using the local and random search method to calculate. Sidoti scheduling problem of AGVs and the second as the AGV path planning
et al. (2017) utilized the multi objective planning and asset routing problem. When a ship first entered the docking area, we arranged for
(TMPLAR) tool and considered the uncertainty of space and time, re- the QC and the block to be ahead of time for the ship. Then, the con-
source constraints, and vehicle waiting for consumption. Roy, Gupta, tainers were discharged off the ship to the specified block, while an-
and Koster (2016), proposed a solution for reducing the AGVs conges- other container was loaded onto the ship from the block at the same
tion in path planning and increasing the throughput capacity of ACTs, a time. In order to improve the efficiency of loading and unloading, QCs
non-linear traffic flow model was used to determine the appropriate need to match with blocks, which means that a designated QC unloads a
number and effective speed of AGVs. Mishra, Roy, and Ommeren container from a ship onto a specified block. The specific operation
(2017), to solve the queuing problem in inter terminal transportation process for the loading and unloading mode is presented in Fig. 2,
(ITT), using a network decomposition method to solve this problem, which shows that when the AGV receives an unloading or loading
and applied the model to Port of Rotterdam. By doing so, they formed a order, a container is discharged via the QC to a specified block or a
time window for the shortest path based on the node network diagram container before the AGV-mate is transported to a specified QC.
to realize the AGV dynamic path planning. In terms of unloading operations, the main trolley in the QC will
In this work, we used the above-mentioned literatures on the op- first place containers on the transfer platform, then the portal trolley of
timal path selection of AGVs and equipment integrated scheduling as a the QC will transport a container from the transfer platform to the AGV.
basis to determine a practical solution for further optimisation and After that, the AGV will transport the container to a specified block of
improved efficiency of automated terminals. the AGV-mate, then the front ARMG of the yard will unload the con-
While numerous researches have published on the loading and un- tainer onto a stored block. In the following part of the sequence, the
loading modes for vehicle scheduling and storage problems of con- back ARMG moves the container from the stored block to a specified
tainers in port yards, minimal studies exist on the integrated scheduling position in the yard, then the AGV receives the next task order at the
of QCs, AGVs, and ARMG in ACTs. For example, Zhang and Kim (2009) same time. The loading operation is similar to unloading, but the op-
considered the loading and unloading mode to reduce the number of erational process is the opposite. The horizontal transportation of AGVs
loading and unloading operations of QCs in two cycles. They created a follows the scheduling rules for the operation side, namely that the AGV
container stacking sequence in the hatch in order using the local search can service any QCs and blocks. When the AGV transports the

484
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

transportation, a rule should be set for vehicle density on the auxiliary

road, which is defined as the number of AGVs on each road in the
transportation area at the same time.
To reduce the probability of congestion, the two AGVs are allowed
on each auxiliary road at the same time. If there are more than two,
another path needs to be planned for the third AGV so there is no
Main
trolley possibility of congestion. Fig. 4 shows our proposed model map, which
uses nodes to represent the inflection points, the crossing points in
discharging Portal horizontal transport, blocks, and QCs.
loading 1
trolley
3 2

3.1. Assumptions
1 8 15 9
2 9 16 8

(1) The main trolley of the QC loads the container onto the transfer
3 10 17 7
4 11 18 6

platform or unloads the container from the transfer platform onto

5 12 19 5
6 13 20 4
7 14 21 3

the ship, regardless of the capacity problem of transfer platforms in

22
1

QCs. The transfer platform can accommodate multiple containers at

the same time. Its running time is associated with the location of
containers on the ship, which is assumed to exhibit uniform dis-
Fig. 2. The specific operation process of loading and unloading mode. tribution.
(2) The portal trolley of the QC unloads the container onto the AGV or
container, its driving optional path is established according to a set of places the container from the AGV onto the transfer platform, for
rules. Based on these rules, a suitable path for horizontal transport is which the running time has a fixed value.
selected, and the process is repeated until all the containers have been (3) The speed of AGVs is uniform, regardless of the time AGVs spent on
loaded and unloaded. QCs and AGV-mates.
Through the above problem, we know when containers are loaded (4) All the containers are 40 ft in size, and the QC and ARMG can load
and unloaded and the target position of the container, but which AGVs and unload one container at a time. The AGV also can transport one
is needed to exactly transport the container is unknown, so we need to container at a time.
assign tasks for AGVs (Mishra and Tripathi, 2015). After the assigned (5) ARMG in front of the blocks gets the container from the AGV-mate,
tasks, we plan the path for AGVs, and the alternative driving path of the time of which is negligible, while the time to discharge the
AGV is known. According to the set rules of the auxiliary road, we then container from the AGV-mate onto the storage area is a fixed value.
select an optimal path from alternative paths (Li, Caö, & Tan, 2011). (6) The time required for ARMG in the back of the blocks to retrieve the
The layout of an automated container terminal is presented in container from the storage area can be ignored. The time needed to
Fig. 3, which indicates that the moving direction of the AGV is de- discharge the container from the storage area to a specific location
termined first in clockwise motion to reduce the waiting time and in the back of the block follows uniform distribution, namely the
probability of congestion when planning the AGV path. Because the running time within a time.
single circle line driving is low in efficiency, we choose to increase the (7) A loading task is completed before a discharging task, or a container
auxiliary roads in the whole circle paths. The speed of AGVs is con- is discharged from a ship to complete a loading task.
sidered constant, therefore, the path planning problem can be trans-
formed into the SPP-shortest path problem. 3.2. Model parameters
Horizontal transportation is crucial to link QCs and YCs when there
are many containers in an automated container terminal, which will 1) Set
improve the loading and unloading efficiency and increase the quantity
of AGVs to transport. When simultaneously using many AGVs in hor- U set of import containers, (1, 2, 3……i ) ∊ U
izontal transportation, problems like traffic congestion and AGV con- L set of export containers, (1, 2, 3…… j ) ∊ L
flict may appear. To solve the congestion problem of horizontal V set of AGVs, (1, 2, 3……c ) ∈ V
B set of blocks in yards, (1, 2, 3……b) ∈ B
Ship
Q set of QCs, (1, 2, 3……k, l ) ∈ N
N set of all containers, U L
G set of nodes at a cross-road in horizontal transportation
K set of nodes at an uncross-road in horizontal transportation
N B Q G K
Nk set of the QC k handling the containers
AGV guide path S a dummy starting QC
F a dummy ending QC
Quay crane OS Q S , set including all QCs (i.e. all the containers to be loaded
AGV-mate and unloaded by QCs) plus the dummy starting QC
OF Q F , set including all QCs plus the dummy ending QC
Yard crane O Q S F , set including all real QCs, the dummy starting QC
and ending QC
A set the directed line segment between the nodes
Storage yard
2) Parameter

v The speed of AGVs

M A very large positive number
Fig. 3. The layout of the automated container terminal. T1

485
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

Fig. 4. The path planning of AGV.

The time of the portal trolley unloads the container to the Subject to:
transfer platform under the QC, also said the time of the
Fk = max i Nk {fik } k OF (2)
container in apron be discharged to the transfer platform
T2 The time of the first ARMG puts the container on the storage Sk = mini Nk {rik} k OS (3)
area
eik The time when the QC k uses the main trolley to handle the i th Constraint (2) means that we choose the latest time from a set of all
container from the ship to the transfer platform, also said the the containers as the completion time of the last container. The con-
time when the QC k puts the i th container from the transfer straint expressed on (3) ensures that we consider the earliest time from
platform to the ship a set of all containers as the starting time of the first container.
tc, i j The time of AGV c from node i to node j xikjl = 1 k OS , i U
gik The time when the second ARMG putting the i th container l OF j L (4)
from the storage area to the end-position after the QC k
handling the i th container x ikjl = 1 l OF , j L
di j The distance between node i and node j k OS i U (5)
ai j The connection matrix between node i and node j =1 k OS , c V
ikc
bi j The auxiliary road of the connection matrix between node i i Nk (6)
and node j
Tv, i j The time window function of node i and node j ikc =1 k OF , c V
i Nk (7)
3) Decision variables
ikb =1 k OS , b B
(8)
No 0–1 variables i Nk

ikb =1 i Nk , k OS
uik The time when the QC k starts to handle the i th container, b B (9)
i Nk
rik The time when the QC k uses the portal trolley to get the i th Constraint expressed on (4) ensures that the same AGV complete a
container from AGV or the i th container to be put on the AGV loading task using a QC only after finishing an unloading task. Con-
hik The time when the QC k unloads the i th container on AGV- straint (5) implies that after the QC finishes a loading task, the same
mate or loads the i th container from AGV-mate AGV can only complete an unloading task by the QC. Constraint (4) and
Constraint (5) confirm completion of the loading and unloading pro-
fik The time when the QC k finishes the i th container
cesses. Constraint (6) ensures that each loading and unloading task is
tin, i j The time when the AGV enters into the auxiliary road of node
handled only by one AGV. Constraint (7) implies that every AGV only
i and node j
handles one container at a time. Constraint (8) means that the ARMG
tout , i j The time when the AGV leaves away the auxiliary road of
transports a container to be stacked in the assigned block. Constraint
node i and node j (9) means that each block can only load and unload one container at a
0–1 variables time via the ARMG.

x ikjl The AGV, which just handling the i th container of the QC k is uik + eik + T1 rik i Uk, k O (10)
scheduled to handle the jth container of QC l , i U , j L or
rik + tc , i j ikc hik i Uk, k O, i O, j B
i L, j U c V (11)
ikc The AGV c to handle the i th container of QC k
ikb the i th container of QC k is located in block b
hik + T2 + gik ikb fik i Uk, k O
b B (12)
yi j If the AGV gets through the connected path of node i , j
z i j If the vehicle density of the auxiliary road of node i and node j Constraints (10)–(12) represent that the relationship between each
is more than 2 time that a ship starts and finishes a discharging task. Constraint (10)
represents the time that the AGV begins to transport the container from
3.3. Model 1: Scheduling model the QC based on the time that the portal trolley in the QC handles the
container. Constraint (11) represents the relationship between the time
The above assumptions and parameters are considered to build the that the AGV starts to transport the container to the AGV-mate. Con-
model and minimise the makespan of loading and unloading the ship straint (12) signifies the relationship between the time the container is
via bi-level programming. finished by ARMG and the time it is transported to the AGV-mate.

min T= max k O {Fk Sk } (1) hik + tc , i j ikc hjl + M(1 x ikjl ) i Uk, j Ll , k OS , l
c V
The objective of this model is to minimise the time difference be-
OF , i,j B (13)
tween finishing the last container and starting the first container, which
represents the loading and unloading of the makespan of the ship. Constraint (13) gives the relationship between the time that the same

486
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

AGV finishes an unloading task and starts the next loading task. 1, If the density of auxiliary vehicle
is less than 2,
ujl + gjl jlb + T2 hjl j Ll , l O
b B (14) zi j = 0, If the density of auxiliary vehicle
is 2.
hjl + tc , i j jlc r jl j Ll , l O, i B, j Q i,j G (26)
c V (15)
zi j bi j i,j G (27)
r jl + T1 + ejl f jl j Ll , l OF (16)
From constraints (23)–(27), we obtain the constraints for the
Constraints (14)–(16) express the relationship between the time the driving distance of AGVs. Among them, constraint (23) represents the
container is initially loaded from the block and completion of loading at distance between the node i to node j, which are equal. Constraint (24)
each time of shipment. Constraint (14) represents the time that the shows that the AGV will get through the route of node i and node j.
ARMG in the back of the block gets the container, which is less than the Constraint (25) gives the relationship between the 0–1 variable and the
time needed for AGV to obtain the container from the AGV-mate. connection matrix. Constraint (26) shows that the AGV can get through
Constraint (15) means that the starting time of AGV from the block does the auxiliary road of node i and node j . Constraint (27) provides the
not exceed the time the AGV arrives at the QC. Constraint (16) implies relationship between the 0–1 variable and the connection matrix of the
that the time the portal trolley in the QC obtains the container from the auxiliary road.
AGV is no more than the time that the loading task is finished.
TV , i j = (c, tin, i j , tout , i j ) i,j G (28)
r jl + tc, i j rik + M(1 x jlik ) i Uk, j Ll , k OS , l
c V
jlc tout , i j = tin, i j + di j / v i,j G (29)
OF , i,j Q (17)
(tin,i j )c < (tin,i j )c+1 i,j G (30)
Constraint (17) represents the time relation between completion of
a loading task by the AGV and start of the next unloading task. (tin,i j )c + di j /v (tin,i j )c+2 i,j G (31)
u (i + 1) k uik = eik + e(i + 1) k i Uk, k O (18) Constraints (28)–(31) are window of time constraints, the time
window constraints that are used to judge the vehicle density of the
u (i + 1) k uik = gik + g(i + 1) k i Lk , k O (19) auxiliary road and then determine if the AGV can get through the road.
Constraint (28), the time window, concerns the time that the AGV en-
uik 0, rik > 0, hik > 0, fik > 0, gik > 0, eik > 0 i Nk , k O ters and leaves the auxiliary road. Constraint (29) represents that the
(20) time relationship of the AGV entering and leaving the auxiliary road.
Constraint (30) shares the time relation of two consecutive AGVs when
tc, i j 0 i,j N ,c V (21) they enter the same auxiliary road. Constraint (31) provides the ne-
cessary conditions at the time the first AGV enters the auxiliary road,
Constraint (18) explains the time relation of the main trolley in the
which should not exceed the time that the third AGV enters the aux-
QC when it starts unloading two consecutive containers. Constraint (19)
iliary road.
represents the time relationship of ARMG in the back of the block when
it loads two consecutive containers. Constraint (20) represents the rik + (dki / v ) ikc = tin, i j i,j G, i Uk , k Q
range of time parameters. Constraint (21) expresses the range of time c V (32)
parameters of the AGVs’ transportation.
tout , i j + (d j b / v ) ikc hik i,j G, k Q, i Uk, b B
c V
3.4. Model 2: Path planning model of AGVs (33)
Constraint (32) explains that the time of the AGV starting to handle
To determine the time for AGV transportation in the path planning
the discharging container by the QC and AGV from the QC to auxiliary
model in this work, we obtained the minimum makespan when all the
road is the time of AGV entering into the auxiliary road. Constraint (33)
containers were finished. If the AGV transportation time is short, the
ensures that the time the container is discharged onto the AGV-mate
loading and unloading makespan are also short. According to Fig. 4, the
does not exceed the time the AGV leaves the auxiliary road.
model can be described by the following equation:
Constraint (32) explains that the time of the AGV starting to handle
the discharging container by the QC and AGV from the QC to auxiliary
tc, i j = min yi j (di j + M (1 z i j )) / v i, j N ,c V road is the time of AGV entering into the auxiliary road. Constraint (33)
(i , j ) A ensures that the time the container is discharged onto the AGV-mate
(22) does not exceed the time the AGV leaves the auxiliary road.
Constraint (22) represents the time of the AGV’s horizontal trans- hik + (dab/v ) ikc hjl + M (1 x ikjl ) i Uk , j Ll , a, b
portation with constant speed. We use the length of the AGV moving c V
path divided by the AGV’s speed to represent the time of horizontal B, k O (34)
transportation.
hjl + (dbi / v ) jlc = tin, i j i,j G, j Ll , l Q, b B
1, i = s, c V (35)
yi j yj i = 1, i = t , i,j N
tout , i j + (d j b / v ) r jl i,j G, j Ll , l Q, b B
j :(i , j ) A j :(i , j ) A 0, i s, t , (23) jlc
(36)
c V

1, the AGV runs this road, r jl + (dlk / v ) rik + M (1 xjlik ) i U, j Ll , l, k Q

yi j = i,j N jlc
0, otherwise. (24) c V

(37)
yi j ai j i,j N (25) Constraint (34) represents the relationship of the time for the AGV

487
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

to complete the discharging task and begin the next loading task.
Unloading 1 5 4 2 7 6 8 3
Constraint (35) expresses that the time the AGV starts to unload is equal
to the time AGV enters the auxiliary road. Constraint (36) ensures that
the time the AGV finishes the loading task is no more than the time it Loading 5 2 8 4 1 3 7 6 Chromosom
takes to leave the auxiliary road. Constraint (37) represents the time
relationship between the AGV finishing the loading task and starting AGV Number 1 2 3 4 1 2 3 4
the next unloading task.
The integrated scheduling problem of AGVs and QCs, which is based Fig. 6. Chromosome representation example for task.
on path planning is a nested model, and no accurate software exists to
solve the problem, especially for large-size loading and unloading
modes. Therefore, in the next section, we present the Bi-level Genetic 4.1. Chromosome coding and encoding
Algorithm as a solution for this problem.
1) The upper level coding

4. Algorithm First, for the upper level of the model, we coded the QCs to load and
unload containers and the task allocation of AGVs with integers. In
We combined a heuristic algorithm with Genetic Algorithm (Harik, order to better distinguish the loading and unloading of containers of
Lobo, & Goldberg, 2002; Baker and Ayechew, 2003; Pezzella, Morganti, QCs, we implemented multi-layer chromosomes. Because the QCs and
& Ciaschetti, 2008), and provided reasons for this approach as follows: blocks are matched in the assumed model, the loading and unloading of
(1) It can be very effective in global search, and its great ability of containers onto blocks is confirmed when the loading and unloading of
obtaining accurate solutions. (2) Its flexibility, expansibility can be containers of QCs is verified. At the time of AGV transportation and to
integrated can to the heuristic problem that was defined. (3) The pro- reduce the driving distance of empty AGVs, the AGV will load a con-
posed model is complex, which is a multiple objective function and tainer once another container has been unloaded. After one loading is
constraint, and the heuristic GA is suitable for solving this kind of complete, the AGV will transport the next unloading container.
problem (Chiang, 2005; Qu, Xing, & Alexander, 2013). In terms of Fig. 6 illustrates the encoding process, assuming there are 2 QCs,
heuristic GA in which the speed of convergence is fast and optimisation each having 4 loading containers and 4 unloading containers, and 4
has high efficiency. we used the Bi-level Genetic Algorithm, to put the AGVs to transport. Numbers 1–4 represent the containers belonging to
optimal solution of lower level as the decision variable of upper level, QC1, and numbers 5–8 represent the containers belonging to QC2. The
finally to achieve the optimal solution of the objective function (Yang, number of AGVs is from 1 to 4, where AGV 1 and AGV2 perform the
Zhang, He, & Yang, 2009; Wang, Wan, Wang, & Lv, 2008). unloading task, and AGV3 and AGV 4 perform the loading task initially.
In this work, we considered the integrated scheduling of QCs, AGVs, The specific task allocation of AGV is presented in Fig. 7.
and to construct the bi-level programming model. The upper level of
the model concerns the integrated scheduling, while the lower level 2) The lower level coding
pertains to the path planning of AGVs. We aim to decrease or eliminate
the phenomenon of AGV congestion in actual operations of automation The lower level of the model is for path planning of AGVs, for which
terminals, which reduces the work efficiency of the terminal. As a so- we encode the path. The order of tasks of AGVs can be determined by
lution, we added a rule to the algorithm to prevent congestion, the the upper chromosomes, which confirms the order of the starting and
Congestion Prevention Rule-based Bi-level Genetic Algorithm, which is ending point of the AGV performing the task. According to Fig. 4 in the
described in Fig. 5. last section, we know the node of AGVs to transport the containers.
Taking AGV 1 in Fig. 6 as an example, AGV 1 first unloads the container
of QC 1 and places it onto block 1. In other words, the starting node is 2
and the ending node is 8, as presented in Fig. 8 that shows the parti-
cular coding.
In this paper, chromosomes are decoded based on the priority
weight, which allows us to plan the path for the AGV to unload the
container from QC 1, we can plan the path of the AGV to unload the
container from the QC 1. The AGV starts at node 2, goes through node
3, then through node 4 or 7, depending on their priority weights. In this

Fig. 5. The implemented genetic algorithm flowchart. Fig. 7. The task allocation of AGV.

488
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

1 5 4 2 7 6 8 3 0 0 6 7 5 1 0 0 4 2 6 7 5 1 8 3 4 2 6 7 5 1 8 3 1 5 4 2 7 6 8 3

5 2 8 4 1 3 7 6 0 0 5 3 7 2 0 0 8 4 5 3 7 2 1 6
8 4 5 3 7 2 1 6 5 2 8 4 1 3 7 6
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

Parent 1 Child 1 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

Parent Child

Fig. 10. An illusion of swap mutation for chromosome.

8 3 6 7 5 1 2 4 0 0 4 2 7 6 0 0 8 3 4 2 7 6 5 1

6 1 5 3 7 2 8 4 0 0 8 4 1 3 0 0 6 5 8 4 1 3 7 2
4.3. Stopping criterion
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
In order to balance the searching computation time and approx-
Parent 2 Child 2
imate an optimal solution, two stopping criterions were used: (1) the
Fig. 8. Chromosome representation example for driving. maximum number of evolving generations allowed for GA, which is a
common criterion adopted by many GA-based optimisation problems.
example, because node 7 has priority over node 4, AGV goes to node 7 (2) The standard deviation of the fitness value of chromosomes (σL) in
and then finally to node 8, so the driving path of the AGV is 2-3-7-8. the current generation, which is below a small value (Baker & Ayechew,
2003). This parameter implies the diversity of the current generation in
terms of the values of objective functions. The decreasing σL represents
4.2. Crossover and mutation the decreasing diversity, where the algorithm is stopped if σL decreases
below a small arbitrary constant ξ.
1) The upper level
5. Numerical experiments
Because AGVs can perform any loading and unloading tasks of QCs,
no crossover for AGVs is considered, but crossover for the chromosome The proposed model and algorithm are validated for small and
of the loading and unloading tasks is considered. In order to improve large-size problems. For small-size problems, the Rolling Horizon
the efficiency of the crossover, Multi-point Crossover was used. The Procedure (RHP) (Vecchia, Marco, & Jean-Marie, 2012; Díaz-
algorithm randomly selects multiple crossing points on chromosomes, Madroñero, Mula, Jiménez, & Peidro, 2017) and Congestion Prevention
where every two crossing points matches at a location and then chro- Rule-based Bi-level Genetic Algorithm (CPR-BGA) were considered, and
mosomes are exchanged between two points. Although each number the objective functions values (OFV) and computation times were
can only appear once in the loading and unloading task, the exchange of compared. However, the RHP method cannot be used to solve large-size
chromosomes between two crossing points may lead to some code problems within a reasonable computing time, so the proposed CPR-
numbers to appear twice, so we may need to repair one of those BGA algorithm was used to solve instead, which reduces the computing
chromosomes. First, 0 is used to complete the no-crossing chromosomes time and allows access of the OFV values. This Bi-level Genetic Algo-
before crossover, so the separated chromosomes are added to the oc- rithm was implemented in MATLAB 2016a, and all the simulations
cupied positions of 0. If repeating numbers appear, then give it up and were performed on a computer with Intel Core TM i5 CPU 2.4 GHz and
continue, until all the occupied positions of 0 have been replaced. The 8 GB RAM under a Windows operatingsystem. In order to reduce the
details are presented in Fig. 9. deviation caused by the randomness of the Genetic Algorithm, every
Fig. 10 shows the process of swap mutation. The AGV needs to load problem was solved 20 times, where the average computation time and
a container (unload a container) after unloading a container (loading a OFV were used as the final results.
container), so the mutation of the chromosome only needs to mutate
the unloading or loading tasks. We adopted the Multi-points Mutation 5.1. Parameter settings
to randomly select the multiple points of mutation in a chromosome to
form a new chromosome. (1) The considered number of loading and unloading containers varied
from 1 to 2000, where 4–20 were considered for small-size pro-
2) The lower level blems and 30–2000 for large-size problems. We also considered the
number of QCs and blocks in the range 2–8, while the number of
A set of 34 nodes were considered, which has a relatively less considered AGVs varied from 8 to 20.
number of nodes in the AGV path, and the Two-point crossover was (2) The processing time of the main trolley that placed the container
adopted. At first, two crossing points were randomly generated, then onto the transfer platform followed uniform distribution U (20, 40)
two chromosomes were crossed to obtain chromosomes of the new s. The processing time of the portal trolley that placed the container
offspring. This method of mutation is considered two-point mutation, onto the AGV from the transfer platform was fixed at 20 s, and the
where two points are randomly generated in a priority layer of chro- processing time of the ARMG localized in the front of the yard,
mosomes, then the two priorities are regenerated to replace the muta- which obtained the container from the AGV-mate and then un-
tion point in the substring of chromosomes. loaded it in the storage area, was fixed at 25 s. The processing time
of ARMG localized in the back of the yard that moved the container
from the storage area to the assigned truck followed uniform dis-
tribution U (20, 30) s. All of these values correspond with a real-
Path Node 1 2 3 4 5 6 7 8 9 10 time situation.
(3) In this work, we obtained port operation values from the Xiamen
Ocean gate automated container terminal, which included an AGV
Priority 2 8 7 5 2 2 6 4 9 5
horizontal speed of 5 m/s, AGV transportation length of 240 m,
AGV transportation width of 100 m, and a distance between the
adjacent auxiliary roads of 30 m.
Fig. 9. An illustration of multi-point crossover for chromosome.

489
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

Table 1
Results of computational experiments in small sizes.
No. Containers AGVs-QCs-Block RHP CPR-BGA OFV gap rate (%)

Computation time (s) OFV (s) Computation time (s) OFV (s)

1 4 2-2-2 119.37 143 s 3.46 157 s 8.91

2 8 4-2-2 221.56 203 s 2.74 223 s 8.97
3 8 6-2-2 208.90 189 s 3.08 202 s 6.44
4 10 3-3-3 404.67 218 s 1.89 241 s 9.54
5 12 6-3-3 444.89 164 s 2.52 170 s 3.53
6 12 9-3-3 373.78 154 s 2.85 162 s 4.94
7 16 4-4-4 528.43 280 s 1.76 302 s 7.28
8 16 8-4-4 612.28 207 s 1.95 217 s 4.61
9 24 12-4-4 934.82 183 s 2.17 194 s 5.67
10 30 5-5-5 / / 1.83 403 s /
11 30 10-5-5 / / 2.64 325 s /
12 30 15-5-5 / / 2.98 302 s /

(4) GA parameters were set based on preliminary tests, including a Table 2

crossover rate (Pc) of 0.8, mutation rate (Pm) of 0.01, population Results of large-sized problems.
size (Ps) of 20, and maximum generation (Mg) of 500. No. Containers AGVs-QCs-block Computation time (s) OFV (s)

13 32 2-2-2 2.54 891

5.2. Results for small-sized problems 14 32 4-2-2 3.03 498
15 32 6-2-2 7.09 398
Twelve small-sized experiments were performed, where the number 16 64 4-2-2 9.03 969
of containers varied from 4 to 30. Table 1 shows that for the small-sized 17 120 4-2-2 28.25 1738
18 32 3-3-3 11.37 572
problems, the Bi-level Genetic Algorithm based on the rule of pre-
19 32 6-3-3 11.72 291
venting congestion obtained better performances compared to the RHP 20 32 9-3-3 12.48 221
algorithm in terms of speed, where computation time of the former 21 64 6-3-3 23.31 650
algorithm ranged from 1.89 s to 3.46 s and that of RHP ranged from 22 120 6-3-3 19.33 1253
119.37 s to 934.82 s. The RHP requires a rolling time axis for calcula- 23 64 4-4-4 4.10 949
24 64 8-4-4 5.18 561
tions, which increases the computation time. In addition, we observed
25 64 12-4-4 13.34 488
that the difference of OFV between the Bi-level Genetic Algorithm 26 240 8-4-4 55.19 1862
based on the rule of preventing congestion and the RHP was small, 27 120 5-5-5 9.15 1442
where the average gap rate of OFV was 6.65%. The results also confirm 28 120 10-5-5 11.99 810
29 240 10-5-5 44.02 1522
that RHP cannot solve the large-size problems within a reasonable time
30 240 6-6-6 27.05 2347
frame. However, results were not obtained for experiments with more 31 240 12-6-6 37.76 1283
than 24 containers. Table 1 also shows that OFV exhibits the same 32 320 12-6-6 96.67 1642
growth trend as the number of containers increased. 33 320 8-8-8 35.70 2377
34 320 16-8-8 49.03 1286
35 400 8-8-8 53.70 2923
5.3. Results for large-sized problems 36 400 16-8-8 114.56 1427
37 800 18-9-9 269.46 2679
38 1000 20-10-10 255.68 3064
From our experiments in Table 2, we conclude that using the con-
39 2000 20-10-10 833.26 5901
gestion prevention rule of Bi-level Genetic Algorithm, can obtain a
better OFV within a reasonable computation time. For the 39th case
with 2000 containers, the computation time was 833.26 s, which shows
that the CPR-BGA reduces the computation time. Under the same
conditions, increasing the number of containers also increases the ob-
jective function value (completion of working time). For example, for
the 21–22 case and 16–17 case, due to the multiple number of con-
tainers, the OFVs (finished working time) were similar. Under the
condition with an invariant number of containers, an increased number
of AGVs leads to a smaller OFV, namely the speed to finish the work is
faster, such as in cases 14, 15, 19, and 20. Experiment results show that
the terminal’s work efficiency can be improved by adjusting the amount
of AGVs, QCs, and ARMG. As shown in Table 2 for the cases with 32
containers, the OFV can be improved two- and threefold by increasing
the number of AGVs from 13 to 14 and 15 and from 18 to 19 and 20,
respectively.
It can also be observed that if will be duplicate the number of AGVs
or even triplicate the number of AGVs, the values of objective functions
become smaller, meaning enhanced efficiency. However, because the
difference between OFV values of two times the number of AGVs and
three times the number of AGVs is very little, we then comprehensively Fig. 11. Typical convergence of Bi-level Genetic Algorithm for case with 400
considered the cost factor in actual operations, where duplicating the containers, 16 AGVs, 8 QCs and 8 Blocks.
number of AGVs proved to be more suitable in the model. From the

490
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

second time period was when AGVs finished the last task and waited the
start the next task. The driving process and task allocation of AGV 6 was
designated as beginning to handle the task of block 1 and then per-
forming the discharge task of QC 1. From this sequence, we see that the
path of AGV 6 was: node 33 to node 34 to node 1 to node 2 to node 3 to
node 32 and finally to node 33. The time that the AGV completed the
first loading task was 72 s, while the second unloading task spent 140 s.
By comparing Figs. 12 and 13, it can be concluded that the in-
tegrated scheduling of QCs, AGVs and ARMG and the introduction of
the proposed preventive congestion rule for path planning resulted in a
higher efficiency than the case without this rule. Fig. 13 reveals that
only one AGV can be at a node at a time, or two AGVs cannot be at the
same node simultaneously, which prevents conflicts and optimises the
congested path. This satisfies all the timing constraints related to in-
tegrated scheduling and illustrates that the path planning method based
on the rule of preventing congestion is successful and effective.
Fig. 12. Detailed routing result for the example of 12 containers, 6 AGVs, and 6
blocks without considering integrated scheduling and congestion prevention. 6. Concluding remarks

above discussion, it proved that choosing the appropriate number of This paper has investigated the problem of integrated scheduling of
QCs and AGVs, which is calculated using the model, is crucial in QCs, AGVs and ARMGs for simultaneous loading and unloading op-
practice. erations, which has been formulated as a bi-level programming model.
Fig. 11 shows the convergence of the Bi-level Genetic Algorithm for In this model, AGV path planning is considered at the lower level while
the case of 400 containers, 16 AGVs, 8 QCs, and 8 blocks. It reveals that the integrated scheduling of QCs, AGVs, and ARMGs is captured at the
the convergence of the Bi-level Genetic algorithm is relatively stable, upper level with an aim to minimise the completion time of loading and
which fully ensures the effectiveness of our designed algorithm. It also unloading to improve the capacity of automated terminals.
suggests that the convergence speed is high, which means that the re- A mixed integer programming model was used to solve conflictive
sults were obtained in a short time. A faster working time is highly problems and congestion to increase the suitability of the loading and
important for the actual operation of container terminals because it unloading operation mode. However, only small-sized problems can be
relates to a higher efficiency of the working terminal. solved through the RHP algorithm, as computing time rapidly increases
By not considering the integrated scheduling of QCs and ARMG or as the number of containers gets large. Therefore, to solve large-sized
the preventing congestion rule in path planning of AGVs, the routing problems, or scheduling issues of many containers, we propose a bi-
nodes will be randomly assigned, and the choice for the optimal path is level General Algorithm based on the preventive congestion rule (CPR-
based on the Open Shortest Path First, which means the waiting time BGA) to simulate actual situations of automated terminals that handle
will be random and will decrease efficiency. Furthermore, by dis- numerous containers. The numerical results suggest that the CPR-BGA
regarding prevention of congestion problems, the AGVs will face con- algorithm can reduce the computing time, which is faster than using the
gestion. This issue is seen in Fig. 12, where the congestion problem RHP algorithm, and obtain better results within a reasonable time. The
appeared for AGV 2 and AGV 5 within 10–20 s in node 31 and within average gap between the RHP and CPR-BGA algorithms in terms of the
140–145 s in node 3. Further, it can be seen that the conflict problem objective function value for small-sized problems is very small but
occurred within 85 s when AGV 2 and AGV 3 were in node 31. differs greatly for large-sized problems.
Fig. 13 displays case 5 from Table 1 for completing the process of One key intellectual contribution of the paper is, from an academic
loading and unloading, which shows the AGV path, task allocation, and perspective, we analysed the integrated scheduling of AGVs, QCs, and
time of operation, there are a total of 6 unloading containers, 6 loading YCs to optimise path planning in automated terminals by simulta-
containers, 3 blocks, 3 QCs to perform the loading and unloading, and 6 neously implementing the congestion prevention rule and the GA al-
AGVs for the transport. During the first long period 0–50 s, the AGVs gorithm. Second, from a practical perspective, we consider the reality of
waited in a designated area before handling the first container. The loading and unloading in automated container terminals to achieve the
optimised path and overcome the traffic bottleneck that leads to large-
scale congestion in a long queue of AGVs. It is suggested that the ex-
perimental findings are beneficial for terminal managers who oversee
daily operations.
However, as the number of large container ships increase, more
effective scheduling strategies and decision-making algorithms will be
needed for real-time scheduling and dynamic path planning. To further
develop the proposed integrated scheduling model of QCs, AGVs, and
YCs with the ability to assign containers to specific locations, more
accurate and heuristic algorithms should be investigated in future stu-
dies. In addition, we can compare differemt algorithms with BGAs to
see whether better results can be obtained, due to the complexity of the
problem itself, and the GPU parallel computing can contribute to the
algorithm to simplify the problem and reduce the computing time.

Acknowledgements

This work is supported by the National Natural Science Foundation of

Fig. 13. Detailed routing result for the example of 12 containers, 6 AGVs, and 6 China (No. 61540045), Shanghai Science and Technology Commission (No.
blocks considering integrated scheduling and congestion prevention. 18295801100; 2018IB022; 16040501500; 17595810300).

491
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

Appendix A. Supplementary material procedure for dynamic routing of autonomous decentralized AGV systems. Robotics
and Computer-Integrated Manufacturing, 22(2), 154–165.
Nishi, T., Hiranaka, Y., & Grossmann, I. E. (2011). A bilevel decomposition algorithm for
Supplementary data associated with this article can be found, in the simultaneous production scheduling and conflict-free routing for automated guided
online version, at https://doi.org/10.1016/j.cie.2018.10.007. vehicles. Computers & Operations Research, 38(5), 876–888.
Pap, E., Bojanić, V., Georgijević, M., & Bojanić, G. (2011). Application of pseudo-analysis
in the synchronization of container terminal equipment operation. Acta Polytechnica
References Hungarica, 8(6), 5–21.
Park, T., Choe, R., Ok, S. M., & Ryu, K. R. (2010). Real-time scheduling for twin RMGs in
Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing an automated container yard. OR Spectrum, 32(3), 593–615.
problem. Computers & Operations Research, 30(5), 787–800. Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the flexible job-
Boysen, N., Briskorn, D., & Tschöke, M. (2013). Truck scheduling in cross-docking shop scheduling problem. Computers & Operations Research Systems, 35(10),
terminals with fixed outbound departures. OR Spectrum, 35(2), 479–504. 3202–3212.
Boysen, N. (2010). Truck scheduling at zero-inventory cross docking terminals. Computers Qu, H., Xing, K., & Alexander, T. (2013). An improved genetic algorithm with co-evo-
& Operations Research, 37(1), 32–41. lutionary strategy for global path planning of multiple mobile robots.
Chen, L., Bostel, N., Dejax, P., Cai, J., & Xi, L. (2007). A tabu search algorithm for the Neurocomputing, 120(10), 509–517.
integrated scheduling problem of container handling systems in a maritime terminal. Roy, D., & Koster, R. D. (2015). Stochastic modeling of unloading and loading operations
European Journal of Operational Research, 181(1), 40–58. at a container terminal using automated lifting vehicles. Social Science Electronic
Chiang, C. L. (2005). Improved genetic algorithm for power economic dispatch of units Publishing, 5, 1–47.
with valve-point effects and multiple fuels. IEEE Transactions on Power Systems, 20(4), Roy, D., Gupta, A., & Koster, R. B. M. D. (2016). A non-linear traffic flow-based queuing
1690–1699. model to estimate container terminal throughput with AGVs. International Journal of
Díaz-Madroñero, M., Mula, J., Jiménez, M., & Peidro, D. (2017). A rolling horizon ap- Production Research, 54(2), 1–21.
proach for material requirement planning under fuzzy lead times. International Sidoti, D., Avvari, G. V., Mishra, M., Zhang, L., Nadella, B. K., Peak, J. E., et al. (2017). A
Journal of Production Research, 55(8), 2197–2211. multiobjective path-planning algorithm with time windows for asset routing in a
Dhingra, V., Roy, D., & Koster, R. B. M. D. (2015). A cooperative quay crane-based sto- dynamic weather-impacted environment. IEEE Transactions on Systems Man &
chastic model to estimate vessel handling time. Flexible Services & Manufacturing Cybernetics Systems, 99, 1–16.
Journal, 1–28. Skinner, B., Yuan, S., Huang, S., Liu, D., Cai, B., Dissanayake, G., et al. (2013).
Gharehgozli, A. H., Roy, D., & Koster, R. D. (2016). Sea container terminals: New tech- Optimization for job scheduling at automated container terminals using genetic al-
nologies and OR models. Maritime Economics & Logistics, 18(2), 103–140. gorithm. Computers & Industrial Engineering, 64(1), 511–523.
Grunow, M., Günther, H. O., & Lehmann, M. (2006). Strategies for dispatching AGVs at Su, L. L., Samuel, M., & Chong, Y. S. (2000). Self-organizing neural network approach for
automated seaport container terminals. OR Spectrum, 28(4), 587–610. the single AGV routing problem. European Journal of Operational Research, 121(1),
Gupta, A., Roy, D., Koster, R. D., & Parhi, S. (2017). Optimal stack layout in a sea con- 124–137.
tainer terminal with automated lifting vehicles. International Journal of Production Vecchia, E. D., Marco, S. D., & Jean-Marie, A. (2012). Illustrated review of convergence
Research, 55(13), 3747–3765. conditions of the value iteration algorithm and the rolling horizon procedure for
Harik, G. R., Lobo, F. G., & Goldberg, D. E. (2002). The compact genetic algorithm. IEEE average-cost MDPs. Annals of Operations Research, 199(1), 193–214.
Transactions on Evolutionary Computation, 3(4), 287–297. Wu, Y., Luo, J., Zhang, D., & Dong, M. (2013). An integrated programming model for
Hu, Z. H., Sheu, J. B., & Luo, J. X. (2016). Sequencing twin automated stacking cranes in a storage management and vehicle scheduling at container terminals. Research in
block at automated container terminal. Transportation Research Part C: Emerging Transportation Economics, 42(1), 13–27.
Technologies, 69, 208–227. Wen, C., Ekşioğlu, S. D., Greenwood, A., & Zhang, S. (2010). Crane scheduling in a
Hu, H., Lee, B. K., Huang, Y., Lee, L. H., & Chew, E. P. (2013). Performance analysis on shipbuilding environment. International Journal of Production Economics, 124(1),
transfer platforms in frame bridge based automated container terminals. 40–50.
Mathematical Problems in Engineering, 2013(3), 831–842. Wang, G., Wan, Z., Wang, X., & Lv, Y. (2008). Genetic algorithm based on simplex method
Lau, H. Y. K., & Zhao, Y. (2008). Integrated scheduling of handling equipment at auto- for solving linear-quadratic bilevel programming problem. Computers & Mathematics
mated container terminals. Annals of Operations Research, 112(1), 665–682. with Applications, 56(10), 2550–3255.
Le, H. M., Yassine, A., & Riadh, M. (2012). Scheduling of lifting vehicle and quay crane in Yang, X., Mi, W., Li, X., An, G., Zhao, N., & Mi, C. (2015). A simulation study on the
automated port container terminals. International Journal of Intelligent Information & design of a novel automated container terminal. IEEE Transactions on Intelligent
Database Systems, 6(6), 516–531. Transportation Systems, 16(5), 1–11.
Li, W., Goh, M., Wu, Y., Petering, M. E. H., Souza, R. D., & Wu, Y. C. (2016). A continuous- Yang, J., Zhang, M., He, B., & Yang, C. (2009). Bi-level programming model and hybrid
time model for multiple yard crane scheduling with last-minute job arrivals. genetic algorithm for flow interception problem with customer choice. Computers &
International Journal of Production Economics, 136(2), 332–343. Mathematics with Applications, 57(11–12), 1985–1994.
Liang, L., Lu, Z. Q., & Zhou, B. H. (2009). A heuristic algorithm for integrated scheduling Zhao, J., & Tang, L. (2011). The simultaneous quay crane and truck scheduling problem
problem of container handling system. International Conference on Computers & in container terminals. In International conference on intelligent computation tech-
Industrial Engineering, IEEE Xplore, 40–45. nology and automation, IEEE, pp. 279–282.
Liang, Y., Lin, L., Gen, M., & Chien, C. F. (2012). A hybrid evolutionary algorithm for FMS Zhang, J., Ioannou, P. A., & Chassiakos, A. (2006). Automated container transport system
optimization with AGV dispatching. Computers & Industrial Engineering, 296, 1–14. between inland port and terminals. Acm Transactions on Modeling & Computer
Li, Y., Caö, H., & Tan, Y. (2011). Novel method of identifying time series based on net- Simulation, 16(2), 95–118.
work graphs. Complexity, 17(1), 13–34. Zhang, H., & Kim, K. H. (2009). Maximizing the number of dual-cycle operations of quay
Liu, C. I., Jula, H., & Ioannou, P. A. (2002). Design, simulation, and evaluation of auto- cranes in container terminals. Computers & Industrial Engineering, 56(3), 979–992.
mated container terminals. Transactions on Intelligent Transportation Systems, 3(1), Zhang, R., Jin, Z., Ma, Y., & Luan, W. (2015). Optimization for two-stage double-cycle
12–26. operations in container terminals. Computers & Industrial Engineering, 83(C), 316–326.
Luo, J., & Wu, Y. (2015). Modelling of dual-cycle strategy for container storage and ve- Zhang, X., Zeng, Q., & Yang, Z. (2016). Modeling the mixed storage strategy for quay
hicle scheduling problems at automated container terminals. Transportation Research crane double cycling in container terminals. Transportation Research Part E Logistics &
Part E Logistics & Transportation Review, 79, 49–64. Transportation Review, 94, 171–187.
Martín-Soberón, A. M., Monfort, A., Sapiña, R., Monterde, N., & Calduch, D. (2014).
Automation in port container terminals. Procedia - Social and Behavioral Sciences, 160, Yongsheng Yang Pro. Yongsheng Yang, received the Ph.D. degree in systems engineering
195–204. from Nanjing University of Aeronautics & Astronautics, Nanjing, China, in 1998. He is
Meersmans, P. J. M., & Wagelmans, A. P. M. (2006). Effective algorithms for integrated currently a professor in logistics and engineering College, Shanghai Maritime University,
scheduling of handling equipment at automated container terminals. Social Science China, the director of Science and Technology Department. Pro. Yang is the candidate of
Electronic Publishing, 36, 1–26. discipline (Mechanical Design and Theory) leader, the associate editor of Computer-aides
Meisel, F., & Bierwirth, C. (2009). Heuristics for the integration of crane productivity in Engineering, the senior member of China Mechanical Engineering Society and the member
the berth allocation problem. Transportation Research Part E: Logistics and of IEEE.
Transportation Review, 45(1), 196–209.
Meisel, F., & Bierwirth, C. (2013). A framework for integrated berth allocation and crane
Meisu Zhong Meisu Zhong, was born in 1991, she received the master’s degree with the
operations planning in seaport container terminals. Transportation Science, 47(2),
College of Economics & Management from the Shanghai Maritime University, Shanghai,
131–147.
China, where she is currently pursuing the Ph.D. degree with the Institute of logistics
Mishra, A., & Tripathi, A. K. (2015). Complexity of a problem of energy efficient real-time
Science & engineering, is major in the engineering and management of shipping. Her
task scheduling on a multicore processor. Complexity, 21(1), 259–267.
current research interests include the scheduling and controlling of automated container
Mishra, N., Roy, D., & Ommeren, J. K. V. (2017). A stochastic model for interterminal
terminal and the control system of the AGV.
container transportation. Transportation Science, 51(1), 67–87.
Miyamoto, T., & Inoue, K. (2016). Local and random searches for dispatch and conflict-
free routing problem of capacitated AGV systems. Computers & Industrial Engineering, Yasser Dessouky Prof. Yasser Dessouky served on the faculty at Miami University, Ohio,
9, 1–9. prior to joining the faculty at San José State University in 1997. He earned his doctorate
Nguyen, V. D., & Kim, K. H. (2009). A dispatching method for automated lifting vehicles and master’s degrees in industrial and management systems engineering from Arizona
in automated port container terminals. Computers & Industrial Engineering, 56(3), State University and a bachelor’s in industrial engineering from the University of
1002–1020. Wisconsin-Madison. He also serves as an associate editor for an international journal,
Nishi, T., Ando, M., & Konishi, M. (2006). Experimental studies on a local rescheduling Computers and Industrial Engineering, and as an editorial board member on several other

492
Y. Yang et al. Computers & Industrial Engineering 126 (2018) 482–493

prestigious international journals. He has extensive research and consulting experience in a principal researcher of Instituto de Telecomunicações and an assistant professor of EST/
developing models to analyze improvements in the design and efficiency of systems and IPS Setubal and ISCTE-IUL Lisboa in 2001 and 2012, respectively. He is the founder and
work flow patterns. He has gained recognition in the areas of simulation modeling and leader of the Pervasive Sensing and Computing research group. His fields of interest are
analysis, and quality management, including lean six sigma and integrated supply chain smart sensors, and pervasive sensing and computing. He is author and co-author of 9
management. His work in supply chain management includes developing models to op- patents, 7 books, 14 book chapters, 61 peer reviewed papers in international journals, and
timize inventories in the supply network. more than 200 papers in proceedings of international conferences. He is an ACM pro-
fessional member, Chair of IEEE MeMeA 2014, Technical Chair of ICST 2014, and an
Octavian Postolache Instituto de Telecomunicacões/ISCTE-IUL, Lisboa. He graduated in Associate Editor of IEEE Sensors Journal. He received the IEEE I&M outstanding reviewer
the electrical engineering at the Gh. Asachi Technical University of lasi, Romania, in and IEEE Best Associate Editor Awards.
1992, and received his Ph.D. degree in 1999 from the same university. In 2000 he became

493