# A rolling horizon approach for the integrated multi-quays berth allocation and crane assignment problem for bulk ports

Issam Krimi, Rachid Benmansour, Abdessamad Ait El Cadi, Laurent

Deshayes, David Duvivier, Nizar Elhachemi

<figure><img src="image_1.png" /></figure>

## To cite this version:

Issam Krimi, Rachid Benmansour, Abdessamad Ait El Cadi, Laurent Deshayes, David Duvivier, et al.. A rolling horizon approach for the integrated multi-quays berth allocation and crane assignment problem for bulk ports. International Journal of Industrial Engineering Computations, 2019, 10 (4), pp.577-591. 10.5267/j.ijiec.2019.4.003. hal-03576770

HAL Id: hal-03576770

https://uphf.hal.science/hal-03576770

Submitted on 14 Apr 2022

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A rolling horizon approach for the integrated multi-quays berth allocation and crane assignment problem for bulk ports

Issam Krimi<sup>a*</sup>, Rachid Benmansour<sup>b</sup>, Abdessamad Ait El Cadi<sup>b</sup>, Laurent Deshayes<sup>a</sup>, David Duvivier<sup>b</sup> and Nizar Elhachemi<sup>c</sup>

## CHRONICLE

### Article history:

Received January 4 2019

Received in Revised Format

February 4 2019

Accepted April 26 2019

Available online

April 26 2019

### Keywords:

Berth allocation

Crane assignment

Mixed integer programming

Rolling horizon

Bulk Ports

## ABSTRACT

In this paper, an efficient rolling horizon-based heuristic is presented to solve the integrated berth allocation and crane assignment problem in bulk ports. We were guided by a real case study of a multi-terminal port, owned by our Moroccan industrial partner, under several restrictions as high tides and installation's availability. First, we proposed a mixed integer programming model for the problem. Then, we investigated a strategy to dissipate the congestion within the presented rolling horizon. A variety of experiments were conducted, and the obtained results show that the proposed methods were efficient from a practical point of view.

© 2019 by the authors; licensee Growing Science, Canada

## 1. Introduction

According to Stopford (2013), the global economy is mainly related to the maritime industry and that requires more attention to enhance its performance. From this perspective, several researchers have studied the operational aspect of port management by investigating two different decision problems: yard side and seaside operations (Fu & Diabat, 2015). As one of the major seaside problems, we cite berth allocation problem (BAP). However, this problem depends, significantly, on resources utilization and especially on loading/unloading cranes used for the operation. Therefore, dealing with BAP and crane assignment problem (CAP) in one integrated decision problem is more realistic. Indeed, a significant focus has been given to the integrated berth allocation and crane assignment problem for container terminals (e.g. Agra & Oliveira, 2018; Vacca et al., 2013). However, few works exist dealing with the case of bulk ports.

<footnote><sup>a</sup>Mohamed 6 Polytechnic University, Morocco</footnote>

<footnote><sup>b</sup>LAMIH UMR CNRS 8201, Université Polytechnique Hauts de France, France</footnote>

<footnote><sup>c</sup>Mohammadia School of Engineers, Mohamed V University, Morocco</footnote>

<footnote>* Corresponding author
E-mail: issam.krimi@um6p.ma (I. Krimi)</footnote>
In this paper, we investigate the multi-quay berth allocation and crane assignment problem for bulk terminals. We are guided by a real case study of a bulk port owned by our Moroccan industrial partner. The contributions are cited as follows: A mixed integer programming (MIP) model is proposed to solve small and medium instances based on several industrial settings.

1. A greedy rule based-heuristic is used to generate a feasible planning/schedule.

2. It is shown that the proposed MIP is not adequate for large scale or congested instances. Hence, we developed a rolling horizon approach to find good solutions within a reasonable computational time.

The remainder of this paper is organized as follows. In Section 2, we present an overview of the related works, with a focus on the integrated berth allocation and crane assignment problem for both container and bulk ports. Section 3 introduces, formally, the problem and presents the MIP model. In section 4, we detailed the proposed rolling horizon algorithm and the greedy heuristic embedded in it. Finally, Section 5 summarizes the real case study and the experimental results for both the MIP model and the rolling horizon algorithm followed by a conclusion and our work perspectives in the last section.

## 2. Literature review

The purpose of this section is to provide an overview of the existing related research that addressed the berth allocation problem and the crane assignment problem. In the literature, several works studied these problems independently or using an integrated approach. Due to the importance of these operational decisions, researchers specified a taxonomy based on the problem characteristics (Bierwirth & Meisel, 2015). The first distinction is related to the arrival dates. In our case, vessels arrive within the planning horizon. It is called the dynamic berth allocation problem. The port under the study is viewed as a set of continuous berthing layouts. Hence, vessels are placed along the quay respecting the physical restrictions. Several works present the handling time as a predefined amount of time or depend on resource's utilization. In our study, we assumed that the handling time depends on both the number of cranes assigned to the vessel and the quay. The use of cranes is also a characteristic of the integrated BACAP. Some researchers assumed that cranes utilization is time-variant (Raa et al., 2011), that means cranes assignment can be changed during the loading process. In our case, cranes utilization does not change within time. In the container terminal context, Park and Kim (2005) presented the first work that dealt, simultaneously, with the berth Allocation and crane Assignment. They proposed a two-phase approach based on Lagrangian relaxation. In the first stage, they determined berthing positions, handling times and the number of assigned cranes in each period. Then, in the second stage, cranes scheduling were investigated. In the same year, Imai et al. (2005) studied the notion of multi-user terminal, in which quays are a set of berths called the discrete layout. The authors proposed a heuristic procedure to solve the problem. Meisel and Bierwirth (2009) proposed a mathematical formulation integrating the berth allocation problem and the crane assignment problem under several real-world considerations. To solve the problem, they developed a constructive heuristic for generating a feasible solution, a set of local search procedures and metaheuristics. These methods were shown efficient on a set of real-world instances. Based on this work, Iris et al. (2015) studied two variants of the crane assignment: time-variant and time-invariant and proposed new mathematical formulations. Iris et al. (2017) improved the mathematical formulation provided by Meisel and Bierwirth (2009), introducing valid inequalities and variable fixing methods. The same problem but with a more realistic objective was investigated by Liang et al. (2009). The aim was to minimize the handling time, the waiting time and the delay for each vessel. They formulated the problem with a dynamic aspect for vessel's arrival and proposed a genetic algorithm to guarantee a good solution with a reasonable time for real world instances. Giallombardo et al. (2010) formulated the integrated berth allocation and crane assignment as a quadratic model and a linearized formulation. Their models minimize the total quay crane profiles in addition to the housekeeping costs generated by transshipment flows between vessels. These models faced difficulties to solve real-case instances. Hence, the authors proposed a Tabu Search method based on mathematical techniques. Chang et al. (2010) supposed that cranes assignment varies within the planning horizon. They used a
mathematical formulation embedded in a rolling horizon algorithm to solve medium size instances. In addition, the authors hybridized a parallel genetic algorithm using several priority rule heuristics. The handling time may depend, mainly, on cranes assignment. In order to study the importance of this assumption, Blazewicz et al. (2011) considered the problem as a task scheduling problem using a set of processors. They proposed a suboptimal algorithm that obtains a feasible solution for the discrete version of the problem using its continuous version. Raa et al. (2011) studied the same problem but under real-world considerations as the preferred berthing position, priority of the vessel and the handling time. They proposed a MIP model and tested it on a set of real instances. However, this model is time-consuming for daily managerial decisions. Therefore, the authors proposed a rolling horizon framework based on the proposed MIP. Using congested artificial data, the method showed its efficiency. In addition, Vacca et al. (2013) developed a new model for the tactical berth allocation where the decisions of berthing and crane assignment were studied simultaneously. They proposed a branch and price algorithm to solve it. In their work, several accelerating techniques for the master and the pricing problem were presented. The results showed that the integration approach might be efficient in different cases. Recently, Agra and Oliveira (2018) studied the integrated berth allocation, quay crane assignment and scheduling problem motivated by a real case where a heterogeneous set of cranes was considered. They proposed a MIP model based on the relative position formulation. In order to enhance the bounds of their mathematical formulation, they suggested a new model based on the discretization of the time and space variables. These enhancements were used in a branch and cut method as a relaxing. The integration of BAP and CAP was also investigated using different metaheuristics. Yang et al. (2012) proposed an evolutionary algorithm with multiple stages. First, each stage solves a specific sub-problem and then, the algorithm computes an approximation solution to the problem. In addition, Chang et al. (2011) dealt with a dynamic allocation model using objective programming. The idea was to propose a rolling-horizon technique for the BAP and CAP under the objective of minimizing the total berthing location deviation, the total penalty and the energy consumption by quay cranes. To solve large instances, the authors suggested a hybrid parallel genetic algorithm (HPGA), which combines the parallel genetic algorithm (PGA) and a heuristic algorithm. Diabat and Theodorou (2014) considered the scheduling aspect of the integrated problem (BACASP). They proposed a MIP formulation and a genetic algorithm in which the authors defined a problem-specific chromosome and a set of insertions and selection strategies. Then, Fu and Diabat (2015) implemented a Lagrangian relaxation based for the decomposition of the problem. The authors tested their approach using several problem instances. The results were compared to those obtained by commercial software and to another heuristic, namely a Genetic Algorithm (GA) presented in Diabat and Theodorou (2014).

In the bulk port context, Barros et al. (2011) were interested in the berth allocation problem in bulk port under tidal and stock level restrictions. The main decision for this problem is to define when vessels should be allocated to berths and that during tidal time windows while minimizing the overall cost. In this work, berths are homogeneous and stocks must be kept in safety levels. The problem was represented as a transportation problem and they proposed an integer linear programming formulation to solve it. To deal with the problem complexity, they proposed a simulated annealing-based algorithm. Umang et al. (2013) presented three formulations to solve the dynamic hybrid berth allocation problem. The main differences between the container and bulk port operations are the account for a cargo type and the fixed equipment facilities as conveyors that may be installed in certain berths only. The authors investigated the coordination between seaside and yard side operations. The objective is to minimize the total service time of vessels. The authors developed a generalized set partitioning GSPP model for the problem and showed its efficiency. An alternative can be used in case of GSPP fails to generate the optimal solution in a reasonable time, which is adding bulk-specific components to the metaheuristic, based on squeaky wheel optimization. Rodrigues et al. (2016) proposed a MIP model for the continuous berth allocation problem under cargo operation restrictions to minimize the time that vessels stayed in the port. They supposed that some cargo could not be handled in certain berths along the pier. This assumption is observed in the oil and gas logistics context. Real data showed that the model can solve instances up to 147 vessels with 440 meters of pier and results confirm the possibility of significant gains. In addition,
Ernst et al. (2017) proposed two MIP formulations for the continuous berth allocation problem in dry bulk port context. The main restriction considered is the tidal time window for the vessel departure. The authors presented several properties for the optimal solution and some cuts to tighten the models. The time-indexed model was shown more suitable for large instances. Rolling horizon strategy was used for both seaside and yard side operations. Chang et al. (2011) studied the yard crane scheduling by proposing an integer-programming model to minimize the total delay of tasks at blocks. The model is less efficient considering large-scale instances. Hence, the authors proposed a simulation based-heuristic and then a genetic algorithm to enhance the quality of the initial solutions given by the heuristic. For seaside operations, Xiao et al. (2014) studied large-scale integral scheduling of dynamic continuous berth allocation and crane assignment problem. They proposed a multi-objective MIP formulation in order to optimize both vessels berthing positions and delays. This model was adapted and embedded in a rolling horizon framework in which the time effort is linear with the number of scheduled vessels. The authors showed, via their results, that the rolling horizon parameters had a significant impact on the quality of a schedule. Lately, Hou (2017) investigated the dynamic continuous berth allocation problem considering containership emissions. The author proposed a mixed integer non-linear programming (MINLP) model to minimize the total penalty cost, fuel cost and emissions caused by the deviations from the preferred berth position and delays. To handle the difficulty of the model, the researchers developed a rolling-horizon strategy and a heuristic algorithm that showed satisfactory results based on a numerical case study. In the literature, the multi-quay BACAP problem in bulk context is less studied especially under real-world restrictions. Henceforth, in this paper, we studied the multi-quay berth allocation and crane assignment problem under availability and high tides restrictions. We denoted this problem as MBACAP-NVA. A mixed integer programming model for the MBACAP-NVA. In the following, we provide a detailed description for the problem and its characteristics. Then, we formulate the MBACAP-NVA using a mixed integer programming (MIP) model.

## 3. Problem description

In this paper, we consider a version of the problem in which there are multi continuous quays and in which the number of assigned cranes remains fixed during the loading process. The arrival of vessels is considered dynamic and the handling time depends on the number of cranes used to load a vessel. The objective of the MBACAP-NVA is to find the least-delayed berth plan for a set of vessels using a multi-quay bulk terminal and a given number of available quay cranes. We were inspired by an industrial port in Morocco used for bulk cargo. It is an important component of our industrial partner's supply chain. It ensures two major logistic operations, which are unloading raw materials for the production and loading of final products for final customers. Formally, this bulk terminal contains a set of quays $Q$ with different lengths $L_q$ and each one is equipped with $Q_q$ a set of mobile cranes with a fixed loading/unloading rate $d_q$. Vessels arrive within a predefined planning horizon $H$ and each vessel $j \in V$ has an arrival date $r_j$ and an estimated departure time $Dep_j$. Each vessel may request different quantities $C_{jf}$ of more than one quality $f \in F_j$. Where $F_j$ denotes the set of qualities requested by vessel $j$. During the loading process, the handling time depends on several factors. First, all vessels require a pre-loading *Pre* and post-loading time *Post*, in addition to a draft survey $t_{ds}$ in the case of multiple qualities. Then, the variable handling time is calculated for, each vessel, considering loaded quantities, transfer rate between storage areas and quays, and the number of cranes used for cargo loading. To simplify the problem, we consider that the transfer rate depends only on $d_q$. In addition, due to preventive maintenance of cranes or to bad weather conditions, the port may be unavailable during certain periods $[start_i, finish_i]$, $i \in NVA$. We denote by $NVA$ the set of unavailability periods. Then, each vessel should leave the docks within a high tide interval $[s_{tide}^p, f_{tide}^p]$, $p \in HT$. We define $HT$ as the set of high tides periods over the planning horizon $H$.

### 3.1. A mixed integer programming model

In the following, we present the notations used in the proposed MIP model:
$H$ the planning horizon (in hours),

$Sc$ the security distance between berthed vessels,

$l_j$ the length of vessel j,

$P_j$ the penalty delay for vessel j,

$A_j$ the maximum number of cranes that can be used to load vessel j,

$H_{max}$ a big number in hours (the last period in our planning horizon),

$L_{max}$ a big number in meters.

As decisions variables, we define for each vessel j, $S_j \ge 0$ the berthing start date (in hours), $b_j \ge 0$ the berthing position in the quay (in meters), $h_j \ge 0$ the handling time (in hours) and the possible tardiness $T_j \ge 0$. In addition the MIP model uses a set of binary variables:

$x_{jk} = 1$ if vessel j is berthed completely at the left of vessel k without overlapping,

$t_{jk} = 1$ if vessel j is berthed completely before vessel k without overlapping,

$y_{jq} = 1$ if vessel j is affected to quay q,

$z_{jcqt} = 1$ if vessel j uses the crane c during the period of time t in quay q,

$g_{jcq} = 1$ if crane c is affected to vessel j in quay q,

$IAP_{ji} = 1$ if vessel j is planned after the unavailability period $i \in NVA$,

$IAV_{ji} = 1$ if vessel j is planned before the unavailability period $i \in NVA$,

$\gamma_{jp} = 1$ if the departure of vessel j is planned in the high tide $p \in HT$.

These variables and the defined notations are the key elements of the following MIP model:

$$ \min \sum_{j \in V} P_j \times T_j \qquad (1) $$

subject to

$$ T_j \ge S_j + h_j + \text{post} - \text{dep}_j \qquad \forall j \in V, \qquad (2) $$

$$ b_j + l_j \le \sum_{q \in Q} L_q y_{jq} \qquad \forall j \in V, \qquad (3) $$

$$ \sum_{q \in Q} y_{jq} = 1 \qquad \forall j \in V \qquad (4) $$

$$ b_j + l_j + Sc - L(1 - x_{jk}) \le b_k \qquad \forall j, k \in V, j \ne k, \qquad (5) $$

$$ x_{jk} + x_{kj} \le 1 \qquad \forall j, k \in V, j \ne k, \qquad (6) $$

$$ t_{jk} + t_{kj} \le 1 \qquad \forall j, k \in V, j \ne k, \qquad (7) $$

$$ S_j + h_j + \text{Post} - H_{max}(1 - t_{jk}) \le S_k - \text{pre} \qquad \forall j, k \in V, j \ne k, \qquad (8) $$
$$y_{jq} + y_{kq} - t_{jk} - t_{kj} - x_{jk} - x_{kj} \leq 1 \qquad \forall k, j \in V, j \neq k, q \in Q, \qquad (9)$$

$$t_{jk} + t_{kj} + x_{jk} + x_{kj} \leq 2 + 2(y_{jq} - y_{kq}) \qquad \forall k, j \in V, j \neq k, q \in Q, \qquad (10)$$

$$r_j + Pre \leq S_j \qquad \forall j \in V, \qquad (11)$$

$$\sum_{j \in V} z_{jcqt} \leq 1 \qquad \forall c \in Q_q, q \in Q, t \in H, \qquad (12)$$

$$\sum_{c \in Q_q} g_{jcq} \leq A_j y_{jq} \qquad \forall j \in V, q \in Q, \qquad (13)$$

$$z_{jcqt} \leq g_{jcq} \qquad \forall j \in V, c \in Q_q, q \in Q, t \in H, \qquad (14)$$

$$\sum_{p \in F_j} C_{jp} * y_{jq} \leq \sum_{c \in Q_q} \sum_{t \in H} z_{jcqt} * dq - \sum_{c \in Q_q} g_{jcq} * (|F_j| - 1)t_{ds} \qquad \forall j \in V, q \in Q \qquad (15)$$

$$\sum_{c \in Q_q} \sum_{t \in H} z_{jcqt} - \sum_{c \in Q_q} g_{jcq} * (|F_j| - 1)t_{ds} \leq \left[ \frac{\sum_{p \in F_j} C_{jp}}{d_q} \right] \qquad \forall j \in V, q \in Q, \qquad (16)$$

$$\sum_{t=r_i+pre}^{Hmax} z_{jcqt} \leq h_j \qquad \forall j \in V, c \in Q_q, q \in Q, \qquad (17)$$

$$h_j - H_{max}(1 - g_{jcq}) \leq \sum_{t \in H} z_{jcqt} \qquad \forall j \in V, c \in Q_q, q \in Q, \qquad (18)$$

$$S_j - H_{max}(1 - z_{jcqt}) \leq t * z_{jcqt} \qquad \forall j \in V, c \in Q_q, q \in Q, t \in H, \qquad (19)$$

$$t * z_{jcqt} \leq S_j + h_j - 1 \qquad \forall j \in V, c \in Q_q, q \in Q, t \in H, \qquad (20)$$

$$\sum_{t \in [start_i, finish_i]} z_{jcqt} = 0 \qquad \forall j \in V, c \in Q_q, q \in Q, i \in NVA, \qquad (21)$$

$$IAV_{ji} + IAP_{ji} = 1 \qquad \forall j \in V, i \in NVA, \qquad (22)$$

$$finish_i \times IAP_{ji} \leq S_j - Pre \qquad \forall j \in V, i \in NVA, \qquad (23)$$

$$S_j + h_j + Post \leq start_i \times IAV_{ji} + H_{max}(1 - IAP_{ji}) \qquad \forall j \in V, i \in NVA \qquad (24)$$

$$\sum_{p \in HT} \gamma_{jp} = 1 \qquad \forall j \in V, \qquad (25)$$

$$S_j + h_j + post \geq \sum_{p \in HT} s_{tide}^p \gamma_{jp} \qquad \forall j \in V, \qquad (26)$$

$$S_j + h_j + post \leq \sum_{p \in HT} f_{tide}^p \gamma_{jp} \qquad \forall j \in V, \qquad (27)$$

The objective function (1) minimizes the total cost of the delayed vessels. The tardiness is calculated by the set of constraints (2). Each vessel is assigned to only one quay (4) and the position of a vessel is computed considering quay's length (3). Constraints (5-9) avoid the overlapping between vessels in time and space. This non-overlapping restriction is applied only for vessels affected to the same quay (constraints (10)). A vessel should start its loading after its arrival and the time required for pre-loading operations (11). The constraints (12-14) ensure the resource allocation. A crane cannot handle more than one vessel at a time (12) and the number of used cranes respects the vessel's capacity (13). Constraints (15-18) ensure the demand fulfillment by calculating the required amount of time for the loading. In order to guarantee a continuous flow in every used crane, we propose the set of constraints (19-20). In
this model, we suppose that the preemption of the vessel's loading is not allowed. The model uses the set of constraints (21-24) to schedule a vessel within an available interval of time. The availability restriction may be due to the weather conditions or preventive maintenance of cranes or quays. In addition, the vessel should leave the quay in a high tide period (25-27). In the previous model, we denote by $|F_j|$ the number of qualities supplied by the vessel j.

## 4. A rolling horizon framework for the MBACAP-NVA

In this section, we present a rolling horizon approach considering the integration of the berth allocation and the crane assignment over a fixed planning period. This approach is based on the idea of segmenting the planning horizon into shorter sub-periods. The resulting sub-problems are small enough to be solved in a reasonable time using the proposed MIP model. After generating a partial solution at each period, the rolling horizon method reconstructs a global solution. In this work, the use of such planning method is argued by the problem characteristics: 1) the arrival of vessels is considered dynamic over the planning horizon 2) in some period of the year, vessels may arrive in the same time window due to weather conditions or commercial constraints and then the MIP model may have difficulties to dissipate the congestion. 3) The MIP model efficiency is limited to small/medium instances. In the following, we present a greedy heuristic used in the rolling horizon approach, a congestion dissipation strategy developed to decrease the MIP computational effort and then the overall rolling horizon algorithm.

<caption>**Algorithm 1:** Vessel-quay matching</caption>

1. list= sequence of vessels using FCFS
2. $\pi_q = \emptyset$: q-th quay-permutation in the global solution S
3. $l_v$, $length(q)$ denote, respectively, vessel and quay lengths
4. $q \leftarrow 0$
5. $count \leftarrow 0$
6. **repeat**
7. &nbsp;&nbsp;&nbsp;**for** $v \in list$ **do**
8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $count \le N_{th}$ **then**
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $l_v \le length(q)$ **then**
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assign($v, \pi_q$)
11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$\tau_v \leftarrow A_v$$
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$list = list \setminus \{v\}$$
13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$count \leftarrow count + 1$$
14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$v \leftarrow v + 1$$
18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
19. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
20. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$q \leftarrow q + 1$$
21. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
22. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
23. &nbsp;&nbsp;&nbsp;**until** $list = \emptyset \land q \ge |Q|$;
24. &nbsp;&nbsp;&nbsp;**if** $list \ne \emptyset$ **then**
25. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$N_{th} \leftarrow \infty$$
26. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**goto line 6**
27. &nbsp;&nbsp;&nbsp;**end**
28. &nbsp;&nbsp;&nbsp;**return** S
### 4.1.1. G-FCFS: a greedy heuristic

We represent a solution for MBACAP-NVA as a set of quays $S = (U_{q \in Q}, \pi_q, \tau)$ where each permutation $\pi_q$ contains a list of vessels that can be loaded in the quay $q$ and array $\tau$ where each element $\tau_j$ represents the number of cranes assigned to vessel $j$. The starting point of our idea is inspired by the workstation-balancing assignment (Becker & Scholl, 2006) in which each equipment has the same amount of work to execute. In our problem, we considered the port as a work cell and each quay represents equipment or a workstation. We define a sequence of vessels (tasks) to be loaded (executed) respecting a priority rule. Several priority rules can be used to define a valid sequence of vessels. In the literature, First Come First Served (FCFS) rule was used for many scheduling problems. As we minimize the total delay time for all the vessels, they should be loaded as soon as possible. Hence, we choose FCFS rule to generate an initial sequence. Algorithm 1 is a greedy procedure used to assign vessels to quays based on a predefined order (line 1) and respecting quays length (line 9). As in production line balancing, we define a theoretical capacity $N_{th} = \lceil \frac{|V|}{|Q|} \rceil$, as the maximum number of vessels assigned to each quay (line 8). After matching vessels to quays, we proposed G-FCFS, a constructive heuristic, to generate a feasible solution for the problem. In our approach, we discretized both planning horizon and quays in order to respect time-space constraints. The G-FCFS generates a feasible berthing planning for the initial solution $S$ by calculating for each vessel $v \in \pi_q$ its starting time $S_v$, its berthing position $b_v$, its handling time $h_v$, and the resulting tardiness $T_v$. The first step in our algorithm is to compute the earliest possible starting time respecting quay's availability and the vessels that are loading, and then the corresponding handling time $h_v$. It is calculated using the number of cranes, cargo quantity and the draft survey time. During the planning procedure, we specified, at each period, the number of vessels that are loading. This information is used to define where and when berthing an incoming vessel is possible. At each period, we distinguish three possible situations: 1) where no vessel has been handled 2) where one vessel is loading 3) where more than one is loading. In the first case, the algorithm checks the possibility of starting loading at its earliest starting time avoiding unavailability periods and respecting the departure on a high tide interval. We call this sub-procedure *FindValid$S_v$*. Then, G-FCFS berths the vessel in the first position of the quay. In the case where a vessel is already loading, the algorithm verifies the resource utilization and the number of cranes required by the vessel. Suppose that the vessel in the process is using all available resources and the incoming vessel requires the maximum number of cranes, G-FCFS finds the earliest possible starting time just after the previous vessel finishes its loading and then apply *FindValid$S_v$*. However, if the vessel does not need all available cranes and their utilization is not saturated, the procedure verifies the possibility to schedule the vessel at the same time as the vessel that is loading. However, the algorithm berths it beside the previous vessel respecting the quay length. In case of several vessels are loading, the algorithm checks the resource utilization and the number of cranes required by the vessel. If no resource is available, we schedule it after the earliest departure but respecting the space restriction. However, if there is a match between resources utilization level and their capacity, G-FCFS verifies the space requirement and starts the vessel at the best possible time.

### 4.1.2. Congestion dissipation strategy

Due to the weather conditions or the seasonally strong demand, vessels may arrive or estimate their arrival within a tight time window. However, the planning tool used by our industrial partner becomes less efficient under these circumstances. Especially, when the objective is to minimize the tardiness cost of each vessel and that using a set of limited resources. In order to dissipate the congestion, one can propose a maximal congestion level and major candidates that may produce a bottleneck for the planning method. The strategy requires the definition of a dissipation parameter $\alpha$ that is configurable by the planner. The choice of this parameter depends on the planning objective. If we promote the computation effort over the solution quality, $\alpha$ is set to a small value. Otherwise, we prefer to enhance the solution quality. In addition to the arrival time, the detection of congestion may depend on the technical limitation of the resolution method embedded in the rolling horizon algorithm. In our case, we use the proposed
MIP model for the MBACAP-NVA. The results show that our model is time-efficient for the instances up to eight vessels. Hence, we use it to detect the possible congestion. We resume the dissipation strategy in Algorithm 2. The procedure begins by ordering the vessels using FCFS rule and defines ones that will arrive within the period TW (line 7). Possible congestion is detected (line 8) by using, the limit of our resolution method and then the dissipation begins. First, we construct a feasible schedule for the incoming vessels. G-FCFS computes the maximum planning horizon $TW_{max}$ (line 9). Then, we eliminate the vessels that may be a bottleneck for our resolution method using the configurable parameter $\alpha$ and the possible starting time given by the greedy heuristic. Finally, the algorithm creates $V_a$ and $V_d$, which represent the non-congested vessels and the eliminated vessels. The dissipation strategy is embedded in the overall rolling horizon framework and used to decrease the computational effort.

<table><thead><tr><th colspan="2">Algorithm 2 Congestion dissipation strategy</th></tr></thead><tbody><tr><td>1:</td><td>procedure Cong(list, TW)</td></tr><tr><td>2:</td><td>list: sequence of vessels using FCFS</td></tr><tr><td>3:</td><td>TW: a predefined time window;</td></tr><tr><td>4:</td><td>max: a computational limit of our resolution method</td></tr><tr><td>5:</td><td>V<sub>a</sub> = Ø: a set of non-congested vessels</td></tr><tr><td>6:</td><td>V<sub>d</sub> = Ø: a set of congested vessels</td></tr><tr><td>7:</td><td>V<sub>a</sub> &larr; Arrived(list, TW)</td></tr><tr><td>8:</td><td>if |V<sub>a</sub>| &gt; max then</td></tr><tr><td>9:</td><td>(TW<sub>max</sub>, S) &larr; GFCFS(V<sub>a</sub>)</td></tr><tr><td>10:</td><td>for v &isin; V<sub>a</sub> do</td></tr><tr><td>11:</td><td>if S<sub>v</sub> &ge; &alpha;TW<sub>max</sub> then</td></tr><tr><td>12:</td><td>V<sub>d</sub> &larr; V<sub>d</sub> &cup; v</td></tr><tr><td>13:</td><td>V<sub>a</sub> &larr; A\V<sub>d</sub></td></tr><tr><td>14:</td><td>return V<sub>a</sub>, V<sub>d</sub></td></tr></tbody></table>

### 4.1.3. Rolling horizon algorithm

The dynamic vessels arrival sequence of MBACAP-NVA model provides the foundation for the rolling scheduling in this research. The idea is to decompose the planning horizon into several time windows and then solve the problem with a limited number of incoming vessels.

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Vessels overlapping over consecutive time windows</figcaption></figure>

This approach depends on several parameters as time windows duration, the congestion degree and overlapping between consecutive time intervals. In our case, we used the MIP model to solve, optimally, the sub-problems by fixing their correspondent horizons and the list of incoming vessels. Embedding the MIP model in a rolling horizon algorithm may generate a vessel loading over more than a time window. In other words, a vessel may start its loading within a certain period and finishes at the next one. To avoid this complication, the algorithm updates the scheduling information of overlapping vessels $V_e$. Algorithm
3 computes, for each $v \in V_e$, their new arrival (the completion of the current time window) and the remaining handling time (line 11). The greedy heuristic generates a planning horizon, which is used as the maximum time windows for the MIP model (line 8-9). In line 12, Algorithm 3 constructs the global solution over the overall planning horizon $H$ as a concatenation of partial solutions found at each sub-period $TW \in H$. In the proposed approach, we investigate the flexibility of the resulting planning by allowing the planner to set up the main parameters in order to capture industrial characteristics.

## 5. Computational results and discussion

This section reports the computational experiments that were performed for testing the MIP model and the efficiency of the rolling horizon approach. The algorithms were implemented in C++, tests conducted on an Intel Core i7 2600 CPU (2.8 GHz), and 16 GB RAM. We used ILOG IBM CPLEX 12.7 solver for the MIP model. The tests' instances were obtained from our industrial partner. The baseline data covers a time horizon of 15 days. It provided information about incoming vessels. Each one is characterized by its physical attributes: its length and the maximum number of cranes for loading. In addition, each vessel has a set of products to be loaded. Based on real-data, vessels can supply one or two products. Each vessel defines an estimated arrival time, a time window for its loading, and delay penalties. We designed a set of instances for each $n \in \{6, 7, 8, 10, 12, 14\}$. Regarding the congestion, we differentiate three scenarios: High Congestion, Medium Congestion, and Low Congestion. The overcrowding of vessels is determined by the time window in which boats arrive. In addition, we distinguish two types of instances: one product and two products.

<table><thead><tr><th colspan="2">Algorithm 3 Rolling horizon algorithm</th></tr></thead><tbody><tr><td>1:</td><td><i>list</i>: sequence of vessels using FCFS</td></tr><tr><td>2:</td><td><i>TW</i>: a predefined time window</td></tr><tr><td>3:</td><td><i>V</i><sub>a</sub> = Ø: a set of non-congested vessels</td></tr><tr><td>4:</td><td><i>V</i><sub>d</sub> = Ø: a set of congested vessels</td></tr><tr><td>5:</td><td><i>V</i><sub>e</sub> = Ø: a set of vessels in load</td></tr><tr><td>6:</td><td><b>for</b> <i>TW</i> ∈ <i>H</i> <b>do</b></td></tr><tr><td>7:</td><td>&nbsp;&nbsp;&nbsp;&nbsp;(<i>V</i><sub>a</sub>, <i>V</i><sub>d</sub>) ← Cong(<i>list</i>, <i>TW</i>)</td></tr><tr><td>8:</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>TW</i><sub>max</sub> ← GFCFS(<i>V</i><sub>a</sub>)</td></tr><tr><td>9:</td><td>&nbsp;&nbsp;&nbsp;&nbsp;(<i>SubS</i>, <i>V</i><sub>e</sub>) ← MIP(<i>V</i><sub>a</sub>, <i>TW</i><sub>max</sub>)</td></tr><tr><td>10:</td><td><b>if</b> <i>V</i><sub>d</sub> ≠ Ø ∧ <i>V</i><sub>e</sub> ≠ Ø <b>then</b></td></tr><tr><td>11:</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>V</i><sub>a</sub> ← Update(<i>V</i><sub>d</sub>, <i>V</i><sub>e</sub>)</td></tr><tr><td>12:</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>S</i> ← SubS</td></tr><tr><td>13:</td><td><b>return</b> <i>S</i></td></tr></tbody></table>

In the following, we present the Port terminal characteristics considered in all instances:

* The security distance between berthed vessels *Sc* is equal to *5m*.

* For high tide time-windows, we consider a daily period of *6 hours* (given by weather agency).

* The terminal contains four quays with the respective lengths: *400,200,200,180* and the respective rates: *2000 t/h, 1500 t/h, 1000 t/h, 1000 t/h*,

* The availability restriction, in this problem, is due to the planned maintenance and weather conditions.

In Table 1, we summarize the information about the unavailability of quays given by the baseline data.
<table><caption>**Table 1**
Unavailability periods over the planning horizon</caption><thead><tr><th>Unavailability periods</th><th>start</th><th>finish</th></tr></thead><tbody><tr><td>1</td><td>11/06/2017 11:00</td><td>11/06/2017 16:00</td></tr><tr><td>2</td><td>13/06/2017 17:00</td><td>14/06/2017 04:00</td></tr></tbody></table>

## 5.1. Results for the proposed MIP

In the following, we experimented the proposed MIP model considering low congestion. Table 2 summarizes the computational results of the MIP model. The first two columns correspond to characteristics of instances: the number of vessels (n), the instance (Inst_m_n) where n is the number of the vessels and m the number of the instance. Then, we represent the following results: the execution time (Time (s)) required to find the optimal solution in seconds and the optimal objective function value (Optimal) given by CPLEX. In addition, we calculate the average optimal and the average execution time for each n. We note that the results of our MIP model showed its efficiency for the instances up to 10 vessels. Further, the average time did not exceed 1443.6 seconds. However, solving instances with more than one product required a significant computational effort. For $n \ge 8$, we remark an expressive gap between the average times for one-product and multi-products instances.

<table><caption>**Table 2**
The results of the MIP model under low congestion level</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Instances</th><th colspan="2">One product</th><th colspan="2">Multi-product</th></tr><tr><th>Optimal</th><th>Time(s)</th><th>Optimal</th><th>Time(s)</th></tr></thead><tbody><tr><td rowspan="3">6</td><td>Inst_1_6</td><td>3596</td><td>6120,00</td><td>0</td><td>198,00</td></tr><tr><td>Inst_2_6</td><td>0</td><td>234,00</td><td>255</td><td>288,00</td></tr><tr><td>Inst_3_6</td><td>2596</td><td>24,00</td><td>0</td><td>294,00</td></tr><tr><td colspan="2">Average</td><td>2064</td><td>120</td><td>120,00</td><td>258</td></tr><tr><td rowspan="3">7</td><td>Inst_1_7</td><td>0</td><td>234,00</td><td>0</td><td>354,00</td></tr><tr><td>Inst_2_7</td><td>0</td><td>384,00</td><td>0</td><td>630,00</td></tr><tr><td>Inst_3_7</td><td>0</td><td>66,00</td><td>0</td><td>90,00</td></tr><tr><td colspan="2">Average</td><td>0</td><td>228</td><td>228,00</td><td>354</td></tr><tr><td rowspan="3">8</td><td>Inst_1_8</td><td>2562</td><td>618,00</td><td>0</td><td>780,00</td></tr><tr><td>Inst_2_8</td><td>0</td><td>516,00</td><td>0</td><td>954,00</td></tr><tr><td>Inst_3_8</td><td>0</td><td>54,00</td><td>0</td><td>648,00</td></tr><tr><td colspan="2">Average</td><td>854</td><td>396</td><td>396,00</td><td>798</td></tr><tr><td rowspan="3">10</td><td>Inst_1_10</td><td>0</td><td>120,00</td><td>0</td><td>1752,00</td></tr><tr><td>Inst_2_10</td><td>0</td><td>918,00</td><td>4050</td><td>1068,00</td></tr><tr><td>Inst_3_10</td><td>0</td><td>750,00</td><td>0</td><td>1512,00</td></tr><tr><td colspan="2">Average</td><td>0</td><td>594</td><td>594,00</td><td>1443,6</td></tr></tbody></table>

Table 3 shows the impact of the congestion level on the computational effort. We studied three levels of congestion: high, medium and low. The high congestion is considered when all the vessels arrive within the same period and have a tight due date for leaving the docks. In Table 3, the first two columns correspond to the number of vessels (n) and the congestion level (Congestion). The obtained results are summarized as follows: (Avg_opt) column represents the average objective function value given by CPLEX and (Avg_time (s)) column denotes the average execution time in seconds. According to Table 3, the MIP model is less efficient in solving some particular cases, especially for medium congestion. In addition, the model cannot solve optimally the instances with more than 10 vessels and under the multi-product assumption. One can state that the execution time was more remarkable in the case of medium congestion level. We explain this phenomenon by taking into consideration the visibility over the planning horizon. Indeed, the high congestion level provides a clear vision of the vessels that could arrive. Therefore, the dynamic impact, in this case, is reduced. That explains the gap between the execution times of the high and medium congestion level.
<table><caption>**Table 3**
The impact of vessel's congestion on the MIP model</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Congestion</th><th colspan="2">One product</th><th colspan="2">Multi-product</th></tr><tr><th>Avg_opt</th><th>Avg_time(s)</th><th>Avg_opt</th><th>Avg_time(s)</th></tr></thead><tbody><tr><td rowspan="3">6</td><td>High</td><td>0.00</td><td>120</td><td>774.00</td><td>234</td></tr><tr><td>Medium</td><td>4644.44</td><td>114</td><td>4719.66</td><td>282</td></tr><tr><td>Low</td><td>2064</td><td>120</td><td>85</td><td>258</td></tr><tr><td rowspan="3">7</td><td>High</td><td>510.00</td><td>396</td><td>50.00</td><td>726</td></tr><tr><td>Medium</td><td>6772.66</td><td>402</td><td>1736.66</td><td>978</td></tr><tr><td>Low</td><td>0</td><td>228</td><td>0</td><td>354</td></tr><tr><td rowspan="3">8</td><td>High</td><td>629.66</td><td>1170</td><td>2166.66</td><td>2202</td></tr><tr><td>Medium</td><td>4110.00</td><td>1596</td><td>3834.66</td><td>1776</td></tr><tr><td>Low</td><td>854</td><td>396</td><td>0</td><td>798</td></tr><tr><td rowspan="3">10</td><td>High</td><td>540.00</td><td>2958</td><td>-</td><td>7200</td></tr><tr><td>Medium</td><td>8516.00</td><td>3036</td><td>-</td><td>7200</td></tr><tr><td>Low</td><td>0</td><td>594</td><td>1350</td><td>1443,6</td></tr></tbody></table>

Dealing with one product, the running time does not exceed 1h for all the scenarios. On the other hand, the multi-product aspect has a significant influence on computational time. We remark, for all congestion levels, that the model could not solve instances of 10 vessels with multi-product within 7200 seconds (the solver's time limit). The level of congestion makes the model more difficult to solve and CPLEX could not find an integer solution quickly. In summary, the results do not show a clear pattern of behavior. What is significant is that the results are limited by the size of the instances and the number of products. This motivates the proposition of a heuristic approach to the problem.

## 5.2. Results for the rolling horizon algorithm

In this section, we present the results given by the rolling horizon approach. Table 4 compares the results given by the proposed MIP model and the algorithm based on the rolling horizon (RH) concept. In this study, we consider three sub-periods of the overall planning horizon and we fix the dissipation parameter $\alpha$ to 0.5. We use the following metrics: the average time in seconds (Avg_time MIP (s)) required to find the optimal objective function value, the average gap (Avg gap (%)) between RH and CPLEX solutions and the average execution time in seconds required by the RH. We remark that the rolling horizon is efficient for instances up to 10 vessels. In the case of one product, the average gap did not exceed 2.5%. However, for the multi-product, the algorithm provided solutions with a maximum gap of 4.65%. The rolling horizon did not reach the optimality for some high-level congestion due to the choice of the parameter $\alpha$. From computational effort perspectives, the RH decreases the execution time in all the cases. Indeed, we remark a significant improving of the execution time up to 70% for $n \ge 8$.

<table><caption>**Table 4**
The results of the rolling horizon approach for small and medium instances</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Congestion</th><th colspan="3">One product</th><th colspan="3">Multi-product</th></tr><tr><th>Avg-gap (%)</th><th>Avg_time MIP(s)</th><th>Avg_time RH(s)</th><th>Avg-gap (%)</th><th>Avg_time MIP(s)</th><th>Avg_time RH(s)</th></tr></thead><tbody><tr><td rowspan="3">6</td><td>High</td><td>0.0</td><td>120</td><td>90</td><td>0.0</td><td>234</td><td>132</td></tr><tr><td>Medium</td><td>0.0</td><td>114</td><td>78</td><td>0.0</td><td>282</td><td>228</td></tr><tr><td>Low</td><td>0.0</td><td>120</td><td>102</td><td>0.0</td><td>258</td><td>186</td></tr><tr><td rowspan="3">7</td><td>High</td><td>0.9</td><td>396</td><td>312</td><td>0.0</td><td>726</td><td>378</td></tr><tr><td>Medium</td><td>0.0</td><td>402</td><td>282</td><td>0.5</td><td>978</td><td>576</td></tr><tr><td>Low</td><td>0.0</td><td>228</td><td>96</td><td>0.0</td><td>354</td><td>144</td></tr><tr><td rowspan="3">8</td><td>High</td><td>0.0</td><td>1170</td><td>180</td><td>4.6</td><td>2202</td><td>1578</td></tr><tr><td>Medium</td><td>0.0</td><td>1596</td><td>576</td><td>0.0</td><td>1776</td><td>618</td></tr><tr><td>Low</td><td>0.0</td><td>396</td><td>336</td><td>0.0</td><td>798</td><td>378</td></tr><tr><td rowspan="3">10</td><td>High</td><td>2.5</td><td>2958</td><td>1158</td><td>-</td><td>7200</td><td>7200</td></tr><tr><td>Medium</td><td>1.3</td><td>3036</td><td>918</td><td>-</td><td>7200</td><td>7200</td></tr><tr><td>Low</td><td>0.0</td><td>594</td><td>252</td><td>0.36</td><td>1443,6</td><td>582</td></tr></tbody></table>
The congestion dissipation depends on the value of $\alpha$. We proposed different values to investigate our strategy. We studied two more scenarios: 1) the quality over the computational effort ($\alpha$ = 0.75), 2) the computational effort over the quality ($\alpha$ = 0.25). Tables 5 and 6 resume the results obtained by our rolling horizon algorithm under different dissipation strategies.

Table 5

<table><caption>The results of the rolling horizon algorithm under high dissipation strategy</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Congestion</th><th colspan="4">α = 0.25</th></tr><tr><th colspan="2">One product</th><th colspan="2">Multi-product</th></tr><tr><th></th><th></th><th>Avg_opt</th><th>Avg_time(s)</th><th>Avg_opt</th><th>Avg_time(s)</th></tr></thead><tbody><tr><td rowspan="2">6</td><td>High</td><td>0.00</td><td>120</td><td>774.00</td><td>180</td></tr><tr><td>Medium</td><td>4644.44</td><td>54</td><td>4719.66</td><td>264</td></tr><tr><td rowspan="2">7</td><td>High</td><td>1347.66</td><td>222</td><td>50.00</td><td>468</td></tr><tr><td>Medium</td><td>6772.66</td><td>402</td><td>1736.66</td><td>504</td></tr><tr><td rowspan="2">8</td><td>High</td><td>929.66</td><td>642</td><td>5166.66</td><td>1176</td></tr><tr><td>Medium</td><td>4110.00</td><td>714</td><td>3834.66</td><td>1212</td></tr><tr><td rowspan="2">10</td><td>High</td><td>987.00</td><td>1764</td><td>774.00</td><td>3018</td></tr><tr><td>Medium</td><td>10248.33</td><td>2370</td><td>4719.66</td><td>4590</td></tr></tbody></table>

Table 6

<table><caption>The results of the rolling horizon algorithm under low dissipation strategy</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Congestion</th><th colspan="4">α = 0.75</th></tr><tr><th colspan="2">One product</th><th colspan="2">Multi-product</th></tr><tr><th></th><th></th><th>Avg_opt</th><th>Avg_time(s)</th><th>Avg_opt</th><th>Avg_time(s)</th></tr></thead><tbody><tr><td rowspan="2">6</td><td>High</td><td>0.00</td><td>120</td><td>774.00</td><td>240</td></tr><tr><td>Medium</td><td>4644.44</td><td>114</td><td>4719.66</td><td>294</td></tr><tr><td rowspan="2">7</td><td>High</td><td>510.00</td><td>696</td><td>50.00</td><td>678</td></tr><tr><td>Medium</td><td>6772.66</td><td>822</td><td>1736.66</td><td>1002</td></tr><tr><td rowspan="2">8</td><td>High</td><td>629.66</td><td>1428</td><td>4263.00</td><td>2406</td></tr><tr><td>Medium</td><td>4110.00</td><td>2184</td><td>3834.66</td><td>2394</td></tr><tr><td rowspan="2">10</td><td>High</td><td>1478.33</td><td>6606</td><td>-</td><td>7200</td></tr><tr><td>Medium</td><td>10987.66</td><td>6300</td><td>1326.66</td><td>7200</td></tr></tbody></table>

In Table 5, we studied the impact of promoting computational effort on the quality of the solution. On one hand, a lower dissipation parameter decreased the computational effort. This improvement reduced the execution time by 30% for medium instances ($n \ge 8$). On the other hand, the total cost of tardiness has slightly increased in some instances. However, the resulting cost remained acceptable. Table 6 highlights the results in case of the solution quality is more important than the computational effort ($\alpha$ = 0.75). Indeed, by using, the algorithm becomes more efficient in terms of minimizing the total cost of tardiness. However, the execution time was importantly increased. The results obtained for all the scenarios are very realistic. Naturally, the choice of the dissipation parameter affects the efficiency of our algorithm. Therefore, $\alpha$ will remain as a decisional parameter for our industrial partner, who will calibrate its value according to its needs. $\alpha$ is a tuning parameter that helps the decisional board to arbitrate between quality and rapidity of the solutions. In summary, the results showed the efficiency of our rolling horizon algorithm for small and medium instances, which represent the actual industrial settings. In the following, we experiment the approach for large instances.

Table 7

<table><caption>The results of the rolling horizon algorithm for large instances ($\alpha$=0.5)</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Congestion</th><th colspan="2">One product</th><th colspan="2">Multi-product</th></tr><tr><th>Avg_value</th><th>Avg_time RH(s)</th><th>Avg_value</th><th>Avg_time RH(s)</th></tr></thead><tbody><tr><td rowspan="3">12</td><td>High</td><td>194.33</td><td>2208</td><td>1475.33</td><td>2952</td></tr><tr><td>Medium</td><td>1200</td><td>2400</td><td>1405</td><td>3426</td></tr><tr><td>Low</td><td>0</td><td>1044</td><td>986</td><td>2196</td></tr><tr><td rowspan="3">14</td><td>High</td><td>140</td><td>5832</td><td>22423.67</td><td>6738</td></tr><tr><td>Medium</td><td>2458</td><td>6576</td><td>19654.33</td><td>6006</td></tr><tr><td>Low</td><td>10002.33</td><td>4098</td><td>21877.33</td><td>5772</td></tr></tbody></table>
Table 7 summarizes the results of the rolling horizon algorithm for large instances. We use the “Avg_value” column as the objective function value given by our algorithm. According to the experiments, the rolling horizon algorithm was able to compute the total cost of tardiness for the instances for which the MIP model did not reach the optimal within 7200 seconds. The results showed that the computational effort was very high. However, it did not overpass the time limit.

# 6. Conclusion and perspectives

In this paper, we have studied the integrated berth allocation and crane assignment problem with availability constraints and high tides restrictions in bulk port context. We were guided by a real case study of a port owned by our industrial partner. We proposed a MIP model for the problem under real-word constraints. The model was shown efficient for small and medium size instances. These instances were based on the industrial settings given by our partner. Further, we investigated the impact of the congestion level on the proposed MIP model. According to the experiments, the model is sensitive to the congestion, and especially in case of the medium level. In order to reach an acceptable ratio between the solution quality and the computational effort, we implemented a rolling horizon algorithm based on a novel approach to dissipate the congestion. The results showed that the algorithm depends on the choice of the dissipation parameter and the objective of the planner. The rolling horizon approach was shown efficient for small and medium instances and very promising for large instances. It is important to mention that the proposed model can be applied to any bulk port that has the same operating restrictions. In future research, we intend to compute a tight lower bound for the problem to validate our results for large instances. Another direction of research will be to propose a metaheuristic for the problem to solve the large instances with aim of decreasing the computational effort.

# References

* Agra, A., & Oliveira, M. (2018). MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem. *European Journal of Operational Research*, 264(1), 138-148.

* Barros, V. H., Costa, T. S., Oliveira, A. C., & Lorena, L. A. (2011). Model and heuristic for berth allocation in tidal bulk ports with stock level constraints. *Computers & Industrial Engineering*, 60(4), 606-613.

* Becker, C., & Scholl, A. (2006). A survey on problems and methods in generalized assembly line balancing. *European Journal of Operational Research*, 168(3), 694-715.

* Bierwirth, C., & Meisel, F. (2015). A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. *European Journal of Operational Research*, 244(3), 675-689.

* Blazewicz, J., Cheng, T. E., Machowiak, M., & Oguz, C. (2011). Berth and quay crane allocation: a moldable task scheduling model. *Journal of the Operational Research Society*, 62(7), 1189-1197.

* Chang, D., Jiang, Z., Yan, W., & He, J. (2010). Integrating berth allocation and quay crane assignments. *Transportation Research Part E: Logistics and Transportation Review*, 46(6), 975-990.

* Chang, D., Jiang, Z., Yan, W., & He, J. (2011). Developing a dynamic rolling-horizon decision strategy for yard crane scheduling. *Advanced Engineering Informatics*, 25(3), 485-494.

* Cheng, J. K., Tahar, R. M., & Ang, C. L. (2011). A system dynamics approach to operational and strategic planning of a container terminal. *International Journal of Logistics Systems and Management*, 10(4), 420-436.

* Diabat, A., & Theodorou, E. (2014). An integrated quay crane assignment and scheduling problem. *Computers & Industrial Engineering*, 73, 115-123.

* Ernst, A. T., Oğuz, C., Singh, G., & Taherkhani, G. (2017). Mathematical models for the berth allocation problem in dry bulk terminals. *Journal of Scheduling*, 20(5), 459-473.

* Fu, Y. M., & Diabat, A. (2015). A Lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem. *Applied Mathematical Modelling*, 39(3-4), 1194-1201.

* Giallombardo, G., Moccia, L., Salani, M., & Vacca, I. (2010). Modeling and solving the tactical berth allocation problem. *Transportation Research Part B: Methodological*, 44(2), 232-245.
Hou, J. (2017, September). Dynamic berth allocation problem with two types of shore power for containership based on rolling horizon strategy. *In Intelligent Transportation Engineering (ICITE), 2017 2nd IEEE International Conference* on (pp. 144-149).

Imai, A., Sun, X., Nishimura, E., & Papadimitriou, S. (2005). Berth allocation in a container port: using a continuous location space approach. *Transportation Research Part B: Methodological, 39*(3), 199-221.

Iris, Ç., Pacino, D., & Ropke, S. (2017). Improved formulations and an Adaptive Large Neighborhood Search heuristic for the integrated berth allocation and quay crane assignment problem. *Transportation Research Part E: Logistics and Transportation Review, 105*, 123-147.

Iris, Ç., Pacino, D., Ropke, S., & Larsen, A. (2015). Integrated berth allocation and quay crane assignment problem: Set partitioning models and computational results. *Transportation Research Part E: Logistics and Transportation Review, 81*, 75-97.

Liang, C., Huang, Y., & Yang, Y. (2009). A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning. *Computers & Industrial Engineering, 56*(3), 1021-1028.

Meisel, F., & Bierwirth, C. (2009). Heuristics for the integration of crane productivity in the berth allocation problem. *Transportation Research Part E: Logistics and Transportation Review, 45*(1), 196-209.

Park, Y. M., & Kim, K. H. (2005). A scheduling method for berth and quay cranes. *In Container Terminals and Automated Transport Systems* (pp. 159-181). Springer, Berlin, Heidelberg.

Raa, B., Dullaert, W., & Van Schaeren, R. (2011). An enriched model for the integrated berth allocation and quay crane assignment problem. *Expert Systems with Applications, 38*(11), 14136-14147.

Rodriguez-Molins, M., Salido, M. A., & Barber, F. (2014). A GRASP-based metaheuristic for the Berth Allocation Problem and the Quay Crane Assignment Problem by managing vessel cargo holds. *Applied intelligence, 40*(2), 273-290.

Rodrigues, V., Morabito, R., Yamashita, D., da Silva, B., & Ribas, P. (2016). Ship routing with pickup and delivery for a maritime oil transportation system: MIP model and heuristics. *Systems, 4*(3), 31.

Stopford, M. (2013). Maritime economics. Routledge. (https://www.routledge.com/Maritime-Economics-3e-3rd-Edition/Stopford/p/book/9780415275583).

Umang, N., Bierlaire, M., & Vacca, I. (2013). Exact and heuristic methods to solve the berth allocation problem in bulk ports. *Transportation Research Part E: Logistics and Transportation Review, 54*, 14-31.

Vacca, I., Salani, M., & Bierlaire, M. (2013). An exact algorithm for the integrated planning of berth allocation and quay crane assignment. *Transportation Science, 47*(2), 148-161.

Xiao, L., & Hu, Z. H. (2014). Berth allocation problem with quay crane assignment for container terminals based on rolling-horizon strategy. *Mathematical Problems in Engineering*.

Yang, C., Wang, X., & Li, Z. (2012). An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal. *Computers & Industrial Engineering, 63*(1), 243-253.

<figure><img src="image_4.png" /></figure>