Hamza Bouzekri
email: hamza.bouzekri@emines.um6p.ma

Gülgün Alpan
email: gulgun.alpan@grenoble-inp.fr

Vincent Giard
email: vincent.giard@dauphine.psl.eu

A Dynamic Hybrid Berth Allocation Problem with Routing Constraints in Bulk Ports

Keywords: Berth Allocation Problem, Conveyor System, Bulk Ports

The Berth Allocation Problem (BAP) is considered as one of the most important operational problems in the seaside area of ports. It refers to the problem of assigning a set of vessels to a given berth layout within a given time horizon. In this paper, we study the dynamic and hybrid case of the BAP in the context of bulk ports with multiple quays, different water depths, and heterogeneous loading equipment, considering routing constraints (routes between storage hangars and berths). This study is motivated by the operations of OCP Group, a world leader in the phosphate industry, at the bulk port of Jorf Lasfar in Morocco, recognized as the largest ore port in Africa. The objective of the problem is to enhance the coordination between the berthing and yard activities, besides maximizing the difference between the despatch money and the demurrage charges of all berthed vessels. We propose an integer linear programming model formulated with predicates, which ensures maximum flexibility in the implementation of the model. Finally, the proposed model is tested and validated through numerical experiments based on instances inspired by real bulk port data. The results show that the model can be used to solve to optimality instances with up to 40 vessels within reasonable computational time.

Introduction

Although containerization has played a significant role in developing the port sector and maritime transport, bulk cargoes are still the essential and enduring trades that support the dynamism of maritime shipping. It has to be noted that bulk port operations are very different from container port operations. Indeed, in bulk ports, it is necessary to consider the cargo type and to model the interaction between the storage locations of goods on the yard and the berthing locations of vessels. Hence, establishing a set of feasible routes between berths and storage locations to guarantee that goods are shipped on schedule when making berth allocation decisions, is critical.

Our analysis considers the bulk port of Jorf Lasfar where a complex conveyor system, composed of different routes that share one or more conveyor belts, is used to transport goods from storage hangars to berths. In addition, we consider the draft restrictions on vessels that limit the feasible berthing positions to only those berths having a water depth higher than their draft. To solve this problem, we propose an integer linear programming model. The spatiotemporal constraints of the problem are formulated as disjunctive constraints, thanks to the use of spatiotemporal binary variables. Moreover, all the conditions of the problem are expressed as predicates, which ensures maximum flexibility in the implementation of the model and significantly improves its computational performance. Indeed, it is no longer necessary to introduce the conditions of the problem as constraints in the model, and the space search of solutions becomes smaller.

The rest of the paper is organized as follows: Section 2 provides a literature review. In Sections 3 and 4, the problem and the mathematical formulation are introduced. The results of the numerical experiments are reported in Section 5. Finally, conclusions and future research directions are addressed in Section 6.

Literature Review

The BAP in bulk ports has received little attention in Operations Research literature compared to container ports. In this section, we present a brief review of past research on the BAP in the context of bulk ports. There is a multitude of BAP formulations depending on the spatial and temporal constraints involved in the problem. The spatial attribute concerns the berth layout (discrete, continuous or hybrid) and the draft restrictions, while the temporal one includes the arrival process and the handling time of vessels. Umang et al. [START_REF] Umang | Exact and heuristic methods to solve the berth allocation problem in bulk ports[END_REF] studied the dynamic hybrid BAP taking into account the cargo type and the draft of each vessel. Ernst et al. [START_REF] Ernst | Mathematical models for the berth allocation problem in dry bulk terminals[END_REF] solved the continuous BAP with tidal constraints that limit the departure of fully loaded vessels from the terminal. In contrast, Barros et al. [START_REF] Barros | Model and heuristic for berth allocation in tidal bulk ports with stock level constraints[END_REF] solved the discrete BAP considering homogeneous berths with tide and stock level constraints, prioritizing vessels related to the most critical mineral stock level. Since the problems of berth allocation and yard management are interrelated, some authors have integrated the BAP with the Yard Assignment Problem. Indeed, Robenek et al. [START_REF] Robenek | A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports[END_REF] extended the dynamic hybrid BAP to account for the assignment of yard locations, with the assumptions that each vessel has only one single cargo type.

To solve this integrated problem, the authors proposed an exact solution algorithm based on a branch and price framework and a metaheuristic approach based on critical-shaking neighborhood. Unsal and Oguz [START_REF] Unsal | An exact algorithm for integrated planning of operations in dry bulk terminals[END_REF] proposed a MILP model for an integrated problem that consists of three operations: berth allocation, reclaimer (a large machine used to recover bulk material from a stockpile) scheduling and stockyard allocation, considering tide constraints. In the same logic of integrating problems, Pratap et al. [START_REF] Pratap | An integrated decision support system for berth and ship unloader allocation in bulk material handling port[END_REF] developed a decision support system to solve the integrated problem of berth and ship unloader allocation. Menezes et al. [START_REF] Menezes | A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports[END_REF] integrated production planning and scheduling problems with a First In, First Out (FIFO) policy for berthing vessels. This integrated problem defines the amount and destination of each input or output order between reception, stockyards and piers, establishing a set of feasible routes between these three subsystems, to guarantee that goods are stored and shipped on schedule and to minimize operational costs.

In our paper, we solve the dynamic and hybrid BAP under routing constraints, considering the type of cargo and the capacity limits of the equipment. The storage locations of goods are provided as input parameters to the model. To reduce the gap between the abstract representation of the studied problem and its applicability in real situations, we consider many aspects such as draft restrictions, the heterogeneity of equipment, Charter Party clauses and multiple cargo types on the same vessel.

Problem Description

We consider a bulk port with multiple quays and heterogeneous loading equipment linked to storage hangars by a conveyor system. This latter is composed of different routes that share one or more conveyor belts (see Fig. 1a). Each quay has as hybrid layout where large vessels may occupy more than one berth, however, small vessels cannot share a berth (see Fig. 1b). Each berth is characterized by a length, a fixed loading equipment and a water depth. All the berths of a quay can have the same water depth, or the water depth increases seaward by berths. We assume dynamic vessel arrivals (i.e. Fixed arrival times are given for the vessels; hence, vessels cannot berth before the expected arrival time). Each vessel is characterized by a length, a draft, a maximum waiting time in the harbor and a number of cargo types with different amounts to be loaded in it. These amounts of cargo types can be expressed as batches.

Each batch has an availability date and is stored in a hangar. It has to be noted that the batches to be loaded in a single vessel can be stored in different hangars. Handling times of vessels depend on their berthing position due to the productivity of the loading equipment at the berth. We assume that two (or more) batches cannot be loaded at the same time, but they can be loaded in any order, with no downtime. We also consider technical constraints of vessels that prohibit their berthing at some berths or oblige them to berth at a specific berth. Finally, we consider Charter Party clauses by defining for each vessel the laytime (i.e. contractual handling time), the despatch money (i.e. the bonus payment offered by the shipowner to the charterer if the vessel completes loading before the laytime has expired), and the demurrage charges (i.e. the fees paid by the charterer to the shipowner for exceeding the laytime). These contractual clauses are more detailed in Bouzekri et al. [START_REF] Bouzekri | Integrated Laycan and Berth Allocation Problem[END_REF]. 1b, the pair of berths 3 and 5 share the berth 3, so they cannot be used at the same time).

M v

Maximum waiting time in the harbor of vessel v.

λ v

Length of vessel v.

D v

Draft of vessel v when it is fully loaded.

N vb

Boolean parameter that equals 1 if vessel v can berth at berth b, 0 otherwise.

J v

Contractual handling time of vessel v.

δ v Contractual finishing time of vessel v: A δ J 1, . v v v v     V

O vb

Loading time of vessel v, which equals the sum of loading times of all the batches loaded in this vessel: O θ , , .

v v v i vb vb i v b        I V B K v i v
Date of availability of batch v i to be loaded in vessel v.

H v i v
Storage hangar of batch v i to be loaded in vessel v.

Q r

Index of the berth linked to route r.

S r

Index of the storage hangar linked to route r.

F g r

Boolean parameter that equals 1 if route r belongs to group g of routes that share at least one conveyor belt of the conveyor system, 0 otherwise.

U g

Maximum number of routes that can be used simultaneously in group g of routes.

Variable Description

Mathematical Model

The existence of the decision variable vbt x is subject to four conditions:

1. Vessel v must be able to berth at berth b: N 1 vb  .

A M v v v t    .
The existence of the decision variable v i vbtr y is subject to seven conditions:

1. Conditions 1, 2 and 3 of the existence of the decision variable vbt x .

4. Batch v i can be loaded in vessel v between the expected time of arrival of this ves- sel and its finishing time as it reaches its maximum waiting time in the harbor, minus the loading time of this batch:

A A M O θ v i v v v vb vb t      .
5. Batch v i can be loaded in vessel v only after its date of availability:

K v i v t  .
6. The route used to load the batch v i in vessel v must be linked to the berth b of this vessel: Q r b  . 7. The route used to load the batch v i in vessel v must be linked to the storage hangar of this batch:

H S v i r v  .
We define the intermediate variables v

 and v i v
 , which give for each vessel v, respectively, the berthing position in both decision variables vbt x and v i vbtr

y . N 1 λ L D W A A M , vb v b v b v v v v vbt b t t b x v                  B T V N 1 λ L D W A A M O θ K Q S H , v v i i i v v v vb v b v b v v v vb v r r v vb i i v vbtr b t t t r b b y                         B T R , v v v i     V I
Similarly, we set for each vessel v, the berthing and finishing time v

v v i i vb vbtr t y   
The model for the BAP with routing constraints can be formulated as follows:

  β α v v v v v M ax w u      V (1) s.t. N 1 λ L D W A A M 1, vb v b v b v v v vbt b t t x v                B T V (2) N 1 λ L D W A A M O θ K Q S H 1, v i i i v v v vb v b v b v v v vb v r r v vb i vbtr b t t t r b y                       B T R , v v v i     V I (3) , , v i v v v v v i        V I (4)
, ,

v i v v v v v i        V I (5)
, ,

v i v v v v v i        V I (6)
A M O θ N 1 λ L D W Q S H A K θ 1 1, i v v v vb vb v i i i v v v v v vb v b v b r r v v v vb t t t i vbt r i b r b t t t t y                               I B R , t v     T V (7)
A M O θ N 1 λ L D W F 1 Q S H A K θ 1 U , i v v v vb vb v i g i i v v v v v vb v b v b r r r v v v vb t t t i g vbt r v i b r b t t t t y                                   V I B R , t g     T G (8)
A M N 1 λ L D W A O 1 1, , v v vb v b v b v vb t t t vbt v t t t x t b                       V T B (9)
A M

E 1 N 1 λ L D W A O 1 1, , v v p vb v b v b v vb b t t t vbt v b t t t x t p                           V B T P (10) δ , v v v u v     V (11) δ , v v v w v     V (12) δ , v v v v u w v      V (13) , 0, v v u w v   V (14)
Objective function [START_REF] Umang | Exact and heuristic methods to solve the berth allocation problem in bulk ports[END_REF] maximizes the difference between the despatch money and the demurrage charges of each vessel v. Equation (2) ensures that each vessel v starts berthing at a unique berth b and in a unique time period t. Equation (3) ensures that each batch v i starts its loading in vessel v at a unique berth b, in a unique time period t, and is transported in a unique route r. Equation ( 4) ensures that berth b in both decision variables vtb x and v i vtbr y is the same. Equation ( 5) ensures that the loading of each batch v i can only begin once vessel v has been berthed. Equation [START_REF] Pratap | An integrated decision support system for berth and ship unloader allocation in bulk material handling port[END_REF] ensures that each vessel v can only leave the port when all batches have been loaded. Equation [START_REF] Menezes | A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports[END_REF] ensures that two (or more) batches cannot be loaded at the same time in each vessel v. Equation ( 8) avoids simultaneous use of routes that share at least one conveyor belt of the conveyor system. Equation ( 9) avoids the overlapping of vessels in each berth b. Equation (10) ensures that only one berth can be used from each pair of berths that share a berth since the berth layout of each quay is hybrid. Equations ( 11)-( 14) determine the delay and the advance of each vessel.

Numerical Experiments

The experiments were conducted using a computer with a core Intel® Xeon® CPU E3-1240 v5 @ 3.50 GHz -64 Go RAM, running a 64-bit version of the commercial solver Xpress-IVE 1.24.24. The method used for solving the problem is the primal simplex algorithm. The detailed characteristics of test instances and results can be found at Mendeley in Bouzekri et al. [START_REF] Bouzekri | A Dynamic Hybrid Berth Allocation Problem with Routing Constraints in Bulk Ports: Data sets and results[END_REF].

Input Data

Test instances were generated based on a sample of data obtained from OCP group. This latter operates six quays in the port of Jorf Lasfar to import raw materials (sulfur and ammonia) and export raw materials and products (phosphate rock, phosphoric acid and fertilizers). We focus on the first two quays that are dedicated to the export of fertilizers and partitioned into five berths each (1, 2, 3, 4, and 5 3 4   ). Each berth has a minimum water depth and a fixed quay crane with a specific productivity. The produced fertilizers (around 50 different types) are stored in 9 hangars. All the hangars are linked to all the berths by a conveyor system composed of 90 routes. The data sample received provides information about all the vessels that were berthed during the year 2019. We consider 3 sets of 5 instances each for

 

V 20, 30, 40 ,  generated from the data sample, for a planning horizon of 20 days (480 hours).

Computational Results

The output of the model refers to the scheduling of vessels and batches. These decisions can be illustrated in a same Gantt chart (see Bouzekri et al. [START_REF] Bouzekri | A Dynamic Hybrid Berth Allocation Problem with Routing Constraints in Bulk Ports: Data sets and results[END_REF]). For each set of 5 instances of a given size, the table shows the number of instances solved, the number of instances solved to optimality, the average computation time in seconds, and the average and maximum gap in percentages. For each instance, the computation time was limited to 1 hour and the gap was provided by the solver as   100 / ub lb ub   , where ub is the best upper bound obtained within the time limit, and lb is the value of the objective function corresponding to the best integer solution achieved. Overall, from the results, we can observe that the computation time increases with the number of vessels and the solver can solve to optimality most of the cases. In this paper, we study the Berth Allocation Problem with routing constraints in bulk ports. Our study is motivated by the port of Jorf Lasfar, but it is also valid for any bulk port. A new integer linear programming model is proposed to solve this problem.

The formulation proposed herein is flexible thanks to the use of predicates and it can be used to solve real cases in bulk ports. Computational experiments show that our model is able to solve the problem instances of realistic size (up to 40 vessels, 10 berths, 9 storage hangars, and 90 routes) in a reasonable computation time.

Further improvements are intended to be made such as considering tide constraints and extending our model to integrate storage locations decisions under the restrictions that forbid two or more cargo types to be stored in adjacent yard locations to avoid intermixing. Also, a heuristic could be developed to obtain faster results.

Fig. 1a .

 1a Fig. 1a. Port conveyor system. Fig. 1b. Hybrid berth layout.

  v i Index of batches to be loaded in vessel v   1,..., I v v  I . r Index of routes   1,..., R  R . Each route links a storage hangar to a berth. g Index of groups of routes that share at least one conveyor belt of the conveyor system to transport batches   1,..., G  G . Hence, the routes in a given group cannot be used all at once. Parameter Description L b Length of berth b. W b Minimum water depth of berth b. E p bBoolean parameter that equals 1 if berth b belongs to the pair p of berths that share a berth, 0 otherwise. A vExpected time of arrival of vessel v.

  Contractual demurrage by hour of vessel v.

  Loading time of batch v i in vessel v when this latter is berthed at berth b.

vbt x 1 i

 1 if vessel v starts berthing at berth b in time period t, 0 otherwise. starts to be loaded in vessel v at berth b in time period t using route r, 0 otherwise. of vessel v.

2 . 3 . 4 .

 234 The length of vessel v must not exceed the length of berth b: The draft of vessel v must not exceed the water depth of berth b: Vessel v can berth only after its expected time of arrival without exceeding its maximum waiting time in the harbor: A

  batch v i to be loaded in vessel v, the loading start and finishing time

Table 1 .

 1 Indexes, sets, input parameters and variable decisions.

	4	Model Formulation
	4.1	Notation
	Index	Description
	v	Index of vessels	V		 1,..., V 	.
	b	Index of berths	B		 1,..., B 	.
	t	Index of time periods	T		 1,..., T 	.
	p	Index of pairs of berths that share a berth and cannot be used simultaneously
		P		 1,..., P 		(e.g. in Fig.

Table 2 .

 2 Computational results.

	V	Solved	Optimum	Avg. time	Avg. gap	Max. gap
	20	5	5	5.9	0	0
	30	5	5	203.6	0	0
	40	5	3	1734.2	2.4	7.4