Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

There has been a considerable growth in the share of containerized trade in the world’s total dry cargo during the last 30 years. Therefore, the efficient management of seaport container terminals has become a crucial issue [2]. In this work, we concentrate on the integrated planning of seaside operations, which includes the berth allocation problem (BAP), quay crane assignment problem (CAP) and quay crane scheduling problem (CSP). Generally, BAP deals with the determination of the optimal berthing times and positions of vessels in container terminals. The focus of CSP, on the other hand, is mainly on the problem of determining an optimal handling sequence of vessels for the available cranes at the terminal. However, as can be realized, the assignment of the cranes to vessels has a direct effect on the processing times of the vessels. As a result, crane assignment decisions can be embedded within either BAP or CSP models.

In this work we formulate two new MILP formulations integrating first BAP and CAP (BACAP), and then BAP, CAP, and CSP (BACASP). Both of them consider a continuous berth layout where vessels can berth at arbitrary positions within the range of the quay and dynamic vessel arrivals where vessels cannot berth before the expected arrival time. The crane schedule found by solving the BACASP formulation determines the specific crane allocation to vessels for every time period. These MILP models are the first models solved exactly rather than heuristically in the literature for relatively large instances.

2 Model Formulation

The underlying assumptions of our models are given as follows. The planning horizon is divided into equal-sized time periods. The berth is divided into equal-sized berth sections. Each berth section is occupied by no more than one vessel in each time period. Each quay crane can be assigned to at most one vessel per time period. Each vessel has a minimum and maximum number of quay cranes that can be assigned to it. The service of a vessel by quay cranes begins upon that vessel’s berthing at the terminal, and it is not disrupted until the vessel departs. The number of quay cranes assigned to a vessel does not change during its stay at the berth, which is referred to as a time-invariant assignment [1]. Furthermore, the set of specific cranes assigned to a vessel is kept the same. By letting \(i\) the index of vessels, \(g\) the index of crane groups, \(j\) the index of berth sections, \(k\) the index of number of cranes, \(t\) the index of time periods, \(c_{l}^{g}\) the index of the leftmost crane in group \(g\), \(c_{r}^{g}\) the index of the rightmost crane in group \(g\), and \(C(g)\) the index set of cranes in group \(g\), we define the following parameters: \(B\) = the number of berth sections, \(G\) = the number of crane groups, \(N\) = the number of available quay cranes, \(T\) = the number of time periods in the planning horizon, \(V\) = the number of vessels, \(d_{i}\)= due time of vessel \(i\), \(e_{i}\) = arrival time of vessel \(i\), \(\underline{k}^{i}\) = lower bound on the number of cranes that can be assigned to vessel \(i\), \(\overline{k}^{i}\) = upper bound on the number of cranes that can be assigned to vessel \(i\), \(\ell _{i}\) = the length of vessel \(i\) measured in terms of the number of berth sections occupied, \(p_{i}^{k}\) = processing time of vessel \(i\) if \(k\) cranes are assigned to it, \(s_{i}\) = desired berth section of vessel \(i\), \(\phi _{i1}\) = cost of one unit deviation from the desired berth section for vessel \(i\), \(\phi _{i2}\) = cost of berthing one period later than the arrival time for vessel \(i\), \(\phi _{i3}\) = cost of departing one period later than the due time for vessel \(i\).

Let us define a binary variable \(X_{ijt}^{k}\), which is equal to one if vessel \(i\) starts berthing at section \(j\) in time period \(t\), and \(k\) quay cranes are assigned to it, and zero otherwise. Constraint (1) ensures that each vessel berths at a unique section and time period, and the number of quay cranes assigned to it lies between the minimum and maximum allowed quantities.

$$\begin{aligned} \sum \limits _{j=1}^{B-\ell _{i}+1}\sum \limits _{k=\underline{k}^{i}}^{\overline{k}^{i}}\sum \limits _{t=e_{i}}^{T-p_{i}^{k}+1,}X_{ijt}^{k}=1 \quad \quad \quad i=1,\dots ,V. \end{aligned}$$
(1)

Constraint set (2) guarantees that each berth section is occupied by at most one vessel in each time period. To put it differently, there should not be any overlap among the rectangles representing vessels in the two-dimensional time-berth section space, which are located between \(\max \left( e_{i},t-p_{i}^{k}+1\right) \) and \(\min \left( T-p_{i}^{k}+1, t \right) \) on the time dimension, and between \(\max \left( 1,j-\ell _{i}+1 \right) \) and \(\min \left( B-\ell _{i}+1,j \right) \) on the berth section dimension.

$$\begin{aligned} \sum _{i=1}^{V}\sum _{j'=\max \left( 1,j-\ell _{i}+1\right) }^{\min \left( B-\ell _{i}+1,j \right) }\sum _{k=\underline{k}^{i}}^{\overline{k}^{i}}\sum _{t'=\max \left( e_{i},t-p_{i}^{k}+1\right) }^{\min \left( T-p_{i}^{k}+1, t \right) }X_{ij't'}^{k}\le 1 \quad \quad \quad j=1,\dots , B; t=1,\dots ,T \end{aligned}$$
(2)

We next discuss how quay crane availability can be handled in the BACAP model. Let us denote the number of available quay cranes by \(N\). Constraint set (3) ensures that in each time period the number of active quay cranes is less than or equal to the available number of cranes:

$$\begin{aligned} \sum _{i=1}^{V}\sum _{j=1}^{B-\ell _{i}+1}\sum _{k=\underline{k}^{i}}^{\overline{k}^{i}}\sum _{t'=\max \left( e_{i},t-p_{i}^{k}+1\right) }^{\min \left( T-p_{i}^{k}+1,t \right) }k X_{ijt'}^{k}\le N \quad \quad t=1,\dots ,T \end{aligned}$$
(3)

The objective function (4) of our model minimizes the total cost, whose components for each vessel are: (1) the cost of deviation from the desired berth section, (2) the cost of berthing later than the arrival time, and (3) the cost of departing later than the due time. Our integer programming formulation for BACAP can be summarized as follows:

$$\begin{aligned}&\min \sum _{i=1}^{V}\sum _{k=\underline{k}^{i}}^{\overline{k}^{i}}\sum _{j=1}^{B-\ell _{i}+1}\sum _{t=e_{i}}^{T-p_{i}^{k}+1}\left\{ \phi _{i1}|j-s_{i}| +\phi _{i2}\left( t-e_{i}\right) +\phi _{i3}\left( t+p_{i}^{k}-1-d_{i}\right) ^{+}\right\} X_{ijt}^{k} \end{aligned}$$
(4)

subject to constraints (1), (2), (3)

$$\begin{aligned} X_{ijt}^{k} \in \{0, 1\} \quad i&=1,\dots ,V;j=1,\dots , B-\ell _{i}+1;k =\underline{k}^i, \dots , \overline{k}^i;\\ t&=e_i, \dots , T-p_{i}^{k}+1 . \end{aligned}$$

Recall that although the availability of quay cranes is considered in constraint set (3) in BACAP, a schedule is not generated for each quay crane. To develop a mathematical programming formulation for BACASP we extend the formulation for BACAP by including the constraint sets (1)–(3) and defining new variables and constraints so that feasible schedules are obtained for quay cranes, which do not incur setup due to the change in the relative order of cranes. We should remark that if quay cranes \(i-1\) and \(i+1\) are assigned to a vessel in a time period, then quay crane \(i\) has to be assigned to the same vessel as well since quay cranes are located along the berth on a single railway. Hence, we define a crane group as a set of adjacent quay cranes and let the binary variable \(Y_{it}^{g}\) denote whether crane group \(g\) assigned to vessel \(i\) starts service in time period \(t\). Constraint set (5) relates the \(\mathbf {X}\) and \(\mathbf {Y}\)-variables. It ensures that if \(k\) quay cranes are assigned to vessel \(i\), it must be served by a crane group \(g\) that is formed by \(|C(g)| = k\) cranes, where \(C(g)\) is the index set of cranes in group \(g\) and \(|\cdot |\) denotes the cardinality of a set. Moreover, \(G\) is the total number of crane groups.

$$\begin{aligned} \sum _{j=1}^{B-\ell _{i}+1}X_{ijt}^{k}-\sum _{\underset{|C(g)|=k}{g=1}}^{G}Y_{it}^{g}=0 \quad i=1,\dots ,V;k=\underline{k}^{i},\dots ,\overline{k}^{i};t=e_{i},\dots ,T-p_{i}^{k}+1 \end{aligned}$$
(5)

It should be emphasized that each crane can be a member of multiple crane groups. However, each crane can operate as a member of at most one group in each time period. The next set of constraints (6) guarantees that this condition holds:

$$\begin{aligned} \sum _{i=1}^{V}\sum _{\underset{c\in C(g)}{g=1}}^{G}\sum _{t=\max \left( e_{i},t-p_{i}^{k}+1\right) }^{\min \left( T-p_{i}^{k}+1,t \right) }Y_{it'}^{g}\le 1 \quad c=1,\dots ,N;t=1,\dots ,T \end{aligned}$$
(6)

Even though constraints (5) and (6) make sure that each quay crane is assigned to at most one vessel in any time period, they do not guarantee that quay cranes are assigned to vessels in the correct sequence. In particular, let the quay cranes be indexed in such a way that a crane positioned closer to the beginning of the berth has a lower index. Since all cranes perform their duty along a rail at the berth, they cannot pass each other or stated differently their order cannot be changed. The next four constraint sets help to ensure preserving the crane ordering. Here, \(Z_{ct}\) denotes the position of crane \(c\) in time period \(t\).

$$\begin{aligned} Z_{ct} \le Z_{(c+1)t} \quad c=1,\dots ,N-1;{t} =1,\dots ,T \end{aligned}$$
(7)
$$\begin{aligned} Z_{Nt} \le B \quad t=1,\dots ,T \end{aligned}$$
(8)
$$\begin{aligned} Z_{c_{l}^{g}\overline{t}}+B(1-Y_{it}^{g}) \ge \sum _{j=1}^{B-\ell _{i}+1}\sum \limits _{k=\underline{k}^{i}}^{\overline{k}^{i}}jX_{ijt}^{k} \quad i=\,\,&1,\dots ,V;g=1,\dots ,G;\nonumber \\ t=\,\,&e_{i},\dots ,T-p_{i}^{k}+1; t\le \overline{t}\le t+p_{i}^{k}-1 \end{aligned}$$
(9)
$$\begin{aligned} Z_{c_{r}^{g}\overline{t}} \le \sum _{j=1}^{B-\ell _{i}+1}\sum _{k=\underline{k}^{i}}^{\overline{k}^{i}}\left( j+\ell _{i}-1\right) X_{ijt}^{k}+B(1-Y_{it}^{g}) \quad i&=1,\dots ,V;g=1,\dots ,G;\nonumber \\ t&=e_{i},\dots ,T-p_{i}^{k}+1; t\le \overline{t}\le t+p_{i}^{k}-1 \end{aligned}$$
(10)

Constraint set (7) simply states that the positions of the cranes (in terms of berth sections) are respected by the index of the cranes. This means that the position of crane \(c\) is always less than or equal to the position of crane \(c+1\) during the planning horizon. Constraint set (8) makes sure that the last crane (crane \(N\)) is positioned within the berth. By defining \(c_{l}^{g}\) and \(c_{r}^{g}\) as the index of the crane that is, respectively, the leftmost and rightmost member of crane group \(g\), constraint set (9) guarantees that if crane group \(g\) is assigned to vessel \(i\) and vessel \(i\) berths at section \(j\), then the position of the leftmost member of crane group \(g\) is greater than or equal to \(j\). Similarly, constraint set (10) ensures that if crane group \(g\) is assigned to vessel \(i\) and vessel \(i\) berths at section \(j\), then the position of the rightmost member of crane group \(g\) is less than or equal to \(j+\ell _{i}-1\), which is the last section of the berth occupied by vessel \(i\).

3 Solution

As can be observed, BACASP formulation is significantly larger than our BACAP formulation with which we can solve instances up to 60 vessels. Hence, it should be expected that only small BACASP instances can be solved exactly using CPLEX 12.2. This fact has motivated us to make use of the formulation for BACAP in solving larger sized BACASP instances to optimality. By carefully analyzing the optimal solutions of BACAP and BACASP in small sized instances, we have figured out that an optimal solution of BACASP can be generated from an optimal solution of BACAP provided that the condition given in Proposition 1 is satisfied. This condition is based on the notion of complete sequence of vessels (with respect to their occupied berthing positions), which is defined as follows.

Definition 1

A vessel sequence \(v_{1},v_{2},\dots ,v_{n}\) is complete if (1) \(v_{1}\) is the closest vessel to the beginning of the berth, (2) \(v_{n}\) is the closest vessel to the end of the berth, (3) \(v_{i}\) and \(v_{i+1}\) are two consecutive vessels with \(v_{i}\) closer to the beginning of the berth, and (4) two consecutive vessels in this sequence must be at the berth during at least one time period.

A complete sequence is said to be proper when the sum of the number of cranes assigned to vessels in this sequence is less than or equal to \(N\). Otherwise, it is called an improper complete sequence.

Proposition 1

An optimal solution of BACASP can be obtained from an optimal solution of BACAP by a post-processing algorithm if and only if every complete sequence of vessels is proper.

The proof of this proposition can be found in [3]. If there is at least one improper complete sequence of vessels in an optimal solution of BACAP, then we cannot apply the post-processing algorithm given as Algorithm 1 to obtain an optimal solution of BACASP from an optimal solution of BACAP.

figure a

In Algorithm 1, \(\fancyscript{V}_{A}\) (\(\fancyscript{V}_{NA}\)) denotes the set of vessels to which cranes (no cranes) are assigned yet. Clearly, \(\fancyscript{V}_{NA} \cup \fancyscript{V}_{A} = \{1,2,\dots ,V\}\). Notice that the way the vessels are picked up from \(\fancyscript{V}_{NA}\) and added to the set \(\fancyscript{V}_{A}\) implies that the order of the vessels forms one or more complete sequences in the set \(\fancyscript{V}_{A}\). It is also ensured that these complete sequences are proper.

If there exists a complete sequence where the sum of the number of cranes assigned to vessels is larger than \(N\), then it is possible to add the cut given in (11) corresponding to an improper complete sequence into the formulation of BACAP, where \(I\!S\) refers to an improper complete sequence and \(\left| {I\!S} \right| \) is the total number of vessels involved in that complete sequence. Note that this cut is used to eliminate feasible solutions that involve \(I\!S\).

$$\begin{aligned} \sum _{i\in IS} X_{ij(i)t(i)}^{k(i)} \le \left| {I\!S} \right| -1 \end{aligned}$$
(11)

The left-hand side of (11) consists of the sum of the \(X_{ijt}^{k}\) variables which are set to one for the vessels involved in \(IS\). In other words, there is only one \(X_{ijt}^{k}=1\) for each vessel \(i \in IS\). The \(j,k\), and \(t\) indices for which \(X_{ijt}^{k}=1\) related to vessel \(i\) are denoted as \(j(i)\), \(k(i)\), and \(t(i)\) in (11). Upon the addition of this cut, BACAP is solved again. The addition of these cuts is repeated until the optimal solution of BACAP does not contain any improper complete sequences. At that instant, Algorithm 1 can be called to generate an optimal solution of BACASP from the existing optimal solution of BACAP.