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

Integrated Laycan and Berth Allocation and time-invariant Quay Crane Assignment Problem in tidal ports with multiple quays

Keywords: Scheduling, Laycan allocation, Berth and quay crane assignment, Predicates, Integer programming

Efficient management of port resources plays a crucial role in reducing vessel stay times and avoiding the payment of demurrage charges. In this paper, we focus on the integrated Laycan and Berth Allocation and Quay Crane Assignment Problem (LBACAP), which considers three problems in an integrated way: the Laycan Allocation Problem, the dynamic continuous Berth Allocation Problem and the time-invariant Quay Crane Assignment Problem. Since these problems have different decision levels, a change of decision time scale is made inside the planning horizon. To ensure that this integrated problem is as close as possible to reality, we consider non-working periods and tidal ports with multiple quays that have different water depths. The integer programming model proposed for the LBACAP aims to find an efficient schedule for berthing chartered vessels with an efficient quay crane assignment, and to propose laycans (laydays and canceling) to new vessels to charter. In a second part, we focus on the integrated Laycan and Berth Allocation and Specific Quay Crane Assignment Problem (LBACASP), which extends the LBACAP model to include the assignment of a set of specific quay cranes to each vessel, considering the productivity of quay cranes (homogeneous or heterogeneous) and their maximum outreach.

Moreover, we use predicates in the formulation of both models, which ensure maximum flexibility in their implementation, thereby improving significantly their computational performance. Finally, the computational study on several classes of generated test instances shows that problems with up to 100 vessels can be solved to optimality.

Introduction

Maritime transport is the backbone of international trade and the global economy. Around 80% of global trade by volume and over 70% of global trade by value are carried by sea and are handled by ports (UNCTAD, 2018).

Ports are a very important component of maritime transport and play an important role in integrated supply chains requiring maritime transport, and constitute an important economic activity in coastal areas. Therefore, the efficient management of port operations and resources has become a crucial issue. Indeed, port performance management has been a focus point both in the industry and academia for the last two decades. It is related both to the respect of contractual clauses (e.g. laycan, laytime, demurrage, despatch money, etc.) between the various actors in the maritime chain of transportation (e.g. shipowners, charterers, port operators, etc.) and to the optimal use of port resources (e.g. quays, cranes, transfer vehicles, storage yard, manpower, etc.). Figure 1 illustrates three main decision problems in port management : vessel berthing time windows must be contracted (Laycan Allocation Problem), precise berthing times and positions are to be decided (Berth Allocation Problem) and scarce port resources, in particular quay cranes, must be assigned to handle vessels (Quay Crane Assignment Problem or Specific Quay Crane Assignment Problem). In practice, there is a strong interrelationship between these decisions, which motivates an integrated solution approach for these three problems. To the best of our knowledge, we are the first to integrate these problems. Crane Assignment Problem (LBACASP). These two combined problems illustrated in Figure 1 aim to find an efficient schedule for berthing chartered vessels and new vessels to charter with an efficient quay crane assignment, and to support decisions made by terminal managers in the negotiation process with shipping lines. Since the BACAP and BACASP are operational problems and the LAP is a tactical one, a change of decision time scale is made inside the planning horizon to consider the increasing uncertainty of inputs and to manage easily the integration of these problems.

The objective functions in the Berth Allocation Problem literature mostly aims at minimizing the sum of costs without distinguishing between the different actors involved in the maritime chain of transportation, which makes the applicability of the problem unrealistic, especially because, in most cases, these actors have conflicting objectives and interests. For example, the fuel cost is a cost supported by shipowners. Despite this, most authors consider the speedup cost of vessels as a cost supported by port operators. Some authors pointed the importance of taking into consideration the chosen actor in the definition of the objective function. For instance, [START_REF] Venturini | The multi-port berth allocation problem with speed optimization and emission considerations[END_REF] defined an objective function that implies that the pool of vessels is managed in a collaborative way, where the benefits and costs are shared between shipping lines and port operators. However, they said that the realistic applicability of this objective function needs further investigation. Therefore, in our paper, we consider two different objective functions: one based on a physical criterion to deal with the general case, and another one based on an economic criterion. This latter is based upon Charter Parties' clauses established with shipowners, to illustrate the case where ports belong to one single shipper. [START_REF] Mazioli | Assessment of the impact of Charter Party clauses and port's characteristics on the port's financial result[END_REF] assessed the important impact of the Charter Party clauses on the port's financial result.

The paper is organized as follows. In Section 2, a definition of the used maritime terms is provided to facilitate their understanding, then we present a literature review of the LAP, the BACAP and the BACASP with a focus on tidal ports and ports with multiple quays. The description and the formulation of the LBACAP are presented in Section 3. The model is extended to solve the LBACASP, and its description and formulation are presented in Section 4. In Section 5, we present an illustrative example for both models and the experiments conducted, then we discuss their results. Finally, in Section 6, we draw some conclusions and indicate future research directions.

Maritime vocabulary and literature review

Maritime vocabulary

The contract of carriage, to ship goods from one port to another, is called a "contract of affreightment". If a full shipload is to be transported and particularly where cargo is carried in bulk such as agricultural products (e.g. grain, rice, sugar, coffee, tea) and raw materials (e.g. metals, ores, oils), the whole vessel (or a principal part thereof) is chartered. In this case, the contract of carriage is called a Charter Party. This latter is contracted between shipowners (the shipowner is someone who equips and exploits a vessel for delivering cargo, and is not necessarily the owner of the vessel) and charterers (the charterer is someone who rents a vessel from the shipowner, and might own the cargo), and can be for either a specific voyage (Voyage Charter), or for a certain period (Time/Demise Charter). If a lesser quantity of goods or individually packaged goods are shipped along with other cargo, this is mostly done under a bill of lading, which testifies the contract of carriage. It is a document issued by the carrier to the shipper, providing details of the goods being shipped, and consequently, acting as a receipt for goods being shipped on board the vessel. So the shipowner can act as a carrier or/and a lessor (the carrier undertakes to carry goods from one point to another, and the lessor hires out the use of his vessel to a charterer). Finally, the port operator is the cargo handler in the port. He manages the port resources (quays, cranes, transfer vehicles, manpower, etc.). In some cases, one entity can represent two actors (e.g. Morocco's OCP Group, as a world leader in the phosphate industry, is at the same time, charterer and port operator). Figure 2 illustrates the different actors involved in contracts of affreightment. going to be loaded in ports. It establishes the period during which the shipowner must issue the Notice of Readiness (NOR) to the charterer that the vessel has arrived at the port of loading and is ready in all respects to load. This period is expressed as two dates: the earliest date, when the vessel is required by the charterer, and the latest date for the commencement of the charter. If NOR is not issued during the laycan the charterer has the option of canceling the charter. Once the vessel arrives at the port of loading, the charterer should be ready to start loading its cargo in order not to exceed its laytime. This latter is the amount of time allowed by the shipowner to the charterer in a Voyage Charter for the loading or the unloading of cargo. In the Voyage charter, laytime equals the cargo volume divided by the contractual rate of loading or unloading. The moment when laytime commences is determined by NOR. If the charterer exceeds the laytime, a predetermined penalty called "demurrage" is incurred. This penalty equals the time exceeded multiplied by the demurrage rate. Otherwise, if the whole period of laytime is not needed, a refund called "despatch" may be payable by the shipowner to the charterer. This refund equals the unused time multiplied by the despatch rate. Despatch is usually set at 50% of the demurrage rate "Despatch half Demurrage", but this depends on the terms of the Charter Party. The vessel may thus be able to leave port early. These chartering terms are shown in Figure 3.  SHEX (Sundays/Holidays Excluded): (from 12 am on Saturday until 8 am on Monday, and on Holidays from 5 pm of the day preceding a holiday until 8 am of the next working day).

 SSHINC (Saturdays/Sundays/Holidays Included): No exception periods are in effect and the laytime will count seven days a week as well as during holidays. Very large capacity vessels usually operate without exception periods being in effect.

In Arab countries and Muslim countries in general, weekend holidays differ from those applicable to the Western World. Indeed, Thursdays take the place of Saturdays and Fridays take the place of Sundays : TFHEX (Thursdays/Fridays/Holidays Excluded), FHEX (Fridays/Holidays Excluded), and TFHINC (Thursdays/Fridays/Holidays Included). In Israel and some Arab countries, Fridays take the place of Sundays:

FSHEX (Fridays/Saturdays/Holidays Excluded). Agreements with exceptions favor charterers, as Weekends and Holidays are to be excepted from the counting of laytime, which give charterers more time to complete cargo operations and finish within the laytime allowed without incurring demurrage. In some cases, charterers even quote EIU (Even If Used) which means laytime will not be counted even if cargo operations are carried out on exception days. Similarly, UU (Unless Used) means that if laytime has commenced but loading or discharging is carried out during periods excepted from it, such time shall count. On the contrary, agreements without exceptions favor shipowners because the laytime becomes continuous, including Weekends and other Holidays.

In order to satisfy the above mentioned contractual clauses while using the port resources efficiently, planning and scheduling tools are necessary. In this paper, we focus on three major problems in port planning and scheduling:

the Laycan Allocation Problem (LAP), the Berth Allocation Problem (BAP) and the Quay Crane Assignment Problem (QCAP).

The Laycan Allocation Problem refers to the tactical problem of assigning berthing time windows to new vessels to charter within a medium-term planning (three to four weeks), by taking into consideration commercial, logistical and production constraints such as availability of cargo and port resources, sales forecast, and due dates. Indeed, attending vessels within the agreed time limits at a port depends essentially on the efficient use of the available port resources such as quay space. Hence, LAP has a clear interaction with one of the most important operational problems in the seaside area of ports: the Berth Allocation Problem. This latter refers to the operational problem of assigning berthing positions and times to every vessel projected to be served within a short-term planning horizon (one to two weeks), due to the uncertainties of maritime traveling times, such that a given objective function is optimized. The assignment must respect the constraints of the problem such as vessel lengths and drafts, expected arrival times and projected handling times, etc. Indeed, the draft is a fundamental characteristic of a vessel and forms a major constraint in the Berth Allocation Problem. There are three different kinds of vessels: Feeder, Medium and Jumbo. The largest ones are Jumbo, and have deep drafts. In tidal ports (e.g. Port of Jorf Lasfar, Port of Shanghai, Port of Hamburg, etc.), large vessels can only navigate the route when tide is sufficiently high, which make them tide-dependent, especially when they are loaded, upon entering or leaving the port. Indeed, during low tide periods, large vessels have to wait until the depth of the sea reaches the required depth. Therefore, the vessel's draft must be considered to distinguish a vessel is either tide-dependent or not. For tide-dependent vessels, decision makers of berth planning define feasible tidal time windows for berthing and departure.

In addition to berths, quay cranes are also a scarce resource in ports. The Quay Crane Assignment Problem refers to the operational problem of assigning quay crane to every vessel projected to be served within a short-term planning horizon (one to two weeks). The assignment must respect the constraints of the problem such as the number of quay cranes available at the quay and the non-crossing constraints of quay cranes if they are mounted on rails.

There is an increasing trend to consider the BAP and the QCAP together, because the number of quay cranes assigned to a vessel determines its handling time. The integrated Berth Allocation and Quay Crane Assignment Problem (BACAP) considers the BAP and the QCAP together. We distinguish two versions of the BACAP, the time-invariant and the time-variant. In the BACAP with time-invariant quay crane assignment, a fixed number of quay cranes is assigned to each vessel included in the berth plan throughout its handling, while in the time-variant version, this number can be changed in each period. This second version of the problem allows a more efficient use of quay cranes but the resulting planning can be difficult to apply in practice as it involves a greater number of quay crane movements and task assignments to quay crane drivers. Therefore we consider the time-invariant version.

In the BACAP, all quay cranes have the same characteristics, hence the solution is expressed as a number of quay cranes assigned to a vessel without identifying which individual crane serves which vessel. Since quay cranes are mounted on rails and cannot cross each other, some BACAP solutions may require stopping the handling of some vessels in order to redistribute quay cranes to berthed vessels. Therefore, BACAP is extended to include the assignment of a set of specific quay cranes to each vessel, in order to avoid wasted times. This extended problem is called the integrated Berth Allocation and Specific Quay Crane Assignment Problem (BACASP). In both problems, a fixed number of quay cranes is assigned to each vessel. When quay cranes are identical, the BACAP is more flexible since it allows a reallocation of quay cranes with every new vessel arrival, while BACASP solutions are definitive. [START_REF] Correcher | New exact methods for the time-invariant berth allocation and quay crane assignment problem[END_REF] gave an example of a feasible solution for the BACAP which is not feasible for the BACASP (i.e. requires interruptions or quay crane changes). However, in the case of heterogeneous quay cranes, the BACASP is inevitable. Both problems are considered in this paper.

Literature review

In this section, we review the academic literature on the LAP, the BACAP and the BACASP, with a focus on tidal ports and ports with multiple quays.

LAP literature

Only one paper was found that deals with the LAP. [START_REF] Lorenzoni | A multi-mode resource-constrained scheduling problem in the context of port operations[END_REF] developed a mathematical model based on a multi-mode resource-constrained scheduling problem. The model determines vessel laycans (laydays)

with an efficient use of resources available for port operations for the attendance of vessels, under the condition that once vessels have arrived at the port, they have to be attended in first come first served order. Therefore, the defined laycans must avoid simultaneous or nearly simultaneous arrivals of vessels competing with the same resources.

However, they only proposed a temporal allocation of port resources such as berths and access canals, without considering spatial constraints such as vessel lengths. Finally, they solved the problem using a heuristic procedure based on the Differential Evolution Algorithm. It has to be noted that the LAP concerns the determination of berthing time windows to new vessels to charter, differing from ship routing and scheduling problems. Following the definitions given in [START_REF] Ronen | Ship scheduling: The last decade[END_REF], routing can be defined as the assignment of sequence of ports to a vessel. The term scheduling is used when the temporal aspect is brought into routing.

BACAP and BACASP literature

The berth allocation and quay crane assignment are essential for efficient terminal utilization in container and bulk ports. The surveys of (Bierwirth andMeisel, 2010, 2015) and [START_REF] Carlo | Seaside operations in container terminals: Literature overview, trends, and research directions[END_REF] focus on these two problems and their integration. A list of the most relevant literature for the BACAP and the BACASP is summarized in Table 1, in which the following information is presented.

 Port type: either container ports or/and bulk ports.

 BAP characteristics:

 Spatial attribute: it concerns the berth layout (either discrete, continuous or hybrid), and the consideration of vessel drafts and the quay (in the case of ports with multiple quays) when deciding on vessel berthing positions.

 Temporal attribute: it describes the arrival process of vessels (static, dynamic, stochastic), the possibility of speeding up vessels if soft arrival times are given, and the consideration of due dates and maximum waiting time in harbor for vessels.

 Handling time attribute: It highlights if the interference among quay cranes and the berthing deviation from the desired position are considered (or not) in the calculation of vessel handling times.  BACA(S)P performance measure attribute: it considers the objective function of the problem. Most models consider vessel stay time in ports by minimizing: vessel departure times, waiting times before berthing, tardy vessel departures, etc. Other models aim at reducing costs such as waiting costs, delay costs, berthing deviation costs, demurrage (vs despatch money), speedup costs, etc.

 BACA(S)P solution approach: either novel mathematical models, exact methods, heuristics, metaheuristics, or/and simulation.

 BACA(S)P modeling choices: the conditions of the BACA(S)P (e.g. berthing time and space, tide, draft, etc.) can be modeled either as constraints or predicates using binary variables.

For the BACAP with time-invariant quay crane assignment, [START_REF] Türkoğulları | Optimal berth allocation and time-invariant quay crane assignment in container terminals[END_REF] formulated an integer programming model with a discretization of the planning horizon and the quay length. Their formulation increases the efficiency of the solution procedure, even though it contains a large number of binary variables. However [START_REF] Correcher | New exact methods for the time-invariant berth allocation and quay crane assignment problem[END_REF] proposed a mixed integer programming model for the BACAP without a discretization of the quay length. Indeed, they use a decision variable with only three indexes: vessel's number, its start handling time and the number of quay cranes assigned to it. Consequently, they say that the number of variables involved is reduced and their mathematical formulation of the problem prevents underuse of the quay space. Moreover, they enhanced their model with several families of valid inequalities. Both papers considered an objective function that minimizes the total cost, whose components are the cost of deviation from the desired berthing section, the cost of berthing later than the arrival time, and the cost of departing later than the due time. This form of objective function is commonly used in the literature.

For the BACAP with time-variant quay crane assignment, [START_REF] Meisel | Heuristics for the integration of crane productivity in the berth allocation problem[END_REF] formulated an integer programming model. They considered quay crane interferences and the workload of horizontal transport means as well as the speedup of vessels and the cost of operating quay cranes. Then, they provided a heuristic solution method that allows treating instances of practical size, and some local refinements like quay crane resource leveling and spatial and temporal shifts. Moreover, they proposed two metaheuristics approaches: Squeaky Wheel Optimization and Tabu Search. [START_REF] Elwany | A heuristics-based solution to the continuous berth allocation and crane assignment problem[END_REF] proposed an extension to the BACAP model proposed by [START_REF] Meisel | Heuristics for the integration of crane productivity in the berth allocation problem[END_REF] considering the case in which the water depth is not the same in all berthing positions. Finally, [START_REF] Iris | Integrated Berth Allocation and Quay Crane Assignment Problem: Set partitioning models and computational results[END_REF] proposed generalized set partitioning models for the BACAP considering both the time-variant and timeinvariant quay crane assignment, together with a number of variable reduction techniques.

For the BACASP with time-invariant specific quay crane assignment, [START_REF] Türkoğulları | Optimal berth allocation and time-invariant quay crane assignment in container terminals[END_REF] developed an integer programming model. Since quay cranes must be assigned to vessels in the correct sequence, the authors formulated a set of constraints that ensure preserving the quay crane ordering. Moreover, they developed a polynomial-time algorithm and a cutting plane algorithm to obtain an optimal solution of BACASP from BACAP.

These algorithms can solve to optimality problem instances up to 60 vessels compared to the BACASP model that solve problem instances up to 15 vessels. Similarly, [START_REF] Correcher | New exact methods for the time-invariant berth allocation and quay crane assignment problem[END_REF] extended their BACAP model to include the assignment of specific quay cranes to each vessel which ensures that the handling of each vessel can be carried out without any disruption. They also presented an iterative procedure and a branch-and-cut algorithm using the BACAP model and a new type of constraint in order to solve larger instances of the BACASP.

For the BACASP with time-variant specific quay crane assignment, [START_REF] Chang | Integrating berth allocation and quay crane assignments[END_REF] presented a model using objective programming based on rolling-horizon approach due to the uncertainty of ship. Indeed, they divided the planning horizon into six periods of twelve hours, and upon completion of each period, a new 3-day plan is thereafter formed. Then, they employed a hybrid parallel genetic algorithm, which integrates parallel genetic algorithm and heuristic algorithm due to the large scale with regard to the BACASP. Furthermore, they integrated the employed algorithm with simulation to evaluate the proposed BACASP strategies. Another study in the same vein is [START_REF] Türkoğulları | Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals[END_REF], in which a mixed integer programming model and an efficient cutting plane algorithm based on a decomposition scheme are proposed. Finally, [START_REF] Agra | MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem[END_REF] presented a MIP model, based on the Relative Position Formulation introduced by [START_REF] Guan | The berth allocation problem: Models and solution methods[END_REF], for the BAP part. They considered heterogeneous quay cranes considering the maximum outreach of each quay crane.

BAP and BACAP in tidal ports and ports with multiple quays

Recently, some researchers focusing on the problems of berth allocation and quay crane assignment started introducing tide as a constraint in tidal ports. Indeed, [START_REF] Barros | Model and heuristic for berth allocation in tidal bulk ports with stock level constraints[END_REF] presented an integer programming model for the BAP in tidal bulk ports with stock level conditions. They modeled the BAP as a transportation problem in which vessels are seen as suppliers and favorable tidal condition windows are seen as consumers. Then, they proposed a Simulated Annealing-based heuristic to find good solutions for hard instances. [START_REF] Du | Modeling the Impacts of Tides and the Virtual Arrival Policy in Berth Allocation[END_REF] proposed two mathematical models for the BAP in tidal container ports. The first model considers the impacts of tides on the incoming and outgoing navigations of vessels through the channel, and the second model considers the arrival times of vessels as decision variables to mitigate the impacts of tides on the seaside operations of container ports. This latter model was motivated by the virtual arrival policy, which encourages compromises between port operators and shipping lines to reduce sailing speeds in order to revise vessel arrival times when there are known delays caused by berth unavailability at the next port, which has significant advantages in terms of fuel savings and emissions reduction.

Finally, [START_REF] Zhen | Daily berth planning in a tidal port with channel flow control[END_REF] proposed an integer programming model for the discrete time-variant QCAP, which they called the daily berth planning problem, considering tides and channel flow control constraints. Since the model contains a large number of binary variables and big-M constraints, the authors proposed a set partitioning based formulation. Then, they suggested a column generation based solution approach to solve the proposed model.

Regarding the BAP and the BACAP in ports with multiple quays, [START_REF] Frojan | The continuous Berth Allocation Problem in a container terminal with multiple quays[END_REF] studied the continuous BAP in a container terminal with multiple quays. First, they developed an integer programming model and then a genetic algorithm, based on sequences of vessels. [START_REF] Dadashi | A novel continuous berth scheduling model at multiple marine container terminals with tidal considerations[END_REF] proposed a new mixed integer mathematical model for the Berth Allocation Problem, which they called the Berth Scheduling Problem, at a port with multiple container terminals, considering the access channel depth variations by time of day, which serves as a gate for vessels entering or leaving the port. Each terminal has a continuous berth layout and a different depth. Then, they assumed that there are no vessels at the berths in the beginning of the planning horizon. They also evaluated how dredging may affect marine container terminal operations in terms of allowing vessels better navigation and reducing delayed vessel departures. Finally, [START_REF] Krimi | A rolling horizon approach for the integrated multi-quays berth allocation and crane assignment problem for bulk ports[END_REF] proposed a mixed integer programming model and a rolling horizon-based heuristic to solve the continuous time-invariant BACAP in bulk ports with multiple quays under availability and high tides restrictions. Indeed, the authors defined unavailability periods of the port due to preventive maintenance of quay cranes or bad weather conditions, and high tide intervals, which stipulate that vessels should leave the port only within these intervals. Their objective function minimizes the total cost of the delayed vessels.

In this paper, we consider many conditions in the definition of the LBACA(S)P, which reduces the gap between the abstract representation of the studied problems and their applicability in real situations. Moreover, all the conditions are modeled as predicates, which ensure maximum flexibility in the implementation of both models, and improves significantly their computational performance. Indeed, it is no longer necessary to introduce the conditions as constraints in the models, and the space search of solutions become smaller.

Description and formulation of the LBACAP

In this section, we introduce a description of the LBACAP, then we introduce its formulation.

Description of the LBACAP

Spatial attribute

We consider a tidal port with multiple quays. Each quay has a continuous berth layout partitioned into a set of short length sections with water depth restrictions (i.e. all the sections of a quay can have the same water depth, or the water depth increases seaward by sections, as in Figure 4). We also take into consideration the technical constraints of vessels that prohibit their berthing at some quays or oblige them to berth at a specific quay.

Temporal attribute

We assume dynamic vessel arrivals (i.e. approximate arrival times of vessels are known for a certain planning horizon). Furthermore, a maximum waiting time in harbor and a laytime are preset for each vessel. The role of the maximum waiting time in harbor is to reduce the solution space of berthing times in the planning horizon which improves significantly the computational performance of the model. Moreover, it avoids unrealistic solutions with significant vessel delays. However, new vessels to charter will have high maximum waiting times in harbor, so as not to affect the economic results of already chartered vessels. Indeed, these latter vessels have priority over new vessels to charter, because their Charter Parties are already finalized.

We also take into consideration tide constraints because large loaded vessels are not able to pass through the access channel and thus have to wait for high tide cycles where the sea level is superior to their drafts. Small and medium vessels are tide-independent. Tides are the rise and fall of sea levels caused by the combined effects of the gravitational forces exerted by the Moon and the Sun, and the rotation of the Earth. The Moon orbits the Earth in the same direction as the Earth rotates on its axis, so it takes slightly more than a day, about 24 hours and 50 minutes, for the Moon to return to the same location in the sky. So we define the start and end time of each high tide cycle (high tide windows) that would occur during the planning horizon, which imposes some feasible berthing and departure periods for large loaded vessels (The detailed calculation of tide parameters is shown in the file Tide.xlsx).

Consequently, each loaded large vessel that would be unloaded in the port can enter to the port only during high tide cycles, and similarly, each large empty vessel that was loaded in the port can leave the port only during high tide cycles. Therefore, it is a challenging task to define an efficient schedule for vessels when considering tide constraints. Since the planning horizon is divided into time periods of equal length, these temporal parameters are also expressed as a number of these time periods.

Handling time attribute

Handling times of vessels depend on the fixed number of homogeneous quay cranes assigned to them throughout the service process and take into account the decreasing marginal productivity due to quay crane interferences. In our model, handling times of vessels are determined by data preprocessing. Each vessel has a minimum and a maximum prescribed number of quay cranes that can serve it, and its finishing time can be greater than, less than or equal to its contractual finishing time.

Performance measure attribute

In the general case (i.e. in the presence of several actors with different roles, see Figure 2), an objective function based on a physical criterion is adopted, since the relevant actors have conflicting objectives and interests. This objective function could be the minimization of the sum of expected vessel departure times (shipowner interest) or vessel stay times (port operator interest). Solutions obtained under these physical criterions allow us to better detect the current margins of maneuver for fixing laycans to new vessels to charter. In this paper we arbitrarily choose to minimize the sum of expected vessel departure times. The consideration of the other criterion does not require any change in the models, except in the objective function's formula.

However, when ports belong to one single shipper (the charterer and the port operator are the same entity), an economic objective function, based upon Charter Parties' clauses established with shipowners, is adopted. In this case, we distinguish two kinds of costs, namely: the cost for exceeding the laytime (i.e. the demurrage charges), and the bonus payment offered by the shipowner for completing loading or unloading before the laytime (i.e. the despatch money). The economic objective function is to maximize the difference between despatch money and demurrage charges for each vessel (i.e. minimize demurrage charges and maximize despatch money). In both cases, we favor the berthing of vessels as close as possible to the port yard in order to select one of the optimal solutions.

Formulation of the LBACAP

Notation

Before presenting the model, notations on indexes, sets, parameters and decision variables used in the LBACAP model are listed as follows.

Indexes v

Index of vessels.

t Index of time periods.

q Index of quays.

q s Index of berthing sections at quay q (the closest section to the port yard being the first section).

n Index of quay cranes numbers.

Sets and parameters

1 V Set of already berthed vessels:

  1 1 1,..., V  V . 2 V Set of chartered vessels:   2 1 1 2 V 1,..., V V    V . 3 V Set of new vessels to charter:   3 1 2 V +V 1,..., V   V with 1 2 3 V V V V    . V Set of all vessels:   1,..., V  V . T Set of time periods:   1,...,T  T . Q Set of quays:   1,...,Q  Q . q S
Set of berthing sections at quay q:

  1,...,S q q  S . These sections are the same length.

N q Number of quay cranes at quay q.

N Set of quay cranes numbers:

  1,..., N  N with   N Max N q q  . W q s q
Water depth of berthing section q s at quay q.

A v

Expected time of arrival of each chartered vessel (v in 2 V ). For already berthed vessels (v in 1 V ), A 1 v  . For each new vessel to charter (v in 3 V ), A v is considered as the availability date of its cargo to be exported.

H v Maximum waiting time in harbor of each chartered vessel (v in 2 V ). For already berthed vessels (v in 1 V ), H 0. v  As stated previously, new vessels to charter (v in 3 V ) have high maximum waiting times in harbor, so as not to affect the economic results of chartered vessels (v in 2 V ).

D v Draft of vessel (v in V ). P v Laydays of each new vessel to charter (v in 3 V ).
λ v Length of vessel (v in V ) expressed as a number of berthing sections.

I vq Boolean parameter that equals 1 if vessel (v in V ) can berth at quay q, 0 otherwise. η v Boolean parameter that equals 1 if vessel (v in V ) is tide-dependent at its berthing, 0 otherwise.

ω v Boolean parameter that equals 1 if vessel (v in V ) is tide-dependent at its departure, 0 otherwise   η ω 1 . v v   γ v
Boolean parameter that equals 1 if the handling of vessel (v in V ) is restricted to working periods (excluding, for example, weekends), 0 otherwise.

f v Equals 1 γ 2 η v v    . It
V ), β 1, v 
and for already berthed vessels (v in 1 V ), β 0 v  . Thereafter, we can assign hourly demurrage and despatch rates not equal to one to each new vessel to charter, in order to see their impact on the economic criteria of the objective function. Consequently, it's the decision-maker who will see how much he can accept the deterioration of the economic results.

Decision variables q s n vtq

x 1 if vessel (v in V ) starts berthing in time period t at section q s of quay q, and n quay cranes are assigned to it, 0 otherwise.

v u Integer, delay of vessel (v in V ). v w
Integer, advance of vessel (v in V ).

Representation of time

We define the parameter f 1 γ 2 η v v v     , which can be equal to:

 1: if vessel v is tide-independent at its berthing and its handling is not restricted to working periods

  η 0, γ 0 v v   .
 2: if vessel v is tide-independent at its berthing and its handling is restricted to working periods   η 0, γ 1 .

v v  
 3: if vessel v is tide-dependent at its berthing and its handling is not restricted to working periods

  η 1, γ 0 v v   .
 4: if vessel v is tide-dependent at its berthing and its handling is restricted to working periods  

η 1, γ 1 v v   .
In order to know the index of working periods considering non-working periods, we define the parameter

f 1 Γ t v
.

Boolean parameter f ψ v t equals 1 during non-working periods for vessels for which the handling is restricted to

working periods   γ 1 f 2, 4 v v    , 0 otherwise. Then we write f \ψ 0 f 1 f 1 Γ ψ t v v t v t t t t t        and 1 1 Γ Γ t t v t v v   
, where t is the first non-working period after t. Vessels that their handling is not restricted to working periods

  γ 0 f 1, 3 v v    always have f 1 Γ t v t  . The reverse parameter f 2 Γ t v
gives the calendar period of the working period t, in the case of f .

v Vessel handling times do not change, however, vessel finishing times change. The same approach can be applied to the planned non-availability periods due to the preventive maintenance of port equipment. We also

t / f v 1 2 3 4 1 , 3 2 , 4 1 , 3 2 , 4 1 , 3 2 , 4 1 1 1 0 0 0 0 0 1 1 1 1 2 1 1 0 0 0 0 0 2 2 2 2 3 1 0 1 0 1 0 1 3 3 3 5 4 1 0 1 0 1 0 1 4 3 4 6 5 1 1 1 1 1 0 0 5 3 5 7 6 1 1 1 1 1 0 0 6 4 6 8 7 1 1 0 0 0 0 0 7 5 7 9 8 1 1 0 0 0 0 0 8 6 8 1 2 9 1 1 0 0 0 0 0 9 7 9 1 3 10 1 0 0 0 0 0 1 1 0 8 1 0 1 4 11 1 0 0 0 0 0 1 1 1 8 1 1 1 5 12 1 1 0 0 0 0 0 1 2 8 1 2 1 6 13 1 1 1 1 1 0 0 1 3 9 1 3 1 9 14 1 1 1 1 1 0 0 1 4 1 0 1 4 2 0 15 1 1 1 1 1 0 0 1 5 1 1 1 5 2 1 16 1 1 1 1 1 0 0 1 6 1 2 1 6 2 2 17 1 0 0 0 0 0 1 1 7 1 3 1 7 2 3 18 1 0 0 0 0 0 1 1 8 1 3 1 8 0 19 1 1 0 0 0 0 0 1 9 1 3 1 9 0 20 1 1 0 0 0 0 0 2 0 1 4 2 0 0 21 1 1 0 0 0 0 0 2 1 1 5 2 1 0 22 1 1 1 1 1 0 0 2 2 1 6 2 2 0 23 1 1 1 1 1 0 0 2 3 1 7 2 3 0 f ψ v t f 1 Γ t v f 2 Γ t v f G v t O t

Decision time scale

Naturally, we consider a longer planning horizon for the LBACAP, since planning new vessels to charter (i.e.

LAP) is a tactical problem. In order to reduce the computation complexity and to take into account the increasing uncertainty of inputs as the length of planning horizon increases, we define a boolean parameter K t , that equals 1 if vessels can berth during period t (without considering other constraints). This parameter enables us to restrict the periods when each decision can be made inside the planning horizon, and hence to change the time scale. For example, during the first week, chartered vessels (v in 2 V ) can berth every hour « 1 », hence K t  1,t during week 1; during the second week, every four hours « 0 -0 -0 -1», hence

  mod 4 K 1, | 0 t t t  
 and K t  0 otherwise; during the third week, every eight hours « 0 -0 -0 -0 -0 -0 -0 -1», hence

  mod 8 K 1, | 0 t t t  
 and K t  0 otherwise. New vessels to charter (v in 3 V ) can be planned during the second and third week, providing for them an estimated position in the schedule. It should be noted that we can re-run the model whenever needed (e.g. when

we have new and more precise information about vessels to charter or when some disturbances occur such as vessel delays, bad weather, etc.) or on a regular basis (e.g. once a week in a rolling horizon). Therefore, as we advance in the planning horizon, the schedule is refined: Some chartered vessels (v in 2 V ) will become berthed vessels (v in 1 V ), and some new vessels to charter (v in 3 V ) will become chartered vessels (v in 2 V ). In figure 5, we show a case of vessel scheduling update over a week. The upper sequence shows that a vessel is positioned on period 172 in week 2. At this point, the precise berthing period is not known, but is estimated on a 4-periods range, between periods 169 and 172. When the program is rerun a week later, the precise schedule is obtained. Modulating time scale through the planning period enables us to integrate LAP and BACA(S)P that are on different decision levels, without increasing the number of variables too much, and without placing a border between the operational and tactical problems. Moreover, this solution does not modify the time unit of vessel handling times and high tide cycles.

Mathematical model

The binary decision variable q s n vtq

x determines:

 For each berthed and chartered vessel (v in 1 2  V V ): its berthing time t, its berthing quay q, its berthing space from q s to λ 1 q v s   , and its assigned number of quay cranes n.

 For each new vessel to charter (v in 3

V ): its laycan period:  

, P 1 v t t   , its berthing quay q, its berthing space from q s to λ 1 q v s   , and its assigned number of quay cranes n.

The existence of the decision variable q s n vtq

x is subject to eight conditions:

1. Vessel (v in V ) can berth only at periods where the decision variable exist: K 1 t  .

Vessel (v in V ) can berth between its expected time of arrival and its expected time of arrival increased by its maximum waiting time in harbor:

A A H v v v t    .
3. Vessel (v in V ) must be able to berth at time period t: f G 1 v t  . In other words, vessels that their handling is restricted to working periods can berth only during working periods, and vessels that are tide-dependent at their berthing can berth only during high tide cycles.

4. Vessel (v in V ) must be able to berth at quay q: I 1 vq  .

5. The length of vessel (v in V ) must not exceed the limit of quay q: S q :

S λ 1 q q v s    .

6. The draft of vessel (v in V ) must not exceed the water depth of the section of its berthing position:

W D . q s v q 
If this condition is verified for the first section q s , it will be implicitly verified for the other sections occupied by the vessel because the water depth of sections does not decrease seaward.

7. The number of quay cranes n assigned to vessel (v in V ) must be between its minimum and maximum allowed number:

min max n n v v n   .
8. Vessel (v in V ) must be able to leave the port at its finishing time period

1 f 2 ( θ 1 ) , f n t v v v     : 1 f 2 ( θ 1 ) , f (1-ω )+ω O( ) 1 n t v v v v v       .
In other words, vessels that are tide-dependent for departure (ω 1) v  can leave the port only during high tide cycles (when

1 f 2 ( θ 1 ) , f O( ) 1 n t v v v     
). The other vessels (ω 0) v  always respect this condition.

The logical condition of the existence of the decision variable q s n vtq

x is the following one:

  0,1 , , q s n vtq x v    V f K A A H 1 G 1 , v t v v v t t t          T I 1, vq q    Q S λ 1 W , s D q q q v s q q v q s        S 1 f 2 min max ( θ 1 ) , f n n (1-ω )+ω O( ) 1. n t v v v v v v v n n            N
Conditioning the existence of the decision variable q s n vtq

x to the respect of the eight conditions described above improves significantly the computational performance of the LBACAP model since it is no longer necessary to introduce them as constraints in the model.

Constraint (1) ensures that each vessel (v in V ) starts berthing in a unique time period t at a unique section q s of quay q, with a fixed number of quay cranes n assigned to it :

2 f min max 1 ( θ 1 ) , f f K 1 A A H G 1 I 1 S λ 1 D W n n (1-ω )+ω O( ) 1 1, q s v v q t v v v t v q q q q q v v q v v n v v v t v s n vtq t t q s s n n x                             T Q S N v  V (1)
One can remember that each berthed vessel (v in 1 V ) has a residual handling time with a berthing time 1 t  and a predetermined berthing section at a quay and a number of quay cranes assigned to it.

When a vessel (v in V ) starts berthing in time period t at section q s of quay q, and n quay cranes are assigned to it (i.e. 1 q s n vtq

x  ), it occupies all sections located between q q s s   and λ 1 q q v s s     during the time periods between t t   and

1 f 2 ( θ 1 ) , f n t v v v t       (or θ 1 n v t t
    if we do not consider non-working periods, which is implicitly performed in the general definition of

1 f 2 ( θ 1 ) , f n t v v v    
). Consequently, vessels that berth before or after vessel v, during its handling time at the same quay q, must avoid overlaps. Figure 6 illustrates some forbidden overlaps once "Vessel A" has been berthed.

Figure 6: Example of overlaps between 3 vessels (if their handling is not restricted to working periods)

The spatiotemporal localization of vessel v, berthing at period t assuming

f K A A H 1 G 1 v t v v v t t        , at section q s assuming S λ W I 1 1 D q q q v s vq v q s       
, with n quay cranes assigned to it assuming

1 f 2 min max ( θ 1 ) , f n n (1-ω )+ω O( ) 1 n t v v v v v v v n        
 , can be represented by a rectangle, located between the sections q q s s   and λ 1 q q v s s     on the spacial dimension, and between the periods t t   and

1 f 2 ( θ 1 ) , f n t v v v t      
on the temporal dimension. Consequently, the spatiotemporal spot ( , ) q t s is occupied by a vessel v, if it berths i) at a period

t t   assuming f K A A H 1 G 1 v t v v v t t           (existence constraint) and 1 f 2 ( θ 1 ) , f n t v v v t       (departure not before t); ii) at a section q s , assuming S λ W I 1 1 D q q q v s vq v q s         
(existence constraint) and q q s s   (berthing not after q s ); iii) with n quay cranes assigned to it assuming

1 f 2 min max ( θ 1 ) , f n n (1-ω )+ω O( ) 1 n t v v v v v v v n           . Constraint
(2) is a disjunctive spatiotemporal constraint that avoids spatiotemporal overlapping between vessels.

2 f 1 ( θ 1 ) , f f 2 2 1 f 1 ( θ 1),f ( θ 1),f f f K 1 A H G 1 (1-ω )+ω O( ) 1 S λ 1 D W λ 1 1 D W A K 1 G 1 (1-ω )+ω O( ) 1 1, s q t v v t v v n v q q q q v v q v v t q v s q q q v q v q v t n t v v n v v v v v t t v v t t t s s s s n vt q s s s t t x                                                            max min n I 1 n v v vq n v n        V , , s q q t q       T Q S (2)
We define an intermediate variable, vtq  which gives the number of active quay cranes serving each vessel (v in V ) at each quay and each time period following the reasoning used to get relation (2

): f 1 ( θ 1 ) , f max f min 2 2 1 f 1 ( θ 1),f ( θ 1),f f f K 1 A H G 1 (1-ω )+ω O( ) 1 n n s S λ 1D W A K 1 G 1 (1-ω )+ω O( ) 1
. ,

v t v v t v v n v v v t q v s v q q q q q v v q v t n t v v n v v v v v t t v v t t t n s n vtq vt q n s t t n x                                                    S 1 , , I vq v t q        V T Q Constraint (
3) ensures that in each time period t, the number of active quay cranes serving all vessels that are present in a quay q is not greater than the available number of quay cranes N q at this quay .

I 1 N , , vq vtq q v t q          V T Q (3)
We define another intermediate variable, v  which gives the expected finishing time for each vessel (v in V ):

2 f min max 1 θ 1 f K 1 A A H G 1 I 1 S λ 1 D W n n (1-ω )+ω O( ) 1 s v v q t v v v t v q q q q q v v q v v n v v t v v t t q s s n n                              T Q S N 1 f 2 ( θ 1 ) , f , q n t v v v s n vtq x v        V
The difference between the expected finishing time for each vessel and its contracted finishing time (the worst case finishing time for new vessels to charter (v in 3 V )) can be written as: δ .

v v

 

The integer variable v u should verify the constraints ( 4), ( 5) and ( 8) in order to determine the delay of each vessel (v in V ), and the integer variable v w should verify the constraints ( 6), ( 7) and ( 8) in order to determine its advance.

δ ,

v v v u v     V (4) 0, v u v   V (5) δ , v v v w v     V (6) 0, v w v   V (7) δ , v v v v u w v       V (8)
We define another intermediate variable used in both objective functions, v  which gives the inverse of the berthing section for each vessel (v in V ). Its role is to favor the berthing of vessels as close as possible to the port yard, without impacting the main criterion value used in the objective function.

2 f min max 1 θ 1 f K 1 A A H G 1 I 1 S λ 1 D W n n (1-ω )+ω O( ) 1 s v v q t v v v t v q q q q q v v q v v n v v t v v t t q s s n n                              T Q S N / , q s n vtq q x s v  V
When ports belong to one single shipper (the charterer and the port operator are the same entity), the economic objective function ( 9) of the LBACAP integer programming model is to maximize the difference between despatch money and demurrage charges of each vessel. Furthermore, laycans are proposed for each new vessel to charter by making it arrive to the port as close as possible to the availability date of its cargo to be exported and leave the port as early as possible, without impacting the economic results of already chartered vessels. The final term of the objective function ( 9) favors the berthing of vessels as close as possible to the port yard and enables to select one of the optimal spatial solutions that have the same economic results.

 

(β α ) v v v v v v Max w u        V (9)
In the presence of several actors with conflicting monetary objectives, a physical objective function is coherent:

the LBACAP model minimizes the sum of expected vessel departure times, by berthing each vessel as close as possible to its arrival time, with as many quay cranes as possible, and then laycans are fixed to new vessels to charter.

The second term of the objective function ( 10) also favors the berthing of vessels as close as possible to the port yard without impacting the physical results of vessels, which also enables to select one of the optimal solutions. In this case, we only consider the binary variable q s n vtq

x and the constraints (1), ( 2) and (3). Consequently, the LBACAP model becomes a zero-one integer programming model.

  v v v Min      V (10)
4 Description and formulation of the LBACASP

Description of the LBACASP

The spatial, temporal and performance measure attributes are the same for the LBACAP and the LBACASP.

Regarding the handling time attribute, a group of heterogeneous quay cranes is assigned to each vessel in the LBACASP (Figure 7). For example, if a quay has 4 quay cranes and the maximum number of quay cranes that can be assigned to any vessel is 3, then the possible groups of quay cranes are: {1}, {2}, {3}, {4}, {1, 2}, {2, 3}, {3, 4}, {1, 2, 3}, and {2, 3, 4}. Dealing with heterogeneous quay cranes with different processing rates makes some berthing positions more attractive than others. Indeed, each quay crane has a maximum outreach in the quay (Figure 8).

Consequently, a berthing position that is served by a more efficient quay crane tends to be used more often than the other positions.

Formulation of the LBACASP

Notation

In addition to some indexes, sets, parameters and decision variables used in the LBACAP model, the following ones are used only in the LBACASP model.

Indexes q c

Index of quay cranes at quay q such that a quay crane positioned closer to the port yard has a lower index.

q g Index of groups of quay cranes at quay q.

Sets and parameters q C Set of quay cranes at quay q:

  1,..., N q q  C . q G
Set of groups of quay cranes at quay q:

  1,...,G q q  G . n q g q
Number of quay cranes in group q g . l q g q Index of the leftmost quay crane in group q g (e.g. l 2 q g q  in group {2, 3, 4}). r q g q Index of the rightmost quay crane in group q g (e.g. r 4

q g q  in group {2, 3, 4}). L q g q Index of the leftmost berthing section accessible by the leftmost quay crane in group q g . R q g q Index of the rightmost berthing section accessible by the rightmost quay crane in group q g . θ q g vq Handling time of each chartered and new vessel to charter (v in 2 3  V V ) if group q g of quay cranes is assigned to it (determined by data preprocessing). Already berthed vessels (v in 1 V ) have residual handling times.

B v Contractual handling time of chartered vessels (v in 2 V ) calculated using the contractual rate of handling (determined by data preprocessing). Already berthed vessels (v in 1 V ) have residual contractual handling times. For each new vessel to charter

(v in 3 V ), B θ q g v v q
 with q g a group composed of only one quay crane with the lowest rate of handling (i.e. the longest handling time; also determined by data preprocessing). Such a choice is motivated by the desire to compare the given result with the worst case possible.

Decision variables q q

s g vtq y 1 if vessel (v in V ) starts berthing in time period t at section q s of quay q, and group q g of quay cranes is assigned to it, 0 otherwise. This decision variable replaces the binary variable q s n vtq

x of the LBACAP model. q c tq z Integer, possible position of quay crane q c at quay q in time period t.

Mathematical model

The existence of the decision variable q q s g vtq y is also subject to eight conditions. Seven conditions are shared with the conditions of the existence of the decision variable q s n vtq

x except condition 5 that becomes more restrictive. Indeed, the new condition says that all berthing sections occupied by each vessel (v in V ) must be outreached by all the quay cranes in group q g assigned to this vessel. In other words, the indexes of the first and the last berthing sections occupied by each vessel (v in V ) must be within the outreach range of its assigned group q g of quay cranes: 9 illustrates this condition. The condition that states that the length of each vessel must not exceed the limit of its assigned quay is implicit in this condition.

, +λ 1 L ,R L R λ 1 q q q q g g g g q q v q q q q q v s s s                . Figure

Figure 9: Illustration of the spatial condition

The logical condition of the existence of the decision variable q q s g vtq y is the following one:

  0,1 , , q q s g vtq y v    V f K =1 A A H G 1, v t v v v t t t         T I 1, vq q    Q 1 f 2 min max ( θ 1 ) , f n n n (1-ω )+ω O( ) 1, q g q t v q v v g v v q q q v v g            G W s L R λ 1 D q q q g g s q q q q q v v q s         S
The first two constraints of the LBACASP model are similar to the first two constraints of LBACAP model with some differences in formulation:

As constraint (1), constraint (11) ensures that each vessel (v in V ) starts berthing in a unique time period t at a unique section q s of quay q, with a group q g of quay cranes assigned to it. 12) is a disjunctive spatiotemporal constraint that avoids spatiotemporal overlapping between vessels. In this model, the spatiotemporal spot ( , )

2 f m i n m a x 1 ( θ 1 ) , f f K =1 A A H G 1 I 1 n n n (1-ω )+ω O( ) 1 s L R λ 1 D W 1, q q g g g s v v q q q q t v v v t v q q q q v v g q q q q q v v q v q v vq t v s g vtq t t q g s y                              T Q G S v  V (11) As constraint (2), constraint (
q t s is occupied by a vessel v, if it berths i) at a period t t   assuming f K A A H 1 G 1 v t v v v t t           (existence constraint) and 1 f 2 ( θ 1 ) , f g q t v q v v t       (departure not before t); ii) at a section q s , assuming W I 1 L R λ 1 D q q q g g s vq q q q v v q s           (existence constraint) and q q
s s   (berthing not after q s ); iii) with group q g of quay cranes assigned to it assuming

1 f 2 min max ( θ 1 ) , f n n n (1-ω )+ω O( ) 1 q g q t v q v v g v v q v v           . f 1 ( θ f 2 2 f 1 1 ( θ 1 ) , f ( θ 1 ) , f f f K 1 A H G 1 (1-ω )+ω O( R λ 1 D W λ 1 L D W A K 1 G 1 (1-ω )+ω O( ) 1 1, g s q q t v v t v v v q q q q v v q vq t q q v g s q q q q v q q v q v t g t v v g q v q vq v vq v t t v v t t t s s s s g vt q s s s t t y                                                          2 1),f min max ) 1 I 1 n n n g q v g v v q vq q q q v g           V G , , s q q t q       T Q S (12)
Constraints ( 13) to ( 16) guarantee that quay cranes are assigned to vessels (v in V ) in the correct sequence. These four constraints were inspired from [START_REF] Türkoğulları | Optimal berth allocation and time-invariant quay crane assignment in container terminals[END_REF]:

 Constraint (13) states that the positions of quay cranes at the quay are respected by their indexes. So, during each time period of the planning horizon, the position of quay crane q c is always less than or equal to the position of quay crane 1 q c  at quay q.

1 , , , N 1

q q c c tq tq q q q q z z t q c c           T Q C (13)
 Constraint ( 14) ensures that the last quay crane of each quay is positioned within the quay.

N S , ,

q tq q z t q      T Q (14)
 Constraint (15) ensures that the position l g q q t q z  of the leftmost quay crane l q g q in group q g assigned to each vessel (v in V ) is greater than or equal to its berthing section q s , between its berthing time t t   and its end of handling

1 f 2 ( θ 1 ) , f g q t v q v v t       . l s L R λ 1 D W s L R λ 1 D W S (1 ) , ,
g q q q q q q g g s g g s q q q q q q q q q q q v v q q q q q q v v q s g s g t q q vtq q vtq s s z y sy v

                      S S V f A A H K =1 G 1, I 1, v t v v v t v q t t q            T Q 1 1 f f 2 2 min max θ 1 ( θ 1),f n n n (1-ω )+ω O( ) 1, q g g q q t v q t v q v v v g v v q q q v v g t t t                    G T (15)
Indeed, if vessel (v in V ) starts berthing in time period t at section q s of quay q, and group q g is assigned to it, then s L R λ 1 D W 1 q q g g s q q q q q q q q v v q s g vtq s y

        S
. Consequently, the position l g q q t q z  of the leftmost quay crane l q g q in group q g of quay cranes assigned to this vessel would be greater than or equal to its berthing section s L R λ 1 D W q q g g s q q q q q q q q v v q s g q v t q q s s y s

       
 S : l g q q t q q z s   . Otherwise, l S 0 g q q t q q z    .

 Constraint (16) ensures that the position r g q q t q z  of the rightmost quay crane r q g q of group q g assigned to each vessel (v in V ) is less than or equal to its last occupied berthing section λ 1 q v s   , between its berthing time t t   and its end of handling 1), , g q q q q q q g g s g g s q q q q q q q q q q q v v q q q q q q v v q s g s g t q q v vtq q vtq s s z s y y v

1 f 2 ( θ 1 ) , f g q t v q v v t       . r s L R λ 1 D W s L R λ 1 D W ( λ 1) S (
                      S S V f A A H K =1 G 1, I 1, v t v v v t v q t t q            T Q 1 1 f f 2 2 min max θ 1 ( θ 1),f n n n (1-ω )+ω O( ) 1, q g g q q t v q t v q v v v g v v q q q v v g t t t                    G T (16)
Indeed, if vessel (v in V ) starts berthing in time period t at section q s of quay q, and group q g is assigned to it, then s L R λ 1 D W 1 q q g g s q q q q q q q q v v q s g vtq s y

        S
. Consequently, the position r g q q t q z  of the rightmost quay crane r q g q of group q g of quay cranes assigned to this vessel would be less than or equal to its last occupied berthing section s L R λ 1 D W ( λ 1) λ 1 q q g g s q q q q q q q q v v q s g q v v t q q v s s y s

             S : r λ 1
g q q t q q v z s     . Otherwise, r S g q q t q q z   .

In the LBACASP, the definition of the already introduced intermediate variables, v  and v  , which give respectively the expected finishing time and the inverse of the berthing section for each vessel (v in V ) become:

2 f m i n m a x 1 ( θ 1 ) , f f K 1 A A H G 1 I 1 n n n (1-ω )+ω O( ) 1 s L R λ 1 D W g g g s v v q q q q t v v v t v q q q q v v g q q q q q v v q v q v vq t v v t t q g s                               T Q G S 1 f 2 ( θ 1 ) , f 1, q q g q t v q v v s g vtq y v         V 2 f m i n m a x 1 ( θ 1 ) , f f K 1 A A H G 1 I 1 n n n (1-ω )+ω O( ) 1 s L R λ 1 D W g g g s v v q q q q t v v v t v q q q q v v g q q q q q v v q v q v vq t v v t t q g s                               T Q G S / , q s n vtq q x s v  V
Constraints (4) to ( 8) of the LBACAP model that determine the delay or the advance of each vessel (v in V ) and objective functions ( 9) and ( 10) are also valid for the LBACASP model.

Computational experiments

In this section, we present an illustrative example for the LBACAP and the LBACASP models in order to show the integration of the LAP with the BACAP and BACASP, and the different characteristics considered in these problems (multiplicity of quays, tide constraints, variation of water depth, productivity and outreach of quay cranes, and non-working periods), then we report the computational results obtained on instances generated by our test instance generator. The formulations were written on Mosel and implemented in Xpress-IVE Version 1.24.24, with 64 bits. All the tests were run on a computer of these characteristics (Intel ® Xeon ® CPU E3-1240 v5 @ 3.50 GHz -64 Go RAM) and using the Xpress Optimizer Version 33.01.05 with the default options.

Illustrative example

We consider a time horizon of 4 weeks: T 672  The detailed characteristics of berthing sections and groups of quay cranes are shown, respectively, in Tables 3 and4. By comparing the two Gantt charts, we can see that vessel handling times are shorter in the LBACASP model since quay cranes are heterogeneous, therefore the most productive quay cranes tend to be used more. Moreover, vessels are berthed in such a way that quay cranes outreach is respected. We also note that new vessels to charter have better propositions for laycans in the case of the physical criterion.

Tests instances and implementation issues

In order to evaluate the quality of the LBACAP and the LBACASP models considering all the characteristics described above, several experiments were conducted. Therefore, we have built an instance generator, on a simulation software, which accepts all the relevant characteristics of the problems as configurable parameters and generates feasible solutions (folder Instance contained in Data_set_Harbour.zip). Studying the results obtained by the models on a set of newly generated instances allows us to get some insight into the most influential factors associated with the problems such as the number of quays and vessels.

We first consider 6 sets of instances: 3 sets for each model and 1 set for each number of quays considered:

  Q 1, 3, 5 . 
In all sets, we consider a time horizon of 4 weeks: T 672  hours discretized in units of 1 hour and each quay has a length S 1000 q  meters discretized in units of 10 meters and N 10 q  quay cranes available (which is equivalent to G 27 q  groups of quay cranes: 10 groups of 1 quay crane, 9 groups of 2 quay cranes, and 8 groups of 3 quay cranes). The variation of decision time scale is as in the illustrative example : during the first week vessels can berth every hour, then during the second week, every four hours, after that during the third week, every eight hours, and finally during the fourth week, every twelve hours. Each set consists of 15 randomly generated

Class of water depth

Range of sections of quay q =1 Range of sections of quay q =2 Description g q n g q q L g q q R g q q l q g q r q g q instances, 5 instances for each number of vessels considered: for medium vessels, and   U 28, 40 for huge vessels, the draft as follows: low drafts for small vessels, medium drafts for medium vessels and deep drafts for huge vessels, and the minimum and maximum number of quay cranes that can be assigned to it as follows: from 1 to 2 quay cranes for small and medium vessels, and from 2 to 3 quay cranes for huge vessels. After that, we calculate the handling time of each vessel when n quay cranes are assigned to it as follows: Finally, we have generated 6 other sets with the same instances considered before, changing the discretization of vessel and quay lengths to 50 meters.

W q s q q =1 q =2 q =1 q =2 q =1 q =2 q =1 q =2 q =1 q =2 q =1 q =2 1 { 1 } { 1 } 1 1 1 1 1 1 1 1 1 2 1 4 2 { 2 } { 2 } 1 1 2 2 2 2 2 2 1 3 1 5 3 { 3 } { 3 } 1 1 3 3 3 3 3 3 1 4 1 6 4 { 4 } { 4 } 1 1 4 4 4 4 4 4 1 5 1 7 5 { 5 } { 5 } 1 1 5 5 5 5 5 5 1 6 1 8 6 { 6 } { 6 } 1 1 6 6 6 6 6 6 1 7 1 9 7 { 1 , 2 } { 7 } 2 1 1 7 2 7 1 7 1 3 2 0 8 { 2 , 3 } { 1 , 2 } 2 2 2 1 3 2 2 1 1 4 1 5 9 { 3 , 4 } { 2 , 3 } 2 2 3 2 4 3 3 2 1 5 1 6 1 0 { 4 , 5 } { 3 , 4 } 2 2 4 3 5 4 4 3 1 6 1 7 1 1 { 5 , 6 } { 4 , 5 } 2 2 5 4 6 5 5 4 1 7 1 8 1 2 { 1 , 2 , 3 } { 5 , 6 } 3 2 1 5 3 6 1 5 1 4 1 9 1 3 { 2 , 3 , 4 } { 6 , 7 } 3 2 2 6 4 7 2 6 1 5 2 0 1 4 { 3 , 4 , 5 } { 1 , 2 , 3 } 3 3 3 1 5 3 3 1 1 6 1 6 1 5 { 4 , 5 , 6 } { 2 ,

Evaluation of the LBACAP and the LBACASP models

Evaluation of the LBACAP model

The results obtained for the LBACAP model are shown in Table 5. For each subset 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. Xpress calculates the gap as follows: 100 ( ) / ub lb ub   . In the case of a minimization problem (physical criterion), lb is the value of the best lower bound obtained within the time limit by considering all the decision variables as continuous, and ub is the value of the objective function corresponding to the best integer solution achieved. In the case where the objective function is maximized (economic criterion), ub is the best upper bound obtained within the time limit by considering all the decision variables as continuous, and lb is the value of the objective function corresponding to the best integer solution achieved. As can be seen, we can solve instances up to 100 vessels. This is a significant outcome in terms of the size and the characteristics of the instances since to the best of our knowledge, there are no reported solutions in the literature for this integrated problem of this size and all these characteristics. Some instances are not solved or are not optimally solved due to their extreme congestion (e.g. 1 quay and 100 vessels), or due to the time limit (1 hour). The number of vessels and quays has a strong influence on the results. Indeed, the computation time increases as the number of vessels and quays increases. It has to be noted that the values of the objective functions in the case of the 10m discretization and the case of the 50m discretization are very similar; thereby a 50m discretization of the space is sufficient for the resolution of the problem.

Evaluation of the LBACASP model

In this section, we discuss the results of the LBACASP model. Table 6 shows the results obtained for the LBACASP model with a 50m discretization. The LBACASP model is more difficult than the LBACAP model, especially that quay cranes are heterogeneous.

Moreover, when the number of quay cranes increases, the possible combinations of groups of quay cranes become a lot larger. Our LBACASP model is able to optimally solve most instances with up to 50 vessels.

Conclusions

The Laycan Allocation Problem has a clear interaction with one of the most important operational problems in the seaside area of ports: the Berth Allocation Problem. This latter also has a strong link with the assignment of quay when ports belong to a single shipper. We also considered many characteristics in the definition of the integrated problem to make it as close as possible to the reality such as: tidal ports with multiple quays and different water depths, and non-working periods. All the conditions related to these characteristics have been formulated as predicates, which has ensured maximum flexibility in the implementation of the model, thereby improving significantly its computational performance. As the computational study shows, the LBACAP model can be used to obtain the optimal solution in reasonable computation times for different classes of instances with up to 100 vessels.

Since the LBACAP assigns only homogeneous quay cranes to vessels, we have also introduced a new integer programming model for the integrated Laycan and Berth Allocation and Specific Quay Crane Assignment Problem (LBACASP). This latter assigns a set of specific quay cranes to each vessel, considering the maximum outreach of each quay crane, and thus produces more realistic solutions. In spite of its complexity, we are able to solve instances with up to 50 vessels.

Our models could be extended to the time-variant version of the Quay Crane Allocation Problem while limiting quay cranes changes between each period. Also, a heuristic could be developed to obtain results faster for the LBACASP model. It has to be noted that the optimal solutions proposed by both models may be infeasible because of the unavailability of cargo to be exported in vessels: in practice, there is a strong interaction between vessels' loading and production, unless an important decoupling of these problems is done by high stock levels, which is an expensive solution. So, as a perspective, we would develop a decision support system (DSS) to integrate the different port problems of allocation and scheduling, all in taking into account the constraints of the upstream supply chain.

This DSS would follow an approach that combines optimization and simulation.

Data: https://www.lamsade.dauphine.fr/Documents/Data_set_Harbour.zip

Figure 1 :

 1 Figure 1: Possible combinations between the LAP, the BAP, the QCAP and the QCASP In this paper, we propose two integrated solutions: for i) the integrated Laycan and Berth Allocation and Quay Crane Assignment Problem (LBACAP), and for ii) the integrated Laycan and Berth Allocation and Specific Quay

Figure 2 :

 2 Figure 2: Different actors involved in contracts of affreightment Laycan and laytime are the two main clauses in the Charter Party of the type Voyage Charter. Laycan is an abbreviation for the "Laydays and Canceling" clause in a Charter Party. This clause only concerns vessels that are

Figure 3 :

 3 Figure 3: Contractual and actual parameters of vessels It has to be noted that, in certain countries, it is not unusual to cease cargo operations in ports during some days. These non-working days (exception periods) are either included or excluded in the counting of laytime. The agreement, incorporated in the Charter Party, with exception or without exception periods for each individual port could be expressed as follows (Tsoudis, 2015):  SSHEX (Saturdays/Sundays/Holidays Excluded): The time lost in port on Saturdays, Sundays and Holidays does not count as laytime (from 5 pm on Friday until 8 am on Monday, and on Holidays from 5 pm of the day preceding a holiday until 8 am of the next working day).



  QCA(S)P characteristics: it specifies the version of the problem: either time-variant or time-invariant, the type of quay cranes: either homogeneous or heterogeneous, and the consideration of quay crane movement restrictions in the berth allocation.

Figure 4 :

 4 Figure 4: Example of a port with multiple quays and homogeneous quay cranes

  1 otherwise. An example of these parameters is shown in Table2, where time scale is the hour and non-working periods last two days (here represented by two hours due to space limitation). The detailed calculation of these parameters is shown in the file Time.xlsx.

Figure 5 :

 5 Figure 5: Vessel scheduling update

Figure

  Figure 7: Example of a port with multiple quays and heterogeneous quay cranes Figure 8: Range interval (maximum outreach) of each quay crane

  hours discretized in units of 1 hour, and a tidal port of 2 quays with different lengths discretized in units of 50The berthing sections of each quay are grouped into 3 ranges, and each range is characterized by a class of water depth (water depth increases as the class number increases). The variation of decision time scale is as follows : during the first week vessels can berth every hour, then during the second week, every four hours, then during the third week, every eight hours, and finally during the fourth week, every twelve hours. We also consider V to charter. Some vessels cannot be handled during weekends (SSHEX), and/or are tide-dependent. The detailed characteristics of time periods and vessels are shown, respectively, in the files Time.xlsx and Vessels.xlsx contained in Data_set_Harbour.zip. Figures 10 and 11 show, respectively, parts of the Gantt charts of the LBACAP and the LBACASP models with the economic objective function. The complete Gantt charts of both models with the economic and physical objective functions, and the detailed results are shown in the files LBACAPresults.xlsx and LBACASPresults.xlsx contained in Data_set_Harbour.zip.

Figure 10 :Figure 11 :

 1011 Figure 10: Part of the Gantt chart of the LBACAP model with the economic objective function

  to each vessel are determined by the test instance generator, as follows: an exponential distribution of parameter   10, 7.5, 5 in the LBACAP model and   15, 12.5, 10 in the LBACASP model for the interarrival time which determines the arrival times, and   U 15, 35 for the length. Depending on the length of each vessel, we define the maximum handling time  

  rounding up to the nearest integer, where the interference exponent a 0.4.  This latter reduces the marginal productivity of quay cranes. Since quay cranes are heterogeneous in the LBACASP model, handling times of vessels depend on the global productivity of each group of quay cranes. Half of the vessels with deep drafts are tide-dependent while entering the port, and the other half while leaving it. Vessels with medium and low drafts are tide-independent. 30% of vessels are handled only in working days. Very few vessels have restricted berthing quays to let the choice of the berthing quay open. The contractual processing time of each vessel equals one of its possible processing times, and we consider   U 50, 150 for the contracted demurrage by hour, and 50% of it gives the contracted despatch by hour. The maximum waiting time in harbor is 3 days for all chartered vessels, and one week for new vessels to charter. The laydays are either 2 or 3 days for new vessels to charter.

  cranes. Consequently, in this paper, we have introduced first a new integer programming model for the integrated Laycan and continuous Berth Allocation and time-invariant Quay Crane Assignment Problem (LBACAP). This latter integrates three problems with different decision levels (tactical and operational), therefore a change of decision time scale is made inside the planning horizon. Since the time-variant Quay Crane Assignment Problem usually introduces important shortcomings in the optimization process, we have chosen the time-invariant version, which gives solutions that are easier and more realistic to implement in port terminals. However, a little sacrifice is made in the optimal use of quay cranes. Two different objective functions are proposed: one based on a physical criterion since the actors involved in the port operations have conflicting objectives and interests and one economic objective

  upon Charter Parties' clauses established with shipowners, such as despatch money and demurrage,

Table 1 : BACA(S)P literature

 1

P: Predicate; C: Constraint

  Boolean parameter that equals 1 if the handling of vessel v is not carried out during period t (see section3.2.2.).Boolean parameter that equals 0 outside high tide cycles and during non-working periods (see section 3.2.2.).Relative period of the absolute period t in the case of f v (see section 3.2.2.).Absolute period of the relative period t in the case of f v (see section 3.2.2.). Boolean parameter that equals 0 if period t is within the high tide cycle, 1 otherwise.Handling time of each chartered vessel (v in 2 V ) if n quay cranes are assigned to it. For new vessels to charter (v in 3 V ), their handling time is increased by the laydays: θ P 1

	f 1 Γ t v
	Γ	f 2 t v
	K t	Boolean parameter that equals 1 if vessels can berth during period t (without considering the other
			constraints), 0 otherwise (see section 3.2.2.).
	O t
	min n v	Minimum number of identical quay cranes (technically allowable minimum number) that can be assigned to
			vessel (v in V ).
	θ n v
							n v	v   . Already berthed vessels (v in 1 V )
			have residual handling times.
	B v	Contractual handling time of each chartered vessel (v in 2 V ). Already berthed vessels (v in 1 V ) have residual
			contractual handling times. For each new vessel to charter (v in 3 V ),	B θ n v v 	1 	wish represents its longest
			handling time (determined by data preprocessing).
	δ v	Contracted finishing time for each berthed and chartered vessel (v in 1 V V ) and the longest finishing time 2 
			for each new vessel to charter (v in 3 V ):		v	 	1 A    2 ( B 1 ) , f , v v v	v  V (see section 3.2.2.).
	α v	Contracted demurrage by hour for each chartered vessel (v in 2 V ). For new vessels to charter (v in 3 V ),
			α 1

can take the values 1, 2, 3 or 4 (see section 3.2.2.).

f ψ v t f G v t max n v

Maximum number of identical quay cranes (technically allowable maximum number) that can be assigned to vessel (v in V ).

v  , and for already berthed vessels (v in 1

V ), α 0 v  . β v

Contracted despatch by hour for each chartered vessel (v in 2 V ). For new vessels to charter (v in 3

Table 2 : Calculation of tide and non-working periods parameters

 2

Table 3 : Characteristics of berthing sections Table 4: Characteristics of groups of quay cranes

 3

Table 5 : Solving the LBACAP

 5

Table 6 : Solving the LBACASP with a 50m discretization

 6

  Q V Solved Optimum Avg.time Avg. gap Max. gap Solved Optimum Avg.time Avg. gap Max. gap Solved Optimum Avg.time Avg. gap Max. gap Solved Optimum Avg.time Avg. gap Max. Solved Optimum Avg.time Avg. gap Max. gap Solved Optimum Avg.time Avg. gap Max. gap

							10 m discretization									50m discretization
					LBACAP eco					LBACAP phy					LBACAP eco					LBACAP phy
																						gap
		50	5	5	843.1	0	0	5	5	1593.7	0	0	5	5	18.3	0	0	5	5	40.5	0	0
	1	75	5	5	1583.9	0	0	5	3	3366.3	0.5	1.4	5	5	52.3	0	0	5	5	95.7	0	0
		100 4	2	3058.1	2.7	6.1	4	0	3667.4	5.3	7.9	5	3	1625.9	16.5	76.4	5	3	2240.6	2.5	11.5
		50	5	5	1877.9	0	0	5	5	3256.5	0	0	5	5	48.3	0	0	5	5	64.9	0	0
	3	75	5	5	2317.0	0	0	0					5	5	80.3	0	0	5	5	101.4	0	0
		100 5	4	3103.6	1.2	5.8	0					5	5	126.7	0	0	5	5	143.3	0	0
		50	5	5	2956.5	0	0	0					5	5	109.1	0	0	5	5	144.9	0	0
	5	75	1	1	3326.7	0	0	0					5	5	151.8	0	0	5	5	181.7	0	0
		100 0					0					5	5	218.3	0	0	5	5	244.6	0	0
							Q V

f \ψ 1 f f