# Optimization Approach for Yard Crane Scheduling Problem with Uncertain Parameters in Container Terminals

Authors: Wenqian Liu; Xiaoning Zhu; Li Wang; Baicheng Yan; Xuewei Zhang
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

As the core operational issue in container terminals, yard crane scheduling problem directly affects the overall operation efficiency of port connecting highway or railway transportation and sea transportation. In practice, the scheduling of yard cranes is subject to many uncertain factors, so the scheme may be inapplicable and needs to be adjusted. From the perspective of proactive strategy, considering fluctuations in arrival time of external trucks as well as varied handling volume of yard cranes, a stochastic programming model is established in this paper to obtain a fixed scheme with the minimum expected value of yard crane makespan and total task waiting time over all the scenarios. The scheme does not require rescheduling when facing different situations. Subsequently, two algorithms based on certain rules are proposed to obtain the yard crane operation scheme in the deterministic environment, which are taken as the basic solution in the uncertain conditions, and then a tailored genetic algorithm is adopted to find the optimal solution with good adaptability to the uncertain scenarios. Finally, we use small-scale examples to compare the performance of algorithms in the deterministic and uncertain environment and then analyze the relationship between different yard crane configurations and the number of tasks. Large-scale experiments are performed to study the operation efficiency of the storage yard with different handling volumes assigned to each yard crane.


---

## Body

## 1. Introduction

Accompanied with the development of the world economy and the increasing degree of global integration, container transportation has become an important logistics mode in international trade. As an important node connecting sea and land in the process of container transportation, the ports’ throughputs have increased rapidly year by year. The configuration of the container terminals mainly consists of the intelligent gate, the container yard, and the quayside, as shown in Figure1, where the container yard is the operation area to store the imported containers and exported containers. Yard crane is one of the key equipment and important resources in container yard, the operation efficiency of which may directly affect the scale and operation process of the whole port [1].Figure 1
Configuration of the container terminal.Yard crane scheduling scheme plays a crucial part in the operation process of containers in the port, including the handling sequences of tasks, the access time of each task, and the number of tasks assigned to yard cranes. Each task corresponds to a specific container, which is transported horizontally by trucks to or from one side of container blocks. In reality, the actual arrival time of trucks loading exported containers or retrieving imported containers can be earlier or later than their appointed time. Any changes may have an impact on the suitability of the existing plan, which will lead to an increase of extra cost due to scheme adjustment. In this paper, we adopt two rule-based algorithms to generate an initial scheduling scheme with determined environment, then we deal with the uncertain situations by many scenarios, and a proactive scheduling plan is produced with minimum expected value of the sum of yard crane makespan and total task waiting time over all the scenarios through a tailored genetic algorithm.The rest of this paper is organized as follows. After summarizing the related literatures in Section2, the detailed description of the problem and the mathematical model with fundamental constraints are presented in Section 3. Subsequently, Section 4 puts forward the solution methods. Section 5 includes a series of experiments and the results are discussed, following with concluding remarks and future research topics in Section 6.


## 2. Literature Review

With the increasing importance of container transportation, scholars from various countries have been exploring effective methods to promote the container operation efficiency in the ports.


### 2.1. In the Deterministic Environment

For the scheduling problem of a single yard crane, Kim et al. [2] are the first scholars to put forward the integer programming model to address the path problem and loading sequence of export containers. Narasimhan and Palekar [3] referred to the problem of minimizing the time needed for containers to be carried from the yard to the ship as the transtainer routing problem, proving that this problem is NP-complete. Ng and Mak [4] added storage containers based on the research in [2] to deliberate the scheduling problem of single yard crane to process loading/unloading tasks with different job ready times.For the scheduling problem of multiple yard cranes, Zhang et al. [5] considered the problem of deployment of multiple yard cranes in a container yard with the aim of finding out the number and route of yard cranes moving between different blocks. However, the handling sequence of containers is not considered. Li et al. [6] extended the previous problem by solving scheduling problems for multiple yard cranes considering both storage and retrieval jobs, and some constraints in realistic operations, such as the interference and safe distance between cranes, are also put forward. Furthermore, Chang et al. [7] applied genetic algorithm to the similar scheduling problem of yard crane based on the idea of rolling horizon. Guo et al. [8] are also interested in yard crane dynamic scheduling problem. On the basis of predicting the arrival time of the vehicles, a YC management scheme with the shortest average waiting time of vehicles is proposed. Moreover, in the work of He et al. [9] and Sha et al. [10], the optimization of energy consumption is further added to the traditional yard crane scheduling problem. Wu et al. [11] addressed the yard crane scheduling problem based on continuous time. A clustering redistribution algorithm is proposed and its robustness and stability are verified by simulation. Galle et al. [12] not only considered the yard crane scheduling problem but also studied the container relocation problem. They simultaneously solved the handling sequence of containers and the location decisions of storage and turnover containers. Zhang et al. [13] studied the similar problem of gantry cranes scheduling for containers transshipped from highway to railway based on improved TSP.


### 2.2. In the Uncertain Environment

The research on the uncertainty of port operations started late, and most references focus on the quayside [14–20] and resource allocation problem [21–23], whereas the uncertain yard crane scheduling is involved less. In the work of [24], the cycle operation of a yard crane is divided into different basic movements, of which the expectation and variance formulas are analyzed and deduced. Lu and Le [25] came up with a comprehensive scheduling optimization method for equipment in container terminals under uncertainty based on particle swarm optimization, aiming to minimize the operation time of yard cranes while coordinating quay cranes and truck operations. Considering uncertain friction, Yang et al. [26] developed a new output feedback control method for tower cranes to accomplish rapid jib and trolley positioning and payload sway suppression. Yang et al. [27] addressed the control problem for a class of multi-input-multi-output underactuated systems subject to plant uncertainties and actuator dead zones. The proposed method is verified by two kinds of cranes. He et al. [28] handled uncertainty based on uncertain scenario and employed VRP to formulate the yard crane scheduling problem, aiming to reduce the extra loss of adjusting schedule. Zhou et al. [1] addressed an approach of rolling-horizon strategy to deal with the interference factors on the retrieval operation of external trucks. They mainly optimized the task delay penalty cost and yard crane movement cost. Zheng et al. [29] studied the scheduling problem of a single yard crane with fixed operation area in a single block and formulated a two-stage stochastic programming model considering the uncertain release time of retrieval containers. A processing schedule is produced over all the uncertain scenarios. Lu [30] put forward a joint scheduling optimization model of automated guided vehicle and auto yard crane and handled uncertain variables with given distributions. The literatures closely related to the problem studied in this paper are summarized in Table 1.Table 1
Comparison of research on similar yard crane scheduling problem.
LiteratureSubjectOutcomeUncertaintiesApproachArrival time of trucksSpeed of trucksHandling volume of yard cranesSpeed of yard cranesHe et al. [28]Multiple yard cranesReadjusted scheme√√Three-stage GA-based algorithmZhou et al. [1]Multiple yard cranesReadjusted scheme√Genetic algorithmZheng et al. [29]Single yard craneFixed scheme√Simulated annealing algorithm, genetic algorithmLu [30]Automated yard cranesFixed scheme√√Particle swarm algorithmThis paperMultiple yard cranesFixed scheme√√Rule-based heuristic algorithm, tailored GAAs stated above, it can be summarized that reactive strategy [1, 28] and proactive strategy [29, 30] are the two main methods on yard crane scheduling problem to deal with uncertain factors. This paper is oriented around the scheduling of multiple yard cranes under multiple uncertainties. Different from other studies, we produce a fix scheme adaptable to most uncertain cases for yard crane scheduling problem under uncertainties for the purpose of avoiding additional adjustment costs caused by rescheduling. The main contributions of this work are as follows: (1) a stochastic expected value model with uncertain parameters is presented for minimizing the expected value of yard crane makespan and total task waiting time, (2) two rule-based heuristic algorithms and a tailored genetic algorithm are developed to obtain the baseline schedule based on proactive strategy, and (3) the influence of different yard crane configurations and varied handling volume is measured.


## 2.1. In the Deterministic Environment

For the scheduling problem of a single yard crane, Kim et al. [2] are the first scholars to put forward the integer programming model to address the path problem and loading sequence of export containers. Narasimhan and Palekar [3] referred to the problem of minimizing the time needed for containers to be carried from the yard to the ship as the transtainer routing problem, proving that this problem is NP-complete. Ng and Mak [4] added storage containers based on the research in [2] to deliberate the scheduling problem of single yard crane to process loading/unloading tasks with different job ready times.For the scheduling problem of multiple yard cranes, Zhang et al. [5] considered the problem of deployment of multiple yard cranes in a container yard with the aim of finding out the number and route of yard cranes moving between different blocks. However, the handling sequence of containers is not considered. Li et al. [6] extended the previous problem by solving scheduling problems for multiple yard cranes considering both storage and retrieval jobs, and some constraints in realistic operations, such as the interference and safe distance between cranes, are also put forward. Furthermore, Chang et al. [7] applied genetic algorithm to the similar scheduling problem of yard crane based on the idea of rolling horizon. Guo et al. [8] are also interested in yard crane dynamic scheduling problem. On the basis of predicting the arrival time of the vehicles, a YC management scheme with the shortest average waiting time of vehicles is proposed. Moreover, in the work of He et al. [9] and Sha et al. [10], the optimization of energy consumption is further added to the traditional yard crane scheduling problem. Wu et al. [11] addressed the yard crane scheduling problem based on continuous time. A clustering redistribution algorithm is proposed and its robustness and stability are verified by simulation. Galle et al. [12] not only considered the yard crane scheduling problem but also studied the container relocation problem. They simultaneously solved the handling sequence of containers and the location decisions of storage and turnover containers. Zhang et al. [13] studied the similar problem of gantry cranes scheduling for containers transshipped from highway to railway based on improved TSP.


## 2.2. In the Uncertain Environment

The research on the uncertainty of port operations started late, and most references focus on the quayside [14–20] and resource allocation problem [21–23], whereas the uncertain yard crane scheduling is involved less. In the work of [24], the cycle operation of a yard crane is divided into different basic movements, of which the expectation and variance formulas are analyzed and deduced. Lu and Le [25] came up with a comprehensive scheduling optimization method for equipment in container terminals under uncertainty based on particle swarm optimization, aiming to minimize the operation time of yard cranes while coordinating quay cranes and truck operations. Considering uncertain friction, Yang et al. [26] developed a new output feedback control method for tower cranes to accomplish rapid jib and trolley positioning and payload sway suppression. Yang et al. [27] addressed the control problem for a class of multi-input-multi-output underactuated systems subject to plant uncertainties and actuator dead zones. The proposed method is verified by two kinds of cranes. He et al. [28] handled uncertainty based on uncertain scenario and employed VRP to formulate the yard crane scheduling problem, aiming to reduce the extra loss of adjusting schedule. Zhou et al. [1] addressed an approach of rolling-horizon strategy to deal with the interference factors on the retrieval operation of external trucks. They mainly optimized the task delay penalty cost and yard crane movement cost. Zheng et al. [29] studied the scheduling problem of a single yard crane with fixed operation area in a single block and formulated a two-stage stochastic programming model considering the uncertain release time of retrieval containers. A processing schedule is produced over all the uncertain scenarios. Lu [30] put forward a joint scheduling optimization model of automated guided vehicle and auto yard crane and handled uncertain variables with given distributions. The literatures closely related to the problem studied in this paper are summarized in Table 1.Table 1
Comparison of research on similar yard crane scheduling problem.
LiteratureSubjectOutcomeUncertaintiesApproachArrival time of trucksSpeed of trucksHandling volume of yard cranesSpeed of yard cranesHe et al. [28]Multiple yard cranesReadjusted scheme√√Three-stage GA-based algorithmZhou et al. [1]Multiple yard cranesReadjusted scheme√Genetic algorithmZheng et al. [29]Single yard craneFixed scheme√Simulated annealing algorithm, genetic algorithmLu [30]Automated yard cranesFixed scheme√√Particle swarm algorithmThis paperMultiple yard cranesFixed scheme√√Rule-based heuristic algorithm, tailored GAAs stated above, it can be summarized that reactive strategy [1, 28] and proactive strategy [29, 30] are the two main methods on yard crane scheduling problem to deal with uncertain factors. This paper is oriented around the scheduling of multiple yard cranes under multiple uncertainties. Different from other studies, we produce a fix scheme adaptable to most uncertain cases for yard crane scheduling problem under uncertainties for the purpose of avoiding additional adjustment costs caused by rescheduling. The main contributions of this work are as follows: (1) a stochastic expected value model with uncertain parameters is presented for minimizing the expected value of yard crane makespan and total task waiting time, (2) two rule-based heuristic algorithms and a tailored genetic algorithm are developed to obtain the baseline schedule based on proactive strategy, and (3) the influence of different yard crane configurations and varied handling volume is measured.


## 3. Problem Description and Mathematical Model

### 3.1. Problem Description

The growing volume of containers has brought pressure to the management of storage yard in port, which involves different resources such as yard trucks, yard cranes, and container blocks [31]. An efficient control method of cranes plays an important role in various fields of modern industry [32]. In many studies of yard crane scheduling problem, each yard crane is responsible for the designated container blocks, in which case the problem can be simplified, but the flexibility of yard cranes and some schemes with better results may be missed. In this paper, the yard cranes would not be restricted in a fixed container block, but the same row. The YC scheduling scheme may significantly impact the operation efficiency of container terminal, but in reality, the scheme may not always be appropriate due to uncertain factors. For example, Figure 2 shows a small example of yard crane scheduling, where the arriving sequence of tasks is assumed to be 1-3-2-4-8-6-7-9-5. The task sequence of YC1 is 4-6-9, the task sequence of YC2 is 2-8-5, and the task sequence of YC3 is 1-3-7. If task 2 arrives late, there will be a cross when YC1 accesses task 9 after handling task 6 while YC2 is to travel from task 2 to task 8. Besides, task 8 and task 9 may interfere with each other and one of them is forced to wait until the other finishes because the yard cranes could not be adjacent to each other for reasons of safety, in which case the subsequent tasks would be delayed. However, the schemes YC1: 2-4-6, YC2: 3-8-9, and YC3: 1-7-5 can deal with this situation better. Thus, it is necessary to develop a model to consider the interference of uncertain scenarios. In each scenario, the actual arrival times of tasks fluctuate randomly around the planned arrival time, and the handling volume of tasks assigned to each yard crane is also uncertain. Thus, a proactive scheduling scheme is produced with minimum expected value of two objectives over all the scenarios.Figure 2
A sample of yard crane crossing and interference.Generally, the optimization goal of yard crane scheduling problem is to minimize the finish time of all tasks. However, the equipment scheduling schemes with close makespan may have a large gap in the corresponding total waiting time of the tasks. We randomly generate 1000 sets of feasible operation sequences of 30 tasks processed by 3 yard cranes and calculate the makespan of yard cranes and the total waiting time of tasks corresponding to each sequence. The results are shown in Figure3, in which the sequences are sorted according to the value of makespan.Figure 3
The experiment results of random generated sequences.It can be seen that the makespan of yard cranes and the total waiting time of tasks have the same change trend on the whole. However, for the similar results of makespan, there are many schemes in which the total waiting time of tasks varies greatly. The long waiting time of the task will affect the delivery of the container and the turnaround time of trucks. Therefore, the minimum mathematical expectation of the sum of yard crane makespan and task waiting time over all the scenarios is taken as the objective function in this paper.


### 3.2. Assumptions

To ensure that the model can reasonably describe the problem above, several assumptions are given.Assumption 1.
All the containers are located on the top of the stacks and accessible.Assumption 2.
The traveling speed of each yard crane is the same, without considering the additional time consumption caused by equipment starting and turning.Assumption 3.
The locations of containers are known beforehand.


### 3.3. Parameters and Variables

The above problem can be described as a stochastic programming model using the following parameters and variables.Parameters and sets:N: The set of all tasks to be handledV: The subsets of N, V⊂N, V≥2Y: The set of all yard cranesn: The total number of all tasksl,l′,l″: The index of tasks, l,l′,l″∈N,l≠l′≠l″k: The index of yard cranes, k∈YLlk: The position of yard crane k when completing the task lM: A large integer valueφ: A weight coefficienth: The safe distance between yard craneswtlk: The operating time of yard crane k to handle the task lTll′: The traveling time from task l to task l′Ω: The set of uncertain scenariosθ: The index of uncertain scenarios, θ∈ΩTarlθ: The actual arriving time of task l in scenario θ.Decision variables:wk: The handling volume of yard crane kmtlk: The traveling time of yard crane k to handle the task lTstlθ: The operating start time of task l in scenario θTendlθ: The operating end time of task l in scenario θTstkθ: The time when yard crane k start working in scenario θTendkθ: The time when yard crane k finishes working in scenario θTΔlθ: The waiting time of task l in scenario θp0lk: If task l is the first task of yard crane k, p0lk=1, where 0 is the initial position of yard crane k; otherwise, p0lk=0ql0k: If task l is the last task of yard crane k, ql0k=1, where 0 is the initial position of yard crane k; otherwise, ql0k=0yll′k: If task l′ is consecutively handled by yard crane k after task l,yll′k=1; otherwise, yll′k=0xlk: If task l is handled by yard crane k, xlk=1; otherwise, xlk=0zll′: If task l has been finished before the start time of task l′, zll′=1; otherwise, zll′=0.Each yard crane has three statuses during its operation: processing a task, traveling to next task, and staying idle. Each task also may be in one of two statuses: waiting to be processed and being processed. In order to clearly and intuitively represent the working state of the yard cranes and the relationship between relevant time variables, a schematic diagram of the operation time axis of yard cranes in scenarioθ is shown in Figure 4. The total working time of yard cranes is determined by tasks assigned them, represented by white rectangle.Figure 4
The time axis of yard cranes in scenarioθ.


### 3.4. Mathematical Model

To achieve the rationality and the economy of yard crane scheduling scheme, some constraints are required. The yard crane scheduling problem under uncertainty is formulated as follows:(1)Minf=Eφmaxk∈YTendkθ+1−φ∑l∈NTΔlθ,(2)S.T.∑k∈Ywk=n,(3)∑l∈Nxlk=wk,∀k∈Y,(4)Tendkθ≥Tstkθ+∑l∈Nwtlk+mtlk⋅xlk,∀k∈Y,(5)Tendlθ=Tstlθ+∑k∈Ywtlk⋅xlk,∀l∈N,(6)Tstlθ≥Tarlθ,∀l∈N,(7)Tstl′θ≥Tendlθ+Tll′−M1−yll′k,∀k∈Y,∀l,l′∈N,(8)mtl′k=Tll′⋅yll′k,∀k∈Y,∀l,l′∈N,(9)TΔlθ=Tstlθ−Tarlθ,∀l∈N,(10)Llk−Ll′k′≥h⋅1−zll′−zl′l,∀k≠k′∈Y,∀l,l′∈N,(11)∑k∈Yk⋅xlk+1−∑k′∈Yk′⋅xl′k′≤Mzll′+zl′l,k≠k′,∀l,l′∈N,l≠l′,(12)∑l∈V∑l′∈Vyll′k+1≤∑l∈V∑l′∈Nyll′k,l≠l′,∀k∈Y,∀V⊂N,V≥2,(13)yll′k+yl′lk≤1,∀k∈Y,∀l,l′∈N,l≠l′,(14)∑k∈Y∑l∈Nyll′k≤1,∀l′∈N,l′≠l,(15)∑k∈Y∑l′∈Nyll′k≤1,∀l∈N,l′≠l,(16)∑l∈Nyll′k=∑l'′∈Nyl′l″k,∀l′∈N,l′≠0,∀k∈Y,(17)∑l∈Nyll′k=1−p0l′k,∀k∈Y,∀l′∈N,(18)∑l∈Nyl′lk=1−ql′0k,∀k∈Y,∀l′∈N,(19)∑k∈Yxlk=1,∀l∈N,(20)∑l∈Np0lk=1,∀k∈Y,(21)∑l∈Nql0k=1,∀k∈Y,(22)M1−yll′k≥2−xlk−xl′k,∀k∈Y,∀l,l′∈N,l≠l′,(23)M1−yll′k≥1−zll′,∀k∈Y,∀l,l′∈N,l≠l′,(24)M⋅zll′≥yll′k,∀k∈Y,∀l,l′∈N,l≠l′.The objective function is to minimize the expected value of yard crane makespan and total task waiting time over all the scenarios. Constraint (2) ensures that all the tasks should be handled. Constraint (3) defines the handling volume of each yard crane. Constraint (4) expresses the finish time of yard crane k. Similarly, constraint (5) defines the finish time of task l. Constraint (6) ensures that the start time of any task should not earlier than its arrival time. Constraint (7) and constraint (8) are used to determine the time relationship between two consecutive tasks. The latter task starts after the end time of the previous task with the addition of traveling time of the yard crane. Constraint (9) defines the waiting time of tasks.Constraint (10) shows the operation requirement of yard cranes. The distance between any two yard cranes at the same time must meet the safe limit. Constraint (11) ensures that yard cranes cannot cross each other. Constraint (12) is subtour elimination constraint. Constraints (13)–(16) guarantee the continuity of tasks and the balance of container flow. Constraints (17) and (18) indicate the first task and the last task of yard crane k. Constraint (19) ensures that each task should only be visited once by one yard crane. Constraints (20) and (21) express that each yard crane must start from and back to initial position. Constraints (22)–(24) are the restriction on the decision variables.


## 3.1. Problem Description

The growing volume of containers has brought pressure to the management of storage yard in port, which involves different resources such as yard trucks, yard cranes, and container blocks [31]. An efficient control method of cranes plays an important role in various fields of modern industry [32]. In many studies of yard crane scheduling problem, each yard crane is responsible for the designated container blocks, in which case the problem can be simplified, but the flexibility of yard cranes and some schemes with better results may be missed. In this paper, the yard cranes would not be restricted in a fixed container block, but the same row. The YC scheduling scheme may significantly impact the operation efficiency of container terminal, but in reality, the scheme may not always be appropriate due to uncertain factors. For example, Figure 2 shows a small example of yard crane scheduling, where the arriving sequence of tasks is assumed to be 1-3-2-4-8-6-7-9-5. The task sequence of YC1 is 4-6-9, the task sequence of YC2 is 2-8-5, and the task sequence of YC3 is 1-3-7. If task 2 arrives late, there will be a cross when YC1 accesses task 9 after handling task 6 while YC2 is to travel from task 2 to task 8. Besides, task 8 and task 9 may interfere with each other and one of them is forced to wait until the other finishes because the yard cranes could not be adjacent to each other for reasons of safety, in which case the subsequent tasks would be delayed. However, the schemes YC1: 2-4-6, YC2: 3-8-9, and YC3: 1-7-5 can deal with this situation better. Thus, it is necessary to develop a model to consider the interference of uncertain scenarios. In each scenario, the actual arrival times of tasks fluctuate randomly around the planned arrival time, and the handling volume of tasks assigned to each yard crane is also uncertain. Thus, a proactive scheduling scheme is produced with minimum expected value of two objectives over all the scenarios.Figure 2
A sample of yard crane crossing and interference.Generally, the optimization goal of yard crane scheduling problem is to minimize the finish time of all tasks. However, the equipment scheduling schemes with close makespan may have a large gap in the corresponding total waiting time of the tasks. We randomly generate 1000 sets of feasible operation sequences of 30 tasks processed by 3 yard cranes and calculate the makespan of yard cranes and the total waiting time of tasks corresponding to each sequence. The results are shown in Figure3, in which the sequences are sorted according to the value of makespan.Figure 3
The experiment results of random generated sequences.It can be seen that the makespan of yard cranes and the total waiting time of tasks have the same change trend on the whole. However, for the similar results of makespan, there are many schemes in which the total waiting time of tasks varies greatly. The long waiting time of the task will affect the delivery of the container and the turnaround time of trucks. Therefore, the minimum mathematical expectation of the sum of yard crane makespan and task waiting time over all the scenarios is taken as the objective function in this paper.


## 3.2. Assumptions

To ensure that the model can reasonably describe the problem above, several assumptions are given.Assumption 1.
All the containers are located on the top of the stacks and accessible.Assumption 2.
The traveling speed of each yard crane is the same, without considering the additional time consumption caused by equipment starting and turning.Assumption 3.
The locations of containers are known beforehand.


## 3.3. Parameters and Variables

The above problem can be described as a stochastic programming model using the following parameters and variables.Parameters and sets:N: The set of all tasks to be handledV: The subsets of N, V⊂N, V≥2Y: The set of all yard cranesn: The total number of all tasksl,l′,l″: The index of tasks, l,l′,l″∈N,l≠l′≠l″k: The index of yard cranes, k∈YLlk: The position of yard crane k when completing the task lM: A large integer valueφ: A weight coefficienth: The safe distance between yard craneswtlk: The operating time of yard crane k to handle the task lTll′: The traveling time from task l to task l′Ω: The set of uncertain scenariosθ: The index of uncertain scenarios, θ∈ΩTarlθ: The actual arriving time of task l in scenario θ.Decision variables:wk: The handling volume of yard crane kmtlk: The traveling time of yard crane k to handle the task lTstlθ: The operating start time of task l in scenario θTendlθ: The operating end time of task l in scenario θTstkθ: The time when yard crane k start working in scenario θTendkθ: The time when yard crane k finishes working in scenario θTΔlθ: The waiting time of task l in scenario θp0lk: If task l is the first task of yard crane k, p0lk=1, where 0 is the initial position of yard crane k; otherwise, p0lk=0ql0k: If task l is the last task of yard crane k, ql0k=1, where 0 is the initial position of yard crane k; otherwise, ql0k=0yll′k: If task l′ is consecutively handled by yard crane k after task l,yll′k=1; otherwise, yll′k=0xlk: If task l is handled by yard crane k, xlk=1; otherwise, xlk=0zll′: If task l has been finished before the start time of task l′, zll′=1; otherwise, zll′=0.Each yard crane has three statuses during its operation: processing a task, traveling to next task, and staying idle. Each task also may be in one of two statuses: waiting to be processed and being processed. In order to clearly and intuitively represent the working state of the yard cranes and the relationship between relevant time variables, a schematic diagram of the operation time axis of yard cranes in scenarioθ is shown in Figure 4. The total working time of yard cranes is determined by tasks assigned them, represented by white rectangle.Figure 4
The time axis of yard cranes in scenarioθ.


## 3.4. Mathematical Model

To achieve the rationality and the economy of yard crane scheduling scheme, some constraints are required. The yard crane scheduling problem under uncertainty is formulated as follows:(1)Minf=Eφmaxk∈YTendkθ+1−φ∑l∈NTΔlθ,(2)S.T.∑k∈Ywk=n,(3)∑l∈Nxlk=wk,∀k∈Y,(4)Tendkθ≥Tstkθ+∑l∈Nwtlk+mtlk⋅xlk,∀k∈Y,(5)Tendlθ=Tstlθ+∑k∈Ywtlk⋅xlk,∀l∈N,(6)Tstlθ≥Tarlθ,∀l∈N,(7)Tstl′θ≥Tendlθ+Tll′−M1−yll′k,∀k∈Y,∀l,l′∈N,(8)mtl′k=Tll′⋅yll′k,∀k∈Y,∀l,l′∈N,(9)TΔlθ=Tstlθ−Tarlθ,∀l∈N,(10)Llk−Ll′k′≥h⋅1−zll′−zl′l,∀k≠k′∈Y,∀l,l′∈N,(11)∑k∈Yk⋅xlk+1−∑k′∈Yk′⋅xl′k′≤Mzll′+zl′l,k≠k′,∀l,l′∈N,l≠l′,(12)∑l∈V∑l′∈Vyll′k+1≤∑l∈V∑l′∈Nyll′k,l≠l′,∀k∈Y,∀V⊂N,V≥2,(13)yll′k+yl′lk≤1,∀k∈Y,∀l,l′∈N,l≠l′,(14)∑k∈Y∑l∈Nyll′k≤1,∀l′∈N,l′≠l,(15)∑k∈Y∑l′∈Nyll′k≤1,∀l∈N,l′≠l,(16)∑l∈Nyll′k=∑l'′∈Nyl′l″k,∀l′∈N,l′≠0,∀k∈Y,(17)∑l∈Nyll′k=1−p0l′k,∀k∈Y,∀l′∈N,(18)∑l∈Nyl′lk=1−ql′0k,∀k∈Y,∀l′∈N,(19)∑k∈Yxlk=1,∀l∈N,(20)∑l∈Np0lk=1,∀k∈Y,(21)∑l∈Nql0k=1,∀k∈Y,(22)M1−yll′k≥2−xlk−xl′k,∀k∈Y,∀l,l′∈N,l≠l′,(23)M1−yll′k≥1−zll′,∀k∈Y,∀l,l′∈N,l≠l′,(24)M⋅zll′≥yll′k,∀k∈Y,∀l,l′∈N,l≠l′.The objective function is to minimize the expected value of yard crane makespan and total task waiting time over all the scenarios. Constraint (2) ensures that all the tasks should be handled. Constraint (3) defines the handling volume of each yard crane. Constraint (4) expresses the finish time of yard crane k. Similarly, constraint (5) defines the finish time of task l. Constraint (6) ensures that the start time of any task should not earlier than its arrival time. Constraint (7) and constraint (8) are used to determine the time relationship between two consecutive tasks. The latter task starts after the end time of the previous task with the addition of traveling time of the yard crane. Constraint (9) defines the waiting time of tasks.Constraint (10) shows the operation requirement of yard cranes. The distance between any two yard cranes at the same time must meet the safe limit. Constraint (11) ensures that yard cranes cannot cross each other. Constraint (12) is subtour elimination constraint. Constraints (13)–(16) guarantee the continuity of tasks and the balance of container flow. Constraints (17) and (18) indicate the first task and the last task of yard crane k. Constraint (19) ensures that each task should only be visited once by one yard crane. Constraints (20) and (21) express that each yard crane must start from and back to initial position. Constraints (22)–(24) are the restriction on the decision variables.


## 4. Solution Method

Many heuristic algorithms have been used to solve the scheduling problems (e.g., [33]). He et al. [28] and Zhou et al. [1] mainly used genetic algorithm to obtain a baseline schedule and then generated recovery schedules for different scenarios. In this paper, we propose rule-based heuristic algorithms to obtain a basic operation scheme in the deterministic environment, according to which the initial population in uncertain environment is generated, so as to achieve the purpose of improving the solving efficiency of the algorithm. A tailored genetic algorithm is designed for solving the problem with uncertain scenarios to obtain one well-adapted fixed scheme.


### 4.1. Rule-Based Heuristic Algorithm

The main idea of the rule-based heuristic algorithm is to use two intuitive rules: the principle of proximity and first come first served basis. Two rule-based heuristic algorithms are designed to, respectively, produce operating sequences of tasks. Among the two solutions, the one with the best objective value is selected as the final scheduling scheme of yard cranes in the deterministic environment. The details of the rule-based heuristic algorithms are depicted below.


#### 4.1.1. The Principle of Proximity (POP)

The tasks are completed by the nearest available yard crane in order of arrival time. The candidate sets of yard cranes of the earliest task in the list are determined in turn. All the feasible yard cranes in setsY1 and Y2 meet the safety distance and no crossing constraints, where idle yard cranes belong to the set Y1 while working yard cranes belong to the set Y2. The set Y3 contains two infeasible yard cranes locating on both sides of the task’s position, in which case each of them is unable to travel to the task because the safety distance to another one is not met. The algorithm process of the principle of proximity rule is shown in Figure 5.Figure 5
The algorithm process of the principle of proximity rule.


#### 4.1.2. First Come First Served Basis (FCFS)

The algorithm of first come first served basis is based on the work area division. Each yard crane is responsible for all tasks within a fixed area, where the number of tasks in each area is approximately the same. The corresponding schedules of yard cranes generated by the order of task arrival time are denoted byα1,…,αY. On the other hand, other schedules β1′,…,βY′ are obtained according to the shortest travel distance, taking half an hour for a period. Each yard crane operation sequence is determined in turn by comparing the value of objective function. The specific steps of the Algorithm 1 are as follows.Algorithm 1: Algorithm of first come first served basis.
Input: information of tasks(1)
Initialize the number of iterations:i=0(2)
The yard is divided into Y areas with similar number of tasks.(3)
Whilei<Y, do:(4)
i=i+1(5)
The tasks in areai are sorted in increase order of time, represented by αi. Calculate the schedule of yard crane and the objective value fαi.(6)
Generate the sequenceβi of storage tasks in area i according to the shortest distance, taking every half an hour for a period. Calculate the schedule of yard crane i.(7)
Insert the retrieval tasks in areai one by one in order of their arrival time into the sequence βi. Calculate the schedule of new sequence βi′ and the objective value fβi′.(8)
Iffαi>fβi′, then(9)
Optimal_i=βi′(10)
else(11)
Optimal_i=αi(12)
End if(13)
Add the Optimal_i into the set of optimal solution.(14)
End while(15)
Output the optimal solution.


### 4.2. Genetic Algorithm

In this paper, a tailored genetic algorithm is designed where the update strategies in particle swarm algorithm is introduced. Based on the basic scheme obtained through two rules above, this algorithm uses random method to generate the initial feasible individuals. The main details of the algorithm are described as follows:(1)
Chromosome Coding.In this paper, the integer sequential encoding method is adopted and each code is divided into two sections, where the first section of code represents the operation order of all tasks named by numbers and the second section of code represents the handling volume of each yard cranes. Therefore, the total length of code indicates the sum of the number of tasks and the number of yard cranes (Figure 6).(2)
Population Initialization. We make random changes to the sequence in the deterministic environment obtained through the rule-based heuristic algorithms introduced in Section 4.1 and retain the feasible changed sequences.(3)
Feasibility Judgment. The feasibility of individuals is mainly affected by yard cranes. Yard crane operation constraints such as the prohibition of yard crane to cross each other and the limitation of safe distance are taken as conditions to judge the feasibility of each individual. To be specific, we record the change of relative position of the yard cranes by sorting their coordinates every moment. When a crossover occurs (Figure 7(a)), the two tasks corresponding to the conflicted yard cranes (i.e., yard crane 1 and yard crane 2) are exchanged (Figure 7(b)), or waiting until one of yard cranes finish their current task Figure 7(c)).(4)
Fitness Calculation. The fitness value is calculated for all individuals in the initial population, which is the reciprocal of the objective function.(5)
Update Strategies. In this paper, a tailored individual update method is designed inspired by particle swarm optimization algorithm. We use the historical individual optimal solution and global optimal solution to update the chromosomes to avoid algorithm falling into the local optimal and to find the best solution along the optimal direction. Xvt indicates the state of individual v in the iteration t, Pvt indicates the historical individual optimal state of v after the iteration t, and Pgt represents the historical global optimal state of whole population after the iteration t. X1 and X2 are children generated from the crossover operation of parents Xvt and Pvt, while Y1 and Y2 are from Xvt and Pgt. After mutation operation of Xvt, Z1 and Z2 are gained.Figure 6
Coding schematic diagram.Figure 7
Repair methods of infeasible solutions.
(a)(b)(c)Step 1.
Crossover operation.
The coding of chromosomes contains the operation sequence of multiple yard cranes, and a large number of infeasible solutions will be generated when random exchange is adopted due to the interference between yard cranes. Therefore, we randomly select a segment from the first section of one parent’ code, which represents the operation sequence of a yard crane. The segment and the second section of the code will both be passed on to a child. The codes in other positions of the child are matched and determined in turn in order of another parent’s code. An example is shown in Figure8. When infeasible individual is produced, the tasks corresponding to the yard crane that crossed are exchanged. In particular, X1 and Y1 may be the same when Pvt is the same as Pgt, which only occurs on individual v whose historical individual optimal state happens to be historical global optimal state, similar to X2 and Y2.Figure 8
Crossover operation schematic diagram.Step 2.
Mutation operation.
The operation order mutation is adopted to obtainZ1 by changing the order of any two tasks in the first section. The handling volume mutation is performed by randomly interchanging the code of two sites in the second section, and the information in the first part needs to be adjusted accordingly, in which case Z2 is gained. Besides, each mutation method is accompanied by feasibility judgment, and once infeasible individual is produced, the mutation operation will be re-performed until successful. Figure 9 shows the detailed mutation operation process of an example.Figure 9
Mutation operation schematic diagram.Step 3.
Individual update.
The fitness values of the new individualsX1, X2, Y1, Y2, Z1, Z2 are calculated, respectively, and the historical individual and global optimal states of the population are updated.
The process of the tailored genetic algorithm is shown in Figure10.Figure 10
Process of tailored genetic algorithm.


## 4.1. Rule-Based Heuristic Algorithm

The main idea of the rule-based heuristic algorithm is to use two intuitive rules: the principle of proximity and first come first served basis. Two rule-based heuristic algorithms are designed to, respectively, produce operating sequences of tasks. Among the two solutions, the one with the best objective value is selected as the final scheduling scheme of yard cranes in the deterministic environment. The details of the rule-based heuristic algorithms are depicted below.


### 4.1.1. The Principle of Proximity (POP)

The tasks are completed by the nearest available yard crane in order of arrival time. The candidate sets of yard cranes of the earliest task in the list are determined in turn. All the feasible yard cranes in setsY1 and Y2 meet the safety distance and no crossing constraints, where idle yard cranes belong to the set Y1 while working yard cranes belong to the set Y2. The set Y3 contains two infeasible yard cranes locating on both sides of the task’s position, in which case each of them is unable to travel to the task because the safety distance to another one is not met. The algorithm process of the principle of proximity rule is shown in Figure 5.Figure 5
The algorithm process of the principle of proximity rule.


### 4.1.2. First Come First Served Basis (FCFS)

The algorithm of first come first served basis is based on the work area division. Each yard crane is responsible for all tasks within a fixed area, where the number of tasks in each area is approximately the same. The corresponding schedules of yard cranes generated by the order of task arrival time are denoted byα1,…,αY. On the other hand, other schedules β1′,…,βY′ are obtained according to the shortest travel distance, taking half an hour for a period. Each yard crane operation sequence is determined in turn by comparing the value of objective function. The specific steps of the Algorithm 1 are as follows.Algorithm 1: Algorithm of first come first served basis.
Input: information of tasks(1)
Initialize the number of iterations:i=0(2)
The yard is divided into Y areas with similar number of tasks.(3)
Whilei<Y, do:(4)
i=i+1(5)
The tasks in areai are sorted in increase order of time, represented by αi. Calculate the schedule of yard crane and the objective value fαi.(6)
Generate the sequenceβi of storage tasks in area i according to the shortest distance, taking every half an hour for a period. Calculate the schedule of yard crane i.(7)
Insert the retrieval tasks in areai one by one in order of their arrival time into the sequence βi. Calculate the schedule of new sequence βi′ and the objective value fβi′.(8)
Iffαi>fβi′, then(9)
Optimal_i=βi′(10)
else(11)
Optimal_i=αi(12)
End if(13)
Add the Optimal_i into the set of optimal solution.(14)
End while(15)
Output the optimal solution.


## 4.1.1. The Principle of Proximity (POP)

The tasks are completed by the nearest available yard crane in order of arrival time. The candidate sets of yard cranes of the earliest task in the list are determined in turn. All the feasible yard cranes in setsY1 and Y2 meet the safety distance and no crossing constraints, where idle yard cranes belong to the set Y1 while working yard cranes belong to the set Y2. The set Y3 contains two infeasible yard cranes locating on both sides of the task’s position, in which case each of them is unable to travel to the task because the safety distance to another one is not met. The algorithm process of the principle of proximity rule is shown in Figure 5.Figure 5
The algorithm process of the principle of proximity rule.


## 4.1.2. First Come First Served Basis (FCFS)

The algorithm of first come first served basis is based on the work area division. Each yard crane is responsible for all tasks within a fixed area, where the number of tasks in each area is approximately the same. The corresponding schedules of yard cranes generated by the order of task arrival time are denoted byα1,…,αY. On the other hand, other schedules β1′,…,βY′ are obtained according to the shortest travel distance, taking half an hour for a period. Each yard crane operation sequence is determined in turn by comparing the value of objective function. The specific steps of the Algorithm 1 are as follows.Algorithm 1: Algorithm of first come first served basis.
Input: information of tasks(1)
Initialize the number of iterations:i=0(2)
The yard is divided into Y areas with similar number of tasks.(3)
Whilei<Y, do:(4)
i=i+1(5)
The tasks in areai are sorted in increase order of time, represented by αi. Calculate the schedule of yard crane and the objective value fαi.(6)
Generate the sequenceβi of storage tasks in area i according to the shortest distance, taking every half an hour for a period. Calculate the schedule of yard crane i.(7)
Insert the retrieval tasks in areai one by one in order of their arrival time into the sequence βi. Calculate the schedule of new sequence βi′ and the objective value fβi′.(8)
Iffαi>fβi′, then(9)
Optimal_i=βi′(10)
else(11)
Optimal_i=αi(12)
End if(13)
Add the Optimal_i into the set of optimal solution.(14)
End while(15)
Output the optimal solution.


## 4.2. Genetic Algorithm

In this paper, a tailored genetic algorithm is designed where the update strategies in particle swarm algorithm is introduced. Based on the basic scheme obtained through two rules above, this algorithm uses random method to generate the initial feasible individuals. The main details of the algorithm are described as follows:(1)
Chromosome Coding.In this paper, the integer sequential encoding method is adopted and each code is divided into two sections, where the first section of code represents the operation order of all tasks named by numbers and the second section of code represents the handling volume of each yard cranes. Therefore, the total length of code indicates the sum of the number of tasks and the number of yard cranes (Figure 6).(2)
Population Initialization. We make random changes to the sequence in the deterministic environment obtained through the rule-based heuristic algorithms introduced in Section 4.1 and retain the feasible changed sequences.(3)
Feasibility Judgment. The feasibility of individuals is mainly affected by yard cranes. Yard crane operation constraints such as the prohibition of yard crane to cross each other and the limitation of safe distance are taken as conditions to judge the feasibility of each individual. To be specific, we record the change of relative position of the yard cranes by sorting their coordinates every moment. When a crossover occurs (Figure 7(a)), the two tasks corresponding to the conflicted yard cranes (i.e., yard crane 1 and yard crane 2) are exchanged (Figure 7(b)), or waiting until one of yard cranes finish their current task Figure 7(c)).(4)
Fitness Calculation. The fitness value is calculated for all individuals in the initial population, which is the reciprocal of the objective function.(5)
Update Strategies. In this paper, a tailored individual update method is designed inspired by particle swarm optimization algorithm. We use the historical individual optimal solution and global optimal solution to update the chromosomes to avoid algorithm falling into the local optimal and to find the best solution along the optimal direction. Xvt indicates the state of individual v in the iteration t, Pvt indicates the historical individual optimal state of v after the iteration t, and Pgt represents the historical global optimal state of whole population after the iteration t. X1 and X2 are children generated from the crossover operation of parents Xvt and Pvt, while Y1 and Y2 are from Xvt and Pgt. After mutation operation of Xvt, Z1 and Z2 are gained.Figure 6
Coding schematic diagram.Figure 7
Repair methods of infeasible solutions.
(a)(b)(c)Step 1.
Crossover operation.
The coding of chromosomes contains the operation sequence of multiple yard cranes, and a large number of infeasible solutions will be generated when random exchange is adopted due to the interference between yard cranes. Therefore, we randomly select a segment from the first section of one parent’ code, which represents the operation sequence of a yard crane. The segment and the second section of the code will both be passed on to a child. The codes in other positions of the child are matched and determined in turn in order of another parent’s code. An example is shown in Figure8. When infeasible individual is produced, the tasks corresponding to the yard crane that crossed are exchanged. In particular, X1 and Y1 may be the same when Pvt is the same as Pgt, which only occurs on individual v whose historical individual optimal state happens to be historical global optimal state, similar to X2 and Y2.Figure 8
Crossover operation schematic diagram.Step 2.
Mutation operation.
The operation order mutation is adopted to obtainZ1 by changing the order of any two tasks in the first section. The handling volume mutation is performed by randomly interchanging the code of two sites in the second section, and the information in the first part needs to be adjusted accordingly, in which case Z2 is gained. Besides, each mutation method is accompanied by feasibility judgment, and once infeasible individual is produced, the mutation operation will be re-performed until successful. Figure 9 shows the detailed mutation operation process of an example.Figure 9
Mutation operation schematic diagram.Step 3.
Individual update.
The fitness values of the new individualsX1, X2, Y1, Y2, Z1, Z2 are calculated, respectively, and the historical individual and global optimal states of the population are updated.
The process of the tailored genetic algorithm is shown in Figure10.Figure 10
Process of tailored genetic algorithm.


## 5. Computational Results and Discussion

### 5.1. Weight Experiments

The optimal value of weightφ in objective function is determined through small-scale experiments, where 30 tasks are handled by 3 yard cranes with 10 uncertain scenarios.It is clear that it makes no sense forφ to be 0 or 1, and thus the weight value in experiments gradually increases from 0.1 to 0.9 with the step size of 0.1. Considering the characteristics of probabilistic convergence of the algorithm, different schemes can be obtained when the same parameters are used to solve the same example repeatedly. Therefore, each experiment is conducted 10 times and the mean value is taken as the final result.Figure11(a) shows the experiment results with varied weight values, in which the numbers on the horizontal axis represent the weight values. For example, “0.1” means φ=0.1, which is the weight of the makespan of yard cranes, while the weight of waiting time of tasks is 1−φ=0.9. Figure 11(b) shows the mean value and standard deviation of waiting time with varied weight values. It can be seen that the makespan of yard cranes is stable, while the task waiting time fluctuates obviously with the change of weight value. When φ=0.6, both the mean value and standard deviation of waiting time reached a smaller value, so the weight φ in later experiments is set to 0.6.Figure 11
The results of weight experiments.
(a)(b)


### 5.2. Small-Scale Experiments

Through a series of experiments with different data scales, we firstly compare the performance of proposed algorithm and then analyze the sensitivity of certain parameters.


#### 5.2.1. Algorithm Performance Analysis

In the experiments, we consider a container block with 30 bays and 5 rows, where the number of tasks is 30 and the number of available yard cranes is 4, whose handling volume is unfixed. Besides, the safe separation distance between any two yard cranes is at least 1 bay, and the travel speed of yard cranes is 50 m/min. The detailed information of tasks including type and positions is given in Table2, where “type 1” refers to storage tasks and “type 2” refers to retrieval tasks. The number 0 in position coordinates represents the loading/unloading row. For example, task 1 given in Table 2 needs to be stored to row 4, bay 8, from the truck waiting at row 0, bay 8. The planned arrival time of tasks in the deterministic environment is also given in Table 2, whose intervals obey the exponential distribution E (4 h∗3600 s/200) [26]. Based on the above data, we randomly generate 20 scenarios, where the actual arrival times of half tasks in any scenario randomly fluctuate within 3 time units. Each experiment is conducted 10 times and the mean value is taken as the final result. The results are shown in Table 3.Table 2
The given information of tasks.
TaskTypeFromToarrival_time110; 84; 81210; 93; 92310; 163; 163421; 110; 113510; 22; 24621; 210; 216710; 45; 48810; 185; 188922; 50; 5101010; 174; 17101110; 253; 25121210; 281; 28141323; 160; 16151424; 250; 25161510; 42; 4161622; 100; 10161710; 132; 13181810; 262; 26211910; 84; 8212025; 30; 3232110; 153; 15232210; 291; 29252325; 170; 17262410; 172; 17272523; 290; 29282610; 75; 7292710; 14; 1352810; 143; 14382910; 223; 22403022; 90; 942Table 3
The experiment result comparison of algorithms.
Number of tasksNumber of YCsDeterministic environmentUncertain environment with 20 scenariosPOP ruleFCFS ruleGAPSOObjCT (s)ObjCT (s)ObjCT (s)10178.60.0165.60.4239.457.7610231.60.0114.00.2811.463.0120278.00.0234.40.4031.689.3720324.60.0219.40.4618.6105.0930336.20.0330.20.5531.4151.1630427.40.0327.00.6328.2182.87Note: “Obj” represents the objective function value and “CT” represents computational time.When there are fewer tasks and fewer yard cranes, the total waiting time of tasks could be high due to the long travel distance between scattered tasks. It can be seen from Table3 that the results of tailored genetic algorithm are optimal when the number of tasks is not more than 20 and the number of yard cranes is not more than 3. With the increasing number of tasks and yard cranes, the algorithm based on FCFS rule in the deterministic environment shows better performance compared with POP rule. However, the division of working areas of yard cranes is required ahead in this algorithm, leading to the loss of diversity and flexibility, and some schemes with better results may be missed. Meanwhile, the tailored genetic algorithm is of high complexity under uncertainty and can be time consuming, but the performance of optimizing is stable.


#### 5.2.2. Sensitivity Analysis

In this paper, 10 sets of experiments are carried out to analyze the influence of varying parameters on operation efficiency in terms of makespan of yard cranes and total waiting time of tasks in container terminals. Each set of experiment is repeated for 10 times and the optimal result among them is adopted, as shown in Table4.Table 4
Sensitivity analysis of key parameters.
Number of tasksNumber of YCsMakespanWaiting time101236415135150201512281522117202264025247502032592532993034314304436It can be observed that with the same number of yard cranes, the more tasks there are, the longer the makespan of yard cranes and the longer the total waiting time of tasks it takes. When the number of tasks keeps unchanged, deploying more yard cranes can shorten the makespan and improve the operation efficiency. Moreover, the result of “30–3” shows little gap compared with results of “30–4,” which indicates that the number of yard cranes is enough to process the tasks and there is no need for another equipment. In practice, it is necessary to determine the optimal configuration of equipment considering the requirement of the balance between the equipment cost and the operation efficiency.


### 5.3. Large-Scale Experiments

In the yard crane scheduling problem studied in this paper, the handling volume of each yard crane is uncertain, which plays a key role in operation efficiency of container terminals. A series of large-scale experiments are carried out to analyze the relationship between different handling volume assignment of yard cranes and the operation efficiency. The experiments involve 20 uncertain scenarios and 200 tasks processed by 6 yard cranes. The arrival intervals of tasks obey the exponential distribution. The container yard is of size with 30 bays and 15 rows. The specific results of experiments are shown in Table5.Table 5
The experiment results of different handling volume assignment of yard cranes.
No.Handling volumeMakespanWaiting timeObj135; 36; 42; 35; 29; 2326298196.4233; 34; 36; 31; 32; 3426048175.2333; 34; 34; 33; 32; 3426035170430; 37; 36; 31; 32; 3426043173.2536; 31; 33; 34; 28; 3826048175.2638; 29; 31; 36; 34; 3226060180It is clear that the varied handling volume of yard cranes has a noticeable impact on the operation time in the container yard when the total number of tasks keeps unchanged. When there is a large gap between handling volume of yard cranes, the operation completion time of each yard crane is unbalanced, in which case the makespan depends on the yard crane with the largest handling volume. The busy yard crane is also responsible for the task delays, while the situation is that the yard cranes with a small amount of tasks are often idle, whose abilities are not fully used. On the contrary, the makespan of yard cranes and the total waiting time of tasks both reach the minimum when the assignment of handling volume is more balanced, which is conducive to improving the operating efficiency in container terminal and achieving the optimality of the system.


## 5.1. Weight Experiments

The optimal value of weightφ in objective function is determined through small-scale experiments, where 30 tasks are handled by 3 yard cranes with 10 uncertain scenarios.It is clear that it makes no sense forφ to be 0 or 1, and thus the weight value in experiments gradually increases from 0.1 to 0.9 with the step size of 0.1. Considering the characteristics of probabilistic convergence of the algorithm, different schemes can be obtained when the same parameters are used to solve the same example repeatedly. Therefore, each experiment is conducted 10 times and the mean value is taken as the final result.Figure11(a) shows the experiment results with varied weight values, in which the numbers on the horizontal axis represent the weight values. For example, “0.1” means φ=0.1, which is the weight of the makespan of yard cranes, while the weight of waiting time of tasks is 1−φ=0.9. Figure 11(b) shows the mean value and standard deviation of waiting time with varied weight values. It can be seen that the makespan of yard cranes is stable, while the task waiting time fluctuates obviously with the change of weight value. When φ=0.6, both the mean value and standard deviation of waiting time reached a smaller value, so the weight φ in later experiments is set to 0.6.Figure 11
The results of weight experiments.
(a)(b)


## 5.2. Small-Scale Experiments

Through a series of experiments with different data scales, we firstly compare the performance of proposed algorithm and then analyze the sensitivity of certain parameters.


### 5.2.1. Algorithm Performance Analysis

In the experiments, we consider a container block with 30 bays and 5 rows, where the number of tasks is 30 and the number of available yard cranes is 4, whose handling volume is unfixed. Besides, the safe separation distance between any two yard cranes is at least 1 bay, and the travel speed of yard cranes is 50 m/min. The detailed information of tasks including type and positions is given in Table2, where “type 1” refers to storage tasks and “type 2” refers to retrieval tasks. The number 0 in position coordinates represents the loading/unloading row. For example, task 1 given in Table 2 needs to be stored to row 4, bay 8, from the truck waiting at row 0, bay 8. The planned arrival time of tasks in the deterministic environment is also given in Table 2, whose intervals obey the exponential distribution E (4 h∗3600 s/200) [26]. Based on the above data, we randomly generate 20 scenarios, where the actual arrival times of half tasks in any scenario randomly fluctuate within 3 time units. Each experiment is conducted 10 times and the mean value is taken as the final result. The results are shown in Table 3.Table 2
The given information of tasks.
TaskTypeFromToarrival_time110; 84; 81210; 93; 92310; 163; 163421; 110; 113510; 22; 24621; 210; 216710; 45; 48810; 185; 188922; 50; 5101010; 174; 17101110; 253; 25121210; 281; 28141323; 160; 16151424; 250; 25161510; 42; 4161622; 100; 10161710; 132; 13181810; 262; 26211910; 84; 8212025; 30; 3232110; 153; 15232210; 291; 29252325; 170; 17262410; 172; 17272523; 290; 29282610; 75; 7292710; 14; 1352810; 143; 14382910; 223; 22403022; 90; 942Table 3
The experiment result comparison of algorithms.
Number of tasksNumber of YCsDeterministic environmentUncertain environment with 20 scenariosPOP ruleFCFS ruleGAPSOObjCT (s)ObjCT (s)ObjCT (s)10178.60.0165.60.4239.457.7610231.60.0114.00.2811.463.0120278.00.0234.40.4031.689.3720324.60.0219.40.4618.6105.0930336.20.0330.20.5531.4151.1630427.40.0327.00.6328.2182.87Note: “Obj” represents the objective function value and “CT” represents computational time.When there are fewer tasks and fewer yard cranes, the total waiting time of tasks could be high due to the long travel distance between scattered tasks. It can be seen from Table3 that the results of tailored genetic algorithm are optimal when the number of tasks is not more than 20 and the number of yard cranes is not more than 3. With the increasing number of tasks and yard cranes, the algorithm based on FCFS rule in the deterministic environment shows better performance compared with POP rule. However, the division of working areas of yard cranes is required ahead in this algorithm, leading to the loss of diversity and flexibility, and some schemes with better results may be missed. Meanwhile, the tailored genetic algorithm is of high complexity under uncertainty and can be time consuming, but the performance of optimizing is stable.


### 5.2.2. Sensitivity Analysis

In this paper, 10 sets of experiments are carried out to analyze the influence of varying parameters on operation efficiency in terms of makespan of yard cranes and total waiting time of tasks in container terminals. Each set of experiment is repeated for 10 times and the optimal result among them is adopted, as shown in Table4.Table 4
Sensitivity analysis of key parameters.
Number of tasksNumber of YCsMakespanWaiting time101236415135150201512281522117202264025247502032592532993034314304436It can be observed that with the same number of yard cranes, the more tasks there are, the longer the makespan of yard cranes and the longer the total waiting time of tasks it takes. When the number of tasks keeps unchanged, deploying more yard cranes can shorten the makespan and improve the operation efficiency. Moreover, the result of “30–3” shows little gap compared with results of “30–4,” which indicates that the number of yard cranes is enough to process the tasks and there is no need for another equipment. In practice, it is necessary to determine the optimal configuration of equipment considering the requirement of the balance between the equipment cost and the operation efficiency.


## 5.2.1. Algorithm Performance Analysis

In the experiments, we consider a container block with 30 bays and 5 rows, where the number of tasks is 30 and the number of available yard cranes is 4, whose handling volume is unfixed. Besides, the safe separation distance between any two yard cranes is at least 1 bay, and the travel speed of yard cranes is 50 m/min. The detailed information of tasks including type and positions is given in Table2, where “type 1” refers to storage tasks and “type 2” refers to retrieval tasks. The number 0 in position coordinates represents the loading/unloading row. For example, task 1 given in Table 2 needs to be stored to row 4, bay 8, from the truck waiting at row 0, bay 8. The planned arrival time of tasks in the deterministic environment is also given in Table 2, whose intervals obey the exponential distribution E (4 h∗3600 s/200) [26]. Based on the above data, we randomly generate 20 scenarios, where the actual arrival times of half tasks in any scenario randomly fluctuate within 3 time units. Each experiment is conducted 10 times and the mean value is taken as the final result. The results are shown in Table 3.Table 2
The given information of tasks.
TaskTypeFromToarrival_time110; 84; 81210; 93; 92310; 163; 163421; 110; 113510; 22; 24621; 210; 216710; 45; 48810; 185; 188922; 50; 5101010; 174; 17101110; 253; 25121210; 281; 28141323; 160; 16151424; 250; 25161510; 42; 4161622; 100; 10161710; 132; 13181810; 262; 26211910; 84; 8212025; 30; 3232110; 153; 15232210; 291; 29252325; 170; 17262410; 172; 17272523; 290; 29282610; 75; 7292710; 14; 1352810; 143; 14382910; 223; 22403022; 90; 942Table 3
The experiment result comparison of algorithms.
Number of tasksNumber of YCsDeterministic environmentUncertain environment with 20 scenariosPOP ruleFCFS ruleGAPSOObjCT (s)ObjCT (s)ObjCT (s)10178.60.0165.60.4239.457.7610231.60.0114.00.2811.463.0120278.00.0234.40.4031.689.3720324.60.0219.40.4618.6105.0930336.20.0330.20.5531.4151.1630427.40.0327.00.6328.2182.87Note: “Obj” represents the objective function value and “CT” represents computational time.When there are fewer tasks and fewer yard cranes, the total waiting time of tasks could be high due to the long travel distance between scattered tasks. It can be seen from Table3 that the results of tailored genetic algorithm are optimal when the number of tasks is not more than 20 and the number of yard cranes is not more than 3. With the increasing number of tasks and yard cranes, the algorithm based on FCFS rule in the deterministic environment shows better performance compared with POP rule. However, the division of working areas of yard cranes is required ahead in this algorithm, leading to the loss of diversity and flexibility, and some schemes with better results may be missed. Meanwhile, the tailored genetic algorithm is of high complexity under uncertainty and can be time consuming, but the performance of optimizing is stable.


## 5.2.2. Sensitivity Analysis

In this paper, 10 sets of experiments are carried out to analyze the influence of varying parameters on operation efficiency in terms of makespan of yard cranes and total waiting time of tasks in container terminals. Each set of experiment is repeated for 10 times and the optimal result among them is adopted, as shown in Table4.Table 4
Sensitivity analysis of key parameters.
Number of tasksNumber of YCsMakespanWaiting time101236415135150201512281522117202264025247502032592532993034314304436It can be observed that with the same number of yard cranes, the more tasks there are, the longer the makespan of yard cranes and the longer the total waiting time of tasks it takes. When the number of tasks keeps unchanged, deploying more yard cranes can shorten the makespan and improve the operation efficiency. Moreover, the result of “30–3” shows little gap compared with results of “30–4,” which indicates that the number of yard cranes is enough to process the tasks and there is no need for another equipment. In practice, it is necessary to determine the optimal configuration of equipment considering the requirement of the balance between the equipment cost and the operation efficiency.


## 5.3. Large-Scale Experiments

In the yard crane scheduling problem studied in this paper, the handling volume of each yard crane is uncertain, which plays a key role in operation efficiency of container terminals. A series of large-scale experiments are carried out to analyze the relationship between different handling volume assignment of yard cranes and the operation efficiency. The experiments involve 20 uncertain scenarios and 200 tasks processed by 6 yard cranes. The arrival intervals of tasks obey the exponential distribution. The container yard is of size with 30 bays and 15 rows. The specific results of experiments are shown in Table5.Table 5
The experiment results of different handling volume assignment of yard cranes.
No.Handling volumeMakespanWaiting timeObj135; 36; 42; 35; 29; 2326298196.4233; 34; 36; 31; 32; 3426048175.2333; 34; 34; 33; 32; 3426035170430; 37; 36; 31; 32; 3426043173.2536; 31; 33; 34; 28; 3826048175.2638; 29; 31; 36; 34; 3226060180It is clear that the varied handling volume of yard cranes has a noticeable impact on the operation time in the container yard when the total number of tasks keeps unchanged. When there is a large gap between handling volume of yard cranes, the operation completion time of each yard crane is unbalanced, in which case the makespan depends on the yard crane with the largest handling volume. The busy yard crane is also responsible for the task delays, while the situation is that the yard cranes with a small amount of tasks are often idle, whose abilities are not fully used. On the contrary, the makespan of yard cranes and the total waiting time of tasks both reach the minimum when the assignment of handling volume is more balanced, which is conducive to improving the operating efficiency in container terminal and achieving the optimality of the system.


## 6. Conclusion

With the expansion of global economy, container throughput keeps the upward trend, in which case the effective management and scheduling of resources in container terminals is a necessary guarantee for the smooth circulation of container flow. The problem of yard crane scheduling with uncertain factors studied in this paper can not only adapt to the realistic situation but also reduce the extra cost of scheme adjustment due to uncertain situation. We fully consider the characteristics of dynamics, uncertainty, and complexity of the yard crane scheduling problem in the uncertain environment and design the algorithms for solving the model based on the idea of heuristic rules and genetic algorithm. Experimental results reveal that the algorithm under uncertainty is of high complexity and is time consuming, but the overall optimization ability is stable and the results are satisfactory. Besides, the changes of the number of tasks as well as the configuration of yard cranes have a certain influence on the makespan of yard cranes and the waiting time of tasks. Moreover, the experiments also indicate that the balanced assignment of handling volume of yard cranes is conducive to the improvement of the operation efficiency in container terminals.From the perspective of the whole operation process of containers in the port, the improvement of overall operation efficiency and capacity of the port requires the coordination of all equipment during multiple operations in both space and time. Therefore, the integrated scheduling problem of key resources such as trucks, yard cranes, and quay cranes in the uncertain environment can be a valuable research topic.



---

*Source: 5537114-2021-03-10.xml*