Skipping the Storage Phase in Container Transshipment Operations

Abstract

The paper deals with the problem of scheduling the loading/discharging operations of two simultaneously berthed vessels, assuming that some of the containers discharged from a vessel must be directly loaded on the other one. For these containers also the stowage position must be decided. The aim is to minimize the time needed to complete all the operations required by the involved vessels. For this problem we present a mathematical model, a heuristic algorithm and discuss the computational results on a set of randomly generated instances.

The research has been supported by Ministero dell’Istruzione, Università e Ricerca under the PRIN 2015 research program - Grant 2015XAPRKF - Smart PORt Terminals.

1 Introduction

At a maritime terminal the conventional transshipment flow of containers follows the quay-yard-(yard)-quay cycle, where the yard-to-yard movements concern possible housekeeping operations aimed at reconfiguring the yard and recovering storage spaces. From the operative point of view, the storage of the containers in the yard is essential to decouple in time the ingoing and outgoing container flows. Therefore the discharging and loading operations (of the same containers) are independent and can be planned and scheduled separately and efficiently. On the other hand, the yard is a critical resource, due to its limited capacity, and terminal planners are concerned with the reduction of the sojourn time of the containers in the yard (dwell-time) because that could increase the terminal throughput. The dwell-times have also a relevant economic impact for the shipping operators, since they contribute to determine the port fees. Therefore, reducing the dwell-times is a common target for the two main operators of the transshipment market. In view of that, we investigate the feasibility of a new operative transshipment modality, called Direct Transshipment.

We consider two vessels, simultaneously berthed at not necessarily adjacent berths, and we assume that some of the containers discharged from each of them must be directly loaded into the other, while the rest of the cargo follows the conventional transshipment flow (quay-yard-quay). Clearly, in the direct transshipment modality the unloading and loading operations are no longer independent and the related scheduling processes are concurrent: each container to be directly transshipped represents two dependent tasks (unloading/loading), to be executed by different machines (quay cranes) operating on different vessels, linked by a strict precedence relationship. In order to fully take advantage from this operative modality, the stowage decisions for the directly transshipped containers must become a degree of freedom for the planners. This is to say that the stowage positions of such containers and the cranes scheduling will be determined concurrently. The Direct Container Transshipment Problem (DCTP) is then the problem of scheduling all the vessel operations while deciding the stowage positions for the containers to be directly transshipped, so as to minimize the overall service time of the vessels.

The paper is organized as follows. The scientific literature related to the DCTP is discussed in Sect. 2. In Sects. 3 and 4 we state and formulate the problem. The solution algorithm is presented in Sect. 5. Section 6 discusses the computational experience. Finally conclusions are drawn in Sect. 7.

2 Related Works

The direct transshipment of containers between vessels seems to be a relatively new problem in the literature concerning the management of container terminals. In a more wide research stream, it has some similarities with the Cross Docking policy at a distribution terminal in a logistic network [4]. The main analogy between them is the common need of synchronizing the arrival and departure sequences of the carriers, while having low or possibly zero inventory levels.

The effectiveness of the direct transshipment of containers between different means of transport has been investigated in [1] for the case of rail hubs, in [7] for the case of trains and trucks, and in [3] for the case of mother ships and barges. Only few papers refer to the direct ship-to-ship transshipment. In [8] the authors consider a one-way direct transshipment between a mother vessel and a feeder, which “moor at the same berth and utilize the same handling equipment”. Some researchers have recently studied an analogous problem in the case of mobile (or offshore) harbours, which are floating platforms equipped with portal cranes and are used to perform unloading and loading operations in the open sea (see [13]).

The only work that recognizes the effectiveness of the direct transshipment of containers between vessels is described in [15]. The authors present a model that integrates the berth allocation of the vessels, the yard space assignment, and the direct transshipment plan; the aim is to minimize the operative costs of trucks and yard cranes, as well as the delay cost of the vessels.

The DCTP we address in this paper, formerly introduced in [11], completely differs from that described in [15]; we deal with the operative management of the direct transshipment of containers between vessels, so integrating the scheduling of the quay cranes allocated to the vessels and the stowage of the directly transshipped containers.

3 Problem Statement

In order to derive the mathematical model for the DCTP, we first need to introduce the adopted notation and to detail the complex interactions between the main decision components of the problem, from which the constraints originate. As noted before, the management of the direct transshipment operative modality calls for the integration of two decision processes: the scheduling of the cranes operating on the two vessels and the stowage of the containers to be directly transshipped. Therefore, we will model it as a Quay Crane Scheduling Problem QCSP (see e.g. [2, 14]) on a virtual vessel, with stowage constraints.

3.1 Notation

The mathematical model for the DCTP relies on the following main entities, that are vessels ($V=\{A,B\}$), tasks ($\varOmega ^v, v \in V$), and quay cranes ($Q^v, v \in V)$. For each vessel v, the set of tasks consists of three disjoint subsets $\varOmega ^v=G^v\cup D^v\cup L^v$. $G^v$ is the set of groups of containers, to be loaded or discharged, following the conventional transshipment flow, also called conventional tasks; $D^v$ is the set of single containers discharged from v and directly transshipped to the other vessel; $L^v$ is the set of containers directly transshipped from the other vessel and to be loaded into v. In the following we will refer to a container to be directly transshipped as a DT container. The vessels V can be seen as a single virtual vessel, with task set $\varOmega = \varOmega ^A \cup \varOmega ^B$ and crane set $Q=Q^A\cup Q^B$.

In Table 1 we detail the characteristics and the attributes of vessels, tasks, and cranes.

Table 1. Notation

Some of the entries in Table 1 need to be further explained. Each element $\theta$ of the sets $\varTheta ^v$ actually represents a single stowage slot in terms of (bay, row, tier) coordinates; moreover each $\theta \in \varTheta ^v$ is able to accommodate only a subset of the containers in $L^v$, as indicated by the class-based stowage plan (see [12]). Therefore we define by $\varTheta _i^v \subseteq \varTheta ^v, i \in L^v$ the set of slots where container i can be stowed, and by $H_i^v \subset H^v$ the set of bays where a stowage slot compatible with the container $i \in L^v$ is located, that is $H_i^v=\{b \in H^v\ |\ b=b_\theta , \theta \in \varTheta _i^v\}$, where $b_\theta$ is the bay coordinate corresponding to $\theta$. In passing, we observe that $H_i^v$ can also be defined for tasks $i \in G^v \cup D^v$, being in this case $H_i^v=\{b(i)\}$ a singleton. Finally, we define $\varTheta ^v(b,i)$ the set of slots $\theta \in \varTheta ^v_i$ compatible with i and located in the bay b.

Due to physical restrictions, there are tasks whose processing can not overlap in time. For example, in the same bay unloading tasks always precede the loading ones, while in adjacent bays simultaneous processing of tasks by different cranes is forbidden, due to safety issues. This is to say that, for each vessel, some temporal restrictions on task pairs are defined. They impose either precedence or non-simultaneity constraints on the processing of the tasks. More clearly, if there is a precedence between tasks i and j, then the processing of j can not start before the processing of i has been completed. Conversely, a non-simultaneity relationship between i and j imposes that either i must precede j, or j must precede i. To model these relations we need to extend our notation.

Precedence Relationships: A first set of precedence relationships is given by

$$\begin{aligned}&\varPhi = \bigcup _{v \in V}\varPhi ^v \cup \bar{\varPhi } \end{aligned}$$

where

$$\begin{aligned} \varPhi ^v=\{(i,j) \ | \ i \rightarrow j,\ i,j \in G^v \cup D^v\}\ \ \ v \in V \end{aligned}$$

relates to pairs of tasks belonging to the same vessel. $\varPhi ^v$ basically expresses precedences due to the operations the tasks require and can be populated using the stowage plan. Conversely

$$\begin{aligned} \bar{\varPhi }=\{(i,j) \ |\ i \rightarrow j,(i \in D^A, j \in L^B) \vee (i \in D^B, j \in L^A)\} \end{aligned}$$

are the precedence relationships between discharging and loading operations on different vessels for the DT containers.

Further precedence relationships for a given vessel are needed to guarantee that the directly transshipped containers will be loaded according to the stowage plan. To this aim we define

$$\begin{aligned}&\varPhi _1^v=\{(i,\theta )\ |\ i \rightarrow \theta , i \in G^v \cup D^v, \theta \in \varTheta ^v\}&v \in V\\&\varPhi _2^v=\{(\theta ,i)\ |\ \theta \rightarrow i, \theta \in \varTheta ^v, i \in G^v\}&v \in V\\&\varPhi _3^v=\{(\theta _1,\theta _2)\ |\ \theta _1 \rightarrow \theta _2, \theta _1, \theta _2 \in \varTheta ^v\}&v \in V \end{aligned}$$

The sets $\varPhi _1^v$ and $\varPhi _2^v$ induce precedence relationships between a task whose stowage position is known and the container that will be stowed into the ship-slot $\theta$. The sets $\varPhi _3^v$ define precedence relationships between pairs of ship-slots due to their relative positions within the same bay. As a consequence they will induce, at runtime, also a set of precedence relations on the containers that will be stowed there.

Non Simultaneity Relationships: Assumed $\delta$ to be the safety distance between two adjacent cranes, expressed in number of bays, we define the set of bays that cannot be operated simultaneously by different cranes as follows

$$\begin{aligned}&\varPsi ^v=\{(b_1,b_2) \ |\ b_1,b_2 \in H^v, b_1 < b_2, b_2-b_1 \le \delta \}&v \in V \end{aligned}$$

The above sets allow to impose the non-simultaneity constraints between each pair of tasks in close bays, even for the loading ones whose stowage bay must be decided by the model. However, as disclosed in [2], the sets $\varPsi ^v$ are not sufficient to model the interferences between non adjacent cranes working on the vessel v. To this aim we define

$$\begin{aligned}&\varDelta _{b_{1}b_{2}}^{hk}(v) = \max \left\{ \hat{t}\left( (\delta +1)(k-h)-(b_2-b_1)\right) , 0\right\} \!&b_1, b_2 \in H^v, h,k \in Q^v, v\in V \end{aligned}$$

as the minimum time to elapse between the processing of any task located in the bay $b_1$ and any task in bay $b_2$ by cranes h and k, respectively. Therefore

$$\begin{aligned} \hat{\varDelta }(v)=\left\{ (b_1,b_2,h,k) \ |\ \varDelta _{b_{1}b_{2}}^{hk}(v) >0 \right\} \end{aligned}$$

is the set of all combinations of bays and cranes that cause interferences on the vessel v. Observe that if $(b_1,b_2) \in \varPsi ^v$, then $(b_1,b_2,h,k) \in \hat{\varDelta }(v)$ for all cranes $h,k \in Q^v$ such that $h \in Q(b_1), k \in Q(b_2)$. Thus, $\hat{\varDelta }(v)$ is a generalization of $\varPsi ^v$ and extends the corresponding definition in [2].

3.2 The Mathematical Model

The DCTP model involves both binary and continuous variables, as detailed in Table 2. Note that, as $H_i^v = \{b(i) \}$, then $\alpha _{i b(i)}=1$, $\alpha _{ib}=0 \ \forall b \ne b(i)$ are input data for all tasks $i \in G^v \cup D^v$, $v \in V$.

The constraints to be imposed for each vessel $v \in V$ can be stated as follows:

Table 2. Variables

Crane Routing Constraints: Constraints (1) to (4) define the sequence of tasks performed by each crane. Note that 0 and T are dummy tasks with $p_0=p_T=0$, $\varOmega _0^v=\varOmega ^v \cup \{0\}$, $\varOmega _T^v=\varOmega ^v \cup \{T\}$ and $x_{0Tk}=1$ corresponds to an empty sequence for crane k.

$$\begin{aligned}&\sum _{j \in \varOmega _{T}^v}x_{0jk}=1&k \in Q^v\ \end{aligned}$$

(1)

$$\begin{aligned}&\sum _{i \in \varOmega _0^v}x_{iTk}=1&k \in Q^v\ \end{aligned}$$

(2)

$$\begin{aligned}&\sum _{k \in Q^v}\sum _{j \in \varOmega _T^v}x_{ijk}=1&i \in \varOmega ^v\ \end{aligned}$$

(3)

$$\begin{aligned}&\sum _{j \in \varOmega _T^v}x_{ijk}-\sum _{j \in \varOmega _0^v}x_{jik}=0&i \in \varOmega ^v, k \in Q^v\ \end{aligned}$$

(4)

Stowage Constraints: Constraints (5) and (6) assign a stowage position, in terms of slot and bay, to the DT containers, while constraints (7) and (8) state the relationships between $y's$ and $\alpha 's$, $x's$ and $\alpha 's$ variables, respectively. Note that, for a fixed $i \in L^v$, summing up constraints (7) on the compatible bays $b \in H_i^v$ and taking into account constraints (6), one gets $\sum _{\theta \in \varTheta _{i}^{v}}y_{i\theta }=1$. Constraints (8) impose that if a task must be performed in a bay b, it has to be assigned to a crane able to operate that bay.

$$\begin{aligned}&\sum _{i \in L^v}y_{i\theta }=1&\theta \in \varTheta ^v \\&\sum _{b \in H_i^v}\alpha _{ib} =1&i \in L^v \\&\sum _{\theta \in \varTheta (i,b)} y_{i\theta } = \alpha _{ib}&i \in \L ^v, b \in H_i^v \\&\sum _{k \in Q(b)}\sum _{j \in \varOmega ^v} x_{ijk} \ge \alpha _{ib}&i \in \varOmega ^v, b \in H_i^v \end{aligned}$$

(5)

Completion Time Constraints: The completion times of the tasks are computed through constraints (9)–(12). Here and in what follows M is a big constant.

$$\begin{aligned}&c_i-p_i \ge a^v&i \in \varOmega ^v \end{aligned}$$

(6)

$$\begin{aligned}&r_k-c_j+\sum _{b \in H_{j}^{v}}\alpha _{jb}t_{l_{k}^{0}b}+p_j \le M(1-x_{0jk})&j \in \varOmega ^v, k \in Q^v \end{aligned}$$

(7)

$$\begin{aligned}&c_i-c_T \le M(1-x_{iTk})&i \in \varOmega _{0}^v, k \in Q^v \end{aligned}$$

(8)

$$\begin{aligned}&c_i+\hat{t}\left| \sum _{b \in H_{i}^{v}}b\alpha _{ib}-\sum _{b \in H_{j}^{v}}b\alpha _{jb}\right| +p_j-c_j\le M(1-x_{ijk})&i,j \in \varOmega ^v, k \in Q^v \end{aligned}$$

(9)

The non linearity in constraints (12) can be easily handled replacing each of them with the following set of constraints

$$\begin{aligned}&c_i+(\alpha _{ib_{1}}+\alpha _{jb_{2}}-1)t_{b_{1}b_{2}}+p_j-c_j\le M(1-x_{ijk})&b_1 \in H_i^v, b_2 \in H_j^v \end{aligned}$$

(10)

Precedence Constraints: Constraints (14)–(18) impose the precedence relationships between pairs of tasks.

$$\begin{aligned}&c_i+p_j-c_j \le 0&(i,j) \in \varPhi ^v&\end{aligned}$$

(11)

$$\begin{aligned}&c_i+p_j-c_j \le M(1-y_{j \theta })&j \in L^v, \theta \in \varTheta _j^v, (i,\theta ) \in \varPhi _1^v \end{aligned}$$

(12)

$$\begin{aligned}&c_j+p_i-c_i \le M(1-y_{j \theta })&j \in L^v, \theta \in \varTheta _j^v, (\theta ,i) \in \varPhi _2^v \end{aligned}$$

(13)

$$\begin{aligned}&c_i+p_j-c_j \le M(2-y_{i \theta _{1}}-y_{j \theta _{2}})&i,j \in L^v, \theta _1 \in \varTheta _i^v, \theta _2 \in \varTheta _j^v,(\theta _1,\theta _2) \in \varPhi _3^v&\end{aligned}$$

(14)

$$\begin{aligned}&c_i+\sigma _{ij}+p_j-c_j \le 0&(i,j) \in \bar{\varPhi } \end{aligned}$$

(15)

In particular, (14) define the precedence between tasks whose stowage position is known, while (15) to (18) take into account precedence relationships involving DT containers to be loaded. The variables $\sigma _{ij}$ in (18) are defined through equations (19), where $l_A^F$ is the last bay of vessel A, $d_{AB}$ is the inter-vessel distance expressed in number of bays, and $\tau$ is the time a straddle carrier takes to cover a ship-bay (see [5]).

$$\begin{aligned}&\sigma _{ij}=\tau \left( \sum _{v \in V}\sum _{b \in H_{j}^{v}}b\alpha _{jb}-b(i)+l_A^F+d_{AB}\right)&(i,j) \in \bar{\varPhi } \end{aligned}$$

(16)

Non Simultaneity Constraints: The relations between the completion times of the tasks and the $z's$ variables are stated by constraints (20), (21), and (22). They impose a partial time-ordering on the tasks of the same vessel. Actually, for each pair of tasks, either i precedes j ($z_{ij}=1, z_{ji}=0$), or j precedes i ($z_{ji}=1, z_{ij}=0$), or, finally, the processing of i and j overlap ($z_{ij}=z_{ji}=0$). Note that if i and j are tasks located in too close bays, constraints (22) avoid that they are processed simultaneously.

$$\begin{aligned}&c_i+p_j-c_j \le M(1-z_{ij})&i,j \in \varOmega ^v \end{aligned}$$

(17)

$$\begin{aligned}&c_j-p_j-c_i \le Mz_{ij}&i,j \in \varOmega ^v \end{aligned}$$

(18)

$$\begin{aligned}&z_{ij}+z_{ji} \ge \alpha _{ib_{1}}+\alpha _{jb_{2}}-1&i,j \in \varOmega ^v, b_1 \in H_i^v, b_2 \in H_j^v, (b_1,b_2) \in \varPsi ^v \end{aligned}$$

(19)

Non Interference Constraints: For each pair of tasks $i,j \in \varOmega ^v$ and for each pair of compatible bays $b_1 \in H_i^v, b_2 \in H_j^v$, the following constraints must hold for each pair of cranes h and k that would cause interference working simultaneously on bays $b_1$ and $b_2$, that is $(b_1,b_2,h,k)\in \hat{\varDelta }(v)$:

$$\begin{aligned} \sum _{u \in \varOmega _{0}^{v}}x_{uih}+\sum _{u \in \varOmega _{0}^{v}}x_{ujk}+\alpha _{ib_{1}}+\alpha _{jb_{2}}\le 3 + z_{ij}+z_{ji} \end{aligned}$$

(20)

$$\begin{aligned} c_{i}+\varDelta _{b_{1}b_{2}}^{hk}(v)+p_j-c_j\le M\left( 5-\alpha _{ib_{1}}-\alpha _{jb_{2}}-z_{ij}-\sum _{u \in \varOmega _{0}^v}x_{uih}-\sum _{u \in \varOmega _{0}^{v}}x_{ujk}\right) \end{aligned}$$

(21)

$$\begin{aligned} c_{j}+\varDelta _{b_{1}b_{2}}^{hk}(v)+p_i-c_i\le M\left( 5-\alpha _{ib_{1}}-\alpha _{jb_{2}}-z_{ji}-\sum _{u \in \varOmega _{0}^v}x_{uih}-\sum _{u \in \varOmega _{0}^{v}}x_{ujk}\right) \end{aligned}$$

(22)

Objective Function Definition. The objective function to be minimized is a linear combination of two conflicting functions: the makespan of the virtual vessel, defined by (26)–(27), and the average waiting time for the DT containers (28).

$$\begin{aligned} c_i \le w^v \quad i \in \varOmega ^v, v \in V \end{aligned}$$

(23)

$$\begin{aligned} w^v \le w \quad v \in V \end{aligned}$$

(24)

$$\begin{aligned} \min \lambda w + \mu \dfrac{1}{|\bar{\varPhi }|}\sum _{(i,j)\in \bar{\varPhi }}(c_j-p_j-\sigma _{ij}-c_i) \end{aligned}$$

(25)

4 Refinement of the DCTP Model

As motivated in [2, 10], the search of feasible solutions of the QCSP can be limited to the unidirectional schedules, where all the cranes move from the bow to the stern of the vessel, or in the opposite direction. Therefore, also in the DCTP model (1)–(11), (13)–(28) it is possible to impose the one-way movement of all the cranes allocated to the single vessels. To this aim we introduce two new binary variables: $\gamma ^v =1$ if the cranes in $Q^v$ move from the bow to the stern, $v \in V$, and a set of additional constraints (see [10]):

$$\begin{aligned}&\sum _{b \in H_i^v} b \alpha _{ib} - \sum _{b \in H_j^v} b \alpha _{jb} \le M(1 - x_{ijk}) + M(1- \gamma ^v)&i,j \in \varOmega ^v, \ v \in V \end{aligned}$$

(26)

$$\begin{aligned}&\sum _{b \in H_j^v} b \alpha _{jb} - \sum _{b \in H_i^v} b \alpha _{ib} \le M(1 - x_{ijk}) + M \gamma ^v&i,j \in \varOmega ^v, \ v \in V \end{aligned}$$

(27)

Note that (29), (30) extend the corresponding constraints (16), (17) in [10], also to the DT containers to be loaded, whose stowage bay is unknown.

5 Solution Algorithm

The formulation of the DCTP (1)–(11), (13)–(30) as a QCSP on a virtual vessel with side constraints naturally drives to design a solution algorithm by suitably modifying the Tabu Search Algorithm for the QCSP described in [10].

Given a feasible stowage plan for the DT containers, our algorithm iterates over feasible solutions constructed by a two-phases approach:

• 1. Routing phase: for each crane, a feasible sequence of tasks is determined taking into account precedence, one-way and cranes’ operative range constraints.

• 2. Scheduling phase: the completion time of the tasks is computed imposing the non simultaneity and non interference constraints, and the precedence constraints related to the DT containers.

A feasible schedule for the cranes can be represented by a disjunctive graph with node set $\varOmega \cup \{ 0,T \}$ (see [10]), where disjunctive edges model the non simultaneity and the non interference constraints. To perform the scheduling phase and evaluate the makespan for the virtual vessel, we have to find the critical path from 0 to T on such a disjunctive graph. This problem is, in general, ${\mathcal NP}$-hard, while in our case it becomes easier to solve. The one-way assumption, in fact, uniquely identify the orientation of the disjunctive edges giving rise to an acyclic graph.

To describe the Tabu Search algorithm for the DCTP, it is sufficient to specify the memory mechanism and the neighbourhood structure. We adopt the attributive memory mechanism, meaning that a solution is declared tabu if at least one of the attributes describing that solution is tabu [6]. In order to introduce the neighbourhood structure, let us denote by $(\bar{x}, \bar{y})$ a given feasible solution in terms of the main scheduling variables (x) and stowage variables (y). We define swap move the swapping of the stowage positions of two containers in $L^v, v \in V$; $N_1(\bar{y})$ is the set of all feasible stowage configurations obtained from $\bar{y}$ by performing a swap move. Furthermore, we define shift move the shifting of a task currently assigned to the crane k to an adjacent crane ($k-1$ or $k+1$), and $N_2(\bar{x})$ as the set of all feasible schedules obtained from $\bar{x}$ by performing a shift move. The neighborhood of $(\bar{x}, \bar{y}$) can now be defined as follows:

$$\begin{aligned} \mathcal{N}(\bar{x}, \bar{y})=\{(\bar{x},y) \ | \ y \in N_1(\bar{y})\} \cup \{(x, \bar{y}) \ |\ x \in N_2(\bar{x}) \} \end{aligned}$$

(28)

6 Computational Experience

The Tabu Search Algorithm (TSA) has been implemented in C++. The stopping criterion is based on a maximum number of iterations equal to 2000. The tabu tenure has been set to 15 iterations; the diversification penalty has been set equal to 0.05. The tests have been carried out on a machine equipped with a 3.1 GHz Intel Core i5 CPU and 16 GB of RAM. TSA has been tested on a set of instances randomly generated as described in the next subsection.

6.1 Instance Generator Algorithm

Let I an instance of the standard QCSP defined by: number of conventional tasks (T), number of cranes (Q), and number of bays (B). In such an instance each conventional task is characterized by a processing time p and a bay location b. Given two QCSP instances, say $I_A$ and $I_B$, called seed instances, an instance $I_{AB}$ of the DCTP can be constructed as follows. First, we assume that a task i of $I_A$ or $I_B$ with processing time $p_i$ is a group of $p_i$ containers. Let c be the number of container classes and $n_c$ the number of DT containers of class c in the instance $I_{AB}$. For each instance $I_A$ and $I_B$, apply the following algorithm (DCTP-G):

• 1. Randomly select a class c and a bay b.

• 2. Randomly select in the bay b a conventional task i of class c; let $p_i$ its processing time.

• 3. If $n_c \le p_i$, replace the task i with $n_c+1$ tasks, where the first tasks represent $n_c$ DT containers, while the last one, if any, represents a residual conventional task $i^{\prime }$ with processing time $p_{i^{\prime }}= p_i-n_c$. GO TO 1.

• 4. If $n_c > p_i$, replace the selected conventional task i with $p_i$ DT containers; set $n_c=n_c-p_i$, $b=b+1$ and GO TO 2.

To generate the seed instances, we have adopted the instance generator QCSPgen developed by Meisel and Bierwirth in [9]. The interested reader is referred to [9] for more details on the QCSPgen algorithm. Here we just mention that, among the input parameters of QCSPgen, we have set the distribution of the tasks within the vessel to be uniform; the density of precedence relationships among tasks of the same bay to be one, meaning that within the same bay all the tasks are sorted to reflect the stowage constraints. Finally we have set the crane safety distance to be one bay. We have generated two sets of instances to represent two kind of vessels: mother vessels and feeder vessels. The dimensions of the seed instances are reported in Table 3, where NoI indicates the number of instances of each type generated.

Table 3. Dimensions of the seed instances.

The seed-instances of Table 3 are combined each other and become the input for the DCTP-G algorithm, either as $I_A$ or as $I_B$, together with the number of container classes c and the number of DT containers per class, $n_c$, giving rise to 33 DCTP instances as detailed in Table 4.

Table 4. Description of the DCTP instances.

6.2 Lower Bounds for the DCTP

In order to evaluate the effectiveness of TSA, we need to compute lower bounds for the DCTP. The most natural way to achieve this aim is to consider a relaxed DCTP model obtained by removing constraints (5) to (8) related to the stowage decision. The resulting DCTP-SR relaxed problem, consisting of two standard QCSPs linked by constraints (18), is hard to solve to optimality. Actually standard ILP solvers easily run out of memory, due to the high number of constraints and variables. For these reasons we also relax constraints (18), getting the DCTP-WR problem that decomposes in two QCSPs no longer dependent on each other, and relatively easy to be solved by a standard ILP solver.

Table 5. Results on Mother-Feeder instances.

Table 6. Results on Feeder-Mother instances.

Table 7. Results on Mother-Mother instances.

6.3 Analysis of the Results

In the following Tables 5, 6, and 7, we summarize the computational results obtained by solving the instances described in Table 4 by our TSA, and the corresponding DCTP-WR problems by ILOG Cplex 12.6.2., setting $\lambda = \mu =1$ in the objective function. For each instance, in the leftmost columns of the result Tables we report: the data related to the number of bays and cranes (B-Q) of each vessel; the number of tasks T in the form (DT containers - conventional tasks). Observe that the instance code $I_AI_B-\alpha -\beta -\gamma -\delta$ is useful to recognize the seed instances generating it, being $\alpha -\beta$ the number of bays and tasks of $I_A$ and $\gamma -\delta$ the number of bays and tasks of $I_B$. Then we report the makespan of the two vessels, both for the DCTP-WR and DCTP models, marking in bold the maximum between them. As for the DT containers, in the second last column (AvgD) we report the average waiting time between the discharging and the loading operation. Finally, in the last column, we report the gap computed as $Gap \% = 100 \times (UB - LB)/ LB$ where $LB= \max \{w^A, w^B \}$ and $UB = \max \{w^A, w^B \} + AvgD$. We do not report the computation times, since they are about 300 s almost uniformely on all the instances.

A first oversight to the Tables shows that TSA gives satisfactory results on all but the first two groups of instances in Table 6. Actually, very often the overall makespan coincides with its lower bound, and the average delay of the DT containers is small enough, resulting in a gap that does not exceed 7% for the M-F instances, 5% for the last group of F-M instances, and 10% for the M-M instances. In particular, the results obtained on the M-F instances (Table 5) can be motivated as follows: the makespan of the virtual vessel is always attained at the mother vessel, therefore the delay of the DT containers can be reduced by, eventually, letting the cranes working on the feeder vessel wait. This is because the makespan of the feeder can increase without affecting the objective function. This phenomenon is especially evident in the first and fourth instances of the first group, and in the fourth instance of the last group in Table 5.

But the delay of the DT containers could be unavoidable. In fact, it is strictly related to their class and to the class-based stowage plan of both vessels, that is to the data set of the seed instances and to the random procedure implemented by DCTP-G, whose output could likely be an instance not enough suitable for the Direct Transshipment modality. Looking, for example, at the third instance of the first group in Table 5, we observe that the average delay of DT containers is relatively high, in spite of the remarkable growth of the makespan of the feeder vessel. As for the F-M instances, most of them seem to belong to the class of instances for which the Direct Transshipment is not a convenient approach. Actually, even for the last (end best) group of instances in Table 6, we can observe that the delay of the DT containers is unavoidable. This is very clear for the instance FM-10-10-20-20-2, where the makespan of both vessels is computed in an optimal way.

The results in Table 7, related to the bi-directional flow of DT containers between mother vessels, exhibit both the characteristics discussed before. The minimum value of AvgD is attained at the third instance, for which the makespan of vessel A, that was the minimum in the relaxed problem, grows so much to become the makespan of the virtual vessel in DCTP. In the second instance, instead, it is evident that the waiting time for the DT containers can not be reduced any further.

7 Conclusions

In this paper we have addressed the Direct Container Transshipment Problem (DCTP), that is the problem of scheduling the loading/discharging operations of two vessels sharing the berthing time windows, and assuming that some containers discharged from a vessel must be directly loaded on the other one, completely skipping the storage phase in the yard. The aim is to minimize a linear combination of the time needed to complete all the operations and the average waiting time for the directly transshipped containers. The DCTP integrates two operative decision processes: the scheduling of the quay cranes and the stowage of the container directly transshipped. For this problem we have described a mixed integer linear model and we have derived a Tabu Search heuristic algorithm. We have tested the heuristic algorithm on a set of randomly generated instances. The algorithm is able to find feasible solutions of good quality in almost all the considered instances within a short amount of computation time, despite the intrinsic hardness of the problem.

The DCTP generalizes the Quay Crane Scheduling Problem (QCSP). Actually, when no direct transshipment operation has to be performed, the DCTP separates into two non-standard QCSP, where for some export containers also the stowage position must be decided. Vice-versa, if the stowage plans of the two involved vessels are completely known, the resulting DCTP reduces to two independent QCSP, one for each vessel.

The direct transshipment of containers allows to reduce yard congestions and, at the same time, the storage costs. From this point of view, it seems certainly a profitable modality for the terminal management. As for the shipping line companies, the saving in the storage costs must be evaluated in connection with possible increasing of the berthing times. This is the focus of future developments.