# Integrated Berth Allocation and Time-Variant Quay Crane Scheduling with Tidal Impact in Approach Channel

Authors: Xiaogang Jiao; Feifeng Zheng; Ming Liu; Yinfeng Xu
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

This paper addresses the integrated problem of dynamic continuous berth allocation and time-variant quay crane scheduling in container terminals and introduces the factor of tidal impacts into the problem. We mainly consider the impact of tides on the transport capacity of an approach channel that connects quay and anchorage. An integer linear programming model is developed, and then three heuristic algorithms, Genetic Algorithm, Hybrid Particle Swarm Optimization, and Hybrid Simulated Annealing, are proposed to solve the model. Numerical experiments are conducted to verify the efficient performances of the proposed heuristics. Moreover, experimental results also demonstrate the nonignorable impact of tides on the vessel turnaround time and the utilization of berth and quay cranes.


---

## Body

## 1. Introduction

In the last decades, container shipping plays an important and irreplaceable role in the international trade due to its low shipping cost and high reliability. Huge maritime transport demand brings container ports more business opportunities as well as more challenges [1]. To stand out in the fierce competition, container port managers have to improve the efficiency of services in order to lower service costs and attract more vessels calling. One critical aspect is to maximize the use of key resources, such as berths and quay cranes (QCs). With the quick increase of containership size, the processing schedule of vessels in many container seaports is much impacted by tides. Because their required deep drafts are usually more than the channel’s water depth, mega-containerships have to pass through the approach channel by the aid of tides.Figure1 illustrates the tidal effect. As shown in the figure, the tide fluctuates and it alters the water depth of the channel over time (taking a tidal cycle as an example). When a vessel arrives at the port, the vessel draft h1 becomes known. To ensure the safety during passing through the channel, the under keel clearance h2, which is the distance from the vessel bottom to the fairway bottom, is required to be at least 12% of the vessel draft [2]. Let h3 be the tide datum depth. Then a minimum tide height h∗ required for the vessel to pass through the channel is formulated as h∗=h1+h2-h3. Based on this, the available tide time window [t1,t2] can be calculated according to h∗ and the tidal rhythm together with tidal amplitude at the seaport. The vessel can only pass through channel during time interval [t1,t2] in the tidal cycle. Specifically, if the vessel calls at the port before t1, it waits to the time point. If otherwise it arrives after time t2, the vessel has to wait until the next available tide time window. Similarly, if the vessel has completed service and plans to leave the port via the channel, the same tidal requirement has to be met. So the container terminal manager has to well consider the interaction of berth, QCs, vessels’ drafts, and the fluctuation of tide so as to provide appropriate berthing time for each vessel to prevent its unnecessary waiting at the anchorage ground. An optimal processing schedule of vessels not only maximizes the use of the critical resources, but also greatly reduces vessel bunker fuel costs and greenhouse gas emissions.Figure 1
Illustration of a vessel passing through the approach channel.Many recent works [3–7] have addressed the impact of tides on the seaside operations in a container port. These papers consider the tidal impact in berth allocation problem (BAP), in which the processing times of vessels are generally assumed to be constants. That is, QC assignment is not involved. In practice, however, the turnaround time of a vessel is a variable and depends on not only the number of containers to be processed but also the number of QCs assigned to the vessel. Motivated by this, we investigate the integrated berth and QC scheduling problem with tidal impact in this work such that the turnaround time of any vessel relies on its schedule.The main contributions of this work are threefold. (i) We introduce the impact of tides into the integrated problem of dynamic continuous berth allocation and time-variant QC scheduling. (ii) An integer linear programming model is established and three heuristic algorithms are exploited to solve the model. (iii) Numerical experiments are conducted to reveal the nonneglected tidal impacts on the turnaround times of vessels and the utilization of berth and QCs.The rest of this paper is organized as follows. Section2 reviews relevant literature. The description of the problem is presented in Section 3. Section 4 formulates the integer linear programming model of the considered problem, and three heuristic algorithms are employed in Section 5. In Section 6 we conduct extensive numerical experiments to further verify the impact of tides in scheduling and make comparison between the proposed heuristics. Finally, conclusions and some suggestions of further research are provided in Section 7.


## 2. Literature Review

Seaside operations scheduling in container terminals have been of large interest in the fields of management science, operations research, and computer sciences in the last decades. For a comprehensive understanding of container terminal operations, readers are referred to literature [8–12]. According to Bierwirth and Meisel [10], there are three basic scheduling problems in seaside operations, i.e., the berth allocation problem (BAP), the QC assignment problem (QCAP), and the QC scheduling problem (QCSP). Moreover, the integration of these problems, such as BAP-QCAP and BAP-QCSP, has also caught a lot of interest in literature.


### 2.1. Integrated Seaside Operations Scheduling

Park and Kim [13] put forward a pioneering integration method for scheduling berth and QCs. They establish a mixed integer linear programming (MILP) model and propose a two-phase solution procedure to solve the model. At the first stage, the assignment of berths and QCs to vessels is determined by Lagrangian relaxation and a subgradient optimization method. Then a dynamic programming technique is adopted to schedule the assigned QCs for the vessels. Liang et al. [14] study an integration of discrete berth allocation problem and QC dynamic assignment problem. They formulate a multiobjective mathematical model to minimize both turnaround time of vessels and the number of QC movements simultaneously. To solve the model, a multiobjective hybrid genetic algorithm approach with a priority-based encoding method is applied. Zhang et al. [15] address a BAP-QCAP problem considering the coverage ranges and limited adjustments of QCs during processing. They construct a mixed integer programming model and apply a subgradient optimization algorithm to solve the model. Giallombardo et al. [16] propose a novel concept of QC assignment profiles to integrate berth allocation and QC assignment. A mixed integer quadratic programming formulation and a mixed integer linear program are constructed, which aim to maximize the total value of chosen QC-profiles and yard costs. Hu et al. [17] construct a nonlinear multiobjective mixed integer programming model for integrating BAP and QCAP, which considers vessel fuel consumption and emissions. A second-order mixed integer cone programming model is adopted in solving the model.Meisel and Bierwirth [18] establish a framework for the integration of berth allocation, QC assignment and scheduling problem. The framework proceeds in three phases. Phase 1 calculates the crane productivity rates according to vessel stowage plans. Berthing times and positions as well as crane capacity assignments are determined in Phase 2. Finally, Phase 3 provides QC schedules. Turkogullari et al. [19] study the integration of berth allocation, QC assignment, and time-invariant QC scheduling problem (BACASP) such that the QCs assigned to each vessel stay at where they are until the vessel has been completed. First, they integrate the berth allocation and QC assignment problem (BACAP) in a binary integer linear programming model. In order to incorporate QC scheduling problem, they extend the BACAP and introduce a mixed integer linear programming model for the BACASP. Two algorithms are proposed to generate the optimal solution for the BACASP based on the optimal solution of BACAP. Considering the scenario where the number of QCs assigned to any vessel is allowed to vary during the processing of the vessel, Turkogullari et al. [20] build a mixed integer linear program to combine berth allocation, time-variant QC assignment and scheduling with consideration of QC setup cost owing to the movement between two working locations along the berth. They split it into a relaxed master problem and a subproblem and propose an exact solution algorithm by means of directed, layered, single source, and single sink network. The simulation results demonstrate that the algorithm may obtain optimal solutions for large-scale realistic problem instances.


### 2.2. Seaside Operations considering Tidal Impacts

Although seaside operations in container terminals have caught much interest in literature, there are only a few studies considering the influence of tide in the BAP problem. Most of these works consider the tide impact on the water depth along the berths. Barros et al. [3] investigate a BAP model with tidal time windows and stock level conditions in a tidal bulk port of Brazil. They present an integer linear programming model with homogeneous berths, which aims to minimize the overall demurrage in the planning horizon. A simulated-annealing-based algorithm (SA) is proposed to obtain good solutions. Xu et al. [4] study a discrete BAP model in both static and dynamic cases for container terminals in which the assignment of berths is limited by water depth due to tides. They assume that the time horizon is divided into only one high water period and one low water period. Qin et al. [7] address the BAP at a tidal river port in a more precise manner than [3, 4] by introducing time-varying draft constraints on vessel berthing based on each vessel’s draft and tide conditions of different berths. They build six integer programming models which are various combinations of three objectives (i.e., total weighted turnaround time, total weighted departure delay, and makespan) and two vessel arrival cases (i.e., static and dynamic). The models are then transformed into the innovative constraint programming counterparts. Lalla-Ruiz et al. [6] modify the model proposed in [4] to improve the feasibility of solutions based on the generalized Set Partitioning problem. Numerical experiments indicate that the computational efficiency is also improved significantly.Some other authors investigate the BAP problem with the impact of tide in the approach channel. Sheikholeslami et al. [5] take into consideration not only the tidal constraints in the approach channel but also the variations of water depth in different berths in the continuous dynamic berth allocation. A genetic algorithm combined with pattern search algorithm is proposed to solve the problem. Du et al. [2] develop two mathematical models to figure out the BAP in a tidal port, in which it takes into account the restriction of tides when vessels enter or leave the port through the approach channel. The first model aims to minimize the total departure delay of vessels, and the second model takes vessel arrival times as decision variables and takes the minimum weighted summation of departure delay and fuel consumption as the objective. The second-order cone programming technique is adopted to simplify the nonlinear complexity of the second model. Numerical simulations show that the second model can effectively mitigate the tidal impacts on container terminal operations and vessel emissions. To the best of our knowledge, there are no results on the BACASP problem where the influence of tides is involved. In this work we focus on the BACASP problem with time-variant QC scheduling and tidal impacts.


## 2.1. Integrated Seaside Operations Scheduling

Park and Kim [13] put forward a pioneering integration method for scheduling berth and QCs. They establish a mixed integer linear programming (MILP) model and propose a two-phase solution procedure to solve the model. At the first stage, the assignment of berths and QCs to vessels is determined by Lagrangian relaxation and a subgradient optimization method. Then a dynamic programming technique is adopted to schedule the assigned QCs for the vessels. Liang et al. [14] study an integration of discrete berth allocation problem and QC dynamic assignment problem. They formulate a multiobjective mathematical model to minimize both turnaround time of vessels and the number of QC movements simultaneously. To solve the model, a multiobjective hybrid genetic algorithm approach with a priority-based encoding method is applied. Zhang et al. [15] address a BAP-QCAP problem considering the coverage ranges and limited adjustments of QCs during processing. They construct a mixed integer programming model and apply a subgradient optimization algorithm to solve the model. Giallombardo et al. [16] propose a novel concept of QC assignment profiles to integrate berth allocation and QC assignment. A mixed integer quadratic programming formulation and a mixed integer linear program are constructed, which aim to maximize the total value of chosen QC-profiles and yard costs. Hu et al. [17] construct a nonlinear multiobjective mixed integer programming model for integrating BAP and QCAP, which considers vessel fuel consumption and emissions. A second-order mixed integer cone programming model is adopted in solving the model.Meisel and Bierwirth [18] establish a framework for the integration of berth allocation, QC assignment and scheduling problem. The framework proceeds in three phases. Phase 1 calculates the crane productivity rates according to vessel stowage plans. Berthing times and positions as well as crane capacity assignments are determined in Phase 2. Finally, Phase 3 provides QC schedules. Turkogullari et al. [19] study the integration of berth allocation, QC assignment, and time-invariant QC scheduling problem (BACASP) such that the QCs assigned to each vessel stay at where they are until the vessel has been completed. First, they integrate the berth allocation and QC assignment problem (BACAP) in a binary integer linear programming model. In order to incorporate QC scheduling problem, they extend the BACAP and introduce a mixed integer linear programming model for the BACASP. Two algorithms are proposed to generate the optimal solution for the BACASP based on the optimal solution of BACAP. Considering the scenario where the number of QCs assigned to any vessel is allowed to vary during the processing of the vessel, Turkogullari et al. [20] build a mixed integer linear program to combine berth allocation, time-variant QC assignment and scheduling with consideration of QC setup cost owing to the movement between two working locations along the berth. They split it into a relaxed master problem and a subproblem and propose an exact solution algorithm by means of directed, layered, single source, and single sink network. The simulation results demonstrate that the algorithm may obtain optimal solutions for large-scale realistic problem instances.


## 2.2. Seaside Operations considering Tidal Impacts

Although seaside operations in container terminals have caught much interest in literature, there are only a few studies considering the influence of tide in the BAP problem. Most of these works consider the tide impact on the water depth along the berths. Barros et al. [3] investigate a BAP model with tidal time windows and stock level conditions in a tidal bulk port of Brazil. They present an integer linear programming model with homogeneous berths, which aims to minimize the overall demurrage in the planning horizon. A simulated-annealing-based algorithm (SA) is proposed to obtain good solutions. Xu et al. [4] study a discrete BAP model in both static and dynamic cases for container terminals in which the assignment of berths is limited by water depth due to tides. They assume that the time horizon is divided into only one high water period and one low water period. Qin et al. [7] address the BAP at a tidal river port in a more precise manner than [3, 4] by introducing time-varying draft constraints on vessel berthing based on each vessel’s draft and tide conditions of different berths. They build six integer programming models which are various combinations of three objectives (i.e., total weighted turnaround time, total weighted departure delay, and makespan) and two vessel arrival cases (i.e., static and dynamic). The models are then transformed into the innovative constraint programming counterparts. Lalla-Ruiz et al. [6] modify the model proposed in [4] to improve the feasibility of solutions based on the generalized Set Partitioning problem. Numerical experiments indicate that the computational efficiency is also improved significantly.Some other authors investigate the BAP problem with the impact of tide in the approach channel. Sheikholeslami et al. [5] take into consideration not only the tidal constraints in the approach channel but also the variations of water depth in different berths in the continuous dynamic berth allocation. A genetic algorithm combined with pattern search algorithm is proposed to solve the problem. Du et al. [2] develop two mathematical models to figure out the BAP in a tidal port, in which it takes into account the restriction of tides when vessels enter or leave the port through the approach channel. The first model aims to minimize the total departure delay of vessels, and the second model takes vessel arrival times as decision variables and takes the minimum weighted summation of departure delay and fuel consumption as the objective. The second-order cone programming technique is adopted to simplify the nonlinear complexity of the second model. Numerical simulations show that the second model can effectively mitigate the tidal impacts on container terminal operations and vessel emissions. To the best of our knowledge, there are no results on the BACASP problem where the influence of tides is involved. In this work we focus on the BACASP problem with time-variant QC scheduling and tidal impacts.


## 3. Problem Statement

We consider the integrated berth allocation, QC assignment, and time-variant QC scheduling problem with tide constraint and denote it as BACASP-TC as in [19, 20], where the notation TC denotes the factor of tide constraint. By reasonable discretization of the continuous berth and time horizon, we can treat the considered problem as a discrete optimization model. We discretize the planning time horizon into time steps 1,2,3,… with one hour per time step [15, 18–20]. Moreover, the continuous quay berth is partitioned into discretized segments with 50 meters per berth segment [15, 19–21]. Thus, the length li of vessel i can be measured by the number of required berth segments. For example, li=2 means it is of length equal to 100 meters. Considering the average productivity of one QC, we assume based on field investigation that any QC processes 30 containers in each hour. Together with the above time discretization method, we define a notationQC-time-step to measure the workload of a vessel such that one QC-time-step means a workload of 30 containers. For example, if vessel i is of workload ci=10, then it means there are 30×ci=300 containers to be handled for the vessel. Notice that if there are only 275 but not 300 containers to be processed for the vessel, we still set ci=10 since nine QC-time-steps can only satisfy 270 containers.We partition vessels into three types by their sizes, i.e., feeders, mediums, and jumbos, where feeders are of the smallest size while jumbos are of the largest size. Considering tidal impact, we assume that only jumbos aretide dependent; that is, these vessels can only pass through the approach channel in the duration of high water level. This constraint is enforced when jumbos are either approaching the quay berth for processing or leaving the quay after processing. The other two kinds of vessels, however, aretide independent and they can pass through the channel at any time step. It is assumed as in [2] that any vessel takes one time step to pass through the approach channel. The vessels arrive at the anchorage at various time points and can only pass through the channel on or after arrival. Considering tidal rule, we assume that there are high and low water level time windows alternatively, each of which consists of six consecutive time steps. It is assumed without loss of generality that the first six time steps are of high water level.For QC scheduling in processing any vessel, we consider the time-variant version in this work such that the number of QCs assigned to the same vessel can be different in two consecutive time steps. Compared with the time-invariant scenario where the set of QCs assigned to each vessel is predetermined and keeps unchanged during processing [16, 21–23], the time-variant QC scheduling fashion may improve the utilization of both QCs and berth segments. As all the QCs move on the same rail along the quay, their relative positions keep unchanged all the time. Moreover, any vessel stays still during its processing. Together with the fact that each QC is of width equal to about one berth segment length, it is reasonable to assume that at most one QC serving vessel i is allowed to leave for processing a neighbor vessel before completing vessel i at any time step.To illustrate the integrated berth and QC scheduling in the BACASP-TC problem, we give an example with 8 berth segments, 7 QCs, and 7 vessels, where vesselsV1,V2,V3, and V7 are of small sizes and tide independent, while V4,V5, and V6 are tide dependent. As shown in Figure 2, the vertical axis denotes the berth segments along the wharf, and the horizontal axis represents the time steps, which are divided into high water level time windows and low water level time windows. Each rectangle with solid borderlines stands for the processing duration and position of a vessel, denoted by Vi. The width of the rectangle denotes the processing time of the vessel, and the height represents its length. Each symbol Qj within a rectangle denotes the QC j assigned to the vessel at one time step. For example, the processing of tide-independent vessel V3 occupies berth segments 1 and 2. The vessel passes through the channel in the second time step, starts processing at the beginning of time step 3, and ends processing at the end of time step 6. It then leaves the wharf in time step 7. For QC scheduling, only QC1 processes V3 in time steps 3 and 4, while both QC1 and QC2 process the vessel in time steps 5 and 6. QC4 serves vessel V4 in time steps 5 and 6, but it moves to serve vessel V5 at time step 7, at which V4 is still on processing.Figure 2
An optimal solution of a BACASP-TC instance.Notice that it is not allowed for any two vessels that share the same processing berth segments to be of overlapped processing time steps, while this is not necessary for their setup times, i.e., time steps for entering or leaving the wharf. In Figure2, for example, both V3 and V5 share berth segments 1 and 2. V5 passes through the channel at time step 6 and starts processing at time step 7, while its preceding vessel V3 leaves the wharf at time step 7, which is later than the entering time of V5. When V5 arrives at the port at time step 6, it immediately enters into the channel taking advantage of the high water level and moors at berth segments 1 to 4 one time step later. After finishing processing at the end of time step 10, it vacates the berth segments at once and waits for two time steps to leave the quay at the beginning of the next high water time window. A similar waiting situation occurs for V6 between time step 7 and time step 13 before it enters the channel.There are some fundamental assumptions in the considered BACASP-TC problem as follows.(1)
The time horizon is divided into uniform time steps with one hour per time step, and the wharf is partitioned into equal-sized berth segments with 50 meters per segment.(2)
There are three types of vessels based on their respective lengths, where feeders and mediums are tide independent, while jumbos are tide dependent.(3)
By the tidal rule, in every 12 consecutive time steps or equally 12 hours, the first six time steps are in high water level, and the following six consecutive time steps are in low water level.(4)
It consumes exactly one time step for any vessel to pass through the approach channel.(5)
For any vessel being processed, the difference in the number of its assigned QCs in any two consecutive time steps is at most one.(6)
The setup time of QC, including its move along the berth line, is ignored.


## 4. Mathematical Formulation

In this section we establish an integer linear programming model for the BACASP-TC problem. We first present basic notations and then propose the mathematical model.


### 4.1. Notations

Sets (i)
I T I D E: set of tide-dependent vessels, and ITIDE=1,2,…,ITIDE. (ii)
I F R E E: set of tide-independent vessels, and IFREE=1,2,…,IFREE. (iii)
I: set of vessels, where I=ITIDE⋃IFREE and I=ITIDE+IFREE. (iv)
Q: set of QCs, and Q=1,2,3,…,Q. (v)
B: set of berth segments, and B=1,2,3,…,B. (vi)
N: set of high/low water time windows in the time horizon, and N=1,2,3,…,N. (vii)
T: set of time steps, and T=1,2,3,…,T with T=2NV, where V is the duration of a high (or low) water time window.Indices (i)
i , i ′: indices of vessels. (ii)
q , q ′: indices of QCs. (iii)
t , t ′: indices of time steps. (iv)
b , b ′: indices of berth segments. (v)
n: index of high/low water time windows.Input Parameters (i)
a i: arrival time of vessel i. (ii)
l i: length of vessel i, and it is measured in the number of berth segments. (iii)
c i: workload of vessel i, and it is measured in QC-time-step. (iv)
q i m i n: the minimum number of QCs required to be assigned to vessel i. (v)
q i m a x: the maximum number of QCs allowed to be assigned to vessel i. (vi)
V: duration of a high/low water time window. (vii)
C: the time for any vessel to pass through the approach channel, and C=1 time step. (viii)
M: a sufficiently large constant that is commonly used in describing linear inequality constraints.Decision Variables (i)
λ i: the time at which vessel i passes through the channel for processing. (ii)
ε i: the start time of processing vessel i. The vessel starts processing at the beginning of time step εi. (iii)
ρ i: the processing time of vessel i. (iv)
σ i: the end time of processing vessel i. The vessel completes processing at the end of time step σi. (v)
ψ i: the time at which vessel i passes through the channel and leaves the port. (vi)
ζ i: the departure time of vessel i, and ζi=ψi+C. (vii)
β i: the berth segment occupied by the stem of vessel i. (viii)
η q i t: (Binary) equal to 1 if QC q is assigned to vessel i in time step t, 0 otherwise.Auxiliary Decision Variables (i)
π i t: (binary) equal to 1 if vessel i starts processing at time step t; i.e., εi=t, 0 otherwise. (ii)
φ i t: (binary) equal to 1 if vessel i finishes processing at time step t; i.e., σi=t, 0 otherwise. (iii)
θ i t: (binary) equal to 1 if vessel i is moored and processed in time step t, 0 otherwise. (iv)
ω b i t: (binary) equal to 1 if the stem of vessel i is located at berth segment b in time step t, 0 otherwise. (v)
δ i i ′: (binary) equal to 1 if vessel i is moored below vessel i′; i.e., vessel i is moored at berth segments with indices smaller than those of vessel i′, 0 otherwise. See Figure 2 for illustration. (vi)
μ i n: (binary) equal to 1 if vessel i enters the approach channel to berth in the nth high water time window, 0 otherwise. (vii)
ν i n: (binary) equal to 1 if vessel i passes through the approach channel and leaves the port in the nth high water time window, 0 otherwise.


### 4.2. Formulation of the BACASP-TC

Objective Function. The objective function is to minimize the total turnaround time of vessels, which is one of the most studied objectives in literature [9–12]. (1)Minimize∑i∈Iζi-aiTidal Restriction Constraints (2) λ i ≥ a i ,  ∀ i ∈ I (3) ε i = λ i + C ,  ∀ i ∈ I (4) ψ i ≥ σ i ,  ∀ i ∈ I (5) ζ i = ψ i + C ,  ∀ i ∈ I (6) ∑ n ∈ N μ i n = 1 ,  ∀ i ∈ I T I D E (7) 2 n - 1 V + 1 - M 1 - μ i n ≤ λ i ≤ 2 n - 1 V + M 1 - μ i n ,  ∀ i ∈ I T I D E ,   ∀ n ∈ N (8) ∑ n ∈ N ν i n = 1 ,  ∀ i ∈ I T I D E (9) 2 n - 1 V + 1 - M 1 - ν i n ≤ ψ i ≤ 2 n - 1 V + M 1 - ν i n ,  ∀ i ∈ I T I D E ,   ∀ n ∈ NConstraint (2) ensures that any vessel cannot enter the approach channel before its arrival time. Constraint (3) indicates that any vessel must pass through the approach channel before starting processing. Constraint (4) guarantees that a vessel must pass through the approach channel for leaving the port after processing. Constraint (5) defines the leave time of any vessel. Constraints (6) to (9) ensure that a tide-dependent vessel passes through the approach channel within a high water time window for either berthing or leaving the port.Berth Allocation Constraints (10) ∑ t ∈ T π i t = 1 ,  ∀ i ∈ I (11) ∑ t ∈ T φ i t = 1 ,  ∀ i ∈ I (12) ε i = ∑ t ∈ T t π i t ,  ∀ i ∈ I (13) ρ i = ∑ t ∈ T θ i t ,  ∀ i ∈ I (14) σ i = ∑ t ∈ T t φ i t ,  ∀ i ∈ I (15) σ i = ε i + ρ i - 1 ,  ∀ i ∈ I (16) ∑ t ′ = 1 t - 1 θ i t ′ ≤ M 1 - π i t ,  ∀ i ∈ I ,   ∀ t ∈ 2 , T (17) ∑ t ′ = t + 1 T θ i t ′ ≤ M 1 - φ i t ,  ∀ i ∈ I ,   ∀ t ∈ 1 , T - 1 (18) θ i t ≥ 1 - M 1 - π i t ,  ∀ i ∈ I ,   ∀ t ∈ T (19) θ i t ′ + θ i , t - 1 - θ i t ≤ 1 ,  ∀ i ∈ I ,   ∀ t ∈ 2 , T ,   ∀ t ′ ∈ t + 1 , T (20) ∑ b ∈ B ω b i t = θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (21) β i ≥ ∑ b ∈ B b ω b i t - M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (22) β i ≤ ∑ b ∈ B b ω b i t + M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (23) ω b , i , t + 1 - ω b i t ≥ - M 2 - θ i , t + 1 - θ i t ,  ∀ i ∈ I ,   ∀ b ∈ B ,   ∀ t ∈ 1 , T - 1 (24) ω b , i , t + 1 - ω b i t ≤ M 2 - θ i , t + 1 - θ i t ,  ∀ i ∈ I ,   ∀ b ∈ B ,   ∀ t ∈ 1 , T - 1 (25) β i + l i - 1 ≤ B + M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (26) ∑ i ∈ I θ i t l i ≤ B ,  ∀ t ∈ T (27) ∑ b ′ = b - l i ′ + 1 b + l i - 1 ω b ′ , i ′ , t ≤ M 1 - ω b i t ,  ∀ i , i ′ ∈ I ,   i ≠ i ′ ,   ∀ t ∈ T ,   ∀ b ∈ l i ′ , B - l i + 1 (28) β i + l i ≤ β i ′ + M 1 - δ i i ′ ,  ∀ i , i ′ ∈ I ,   i ≠ i ′ (29) δ i i ′ + δ i ′ i ≤ 1 + M 2 - θ i t - θ i ′ t ,  ∀ i , i ′ ∈ I ,   ∀ t ∈ T ,   i ≠ i ′ (30) δ i i ′ + δ i ′ i ≥ 1 - M 2 - θ i t - θ i ′ t ,  ∀ i , i ′ ∈ I ,   ∀ t ∈ T ,   i ≠ i ′Constraints (10) and (11) state that each vessel starts or ends processing at a certain time step. Constraints (12) and (13) determine the processing start time of vessel i and its processing time, respectively. Constraints (14) and (15) determine the processing end time σi of vessel i. Constraints (16) and (17) guarantee that vessel i cannot be processed either before its berthing time or after its completion time. Constraint (18) ensures that vessel i starts processing once it has been berthed. Constraint (19) guarantees that the processing of any vessel cannot be interrupted. Constraint (20) states that when a vessel is on processing, its stem must be located at some berth segment. Constraints (21) and (22) determine the berth location of vessel i’s stem. Constraints (23) and (24) denote that vessel i stays still during processing. Constraint (25) shows that all the vessels must berth within the boundaries of the quay. Constraint (26) means that the total length of vessels being on processing is no more than the quay length at any time. Constraint (27) avoids the conflicting situation where two vessels occupy the same berth segments at any time step. Constraint (28) defines the variable δii′, which is equal to 1 if vessel i is moored at berth segments with indices smaller than those of vessel i′, 0 otherwise. Constraints (29) and (30) guarantee that only one of δii′ and δi′i equals 1.QC Scheduling Constraints (31) ∑ i ∈ I ∑ q ∈ Q η q i t ≤ Q ,  ∀ t ∈ T (32) ∑ t ∈ T ∑ q ∈ Q η q i t ≥ c i ,  ∀ i ∈ I (33) ∑ i ∈ I η q i t ≤ 1 ,  ∀ t ∈ T ,   ∀ q ∈ Q (34) ∑ q ∈ Q η q i t ≤ q i m a x + M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (35) ∑ q ∈ Q η q i t ≥ q i m i n - M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (36) ∑ q ∈ Q η q i t ≤ M θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (37) η q ′ i t + η q - 1 , i , t - η q i t ≤ 1 ,  ∀ i ∈ I ,   ∀ t ∈ T ,   ∀ q ∈ 2 , Q ,   ∀ q ′ ∈ q + 1 , Q (38) q < q ′ + M 3 - η q i t - η q ′ i ′ t - δ i i ′ ,  ∀ i , i ′ ∈ I ,   ∀ t ∈ T ,   ∀ q , q ′ ∈ Q ,   i ≠ i ′ ,   q ≠ q ′ (39) ∑ q ∈ Q η q i t - ∑ q ∈ Q η q i t ′ ≤ 1 + M 2 - θ i t - θ i t ′ ,  ∀ i ∈ I ,   ∀ t , t ′ ∈ T ,   t ≠ t ′ (40) ∑ q ∈ Q η q i t - ∑ q ∈ Q η q i t ′ ≥ - 1 + M 2 - θ i t - θ i t ′ ,  ∀ i ∈ I   , ∀ t , t ′ ∈ T ,   t ≠ t ′Constraint (31) guarantees that the total number of QCs assigned to vessels at any time cannot exceed the number of available QCs. Constraint (32) ensures that each vessel must complete its processing within the time horizon. Constraint (33) makes sure that each QC processes at most one vessel in any time step. Constraints (34) and (35) guarantee when vessel i is under processing, the number of QCs assigned to it must be within the range [qimin,qimax]. Constraint (36) states that any QC cannot be assigned to a vessel not being processed. Constraint (37) describes the constraint of QC scheduling such that if both QCs q+1 and q-1 are assigned to vessel i, then QC q must also be assigned to the vessel. Constraint (38) states the relative location consistence between QCs and the vessels being processed at any time. Constraints (39) and (40) ensure that for any two consecutive time steps, the difference on the number of QCs assigned to the same vessel is no more than one.Variable Constraints (41) λ i , ε i , ρ i , σ i , ψ i , ζ i , β i ∈ Z 0 + ,  ∀ i ∈ I (42) η q i t , π i t , φ i t , θ i t , ω b i t , δ i i ′ , μ i n , ν i n ∈ 0,1 ,  ∀ i , i ′ ∈ I ,   i ≠ i ′ ,   ∀ t ∈ T ,   ∀ b ∈ B ,   ∀ q ∈ Q ,   ∀ n ∈ N


## 4.1. Notations

Sets (i)
I T I D E: set of tide-dependent vessels, and ITIDE=1,2,…,ITIDE. (ii)
I F R E E: set of tide-independent vessels, and IFREE=1,2,…,IFREE. (iii)
I: set of vessels, where I=ITIDE⋃IFREE and I=ITIDE+IFREE. (iv)
Q: set of QCs, and Q=1,2,3,…,Q. (v)
B: set of berth segments, and B=1,2,3,…,B. (vi)
N: set of high/low water time windows in the time horizon, and N=1,2,3,…,N. (vii)
T: set of time steps, and T=1,2,3,…,T with T=2NV, where V is the duration of a high (or low) water time window.Indices (i)
i , i ′: indices of vessels. (ii)
q , q ′: indices of QCs. (iii)
t , t ′: indices of time steps. (iv)
b , b ′: indices of berth segments. (v)
n: index of high/low water time windows.Input Parameters (i)
a i: arrival time of vessel i. (ii)
l i: length of vessel i, and it is measured in the number of berth segments. (iii)
c i: workload of vessel i, and it is measured in QC-time-step. (iv)
q i m i n: the minimum number of QCs required to be assigned to vessel i. (v)
q i m a x: the maximum number of QCs allowed to be assigned to vessel i. (vi)
V: duration of a high/low water time window. (vii)
C: the time for any vessel to pass through the approach channel, and C=1 time step. (viii)
M: a sufficiently large constant that is commonly used in describing linear inequality constraints.Decision Variables (i)
λ i: the time at which vessel i passes through the channel for processing. (ii)
ε i: the start time of processing vessel i. The vessel starts processing at the beginning of time step εi. (iii)
ρ i: the processing time of vessel i. (iv)
σ i: the end time of processing vessel i. The vessel completes processing at the end of time step σi. (v)
ψ i: the time at which vessel i passes through the channel and leaves the port. (vi)
ζ i: the departure time of vessel i, and ζi=ψi+C. (vii)
β i: the berth segment occupied by the stem of vessel i. (viii)
η q i t: (Binary) equal to 1 if QC q is assigned to vessel i in time step t, 0 otherwise.Auxiliary Decision Variables (i)
π i t: (binary) equal to 1 if vessel i starts processing at time step t; i.e., εi=t, 0 otherwise. (ii)
φ i t: (binary) equal to 1 if vessel i finishes processing at time step t; i.e., σi=t, 0 otherwise. (iii)
θ i t: (binary) equal to 1 if vessel i is moored and processed in time step t, 0 otherwise. (iv)
ω b i t: (binary) equal to 1 if the stem of vessel i is located at berth segment b in time step t, 0 otherwise. (v)
δ i i ′: (binary) equal to 1 if vessel i is moored below vessel i′; i.e., vessel i is moored at berth segments with indices smaller than those of vessel i′, 0 otherwise. See Figure 2 for illustration. (vi)
μ i n: (binary) equal to 1 if vessel i enters the approach channel to berth in the nth high water time window, 0 otherwise. (vii)
ν i n: (binary) equal to 1 if vessel i passes through the approach channel and leaves the port in the nth high water time window, 0 otherwise.


## 4.2. Formulation of the BACASP-TC

Objective Function. The objective function is to minimize the total turnaround time of vessels, which is one of the most studied objectives in literature [9–12]. (1)Minimize∑i∈Iζi-aiTidal Restriction Constraints (2) λ i ≥ a i ,  ∀ i ∈ I (3) ε i = λ i + C ,  ∀ i ∈ I (4) ψ i ≥ σ i ,  ∀ i ∈ I (5) ζ i = ψ i + C ,  ∀ i ∈ I (6) ∑ n ∈ N μ i n = 1 ,  ∀ i ∈ I T I D E (7) 2 n - 1 V + 1 - M 1 - μ i n ≤ λ i ≤ 2 n - 1 V + M 1 - μ i n ,  ∀ i ∈ I T I D E ,   ∀ n ∈ N (8) ∑ n ∈ N ν i n = 1 ,  ∀ i ∈ I T I D E (9) 2 n - 1 V + 1 - M 1 - ν i n ≤ ψ i ≤ 2 n - 1 V + M 1 - ν i n ,  ∀ i ∈ I T I D E ,   ∀ n ∈ NConstraint (2) ensures that any vessel cannot enter the approach channel before its arrival time. Constraint (3) indicates that any vessel must pass through the approach channel before starting processing. Constraint (4) guarantees that a vessel must pass through the approach channel for leaving the port after processing. Constraint (5) defines the leave time of any vessel. Constraints (6) to (9) ensure that a tide-dependent vessel passes through the approach channel within a high water time window for either berthing or leaving the port.Berth Allocation Constraints (10) ∑ t ∈ T π i t = 1 ,  ∀ i ∈ I (11) ∑ t ∈ T φ i t = 1 ,  ∀ i ∈ I (12) ε i = ∑ t ∈ T t π i t ,  ∀ i ∈ I (13) ρ i = ∑ t ∈ T θ i t ,  ∀ i ∈ I (14) σ i = ∑ t ∈ T t φ i t ,  ∀ i ∈ I (15) σ i = ε i + ρ i - 1 ,  ∀ i ∈ I (16) ∑ t ′ = 1 t - 1 θ i t ′ ≤ M 1 - π i t ,  ∀ i ∈ I ,   ∀ t ∈ 2 , T (17) ∑ t ′ = t + 1 T θ i t ′ ≤ M 1 - φ i t ,  ∀ i ∈ I ,   ∀ t ∈ 1 , T - 1 (18) θ i t ≥ 1 - M 1 - π i t ,  ∀ i ∈ I ,   ∀ t ∈ T (19) θ i t ′ + θ i , t - 1 - θ i t ≤ 1 ,  ∀ i ∈ I ,   ∀ t ∈ 2 , T ,   ∀ t ′ ∈ t + 1 , T (20) ∑ b ∈ B ω b i t = θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (21) β i ≥ ∑ b ∈ B b ω b i t - M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (22) β i ≤ ∑ b ∈ B b ω b i t + M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (23) ω b , i , t + 1 - ω b i t ≥ - M 2 - θ i , t + 1 - θ i t ,  ∀ i ∈ I ,   ∀ b ∈ B ,   ∀ t ∈ 1 , T - 1 (24) ω b , i , t + 1 - ω b i t ≤ M 2 - θ i , t + 1 - θ i t ,  ∀ i ∈ I ,   ∀ b ∈ B ,   ∀ t ∈ 1 , T - 1 (25) β i + l i - 1 ≤ B + M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (26) ∑ i ∈ I θ i t l i ≤ B ,  ∀ t ∈ T (27) ∑ b ′ = b - l i ′ + 1 b + l i - 1 ω b ′ , i ′ , t ≤ M 1 - ω b i t ,  ∀ i , i ′ ∈ I ,   i ≠ i ′ ,   ∀ t ∈ T ,   ∀ b ∈ l i ′ , B - l i + 1 (28) β i + l i ≤ β i ′ + M 1 - δ i i ′ ,  ∀ i , i ′ ∈ I ,   i ≠ i ′ (29) δ i i ′ + δ i ′ i ≤ 1 + M 2 - θ i t - θ i ′ t ,  ∀ i , i ′ ∈ I ,   ∀ t ∈ T ,   i ≠ i ′ (30) δ i i ′ + δ i ′ i ≥ 1 - M 2 - θ i t - θ i ′ t ,  ∀ i , i ′ ∈ I ,   ∀ t ∈ T ,   i ≠ i ′Constraints (10) and (11) state that each vessel starts or ends processing at a certain time step. Constraints (12) and (13) determine the processing start time of vessel i and its processing time, respectively. Constraints (14) and (15) determine the processing end time σi of vessel i. Constraints (16) and (17) guarantee that vessel i cannot be processed either before its berthing time or after its completion time. Constraint (18) ensures that vessel i starts processing once it has been berthed. Constraint (19) guarantees that the processing of any vessel cannot be interrupted. Constraint (20) states that when a vessel is on processing, its stem must be located at some berth segment. Constraints (21) and (22) determine the berth location of vessel i’s stem. Constraints (23) and (24) denote that vessel i stays still during processing. Constraint (25) shows that all the vessels must berth within the boundaries of the quay. Constraint (26) means that the total length of vessels being on processing is no more than the quay length at any time. Constraint (27) avoids the conflicting situation where two vessels occupy the same berth segments at any time step. Constraint (28) defines the variable δii′, which is equal to 1 if vessel i is moored at berth segments with indices smaller than those of vessel i′, 0 otherwise. Constraints (29) and (30) guarantee that only one of δii′ and δi′i equals 1.QC Scheduling Constraints (31) ∑ i ∈ I ∑ q ∈ Q η q i t ≤ Q ,  ∀ t ∈ T (32) ∑ t ∈ T ∑ q ∈ Q η q i t ≥ c i ,  ∀ i ∈ I (33) ∑ i ∈ I η q i t ≤ 1 ,  ∀ t ∈ T ,   ∀ q ∈ Q (34) ∑ q ∈ Q η q i t ≤ q i m a x + M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (35) ∑ q ∈ Q η q i t ≥ q i m i n - M 1 - θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (36) ∑ q ∈ Q η q i t ≤ M θ i t ,  ∀ i ∈ I ,   ∀ t ∈ T (37) η q ′ i t + η q - 1 , i , t - η q i t ≤ 1 ,  ∀ i ∈ I ,   ∀ t ∈ T ,   ∀ q ∈ 2 , Q ,   ∀ q ′ ∈ q + 1 , Q (38) q < q ′ + M 3 - η q i t - η q ′ i ′ t - δ i i ′ ,  ∀ i , i ′ ∈ I ,   ∀ t ∈ T ,   ∀ q , q ′ ∈ Q ,   i ≠ i ′ ,   q ≠ q ′ (39) ∑ q ∈ Q η q i t - ∑ q ∈ Q η q i t ′ ≤ 1 + M 2 - θ i t - θ i t ′ ,  ∀ i ∈ I ,   ∀ t , t ′ ∈ T ,   t ≠ t ′ (40) ∑ q ∈ Q η q i t - ∑ q ∈ Q η q i t ′ ≥ - 1 + M 2 - θ i t - θ i t ′ ,  ∀ i ∈ I   , ∀ t , t ′ ∈ T ,   t ≠ t ′Constraint (31) guarantees that the total number of QCs assigned to vessels at any time cannot exceed the number of available QCs. Constraint (32) ensures that each vessel must complete its processing within the time horizon. Constraint (33) makes sure that each QC processes at most one vessel in any time step. Constraints (34) and (35) guarantee when vessel i is under processing, the number of QCs assigned to it must be within the range [qimin,qimax]. Constraint (36) states that any QC cannot be assigned to a vessel not being processed. Constraint (37) describes the constraint of QC scheduling such that if both QCs q+1 and q-1 are assigned to vessel i, then QC q must also be assigned to the vessel. Constraint (38) states the relative location consistence between QCs and the vessels being processed at any time. Constraints (39) and (40) ensure that for any two consecutive time steps, the difference on the number of QCs assigned to the same vessel is no more than one.Variable Constraints (41) λ i , ε i , ρ i , σ i , ψ i , ζ i , β i ∈ Z 0 + ,  ∀ i ∈ I (42) η q i t , π i t , φ i t , θ i t , ω b i t , δ i i ′ , μ i n , ν i n ∈ 0,1 ,  ∀ i , i ′ ∈ I ,   i ≠ i ′ ,   ∀ t ∈ T ,   ∀ b ∈ B ,   ∀ q ∈ Q ,   ∀ n ∈ N


## 5. Solution Algorithms

As the BAP is NP-hard [24], the NP-hardness of the BACASP-TC problem is straightforward. For small instances, it can be solved by CPLEX or LINGO solver, in which the branch and cut algorithm is mainly employed. In practice, however, the problem cannot be solved by the exact algorithm within a reasonable time due to its large input scale. Hence, we employ heuristic algorithms to solve the BACASP-TC problem with large instances. Heuristic algorithms are to seek near-optimal solutions for optimization problems, especially in the cases with large inputs. We propose three heuristic algorithms, Genetic Algorithm (GA), Hybrid Particle Swarm Optimization (HPSO), and Hybrid Simulated Annealing (HSA) below.


### 5.1. Solution Representation

In implementing the three heuristics, the first step is to code any solution. We use an integer code scheme such that the code consists of|I| subsections, corresponding to the |I| vessels, respectively. Each subsection comprises two codes. The first code denotes the index of a vessel, and the position of the index in the code sequence represents the order of vessel berthing or processing. The second code indicates the processing time of the vessel. First, we randomly generate a vessel processing sequence. We also calculate the minimum possible processing time ρimin and the maximum possible processing time ρimax for vessel i, where ρimin=ci/qimax and ρimax=ci/qimin. A random value within interval [ρimin,ρimax] is then generated as the preset processing time. A code representation for an instance with six vessels is depicted in Figure 3. Notice that QC scheduling is not included in the code, which will be elaborated in Section 5.2.Figure 3
A solution representation for an instance with six vessels.


### 5.2. Objective Value Calculation

The objective function value is used to evaluate the quality of a solution produced by any heuristic algorithm. Below we present a specific method in three steps to calculate the objective value of any given solution.Step 1.
Determine the berthing location and the time with tidal constraints in the approach channel for each vessel by Algorithm1 to be described later.Algorithm 1:The greedy heuristic for BAP.
Input: A solution representation; Output: The berthing position βi and the processing start time εi for each vessel i; (1) Initialize  Vberthed=∅; // Set of berthed vessels; (2) for  j=1:I  do (3)  Let i be the index of the vessel whose berthing order in the solution representation is j; (4) Initialize  berthed=false,yrec=0,tienter=0; // tienter is the earliest time for vessel i to enter the approach channel; (5) if  vessel  i∈ITIDE  then (6)  Let tienter be the earliest time step in high water time windows, which is greater than or equal to ai; (7) else (8) tienter=ai; (9) end (10) xrec=tienter+C; (11) recti=(xrec,yrec,ρi,li); // recti is the rectangle in the time-wharf plan, which represents the schedule of vessel i; (12) Search the possible locations for recti and sort them in the ascending order using the time-coordinate as the primary key and the wharf-coordinate as the secondary key; (13) while  berthed==false  do (14) if  (i∈IFREE, andrectidoes not overlap with any rectangle inVberthedand is within the boundary of the time-wharf plan) or ( i ∈ I T I D E , the time-coordinate of the bottom-left corner of r e c t i is in high water time window, and r e c t i does not overlap with any rectangle in V b e r t h e d and is within the boundary of the time-wharf plan) then (15) εi=xrec,βi=yrec; (16) Vberthed=vi∪Vberthed; (17) berthed=true; (18)  break; (19) else (20) Move  recti to the next possible location and update  xrec and yrec; (21) if  there is no more candidate for possible location ofrecti  then (22) βi=0; (23)  let εi=t-+C where t- is the first time step in the next high water time window; (24) Vberthed=vi∪Vberthed; (25) berthed=true; (26) end (27) end (28) end (29) endStep 2.
Assign QCs to vessels in every time step by Algorithm2, as shown later on.Algorithm 2:The greedy heuristic for time-variant QC scheduling.
Input: The berthing position βi and the processing start time εi; Output: The time-variant QC scheduling for vessels and the assignment feasibility f; (1) Initialize f=true; (2) for  t=1:|T|  do (3) Initialize distrt,1=∅, distrt,2=0, distrt,3=∅; (4)for  i=1:|I|  do (5) if  vessel i is being processed in time step t  then (6) distr{t,1}={i}∪distr{t,1}; (7) distr{t,2}=distr{t,2}+1; (8) end (9) end (10) end (11) for  t=1:|T|  do (12) sum=0,avg=∅,percnt=∅; (13) for  j=1:distr{t,2}  do (14) i=distr{t,1}(j); (15) if  vesselistarts processing at time step  t  then (16) remainicon=ci; (17) remainitim=ρi; // ρi is the preseted processing time for vessel i in the solution representation; (18) end (19) avgj=remainiconremainitim; (20) sum=sum+avgj; (21) end (22) for  j=1:distr{t,2}  do (23) i=distrt,1j; (24) percntj=avgjsum; (25) distrt,3j=roundQ∗percntj; (26) if  distr{t,3}(j)<qimin  then (27) distr{t,3}(j)=qimin; (28) end (29) if  distr{t,3}(j)>qimax  then (30) distrt,3j=qimax; (31) end (32)  Adjust distr{t,3}(j) to satisfy Constraints (39) and (40); (33) remainicon=remainicon-distr{t,3}(j),remainitim=remainitim-1; (34) if  remainitim==0  and  remainicon>0  then (35) f=false; (36)  break; (37) end (38) end (39) endStep 3.
If the assignment of QCs for vessels in Step2 is feasible (i.e., f=True), then calculate the objective value obj of the solution where obj=∑i∈I‍(ζi-ai); otherwise, set obj as a sufficiently large constant M such as 10000, implying that the solution is unreasonable and is to be eliminated during calculation iterations of the heuristics. As the considered BACASP-TC problem is of a minimization objective and the heuristics take the reciprocal of the objective value obj of a solution as its fitness value, so a solution with a larger objective value is more likely to be eliminated in the evolution process of any heuristic algorithm.After the coding process in Section5.1, a simple and preliminary scheduling scheme for the BACASP-TC problem is presented, where it includes the vessel berthing sequence and the processing times of vessels. The two algorithms, Algorithms 1 and 2, determine the berthing locations, the processing start times of vessels, and QC scheduling.In Algorithm1, a greedy heuristic method is constructed to assign berthing locations and start times of processing vessels with the tidal constraint, based on the bottom-left bin-packing heuristic in [25]. First, according to a vessel’s preset processing time in the solution together with its length, both the width and height of the rectangle can be determined, as shown in Figure 4. Secondly, the rectangle is to be placed in the time-wharf plan, where point (tienter+C,0) is set as the original possible location. In Figure 4(a), the original possible location for processing vessel 6 is point 1. The rest four possible locations are determined from bottom to top and from left to right. Next, the feasibility of placing vessel 6 is verified from point 1 to 5, according to the conditions in Line 14 of Algorithm 1. If vessel 6 is tide independent, it is placed in point 4, i.e., rectangle (1) in Figure 4(b). If otherwise vessel 6 is tide dependent, then all the five points are verified infeasible and the location of the vessel is to be determined by Lines 22 to 25 of Algorithm 1. In this case, the rectangle (2) in Figure 4(b) is the final location of vessel 6. Note that vessel 6 starts processing at time step 14 but not 13, because it takes one time step to pass through the approach channel in the high water time window.Figure 4
Illustration of possible locations for processing vesselV6.
(a) (b)After determining the vessel berthing locations and processing start times, we employ Algorithm2 to obtain the time-variant QC scheduling for vessels and check the assignment feasibility as well. According to the schedule of vessels from Algorithm 1, the specific berthed vessels and the number of vessels being processed in each time step t are determined and stored in sets distrt,1 and distrt,2, respectively. The algorithm greedily assigns QCs to the vessels in each time step based on the proportions of their average workloads. The numbers of QCs assigned to the vessels in set distrt,1 at each time step are placed in set distrt,3. If there is any vessel uncompleted in its preset processing time steps, it implies that the assignment of vessel location and the QC scheduling are infeasible. In this case the corresponding solution will be discarded in the iterations of the three heuristics. To better understand Algorithm 2, the process of solving the example in Figure 2 is given in Table 1, where the workloads of vessels 1 to 7 are equal to 9, 9, 5, 14, 14, 15, and 11 QC-time-steps, respectively. In time step 1 or the first row of Table 1, there is no vessel on processing and all the columns are of initial values ∅ or 0. In time step 2 or the second row, the numbers in the sixth column distrt,1 mean that vessels 1 and 2 start their processing. Columns remainicon and remainitim show their original workloads 9,9 and preset processing time steps in the solution representation 3,3. So, column avg gives their average workloads 3,3 in the three time steps, and the resulting proportions 0.5,0.5 between the two vessels are given in column percnt. In column distrt,3, the original allocated QC numbers (4,4), as given in the brackets, for the two vessels are out of their allowed ranges. Thus they are replaced with their nearest available numbers 3,3 of allocated QCs. That is, if the original allocated QC number for any vessel in distrt,1 is smaller (or larger) than its lower (or upper) bound of allocated QC number, then the number is replaced by the lower (or upper) bound. The remaining rows of the table can be similarly explained as in the second row.Table 1
An example for Algorithm2.
t remainicon remainitim avg percnt distrt,1 distrt,2 d i s t r t , 3 1 ∅ ∅ ∅ ∅ ∅ 0 ∅ 2 9,9 3,3 3,3 0.5,0.5 1,2 2 3,3   ( 4,4 ) 3 6,6 , 5 2,2 , 4 3,3 , 1.25 0.41,0.41,0.17 1,2 , 3 3 3,3 , 1 4 3,3 , 4 1,1 , 3 3,3 , 1.33 0.41,0.41,0.18 1,2 , 3 3 3,3 , 1 5 3,14 2,4 1.5,3.5 0.3,0.7 3,4 2 2,4   ( 2,5 ) 6 1,10 1,3 1,3.33 0.23,0.77 3,4 2 2,4   ( 2,5 ) 7 6,14 2,4 3,3.5 0.46,0.54 4,5 2 3,4 8 3,10 1,3 3,3.33 0.47,0.53 4,5 2 3,4 9 6,11 2,4 3,2.75 0.52,0.48 5,7 2 4,3 10 2,8 1,3 2,2.67 0.43,0.57 5,7 2 3,3   ( 3,4 ) 11 5 2 2.5 1 7 1 3   ( 7 ) 12 2 1 2 1 7 1 3   ( 7 ) 13 ∅ ∅ ∅ ∅ ∅ 0 ∅ 14 15 3 5 1 6 1 5   ( 7 ) 15 10 2 5 1 6 1 5   ( 7 ) 16 5 1 5 1 6 1 5   ( 7 )The above two greedy algorithms decode a solution of BACASP-TC and calculate the objective function value. Next we propose three heuristic algorithms, Genetic Algorithm (GA), Hybrid Particle Swarm Optimization (HPSO), and Hybrid Simulated Annealing (HSA) to produce optimal or near-optimal solutions for large instances. We only present the frameworks of the three heuristics due to page limitation. For details of the heuristics, readers may refer to [26–28].


### 5.3. Genetic Algorithm

Genetic Algorithm (GA) is a method for tackling both constrained and unconstrained optimization problems by mimicking biological evolution in a natural selection process. Since its first introduction by Holland in 1975 [29], GA has demonstrated its broad applicability in many areas. In this paper, we apply GA to solve BAP and QCSP simultaneously. It generates an initial population of solutions or chromosomes and then repeatedly generates offspring generations by a series of bioinspired operations including selection, crossover, and mutation, which are adopted from [30]. In each evolution, Algorithms 1 and 2 are adopted to calculate the objective values as well as fitness values of individual solutions. Solutions with high fitness values are selected to form the population in the next generation. The flow chart of GA is depicted in Figure 5.Figure 5
Flowchart of GA.


### 5.4. Hybrid Particle Swarm Optimization Algorithm

Particle Swarm Optimization (PSO) is inspired by social behavior of bird flocking or fish schooling. The algorithm is carried out by means of a swarm of candidate solutions or particles. According to some rules, these particles move around in the search space. The movements of the particles are guided by their own best known positions in the search space as well as the entire swarm’s best known position. As illustrated in Figure6, the proposed Hybrid PSO (HPSO) initializes a set of particles with their original locations Xi and objective function values f(Xi) in the solving space. The original locations Xi of particles are taken as their initial individual best locations Pbesti. Among the original locations of particles, the one that has the smallest objective function value is selected as the population best location Gbest. In order to seek a better location or solution, each particle location needs crossover and mutation with its own previous best location Pbesti and the population previous best location Gbest, respectively. The crossover and mutation evolution operators are from the GA in the above subsection. After moving to the new location, each particle updates its Pbesti, provided that the objective function value of its new location is less than the objective function value of its Pbesti. Likewise, update the Gbest if the objective function value of its new location is less than the objective function value of Gbest. By repeating the above process, a satisfying solution is eventually obtained.Figure 6
Flowchart of HPSO.


### 5.5. Hybrid Simulated Annealing Algorithm

The inspiration of simulated annealing (SA) algorithm comes from metallurgical annealing process, and it is first applied to the field of combinatorial optimization by Kirkpatrick et al. [31]. SA initializes with a solution X1 at a high temperature T=T0, and the temperature T gradually drops to a set value Tend at a certain rate q. At each temperature T, the algorithm generates a new solution X2 and measures its quality Y2. If the new solution X2 is better than the current X1, X1 is replaced by X2. Otherwise, whether the current solution X1 is replaced or not depends on a probability that is progressively decreased with the reducing of temperature T. The above operations are repeated for specified times that is called chain length L at every temperature T. This algorithm can effectively avoid being trapped in local minima and is able to explore globally for optimal solutions. In this work the Hybrid SA (HSA) combines the search mechanism of simulated annealing algorithm with genetic operators such as crossover and mutation when a new solution is generated. The flow chart of HSA is given in Figure 7.Figure 7
Flowchart of HSA.


## 5.1. Solution Representation

In implementing the three heuristics, the first step is to code any solution. We use an integer code scheme such that the code consists of|I| subsections, corresponding to the |I| vessels, respectively. Each subsection comprises two codes. The first code denotes the index of a vessel, and the position of the index in the code sequence represents the order of vessel berthing or processing. The second code indicates the processing time of the vessel. First, we randomly generate a vessel processing sequence. We also calculate the minimum possible processing time ρimin and the maximum possible processing time ρimax for vessel i, where ρimin=ci/qimax and ρimax=ci/qimin. A random value within interval [ρimin,ρimax] is then generated as the preset processing time. A code representation for an instance with six vessels is depicted in Figure 3. Notice that QC scheduling is not included in the code, which will be elaborated in Section 5.2.Figure 3
A solution representation for an instance with six vessels.


## 5.2. Objective Value Calculation

The objective function value is used to evaluate the quality of a solution produced by any heuristic algorithm. Below we present a specific method in three steps to calculate the objective value of any given solution.Step 1.
Determine the berthing location and the time with tidal constraints in the approach channel for each vessel by Algorithm1 to be described later.Algorithm 1:The greedy heuristic for BAP.
Input: A solution representation; Output: The berthing position βi and the processing start time εi for each vessel i; (1) Initialize  Vberthed=∅; // Set of berthed vessels; (2) for  j=1:I  do (3)  Let i be the index of the vessel whose berthing order in the solution representation is j; (4) Initialize  berthed=false,yrec=0,tienter=0; // tienter is the earliest time for vessel i to enter the approach channel; (5) if  vessel  i∈ITIDE  then (6)  Let tienter be the earliest time step in high water time windows, which is greater than or equal to ai; (7) else (8) tienter=ai; (9) end (10) xrec=tienter+C; (11) recti=(xrec,yrec,ρi,li); // recti is the rectangle in the time-wharf plan, which represents the schedule of vessel i; (12) Search the possible locations for recti and sort them in the ascending order using the time-coordinate as the primary key and the wharf-coordinate as the secondary key; (13) while  berthed==false  do (14) if  (i∈IFREE, andrectidoes not overlap with any rectangle inVberthedand is within the boundary of the time-wharf plan) or ( i ∈ I T I D E , the time-coordinate of the bottom-left corner of r e c t i is in high water time window, and r e c t i does not overlap with any rectangle in V b e r t h e d and is within the boundary of the time-wharf plan) then (15) εi=xrec,βi=yrec; (16) Vberthed=vi∪Vberthed; (17) berthed=true; (18)  break; (19) else (20) Move  recti to the next possible location and update  xrec and yrec; (21) if  there is no more candidate for possible location ofrecti  then (22) βi=0; (23)  let εi=t-+C where t- is the first time step in the next high water time window; (24) Vberthed=vi∪Vberthed; (25) berthed=true; (26) end (27) end (28) end (29) endStep 2.
Assign QCs to vessels in every time step by Algorithm2, as shown later on.Algorithm 2:The greedy heuristic for time-variant QC scheduling.
Input: The berthing position βi and the processing start time εi; Output: The time-variant QC scheduling for vessels and the assignment feasibility f; (1) Initialize f=true; (2) for  t=1:|T|  do (3) Initialize distrt,1=∅, distrt,2=0, distrt,3=∅; (4)for  i=1:|I|  do (5) if  vessel i is being processed in time step t  then (6) distr{t,1}={i}∪distr{t,1}; (7) distr{t,2}=distr{t,2}+1; (8) end (9) end (10) end (11) for  t=1:|T|  do (12) sum=0,avg=∅,percnt=∅; (13) for  j=1:distr{t,2}  do (14) i=distr{t,1}(j); (15) if  vesselistarts processing at time step  t  then (16) remainicon=ci; (17) remainitim=ρi; // ρi is the preseted processing time for vessel i in the solution representation; (18) end (19) avgj=remainiconremainitim; (20) sum=sum+avgj; (21) end (22) for  j=1:distr{t,2}  do (23) i=distrt,1j; (24) percntj=avgjsum; (25) distrt,3j=roundQ∗percntj; (26) if  distr{t,3}(j)<qimin  then (27) distr{t,3}(j)=qimin; (28) end (29) if  distr{t,3}(j)>qimax  then (30) distrt,3j=qimax; (31) end (32)  Adjust distr{t,3}(j) to satisfy Constraints (39) and (40); (33) remainicon=remainicon-distr{t,3}(j),remainitim=remainitim-1; (34) if  remainitim==0  and  remainicon>0  then (35) f=false; (36)  break; (37) end (38) end (39) endStep 3.
If the assignment of QCs for vessels in Step2 is feasible (i.e., f=True), then calculate the objective value obj of the solution where obj=∑i∈I‍(ζi-ai); otherwise, set obj as a sufficiently large constant M such as 10000, implying that the solution is unreasonable and is to be eliminated during calculation iterations of the heuristics. As the considered BACASP-TC problem is of a minimization objective and the heuristics take the reciprocal of the objective value obj of a solution as its fitness value, so a solution with a larger objective value is more likely to be eliminated in the evolution process of any heuristic algorithm.After the coding process in Section5.1, a simple and preliminary scheduling scheme for the BACASP-TC problem is presented, where it includes the vessel berthing sequence and the processing times of vessels. The two algorithms, Algorithms 1 and 2, determine the berthing locations, the processing start times of vessels, and QC scheduling.In Algorithm1, a greedy heuristic method is constructed to assign berthing locations and start times of processing vessels with the tidal constraint, based on the bottom-left bin-packing heuristic in [25]. First, according to a vessel’s preset processing time in the solution together with its length, both the width and height of the rectangle can be determined, as shown in Figure 4. Secondly, the rectangle is to be placed in the time-wharf plan, where point (tienter+C,0) is set as the original possible location. In Figure 4(a), the original possible location for processing vessel 6 is point 1. The rest four possible locations are determined from bottom to top and from left to right. Next, the feasibility of placing vessel 6 is verified from point 1 to 5, according to the conditions in Line 14 of Algorithm 1. If vessel 6 is tide independent, it is placed in point 4, i.e., rectangle (1) in Figure 4(b). If otherwise vessel 6 is tide dependent, then all the five points are verified infeasible and the location of the vessel is to be determined by Lines 22 to 25 of Algorithm 1. In this case, the rectangle (2) in Figure 4(b) is the final location of vessel 6. Note that vessel 6 starts processing at time step 14 but not 13, because it takes one time step to pass through the approach channel in the high water time window.Figure 4
Illustration of possible locations for processing vesselV6.
(a) (b)After determining the vessel berthing locations and processing start times, we employ Algorithm2 to obtain the time-variant QC scheduling for vessels and check the assignment feasibility as well. According to the schedule of vessels from Algorithm 1, the specific berthed vessels and the number of vessels being processed in each time step t are determined and stored in sets distrt,1 and distrt,2, respectively. The algorithm greedily assigns QCs to the vessels in each time step based on the proportions of their average workloads. The numbers of QCs assigned to the vessels in set distrt,1 at each time step are placed in set distrt,3. If there is any vessel uncompleted in its preset processing time steps, it implies that the assignment of vessel location and the QC scheduling are infeasible. In this case the corresponding solution will be discarded in the iterations of the three heuristics. To better understand Algorithm 2, the process of solving the example in Figure 2 is given in Table 1, where the workloads of vessels 1 to 7 are equal to 9, 9, 5, 14, 14, 15, and 11 QC-time-steps, respectively. In time step 1 or the first row of Table 1, there is no vessel on processing and all the columns are of initial values ∅ or 0. In time step 2 or the second row, the numbers in the sixth column distrt,1 mean that vessels 1 and 2 start their processing. Columns remainicon and remainitim show their original workloads 9,9 and preset processing time steps in the solution representation 3,3. So, column avg gives their average workloads 3,3 in the three time steps, and the resulting proportions 0.5,0.5 between the two vessels are given in column percnt. In column distrt,3, the original allocated QC numbers (4,4), as given in the brackets, for the two vessels are out of their allowed ranges. Thus they are replaced with their nearest available numbers 3,3 of allocated QCs. That is, if the original allocated QC number for any vessel in distrt,1 is smaller (or larger) than its lower (or upper) bound of allocated QC number, then the number is replaced by the lower (or upper) bound. The remaining rows of the table can be similarly explained as in the second row.Table 1
An example for Algorithm2.
t remainicon remainitim avg percnt distrt,1 distrt,2 d i s t r t , 3 1 ∅ ∅ ∅ ∅ ∅ 0 ∅ 2 9,9 3,3 3,3 0.5,0.5 1,2 2 3,3   ( 4,4 ) 3 6,6 , 5 2,2 , 4 3,3 , 1.25 0.41,0.41,0.17 1,2 , 3 3 3,3 , 1 4 3,3 , 4 1,1 , 3 3,3 , 1.33 0.41,0.41,0.18 1,2 , 3 3 3,3 , 1 5 3,14 2,4 1.5,3.5 0.3,0.7 3,4 2 2,4   ( 2,5 ) 6 1,10 1,3 1,3.33 0.23,0.77 3,4 2 2,4   ( 2,5 ) 7 6,14 2,4 3,3.5 0.46,0.54 4,5 2 3,4 8 3,10 1,3 3,3.33 0.47,0.53 4,5 2 3,4 9 6,11 2,4 3,2.75 0.52,0.48 5,7 2 4,3 10 2,8 1,3 2,2.67 0.43,0.57 5,7 2 3,3   ( 3,4 ) 11 5 2 2.5 1 7 1 3   ( 7 ) 12 2 1 2 1 7 1 3   ( 7 ) 13 ∅ ∅ ∅ ∅ ∅ 0 ∅ 14 15 3 5 1 6 1 5   ( 7 ) 15 10 2 5 1 6 1 5   ( 7 ) 16 5 1 5 1 6 1 5   ( 7 )The above two greedy algorithms decode a solution of BACASP-TC and calculate the objective function value. Next we propose three heuristic algorithms, Genetic Algorithm (GA), Hybrid Particle Swarm Optimization (HPSO), and Hybrid Simulated Annealing (HSA) to produce optimal or near-optimal solutions for large instances. We only present the frameworks of the three heuristics due to page limitation. For details of the heuristics, readers may refer to [26–28].


## 5.3. Genetic Algorithm

Genetic Algorithm (GA) is a method for tackling both constrained and unconstrained optimization problems by mimicking biological evolution in a natural selection process. Since its first introduction by Holland in 1975 [29], GA has demonstrated its broad applicability in many areas. In this paper, we apply GA to solve BAP and QCSP simultaneously. It generates an initial population of solutions or chromosomes and then repeatedly generates offspring generations by a series of bioinspired operations including selection, crossover, and mutation, which are adopted from [30]. In each evolution, Algorithms 1 and 2 are adopted to calculate the objective values as well as fitness values of individual solutions. Solutions with high fitness values are selected to form the population in the next generation. The flow chart of GA is depicted in Figure 5.Figure 5
Flowchart of GA.


## 5.4. Hybrid Particle Swarm Optimization Algorithm

Particle Swarm Optimization (PSO) is inspired by social behavior of bird flocking or fish schooling. The algorithm is carried out by means of a swarm of candidate solutions or particles. According to some rules, these particles move around in the search space. The movements of the particles are guided by their own best known positions in the search space as well as the entire swarm’s best known position. As illustrated in Figure6, the proposed Hybrid PSO (HPSO) initializes a set of particles with their original locations Xi and objective function values f(Xi) in the solving space. The original locations Xi of particles are taken as their initial individual best locations Pbesti. Among the original locations of particles, the one that has the smallest objective function value is selected as the population best location Gbest. In order to seek a better location or solution, each particle location needs crossover and mutation with its own previous best location Pbesti and the population previous best location Gbest, respectively. The crossover and mutation evolution operators are from the GA in the above subsection. After moving to the new location, each particle updates its Pbesti, provided that the objective function value of its new location is less than the objective function value of its Pbesti. Likewise, update the Gbest if the objective function value of its new location is less than the objective function value of Gbest. By repeating the above process, a satisfying solution is eventually obtained.Figure 6
Flowchart of HPSO.


## 5.5. Hybrid Simulated Annealing Algorithm

The inspiration of simulated annealing (SA) algorithm comes from metallurgical annealing process, and it is first applied to the field of combinatorial optimization by Kirkpatrick et al. [31]. SA initializes with a solution X1 at a high temperature T=T0, and the temperature T gradually drops to a set value Tend at a certain rate q. At each temperature T, the algorithm generates a new solution X2 and measures its quality Y2. If the new solution X2 is better than the current X1, X1 is replaced by X2. Otherwise, whether the current solution X1 is replaced or not depends on a probability that is progressively decreased with the reducing of temperature T. The above operations are repeated for specified times that is called chain length L at every temperature T. This algorithm can effectively avoid being trapped in local minima and is able to explore globally for optimal solutions. In this work the Hybrid SA (HSA) combines the search mechanism of simulated annealing algorithm with genetic operators such as crossover and mutation when a new solution is generated. The flow chart of HSA is given in Figure 7.Figure 7
Flowchart of HSA.


## 6. Computational Experiments

In this section, a series of computational experiments are conducted to evaluate the performances of the proposed heuristics and demonstrate the impact of tides in the integrated scheduling of berth and QCs. First, we compare the performances of the three heuristics with the exact solutions obtained via CPLEX for small instances. We then make comparison between the heuristic algorithms for large instances. Moreover, we analyze the tidal influence on the processing schedule of vessels and the utilization of berth and QCs.We first make selections on the parameter settings for the heuristics to enhance their experimental performances. To carry out the preliminary test, five instances are randomly generated from a small size scenario(|I|,|B|,|Q|,|T|)=(6,12,8,42), and five instances from a large size scenario (|I|,|B|,|Q|,|T|) = (30, 30, 15, 120). For all the heuristic algorithms, the various combinations of their parameter candidate values are tested on the 10 instances. The parameter values in the best parameter combinations are listed in Table 2 and adopted in all subsequent computational experiments. The three proposed heuristic algorithms will be terminated if one of the following termination criteria is met: (1) the number of generations or the terminal temperature is reached; (2) the quality of the solution is not improved in 50 consecutive generations; and (3) the running time exceeds 2000 seconds.Table 2
Parameter selection for heuristic algorithms.
Heuristic algorithm Parameters Parameter candidate values Best parameter value GA Crossover probability 0.7, 0.8, 0.9 0.9 Mutation probability 0.05, 0.10, 0.15 0.1 Population size 100, 200 200 Number of generations 150, 200 150  HPSO Population size 100, 200, 300 200 Number of generations 100, 150, 200 150  HSA Initial temperature 800, 1000, 1200 1000 Cooling rate 0.85, 0.90, 0.95 0.9 Chain length 100, 200 200 Terminal temperature 0.005, 0.001 0.001The computational experiments are conducted using a PC with Intel Core i7-4700 3.4 GHz processor and 16 GB RAM. The algorithms are coded in Matlab R2014b, and the BACASP-TC model is solved with CPLEX 12.6 called by Matlab. In accordance with [32], the heuristics run each instance 10 times, and the best results among the 10 runs are reported.


### 6.1. Instance Generation

Following the fundamental assumptions of BACASP-TC, the duration of any high/low water time window is equal to 6 time steps. For the three types of vessels, feeder and medium are tide independent, while jumbo is tide dependent. In accordance with [18], the detailed information of vessels in any instance is listed in Table 3, where the workload of a vessel is in units of QC-time-step. For example, the workload of a feeder varies between 10 and 20 QC-time-steps. The interarrival times of vessels are exponentially distributed with a mean of 2 time steps, as in [33].Table 3
Specifications of different types of vessels.
Vessel class Percentage Vessel length Range of used QCs Range of workload Feeder 1/3 3-4 1-2 10-20 Medium 1/3 5-6 2-4 20-40 Jumbo 1/3 7-8 4-6 40-70


### 6.2. Algorithm Performance Evaluation

#### 6.2.1. Small Instances

For small instances, the wharf length, the number of available QCs, and the planning horizon (|B|,|Q|,|T|) are set as (12, 8, 42). For two cases with I=5 and I=6 vessels, we randomly generate ten instances for each. Table 4 shows the computational results of CPLEX and the three heuristic algorithms. In the table, column 1 lists the indices of the instances, while columns 2 and 3 are, respectively, the objective function value of exact solution and the computational time by CPLEX. Columns 4, 7, and 10 are, respectively, the objective function values of the optimal solutions by GA, HPSO, and HSA, and the corresponding running times are given in columns 5, 8, and 11, respectively. The relative errors of objective value between CPLEX and the three heuristics are defined as follows: GGA=OGA-Obj/Obj×100%, GHPSO=OHPSO-Obj/Obj×100%, and GHSA=OHSA-Obj/Obj×100%. First, we observe that all the heuristics obtain optimal solutions as CPLEX does for most of the small instances. For instances 6-2 and 6-7, CPLEX outputs feasible but not exact solutions within the preset 36000 seconds, while the heuristics produce better solutions in much less computational time. Secondly, the running time of CPLEX increases rapidly even for a small growth in the number of vessels, while the heuristics solve all the instances within 600 seconds. Thirdly, although the three heuristics produce the same optimal solution as CPLEX does, the convergence speed of GA outperforms HPSO and HSA.Table 4
Experimental comparison of CPLEX and the heuristic algorithms for small instances.
Instance CPLEX GA HPSO HSA O b j T i m e O G A T i m e G G A O H P S O T i m e G H P S O O H S A T i m e G H S A 5-1 89 1190 89 39 0.0 % 89 513 0.0 % 89 246 0.0 % 5-2 87 5901 87 40 0.0 % 87 534 0.0 % 87 254 0.0 % 5-3 91 10417 91 37 0.0 % 91 489 0.0 % 91 249 0.0 % 5-4 73 1580 73 34 0.0 % 73 466 0.0 % 73 230 0.0 % 5-5 84 1538 84 38 0.0 % 84 502 0.0 % 84 245 0.0 % 5-6 87 1288 87 41 0.0 % 87 527 0.0 % 87 251 0.0 % 5-7 92 1258 92 40 0.0 % 92 504 0.0 % 92 255 0.0 % 5-8 86 1287 86 40 0.0 % 86 505 0.0 % 86 247 0.0 % 5-9 78 834 78 43 0.0 % 78 559 0.0 % 78 261 0.0 % 5-10 83 391 83 36 0.0 % 83 479 0.0 % 83 232 0.0 % 6-1 91 8637 91 45 0.0 % 91 512 0.0 % 91 263 0.0 % 6-2 116 ∗ 36283 106 48 - 106 580 - 106 277 - 6-3 96 14822 96 46 0.0 % 96 530 0.0 % 96 254 0.0 % 6-4 84 1442 84 45 0.0 % 84 525 0.0 % 84 263 0.0 % 6-5 89 3497 89 47 0.0 % 89 552 0.0 % 89 271 0.0 % 6-6 83 11358 83 45 0.0 % 83 513 0.0 % 83 257 0.0 % 6-7 99 ∗ 36324 97 52 - 97 597 - 97 290 - 6-8 89 4474 89 48 0.0 % 89 548 0.0 % 89 278 0.0 % 6-9 108 10970 108 52 0.0 % 108 601 0.0 % 108 292 0.0 % 6-10 95 33375 95 47 0.0 % 95 534 0.0 % 95 265 0.0 % Note: The running time is in seconds. ∗The running time of CPLEX exceeds 36000 seconds in the instance.


#### 6.2.2. Large Instances

For large instances with more than 6 vessels, CPLEX can hardly produce exact solutions in 10 hours. Thus, we compare the performances between the three heuristic algorithms for large instances. We test three scenarios with (|I|,|B|,|Q|,|T|) = (20, 20, 10, 90), (30, 30, 15, 120) and (40, 40, 20, 150), and 10 instances are randomly generated for each scenario. Table 5 summarizes the computational results for the 30 instances, where columns 2, 5, and 8 display, respectively, the best objective function value obtained by GA, HPSO, and HSA in 10 runs. The corresponding running times are reported in columns 3, 6, and 9, respectively. GapGA=ObjGA-ObjHSA/ObjHSA×100% and GapHPSO=ObjHPSO-ObjHSA/ObjHSA×100% are the relative errors of the objective values. It is observed that HSA outperforms GA and HPSO with respect to the solution quality. Moreover, for most instances the relative errors between the best objective values of solutions produced by the three heuristics are within 5%. Hence, we conclude that all the three algorithms can solve large size problems effectively.Table 5
Numerical comparison between the heuristics for large instances.
Instance GA HPSO HSA O b j G A T i m e ( s ) G a p G A O b j H P S O T i m e ( s ) G a p H P S O O b j H S A T i m e ( s ) 20-1 373 1240 6.9% 351 578 0.6% 349 1338 20-2 401 729 7.5% 394 1456 5.6% 373 2000 20-3 432 1026 4.9% 436 1094 5.8% 412 1467 20-4 420 1821 4.5% 418 906 4.0% 402 1985 20-5 414 1823 7.8% 402 1845 4.7% 384 1779 20-6 467 1939 2.0% 479 670 4.6% 458 1971 20-7 494 1719 5.8% 495 504 6.0% 467 1678 20-8 350 1807 0.9% 358 1796 3.2% 347 1680 20-9 319 674 2.2% 330 975 5.8% 312 1329 20-10 377 1915 4.1% 378 972 4.4% 362 1447 30-1 449 1793 2.0% 448 1180 1.8% 440 1822 30-2 445 1977 5.7% 435 1522 3.3% 421 1903 30-3 463 1439 5.0% 457 1130 3.6% 441 1531 30-4 431 1530 4.1% 430 896 3.9% 414 1700 30-5 445 1913 2.3% 440 1538 1.1% 435 1518 30-6 418 1231 0.5% 435 1661 4.6% 416 1482 30-7 527 1858 6.7% 497 1200 0.6% 494 1920 30-8 599 1716 8.5% 571 1642 3.4% 552 1845 30-9 405 1409 0.5% 413 1415 2.5% 403 1864 30-10 431 1189 8.0% 403 1503 1.0% 399 1880 40-1 570 1514 4.2% 553 1796 1.1% 547 1713 40-2 596 1411 2.6% 585 1588 0.7% 581 1636 40-3 553 1871 0.4% 575 1660 4.4% 551 1759 40-4 628 1903 2.1% 644 1633 4.7% 615 1861 40-5 481 1979 1.1% 486 1689 2.1% 476 1827 40-6 503 1177 2.0% 515 1154 4.5% 493 1557 40-7 474 1545 0.2% 476 1569 0.6% 473 1860 40-8 634 1686 0.3% 635 1854 0.5% 632 1821 40-9 489 1709 1.5% 485 1743 0.6% 482 1855 40-10 464 1892 0.7% 472 1736 2.4% 461 1978


#### 6.2.3. Analysis of Tidal Impacts

We carry out numerical experiments to further reveal how the factor of tides impacts the turnaround times of vessels and the utilization of berth and QCs. Four cases 0.1:0.3:0.6(P1), 0.3:0.3:0.4(P2), 0.5:0.2:0.3(P3), and 0.7:0.2:0.1(P4) are investigated according to the different portions of jumbos, mediums, and feeders. For example, in case P1, 10%, 30%, and 60% percentages of the vessels are jumbos, mediums, and feeders, respectively. For each scenario, again 10 instances with (|I|,|B|,|Q|,|T|) = (30, 30, 15, 120) are randomly generated and solved by HSA algorithm, which performs best among the three heuristics in the above experiments. Moreover, we consider three scenarios with different durations V=0, 6 and 12 of high/low water time window. For example, in the first scenario with V=0, there is no tidal impacts involved and all the vessels can pass through the channel at any time, while in the third scenario with V=12, each high or low water time window is of length equal to 12 time steps.The objective values of solutions and the gaps between them are listed in Table7, in which GapV6=ObjV6-ObjV0/ObjV0×100% and GapV12=ObjV12-ObjV0/ObjV0×100%. As shown in Figure 8, the average total turnaround times of vessels increase as the proportion of the tide-dependent vessels (i.e., jumbos) rises in any duration of high/low water time window. This result verifies that the large amount of loading and unloading of jumbos inevitably extends their turnaround times. Moreover, for each case with a fixed proportion of different vessels, it can be seen that the tides result in an obvious increase in vessel turnaround times, compared with the ideal situation without tides, and the tidal effects become more significant with the increase of the duration V of high/low water time window.Figure 8
Tidal impact on vessel turnaround time.In order to explain the above results, we summarize the average waiting times and handling times of tide-dependent vessels (i.e., jumbos) in Table6 based on the instance solutions in Table 7. It shall be noted that column njumbo represents the total number of tide-dependent vessels in ten instances for each combination of vessel ratio and V. Columns Avghdling, Avgwtingpre, and Avgwtingpost mean the average handling time, the average waiting time before berthing and after processing of njumbo tide-dependent vessels, respectively. Columns value and Incrstd denote the corresponding value and increase caused by tides. To take an example of Row 0.3:0.3:0.4, the number of tide-dependent vessels in each instance is 30∗30%=9, and njumbo=10∗9=90. First, these results show that the intensive arriving of more and more jumbos and the increase of duration of high/low water time window prolong the waiting times to enter the approach channel for berthing. Secondly, it is found that the tide effect on the processing times is very small, and the average processing times are all close to the mean processing time of jumbos, which is the mean workload divided by the mean number of used QCs, i.e., 55/5=11. Because the average processing time is nearly twice of V=6 or close to V=12 and jumbos must start processing in high water time window, jumbos have larger chances to meet low water time windows in tidal condition of V=12 than V=6 when they finish their stevedoring to pass through the approach channel. It results in the increasing waiting times after processing as the value of V becomes larger. Thirdly, tides have a greater effect on the waiting time of a jumbo before berthing than that after processing. This provides valuable suggestions for container terminal managers that reasonable times for vessels calling at the port shall be given to reduce unnecessary waiting and improve service quality.Table 6
Tidal impact on jumbos waiting times.
V e s s e l  ratio V n j u m b o A v g w t i n g p r e A v g h d l i n g A v g w t i n g p o s t v a l u e I n c r s t d v a l u e I n c r s t d v a l u e I n c r s t d 0.1:0.3:0.6 0 30 4.87 — 10.40 — 0 — 6 30 5.53 12% 10.47 1% 0.20 100% 12 30 9.67 50% 11.10 6% 2.00 100%  0.3:0.3:0.4 0 90 6.71 — 10.36 — 0 — 6 90 8.87 24% 10.66 3% 0.37 100% 12 90 10.70 37% 11.11 7% 2.31 100%  0.5:0.2:0.3 0 150 12.05 — 10.90 — 0 — 6 150 14.58 17% 11.09 2% 0.23 100% 12 150 18.14 34% 11.62 6% 1.93 100%  0.7:0.2:0.1 0 210 13.22 — 10.58 — 0 — 6 210 15.28 13% 10.92 3% 0.35 100% 12 210 19.90 34% 11.27 6% 1.77 100%Table 7
Tidal impact on vessels turnaround time.
Instance P1 P2 P3 P4 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 1 310 326 5.16% 326 5.16% 416 440 5.77% 523 25.72% 572 596 4.20% 747 30.59% 473 513 8.46% 665 40.59% 2 307 312 1.63% 343 11.73% 389 422 8.48% 448 15.17% 612 636 3.92% 644 5.23% 590 679 15.08% 703 19.15% 3 391 405 3.58% 411 5.12% 414 449 8.45% 460 11.11% 601 667 10.98% 690 14.81% 722 784 8.59% 883 22.30% 4 310 311 0.32% 332 7.10% 406 417 2.71% 450 10.84% 603 628 4.15% 799 32.50% 741 794 7.15% 941 26.99% 5 324 337 4.01% 342 5.56% 406 426 4.93% 456 12.32% 584 611 4.62% 687 17.64% 691 767 11.00% 969 40.23% 6 347 366 5.48% 384 10.66% 390 411 5.38% 461 18.21% 459 513 11.76% 606 32.03% 897 910 1.45% 1018 13.49% 7 300 301 0.33% 337 12.33% 491 509 3.67% 540 9.98% 500 571 14.20% 605 21.00% 523 555 6.12% 735 40.54% 8 298 312 4.70% 330 10.74% 545 580 6.42% 595 9.17% 535 558 4.30% 745 39.25% 544 602 10.66% 702 29.04% 9 363 367 1.10% 386 6.34% 376 413 9.84% 469 24.73% 545 594 8.99% 640 17.43% 703 800 13.80% 1025 45.80% 10 312 314 0.64% 332 6.41% 387 398 2.84% 461 19.12% 592 677 14.36% 744 25.68% 768 816 6.25% 973 26.69%  A v e r a g e 326 335 2.70% 352 8.11% 422 447 5.85% 486 15.64% 560 605 8.15% 691 23.62% 665 722 8.86% 861 30.48%Next, according to the solutions of the instances in Table7, the corresponding utilization ratios of berth and QCs are further reported in Tables 8 and 9 where BU and QCU represent the utilization ratio of berth and QCs, respectively. For intuitive understanding, the average utilization ratios of berth and QCs are plotted in Figures 9(a) and 9(b), respectively. It is evident that the berth utilization ratio and QC utilization ratio in any scenario become worse as the duration V of high/low water time window increases. The reason behind this is that the increasing waiting times of jumbos resulted from the increasing duration of high/low water time window lead to more idleness of berth and QCs. Furthermore, it is observed that both utilization ratios of berth and QCs are enhanced with the increasing portion of the tide-dependent vessels for any given V, and the increasing extent reduces gradually. This is because the average processing time of jumbos is longer than mediums or feeders. So the utilization ratios of berth and QCs increase in the proportion of jumbos for any given duration of high/low water time window.Table 8
Tidal impact on berth utilization ratio.
Instance P1 P2 P3 P4 B U V 0 B U V 6 B U V 12 B U V 0 B U V 6 B U V 12 B U V 0 B U V 6 B U V 12 B U V 0 B U V 6 B U V 12 1 51.28% 51.16% 50.99% 58.41% 56.75% 53.72% 71.12% 71.20% 63.16% 67.43% 64.95% 60.17% 2 46.42% 44.94% 42.11% 66.48% 67.15% 61.95% 71.12% 72.46% 67.26% 71.53% 65.83% 69.43% 3 61.51% 63.98% 54.65% 59.65% 54.18% 58.64% 65.85% 61.91% 65.30% 67.22% 61.34% 65.43% 4 50.09% 50.50% 47.54% 59.28% 56.36% 50.04% 64.58% 58.54% 54.01% 72.81% 71.72% 65.71% 5 65.63% 60.60% 64.44% 69.77% 71.93% 65.24% 67.04% 63.51% 67.47% 69.42% 64.49% 60.31% 6 51.22% 52.34% 52.84% 54.64% 50.95% 54.53% 66.30% 62.81% 63.75% 69.14% 77.15% 69.37% 7 42.08% 40.39% 40.00% 66.46% 61.85% 62.36% 65.82% 61.72% 58.21% 63.27% 60.28% 56.86% 8 37.96% 38.24% 38.21% 71.51% 62.85% 64.77% 69.11% 66.07% 56.19% 67.86% 67.07% 63.56% 9 62.79% 62.62% 55.12% 66.20% 64.30% 58.98% 72.76% 64.70% 69.09% 73.57% 68.70% 62.44% 10 50.72% 52.21% 47.49% 67.81% 62.21% 55.72% 68.24% 64.98% 66.35% 65.73% 70.00% 65.88%  A v e r a g e 51.97% 51.70% 49.34% 64.02% 60.85% 58.60% 68.19% 64.79% 63.08% 68.80% 67.15% 63.92%Table 9
Tidal impact on QC utilization ratio.
Instance P1 P2 P3 P4 Q C U V 0 Q C U V 6 Q C U V 12 Q C U V 0 Q C U V 6 Q C U V 12 Q C U V 0 Q C U V 6 Q C U V 12 Q C U V 0 Q C U V 6 Q C U V 12 1 66.12% 64.62% 65.14% 77.56% 76.63% 67.37% 93.82% 94.62% 82.53% 88.78% 84.36% 75.91% 2 63.33% 61.12% 53.40% 87.03% 84.39% 77.64% 91.55% 94.29% 83.79% 92.59% 86.73% 86.79% 3 78.82% 78.17% 68.26% 77.66% 72.61% 74.40% 86.89% 81.88% 83.58% 89.01% 81.90% 80.95% 4 62.52% 63.65% 58.17% 75.26% 73.10% 65.47% 82.15% 76.95% 68.80% 92.84% 91.96% 85.32% 5 80.23% 77.05% 77.89% 90.00% 89.39% 82.03% 86.52% 81.96% 83.23% 92.99% 84.61% 76.53% 6 65.23% 65.68% 66.22% 72.34% 65.89% 66.53% 87.04% 83.30% 82.29% 91.02% 94.98% 87.42% 7 50.54% 50.47% 50.25% 84.30% 79.92% 82.20% 85.96% 82.29% 77.67% 86.08% 83.61% 74.85% 8 50.75% 50.82% 51.68% 91.05% 81.45% 82.30% 88.51% 87.65% 70.36% 89.84% 87.17% 79.22% 9 80.87% 80.44% 69.39% 87.51% 83.05% 73.05% 89.27% 82.18% 82.39% 94.81% 87.41% 79.72% 10 67.30% 67.39% 61.81% 87.46% 78.96% 69.05% 89.49% 80.28% 80.35% 86.84% 88.47% 82.75%  A v e r a g e 66.57% 65.94% 62.22% 83.02% 78.54% 74.00% 88.12% 84.54% 79.50% 90.48% 87.12% 80.95%Figure 9
Tidal impact on berth and QC utilization.
(a)
Berth utilization (b)
QC utilizationFrom the above experimental results, we may conclude that tides have a nonneglectable impact on the vessel turnaround times and the utilization of critical resources in container terminals. Therefore, the integrated scheduling of berth and QCs considering tidal impacts seems important and meaningful.


## 6.1. Instance Generation

Following the fundamental assumptions of BACASP-TC, the duration of any high/low water time window is equal to 6 time steps. For the three types of vessels, feeder and medium are tide independent, while jumbo is tide dependent. In accordance with [18], the detailed information of vessels in any instance is listed in Table 3, where the workload of a vessel is in units of QC-time-step. For example, the workload of a feeder varies between 10 and 20 QC-time-steps. The interarrival times of vessels are exponentially distributed with a mean of 2 time steps, as in [33].Table 3
Specifications of different types of vessels.
Vessel class Percentage Vessel length Range of used QCs Range of workload Feeder 1/3 3-4 1-2 10-20 Medium 1/3 5-6 2-4 20-40 Jumbo 1/3 7-8 4-6 40-70


## 6.2. Algorithm Performance Evaluation

### 6.2.1. Small Instances

For small instances, the wharf length, the number of available QCs, and the planning horizon (|B|,|Q|,|T|) are set as (12, 8, 42). For two cases with I=5 and I=6 vessels, we randomly generate ten instances for each. Table 4 shows the computational results of CPLEX and the three heuristic algorithms. In the table, column 1 lists the indices of the instances, while columns 2 and 3 are, respectively, the objective function value of exact solution and the computational time by CPLEX. Columns 4, 7, and 10 are, respectively, the objective function values of the optimal solutions by GA, HPSO, and HSA, and the corresponding running times are given in columns 5, 8, and 11, respectively. The relative errors of objective value between CPLEX and the three heuristics are defined as follows: GGA=OGA-Obj/Obj×100%, GHPSO=OHPSO-Obj/Obj×100%, and GHSA=OHSA-Obj/Obj×100%. First, we observe that all the heuristics obtain optimal solutions as CPLEX does for most of the small instances. For instances 6-2 and 6-7, CPLEX outputs feasible but not exact solutions within the preset 36000 seconds, while the heuristics produce better solutions in much less computational time. Secondly, the running time of CPLEX increases rapidly even for a small growth in the number of vessels, while the heuristics solve all the instances within 600 seconds. Thirdly, although the three heuristics produce the same optimal solution as CPLEX does, the convergence speed of GA outperforms HPSO and HSA.Table 4
Experimental comparison of CPLEX and the heuristic algorithms for small instances.
Instance CPLEX GA HPSO HSA O b j T i m e O G A T i m e G G A O H P S O T i m e G H P S O O H S A T i m e G H S A 5-1 89 1190 89 39 0.0 % 89 513 0.0 % 89 246 0.0 % 5-2 87 5901 87 40 0.0 % 87 534 0.0 % 87 254 0.0 % 5-3 91 10417 91 37 0.0 % 91 489 0.0 % 91 249 0.0 % 5-4 73 1580 73 34 0.0 % 73 466 0.0 % 73 230 0.0 % 5-5 84 1538 84 38 0.0 % 84 502 0.0 % 84 245 0.0 % 5-6 87 1288 87 41 0.0 % 87 527 0.0 % 87 251 0.0 % 5-7 92 1258 92 40 0.0 % 92 504 0.0 % 92 255 0.0 % 5-8 86 1287 86 40 0.0 % 86 505 0.0 % 86 247 0.0 % 5-9 78 834 78 43 0.0 % 78 559 0.0 % 78 261 0.0 % 5-10 83 391 83 36 0.0 % 83 479 0.0 % 83 232 0.0 % 6-1 91 8637 91 45 0.0 % 91 512 0.0 % 91 263 0.0 % 6-2 116 ∗ 36283 106 48 - 106 580 - 106 277 - 6-3 96 14822 96 46 0.0 % 96 530 0.0 % 96 254 0.0 % 6-4 84 1442 84 45 0.0 % 84 525 0.0 % 84 263 0.0 % 6-5 89 3497 89 47 0.0 % 89 552 0.0 % 89 271 0.0 % 6-6 83 11358 83 45 0.0 % 83 513 0.0 % 83 257 0.0 % 6-7 99 ∗ 36324 97 52 - 97 597 - 97 290 - 6-8 89 4474 89 48 0.0 % 89 548 0.0 % 89 278 0.0 % 6-9 108 10970 108 52 0.0 % 108 601 0.0 % 108 292 0.0 % 6-10 95 33375 95 47 0.0 % 95 534 0.0 % 95 265 0.0 % Note: The running time is in seconds. ∗The running time of CPLEX exceeds 36000 seconds in the instance.


### 6.2.2. Large Instances

For large instances with more than 6 vessels, CPLEX can hardly produce exact solutions in 10 hours. Thus, we compare the performances between the three heuristic algorithms for large instances. We test three scenarios with (|I|,|B|,|Q|,|T|) = (20, 20, 10, 90), (30, 30, 15, 120) and (40, 40, 20, 150), and 10 instances are randomly generated for each scenario. Table 5 summarizes the computational results for the 30 instances, where columns 2, 5, and 8 display, respectively, the best objective function value obtained by GA, HPSO, and HSA in 10 runs. The corresponding running times are reported in columns 3, 6, and 9, respectively. GapGA=ObjGA-ObjHSA/ObjHSA×100% and GapHPSO=ObjHPSO-ObjHSA/ObjHSA×100% are the relative errors of the objective values. It is observed that HSA outperforms GA and HPSO with respect to the solution quality. Moreover, for most instances the relative errors between the best objective values of solutions produced by the three heuristics are within 5%. Hence, we conclude that all the three algorithms can solve large size problems effectively.Table 5
Numerical comparison between the heuristics for large instances.
Instance GA HPSO HSA O b j G A T i m e ( s ) G a p G A O b j H P S O T i m e ( s ) G a p H P S O O b j H S A T i m e ( s ) 20-1 373 1240 6.9% 351 578 0.6% 349 1338 20-2 401 729 7.5% 394 1456 5.6% 373 2000 20-3 432 1026 4.9% 436 1094 5.8% 412 1467 20-4 420 1821 4.5% 418 906 4.0% 402 1985 20-5 414 1823 7.8% 402 1845 4.7% 384 1779 20-6 467 1939 2.0% 479 670 4.6% 458 1971 20-7 494 1719 5.8% 495 504 6.0% 467 1678 20-8 350 1807 0.9% 358 1796 3.2% 347 1680 20-9 319 674 2.2% 330 975 5.8% 312 1329 20-10 377 1915 4.1% 378 972 4.4% 362 1447 30-1 449 1793 2.0% 448 1180 1.8% 440 1822 30-2 445 1977 5.7% 435 1522 3.3% 421 1903 30-3 463 1439 5.0% 457 1130 3.6% 441 1531 30-4 431 1530 4.1% 430 896 3.9% 414 1700 30-5 445 1913 2.3% 440 1538 1.1% 435 1518 30-6 418 1231 0.5% 435 1661 4.6% 416 1482 30-7 527 1858 6.7% 497 1200 0.6% 494 1920 30-8 599 1716 8.5% 571 1642 3.4% 552 1845 30-9 405 1409 0.5% 413 1415 2.5% 403 1864 30-10 431 1189 8.0% 403 1503 1.0% 399 1880 40-1 570 1514 4.2% 553 1796 1.1% 547 1713 40-2 596 1411 2.6% 585 1588 0.7% 581 1636 40-3 553 1871 0.4% 575 1660 4.4% 551 1759 40-4 628 1903 2.1% 644 1633 4.7% 615 1861 40-5 481 1979 1.1% 486 1689 2.1% 476 1827 40-6 503 1177 2.0% 515 1154 4.5% 493 1557 40-7 474 1545 0.2% 476 1569 0.6% 473 1860 40-8 634 1686 0.3% 635 1854 0.5% 632 1821 40-9 489 1709 1.5% 485 1743 0.6% 482 1855 40-10 464 1892 0.7% 472 1736 2.4% 461 1978


### 6.2.3. Analysis of Tidal Impacts

We carry out numerical experiments to further reveal how the factor of tides impacts the turnaround times of vessels and the utilization of berth and QCs. Four cases 0.1:0.3:0.6(P1), 0.3:0.3:0.4(P2), 0.5:0.2:0.3(P3), and 0.7:0.2:0.1(P4) are investigated according to the different portions of jumbos, mediums, and feeders. For example, in case P1, 10%, 30%, and 60% percentages of the vessels are jumbos, mediums, and feeders, respectively. For each scenario, again 10 instances with (|I|,|B|,|Q|,|T|) = (30, 30, 15, 120) are randomly generated and solved by HSA algorithm, which performs best among the three heuristics in the above experiments. Moreover, we consider three scenarios with different durations V=0, 6 and 12 of high/low water time window. For example, in the first scenario with V=0, there is no tidal impacts involved and all the vessels can pass through the channel at any time, while in the third scenario with V=12, each high or low water time window is of length equal to 12 time steps.The objective values of solutions and the gaps between them are listed in Table7, in which GapV6=ObjV6-ObjV0/ObjV0×100% and GapV12=ObjV12-ObjV0/ObjV0×100%. As shown in Figure 8, the average total turnaround times of vessels increase as the proportion of the tide-dependent vessels (i.e., jumbos) rises in any duration of high/low water time window. This result verifies that the large amount of loading and unloading of jumbos inevitably extends their turnaround times. Moreover, for each case with a fixed proportion of different vessels, it can be seen that the tides result in an obvious increase in vessel turnaround times, compared with the ideal situation without tides, and the tidal effects become more significant with the increase of the duration V of high/low water time window.Figure 8
Tidal impact on vessel turnaround time.In order to explain the above results, we summarize the average waiting times and handling times of tide-dependent vessels (i.e., jumbos) in Table6 based on the instance solutions in Table 7. It shall be noted that column njumbo represents the total number of tide-dependent vessels in ten instances for each combination of vessel ratio and V. Columns Avghdling, Avgwtingpre, and Avgwtingpost mean the average handling time, the average waiting time before berthing and after processing of njumbo tide-dependent vessels, respectively. Columns value and Incrstd denote the corresponding value and increase caused by tides. To take an example of Row 0.3:0.3:0.4, the number of tide-dependent vessels in each instance is 30∗30%=9, and njumbo=10∗9=90. First, these results show that the intensive arriving of more and more jumbos and the increase of duration of high/low water time window prolong the waiting times to enter the approach channel for berthing. Secondly, it is found that the tide effect on the processing times is very small, and the average processing times are all close to the mean processing time of jumbos, which is the mean workload divided by the mean number of used QCs, i.e., 55/5=11. Because the average processing time is nearly twice of V=6 or close to V=12 and jumbos must start processing in high water time window, jumbos have larger chances to meet low water time windows in tidal condition of V=12 than V=6 when they finish their stevedoring to pass through the approach channel. It results in the increasing waiting times after processing as the value of V becomes larger. Thirdly, tides have a greater effect on the waiting time of a jumbo before berthing than that after processing. This provides valuable suggestions for container terminal managers that reasonable times for vessels calling at the port shall be given to reduce unnecessary waiting and improve service quality.Table 6
Tidal impact on jumbos waiting times.
V e s s e l  ratio V n j u m b o A v g w t i n g p r e A v g h d l i n g A v g w t i n g p o s t v a l u e I n c r s t d v a l u e I n c r s t d v a l u e I n c r s t d 0.1:0.3:0.6 0 30 4.87 — 10.40 — 0 — 6 30 5.53 12% 10.47 1% 0.20 100% 12 30 9.67 50% 11.10 6% 2.00 100%  0.3:0.3:0.4 0 90 6.71 — 10.36 — 0 — 6 90 8.87 24% 10.66 3% 0.37 100% 12 90 10.70 37% 11.11 7% 2.31 100%  0.5:0.2:0.3 0 150 12.05 — 10.90 — 0 — 6 150 14.58 17% 11.09 2% 0.23 100% 12 150 18.14 34% 11.62 6% 1.93 100%  0.7:0.2:0.1 0 210 13.22 — 10.58 — 0 — 6 210 15.28 13% 10.92 3% 0.35 100% 12 210 19.90 34% 11.27 6% 1.77 100%Table 7
Tidal impact on vessels turnaround time.
Instance P1 P2 P3 P4 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 1 310 326 5.16% 326 5.16% 416 440 5.77% 523 25.72% 572 596 4.20% 747 30.59% 473 513 8.46% 665 40.59% 2 307 312 1.63% 343 11.73% 389 422 8.48% 448 15.17% 612 636 3.92% 644 5.23% 590 679 15.08% 703 19.15% 3 391 405 3.58% 411 5.12% 414 449 8.45% 460 11.11% 601 667 10.98% 690 14.81% 722 784 8.59% 883 22.30% 4 310 311 0.32% 332 7.10% 406 417 2.71% 450 10.84% 603 628 4.15% 799 32.50% 741 794 7.15% 941 26.99% 5 324 337 4.01% 342 5.56% 406 426 4.93% 456 12.32% 584 611 4.62% 687 17.64% 691 767 11.00% 969 40.23% 6 347 366 5.48% 384 10.66% 390 411 5.38% 461 18.21% 459 513 11.76% 606 32.03% 897 910 1.45% 1018 13.49% 7 300 301 0.33% 337 12.33% 491 509 3.67% 540 9.98% 500 571 14.20% 605 21.00% 523 555 6.12% 735 40.54% 8 298 312 4.70% 330 10.74% 545 580 6.42% 595 9.17% 535 558 4.30% 745 39.25% 544 602 10.66% 702 29.04% 9 363 367 1.10% 386 6.34% 376 413 9.84% 469 24.73% 545 594 8.99% 640 17.43% 703 800 13.80% 1025 45.80% 10 312 314 0.64% 332 6.41% 387 398 2.84% 461 19.12% 592 677 14.36% 744 25.68% 768 816 6.25% 973 26.69%  A v e r a g e 326 335 2.70% 352 8.11% 422 447 5.85% 486 15.64% 560 605 8.15% 691 23.62% 665 722 8.86% 861 30.48%Next, according to the solutions of the instances in Table7, the corresponding utilization ratios of berth and QCs are further reported in Tables 8 and 9 where BU and QCU represent the utilization ratio of berth and QCs, respectively. For intuitive understanding, the average utilization ratios of berth and QCs are plotted in Figures 9(a) and 9(b), respectively. It is evident that the berth utilization ratio and QC utilization ratio in any scenario become worse as the duration V of high/low water time window increases. The reason behind this is that the increasing waiting times of jumbos resulted from the increasing duration of high/low water time window lead to more idleness of berth and QCs. Furthermore, it is observed that both utilization ratios of berth and QCs are enhanced with the increasing portion of the tide-dependent vessels for any given V, and the increasing extent reduces gradually. This is because the average processing time of jumbos is longer than mediums or feeders. So the utilization ratios of berth and QCs increase in the proportion of jumbos for any given duration of high/low water time window.Table 8
Tidal impact on berth utilization ratio.
Instance P1 P2 P3 P4 B U V 0 B U V 6 B U V 12 B U V 0 B U V 6 B U V 12 B U V 0 B U V 6 B U V 12 B U V 0 B U V 6 B U V 12 1 51.28% 51.16% 50.99% 58.41% 56.75% 53.72% 71.12% 71.20% 63.16% 67.43% 64.95% 60.17% 2 46.42% 44.94% 42.11% 66.48% 67.15% 61.95% 71.12% 72.46% 67.26% 71.53% 65.83% 69.43% 3 61.51% 63.98% 54.65% 59.65% 54.18% 58.64% 65.85% 61.91% 65.30% 67.22% 61.34% 65.43% 4 50.09% 50.50% 47.54% 59.28% 56.36% 50.04% 64.58% 58.54% 54.01% 72.81% 71.72% 65.71% 5 65.63% 60.60% 64.44% 69.77% 71.93% 65.24% 67.04% 63.51% 67.47% 69.42% 64.49% 60.31% 6 51.22% 52.34% 52.84% 54.64% 50.95% 54.53% 66.30% 62.81% 63.75% 69.14% 77.15% 69.37% 7 42.08% 40.39% 40.00% 66.46% 61.85% 62.36% 65.82% 61.72% 58.21% 63.27% 60.28% 56.86% 8 37.96% 38.24% 38.21% 71.51% 62.85% 64.77% 69.11% 66.07% 56.19% 67.86% 67.07% 63.56% 9 62.79% 62.62% 55.12% 66.20% 64.30% 58.98% 72.76% 64.70% 69.09% 73.57% 68.70% 62.44% 10 50.72% 52.21% 47.49% 67.81% 62.21% 55.72% 68.24% 64.98% 66.35% 65.73% 70.00% 65.88%  A v e r a g e 51.97% 51.70% 49.34% 64.02% 60.85% 58.60% 68.19% 64.79% 63.08% 68.80% 67.15% 63.92%Table 9
Tidal impact on QC utilization ratio.
Instance P1 P2 P3 P4 Q C U V 0 Q C U V 6 Q C U V 12 Q C U V 0 Q C U V 6 Q C U V 12 Q C U V 0 Q C U V 6 Q C U V 12 Q C U V 0 Q C U V 6 Q C U V 12 1 66.12% 64.62% 65.14% 77.56% 76.63% 67.37% 93.82% 94.62% 82.53% 88.78% 84.36% 75.91% 2 63.33% 61.12% 53.40% 87.03% 84.39% 77.64% 91.55% 94.29% 83.79% 92.59% 86.73% 86.79% 3 78.82% 78.17% 68.26% 77.66% 72.61% 74.40% 86.89% 81.88% 83.58% 89.01% 81.90% 80.95% 4 62.52% 63.65% 58.17% 75.26% 73.10% 65.47% 82.15% 76.95% 68.80% 92.84% 91.96% 85.32% 5 80.23% 77.05% 77.89% 90.00% 89.39% 82.03% 86.52% 81.96% 83.23% 92.99% 84.61% 76.53% 6 65.23% 65.68% 66.22% 72.34% 65.89% 66.53% 87.04% 83.30% 82.29% 91.02% 94.98% 87.42% 7 50.54% 50.47% 50.25% 84.30% 79.92% 82.20% 85.96% 82.29% 77.67% 86.08% 83.61% 74.85% 8 50.75% 50.82% 51.68% 91.05% 81.45% 82.30% 88.51% 87.65% 70.36% 89.84% 87.17% 79.22% 9 80.87% 80.44% 69.39% 87.51% 83.05% 73.05% 89.27% 82.18% 82.39% 94.81% 87.41% 79.72% 10 67.30% 67.39% 61.81% 87.46% 78.96% 69.05% 89.49% 80.28% 80.35% 86.84% 88.47% 82.75%  A v e r a g e 66.57% 65.94% 62.22% 83.02% 78.54% 74.00% 88.12% 84.54% 79.50% 90.48% 87.12% 80.95%Figure 9
Tidal impact on berth and QC utilization.
(a)
Berth utilization (b)
QC utilizationFrom the above experimental results, we may conclude that tides have a nonneglectable impact on the vessel turnaround times and the utilization of critical resources in container terminals. Therefore, the integrated scheduling of berth and QCs considering tidal impacts seems important and meaningful.


## 6.2.1. Small Instances

For small instances, the wharf length, the number of available QCs, and the planning horizon (|B|,|Q|,|T|) are set as (12, 8, 42). For two cases with I=5 and I=6 vessels, we randomly generate ten instances for each. Table 4 shows the computational results of CPLEX and the three heuristic algorithms. In the table, column 1 lists the indices of the instances, while columns 2 and 3 are, respectively, the objective function value of exact solution and the computational time by CPLEX. Columns 4, 7, and 10 are, respectively, the objective function values of the optimal solutions by GA, HPSO, and HSA, and the corresponding running times are given in columns 5, 8, and 11, respectively. The relative errors of objective value between CPLEX and the three heuristics are defined as follows: GGA=OGA-Obj/Obj×100%, GHPSO=OHPSO-Obj/Obj×100%, and GHSA=OHSA-Obj/Obj×100%. First, we observe that all the heuristics obtain optimal solutions as CPLEX does for most of the small instances. For instances 6-2 and 6-7, CPLEX outputs feasible but not exact solutions within the preset 36000 seconds, while the heuristics produce better solutions in much less computational time. Secondly, the running time of CPLEX increases rapidly even for a small growth in the number of vessels, while the heuristics solve all the instances within 600 seconds. Thirdly, although the three heuristics produce the same optimal solution as CPLEX does, the convergence speed of GA outperforms HPSO and HSA.Table 4
Experimental comparison of CPLEX and the heuristic algorithms for small instances.
Instance CPLEX GA HPSO HSA O b j T i m e O G A T i m e G G A O H P S O T i m e G H P S O O H S A T i m e G H S A 5-1 89 1190 89 39 0.0 % 89 513 0.0 % 89 246 0.0 % 5-2 87 5901 87 40 0.0 % 87 534 0.0 % 87 254 0.0 % 5-3 91 10417 91 37 0.0 % 91 489 0.0 % 91 249 0.0 % 5-4 73 1580 73 34 0.0 % 73 466 0.0 % 73 230 0.0 % 5-5 84 1538 84 38 0.0 % 84 502 0.0 % 84 245 0.0 % 5-6 87 1288 87 41 0.0 % 87 527 0.0 % 87 251 0.0 % 5-7 92 1258 92 40 0.0 % 92 504 0.0 % 92 255 0.0 % 5-8 86 1287 86 40 0.0 % 86 505 0.0 % 86 247 0.0 % 5-9 78 834 78 43 0.0 % 78 559 0.0 % 78 261 0.0 % 5-10 83 391 83 36 0.0 % 83 479 0.0 % 83 232 0.0 % 6-1 91 8637 91 45 0.0 % 91 512 0.0 % 91 263 0.0 % 6-2 116 ∗ 36283 106 48 - 106 580 - 106 277 - 6-3 96 14822 96 46 0.0 % 96 530 0.0 % 96 254 0.0 % 6-4 84 1442 84 45 0.0 % 84 525 0.0 % 84 263 0.0 % 6-5 89 3497 89 47 0.0 % 89 552 0.0 % 89 271 0.0 % 6-6 83 11358 83 45 0.0 % 83 513 0.0 % 83 257 0.0 % 6-7 99 ∗ 36324 97 52 - 97 597 - 97 290 - 6-8 89 4474 89 48 0.0 % 89 548 0.0 % 89 278 0.0 % 6-9 108 10970 108 52 0.0 % 108 601 0.0 % 108 292 0.0 % 6-10 95 33375 95 47 0.0 % 95 534 0.0 % 95 265 0.0 % Note: The running time is in seconds. ∗The running time of CPLEX exceeds 36000 seconds in the instance.


## 6.2.2. Large Instances

For large instances with more than 6 vessels, CPLEX can hardly produce exact solutions in 10 hours. Thus, we compare the performances between the three heuristic algorithms for large instances. We test three scenarios with (|I|,|B|,|Q|,|T|) = (20, 20, 10, 90), (30, 30, 15, 120) and (40, 40, 20, 150), and 10 instances are randomly generated for each scenario. Table 5 summarizes the computational results for the 30 instances, where columns 2, 5, and 8 display, respectively, the best objective function value obtained by GA, HPSO, and HSA in 10 runs. The corresponding running times are reported in columns 3, 6, and 9, respectively. GapGA=ObjGA-ObjHSA/ObjHSA×100% and GapHPSO=ObjHPSO-ObjHSA/ObjHSA×100% are the relative errors of the objective values. It is observed that HSA outperforms GA and HPSO with respect to the solution quality. Moreover, for most instances the relative errors between the best objective values of solutions produced by the three heuristics are within 5%. Hence, we conclude that all the three algorithms can solve large size problems effectively.Table 5
Numerical comparison between the heuristics for large instances.
Instance GA HPSO HSA O b j G A T i m e ( s ) G a p G A O b j H P S O T i m e ( s ) G a p H P S O O b j H S A T i m e ( s ) 20-1 373 1240 6.9% 351 578 0.6% 349 1338 20-2 401 729 7.5% 394 1456 5.6% 373 2000 20-3 432 1026 4.9% 436 1094 5.8% 412 1467 20-4 420 1821 4.5% 418 906 4.0% 402 1985 20-5 414 1823 7.8% 402 1845 4.7% 384 1779 20-6 467 1939 2.0% 479 670 4.6% 458 1971 20-7 494 1719 5.8% 495 504 6.0% 467 1678 20-8 350 1807 0.9% 358 1796 3.2% 347 1680 20-9 319 674 2.2% 330 975 5.8% 312 1329 20-10 377 1915 4.1% 378 972 4.4% 362 1447 30-1 449 1793 2.0% 448 1180 1.8% 440 1822 30-2 445 1977 5.7% 435 1522 3.3% 421 1903 30-3 463 1439 5.0% 457 1130 3.6% 441 1531 30-4 431 1530 4.1% 430 896 3.9% 414 1700 30-5 445 1913 2.3% 440 1538 1.1% 435 1518 30-6 418 1231 0.5% 435 1661 4.6% 416 1482 30-7 527 1858 6.7% 497 1200 0.6% 494 1920 30-8 599 1716 8.5% 571 1642 3.4% 552 1845 30-9 405 1409 0.5% 413 1415 2.5% 403 1864 30-10 431 1189 8.0% 403 1503 1.0% 399 1880 40-1 570 1514 4.2% 553 1796 1.1% 547 1713 40-2 596 1411 2.6% 585 1588 0.7% 581 1636 40-3 553 1871 0.4% 575 1660 4.4% 551 1759 40-4 628 1903 2.1% 644 1633 4.7% 615 1861 40-5 481 1979 1.1% 486 1689 2.1% 476 1827 40-6 503 1177 2.0% 515 1154 4.5% 493 1557 40-7 474 1545 0.2% 476 1569 0.6% 473 1860 40-8 634 1686 0.3% 635 1854 0.5% 632 1821 40-9 489 1709 1.5% 485 1743 0.6% 482 1855 40-10 464 1892 0.7% 472 1736 2.4% 461 1978


## 6.2.3. Analysis of Tidal Impacts

We carry out numerical experiments to further reveal how the factor of tides impacts the turnaround times of vessels and the utilization of berth and QCs. Four cases 0.1:0.3:0.6(P1), 0.3:0.3:0.4(P2), 0.5:0.2:0.3(P3), and 0.7:0.2:0.1(P4) are investigated according to the different portions of jumbos, mediums, and feeders. For example, in case P1, 10%, 30%, and 60% percentages of the vessels are jumbos, mediums, and feeders, respectively. For each scenario, again 10 instances with (|I|,|B|,|Q|,|T|) = (30, 30, 15, 120) are randomly generated and solved by HSA algorithm, which performs best among the three heuristics in the above experiments. Moreover, we consider three scenarios with different durations V=0, 6 and 12 of high/low water time window. For example, in the first scenario with V=0, there is no tidal impacts involved and all the vessels can pass through the channel at any time, while in the third scenario with V=12, each high or low water time window is of length equal to 12 time steps.The objective values of solutions and the gaps between them are listed in Table7, in which GapV6=ObjV6-ObjV0/ObjV0×100% and GapV12=ObjV12-ObjV0/ObjV0×100%. As shown in Figure 8, the average total turnaround times of vessels increase as the proportion of the tide-dependent vessels (i.e., jumbos) rises in any duration of high/low water time window. This result verifies that the large amount of loading and unloading of jumbos inevitably extends their turnaround times. Moreover, for each case with a fixed proportion of different vessels, it can be seen that the tides result in an obvious increase in vessel turnaround times, compared with the ideal situation without tides, and the tidal effects become more significant with the increase of the duration V of high/low water time window.Figure 8
Tidal impact on vessel turnaround time.In order to explain the above results, we summarize the average waiting times and handling times of tide-dependent vessels (i.e., jumbos) in Table6 based on the instance solutions in Table 7. It shall be noted that column njumbo represents the total number of tide-dependent vessels in ten instances for each combination of vessel ratio and V. Columns Avghdling, Avgwtingpre, and Avgwtingpost mean the average handling time, the average waiting time before berthing and after processing of njumbo tide-dependent vessels, respectively. Columns value and Incrstd denote the corresponding value and increase caused by tides. To take an example of Row 0.3:0.3:0.4, the number of tide-dependent vessels in each instance is 30∗30%=9, and njumbo=10∗9=90. First, these results show that the intensive arriving of more and more jumbos and the increase of duration of high/low water time window prolong the waiting times to enter the approach channel for berthing. Secondly, it is found that the tide effect on the processing times is very small, and the average processing times are all close to the mean processing time of jumbos, which is the mean workload divided by the mean number of used QCs, i.e., 55/5=11. Because the average processing time is nearly twice of V=6 or close to V=12 and jumbos must start processing in high water time window, jumbos have larger chances to meet low water time windows in tidal condition of V=12 than V=6 when they finish their stevedoring to pass through the approach channel. It results in the increasing waiting times after processing as the value of V becomes larger. Thirdly, tides have a greater effect on the waiting time of a jumbo before berthing than that after processing. This provides valuable suggestions for container terminal managers that reasonable times for vessels calling at the port shall be given to reduce unnecessary waiting and improve service quality.Table 6
Tidal impact on jumbos waiting times.
V e s s e l  ratio V n j u m b o A v g w t i n g p r e A v g h d l i n g A v g w t i n g p o s t v a l u e I n c r s t d v a l u e I n c r s t d v a l u e I n c r s t d 0.1:0.3:0.6 0 30 4.87 — 10.40 — 0 — 6 30 5.53 12% 10.47 1% 0.20 100% 12 30 9.67 50% 11.10 6% 2.00 100%  0.3:0.3:0.4 0 90 6.71 — 10.36 — 0 — 6 90 8.87 24% 10.66 3% 0.37 100% 12 90 10.70 37% 11.11 7% 2.31 100%  0.5:0.2:0.3 0 150 12.05 — 10.90 — 0 — 6 150 14.58 17% 11.09 2% 0.23 100% 12 150 18.14 34% 11.62 6% 1.93 100%  0.7:0.2:0.1 0 210 13.22 — 10.58 — 0 — 6 210 15.28 13% 10.92 3% 0.35 100% 12 210 19.90 34% 11.27 6% 1.77 100%Table 7
Tidal impact on vessels turnaround time.
Instance P1 P2 P3 P4 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 O b j V 0 O b j V 6 G a p V 6 O b j V 12 G a p V 12 1 310 326 5.16% 326 5.16% 416 440 5.77% 523 25.72% 572 596 4.20% 747 30.59% 473 513 8.46% 665 40.59% 2 307 312 1.63% 343 11.73% 389 422 8.48% 448 15.17% 612 636 3.92% 644 5.23% 590 679 15.08% 703 19.15% 3 391 405 3.58% 411 5.12% 414 449 8.45% 460 11.11% 601 667 10.98% 690 14.81% 722 784 8.59% 883 22.30% 4 310 311 0.32% 332 7.10% 406 417 2.71% 450 10.84% 603 628 4.15% 799 32.50% 741 794 7.15% 941 26.99% 5 324 337 4.01% 342 5.56% 406 426 4.93% 456 12.32% 584 611 4.62% 687 17.64% 691 767 11.00% 969 40.23% 6 347 366 5.48% 384 10.66% 390 411 5.38% 461 18.21% 459 513 11.76% 606 32.03% 897 910 1.45% 1018 13.49% 7 300 301 0.33% 337 12.33% 491 509 3.67% 540 9.98% 500 571 14.20% 605 21.00% 523 555 6.12% 735 40.54% 8 298 312 4.70% 330 10.74% 545 580 6.42% 595 9.17% 535 558 4.30% 745 39.25% 544 602 10.66% 702 29.04% 9 363 367 1.10% 386 6.34% 376 413 9.84% 469 24.73% 545 594 8.99% 640 17.43% 703 800 13.80% 1025 45.80% 10 312 314 0.64% 332 6.41% 387 398 2.84% 461 19.12% 592 677 14.36% 744 25.68% 768 816 6.25% 973 26.69%  A v e r a g e 326 335 2.70% 352 8.11% 422 447 5.85% 486 15.64% 560 605 8.15% 691 23.62% 665 722 8.86% 861 30.48%Next, according to the solutions of the instances in Table7, the corresponding utilization ratios of berth and QCs are further reported in Tables 8 and 9 where BU and QCU represent the utilization ratio of berth and QCs, respectively. For intuitive understanding, the average utilization ratios of berth and QCs are plotted in Figures 9(a) and 9(b), respectively. It is evident that the berth utilization ratio and QC utilization ratio in any scenario become worse as the duration V of high/low water time window increases. The reason behind this is that the increasing waiting times of jumbos resulted from the increasing duration of high/low water time window lead to more idleness of berth and QCs. Furthermore, it is observed that both utilization ratios of berth and QCs are enhanced with the increasing portion of the tide-dependent vessels for any given V, and the increasing extent reduces gradually. This is because the average processing time of jumbos is longer than mediums or feeders. So the utilization ratios of berth and QCs increase in the proportion of jumbos for any given duration of high/low water time window.Table 8
Tidal impact on berth utilization ratio.
Instance P1 P2 P3 P4 B U V 0 B U V 6 B U V 12 B U V 0 B U V 6 B U V 12 B U V 0 B U V 6 B U V 12 B U V 0 B U V 6 B U V 12 1 51.28% 51.16% 50.99% 58.41% 56.75% 53.72% 71.12% 71.20% 63.16% 67.43% 64.95% 60.17% 2 46.42% 44.94% 42.11% 66.48% 67.15% 61.95% 71.12% 72.46% 67.26% 71.53% 65.83% 69.43% 3 61.51% 63.98% 54.65% 59.65% 54.18% 58.64% 65.85% 61.91% 65.30% 67.22% 61.34% 65.43% 4 50.09% 50.50% 47.54% 59.28% 56.36% 50.04% 64.58% 58.54% 54.01% 72.81% 71.72% 65.71% 5 65.63% 60.60% 64.44% 69.77% 71.93% 65.24% 67.04% 63.51% 67.47% 69.42% 64.49% 60.31% 6 51.22% 52.34% 52.84% 54.64% 50.95% 54.53% 66.30% 62.81% 63.75% 69.14% 77.15% 69.37% 7 42.08% 40.39% 40.00% 66.46% 61.85% 62.36% 65.82% 61.72% 58.21% 63.27% 60.28% 56.86% 8 37.96% 38.24% 38.21% 71.51% 62.85% 64.77% 69.11% 66.07% 56.19% 67.86% 67.07% 63.56% 9 62.79% 62.62% 55.12% 66.20% 64.30% 58.98% 72.76% 64.70% 69.09% 73.57% 68.70% 62.44% 10 50.72% 52.21% 47.49% 67.81% 62.21% 55.72% 68.24% 64.98% 66.35% 65.73% 70.00% 65.88%  A v e r a g e 51.97% 51.70% 49.34% 64.02% 60.85% 58.60% 68.19% 64.79% 63.08% 68.80% 67.15% 63.92%Table 9
Tidal impact on QC utilization ratio.
Instance P1 P2 P3 P4 Q C U V 0 Q C U V 6 Q C U V 12 Q C U V 0 Q C U V 6 Q C U V 12 Q C U V 0 Q C U V 6 Q C U V 12 Q C U V 0 Q C U V 6 Q C U V 12 1 66.12% 64.62% 65.14% 77.56% 76.63% 67.37% 93.82% 94.62% 82.53% 88.78% 84.36% 75.91% 2 63.33% 61.12% 53.40% 87.03% 84.39% 77.64% 91.55% 94.29% 83.79% 92.59% 86.73% 86.79% 3 78.82% 78.17% 68.26% 77.66% 72.61% 74.40% 86.89% 81.88% 83.58% 89.01% 81.90% 80.95% 4 62.52% 63.65% 58.17% 75.26% 73.10% 65.47% 82.15% 76.95% 68.80% 92.84% 91.96% 85.32% 5 80.23% 77.05% 77.89% 90.00% 89.39% 82.03% 86.52% 81.96% 83.23% 92.99% 84.61% 76.53% 6 65.23% 65.68% 66.22% 72.34% 65.89% 66.53% 87.04% 83.30% 82.29% 91.02% 94.98% 87.42% 7 50.54% 50.47% 50.25% 84.30% 79.92% 82.20% 85.96% 82.29% 77.67% 86.08% 83.61% 74.85% 8 50.75% 50.82% 51.68% 91.05% 81.45% 82.30% 88.51% 87.65% 70.36% 89.84% 87.17% 79.22% 9 80.87% 80.44% 69.39% 87.51% 83.05% 73.05% 89.27% 82.18% 82.39% 94.81% 87.41% 79.72% 10 67.30% 67.39% 61.81% 87.46% 78.96% 69.05% 89.49% 80.28% 80.35% 86.84% 88.47% 82.75%  A v e r a g e 66.57% 65.94% 62.22% 83.02% 78.54% 74.00% 88.12% 84.54% 79.50% 90.48% 87.12% 80.95%Figure 9
Tidal impact on berth and QC utilization.
(a)
Berth utilization (b)
QC utilizationFrom the above experimental results, we may conclude that tides have a nonneglectable impact on the vessel turnaround times and the utilization of critical resources in container terminals. Therefore, the integrated scheduling of berth and QCs considering tidal impacts seems important and meaningful.


## 7. Conclusion

This work introduces tidal impacts into the integrated berth and QC scheduling problem. We focus on the time-variant version of QC scheduling such that the set of QCs assigned to the same vessel can be different in two consecutive time steps. An integer linear programming model for the considered problem is proposed. Three heuristics, GA, HPSO, and HSA, based on two greedy algorithms are proposed to solve the problem. Computational experiments are conducted to demonstrate the good performances of the proposed algorithms, which produce optimal solutions for small size instances and generate high quality solutions for large size instances. Numerical results also reveal that tides have a significant impact on the total turnaround time of vessels as well as the resource utilization.The following two extensions may be of interest for the studied problem in this work. The first one is to investigate multiobjective models which minimize simultaneously more than one objective function such as the total turnaround time, the departure delay cost of vessels, and the penalties of nondesired berthing location assignments. Another extension is to study the scenario with uncertain arrival times or processing times of vessels due to bad weather and traffic jam in the port. Robust schedules are usually the target for the model with uncertainty, and it may be an interesting challenge.



---

*Source: 9097047-2018-10-15.xml*