1 Introduction

Maritime terminals play a strategic role within logistics networks. For this reason, a still increasing number of works have been recently proposed in the literature, aiming to optimize the flow of both import/export and transhipment containers and minimising the total logistics cost. A recent overview of relevant literature for these problems is provided in Stahlbock and Voss (2008).

In this paper, the focus is on the quay and ship activities; more precisely, the stowage planning problem is analysed, with the aim to minimize the overall berthing costs. This problem is denoted in literature master bay plan problem (MBPP). A detailed description of MBPP, together with its main constraints, is given in Ambrosino et al. (2004). MBPP is a NP-Hard problem (Avriel et al. 2000). Heuristic methods for MBPP are compared in Ambrosino et al. (2010).

Note that MBPP involves only the loading decisions at the first port, without taking into account possible loading operations in the successive ports of the ship route.

At least to the authors’ knowledge, few papers deal with the placement of containers into a containership on a multi-port journey. In this paper MBPP is extended to the multi-port master bay plan problem (MP-MBPP), where there is the need of determining a stowage plan for each port in the route of the ship, considering all different sets of containers that must be loaded for shipping to the successive ports. Since loading is a very difficult task and strongly impacts on the efficiency of the terminal operations (Imai et al. 2002; Rashidi and Tsang 2013), this work focuses on the optimization of the stowage plans at each port visited by the ship.

MBPP involves stowage plans at a single port and it is faced by the terminal manager, while MP-MBPP is a planning problem concerning the shipping line operator. Interested readers can find in Steenken et al. (2004) an explanation of how the stowage planning problem is split into a two-step process concerning, respectively, the shipping line operator and the terminal manager.

Imai et al. (2006) present a unified approach for taking into account the route planning problem from both the liner and the terminal manager point of view. Some MIP models for MP-MBPP are presented in Li et al. (2008) and Ambrosino et al. (2009). Li et al. (2008) present an 0/1 integer programming model aimed to determine the exact location of each container, in order to minimize the number of container shifting and maximise the stowage space utilization in real operative scenarios for different instances of 800 TEU and 18,000 tons containerships. The obtained solutions are verified by a simulation and visualization tool. No other details are reported on the test of the model. Ambrosino et al. (2009) proposed a MIP model for finding stowage plans at each port visited by the ship, while minimizing the total berthing time of the whole trip of the ship, the number of not loaded containers and the number of unproductive movements. For each stowage location is specified the kind of container assigned (i.e. its class of weight, its length 20′ or 40′ and its destination). The model is tested only with small instances.

Decomposition approaches are commonly used for facing MP-MBPP. For instance, Wilson and Roach (2000) and Wilson et al. (2001) propose a methodology for generating stowage plans for a containership on a multi-port journey that decomposes the decision process into two planning sub-processes: a strategic and a tactical one. The strategic objective function includes, among others, the minimization of: (1) the cargo space occupied by each destination; (2) the re-handles; (3) the cargo blocks occupied by containers. It is also considered the maximization of the number of cranes simultaneously in operation at each port. A decomposition of the stowage planning problem into two sub-problems is also proposed by Kang and Kim (2002); in the first phase the authors assign groups of 20′ and 40′ containers to holds of the ship, while in the second one they determine the loading sequence of containers in each hold. Heuristics methods are proposed with the aim to minimize the total handling time in each port on the route of the ship. They optimize the berthing time at each port by minimizing both overstows and the number of bays occupied by the containers with the same destination port. Further, Zhang et al. (2005) decompose the stowage planning problem for a containership that serves many ports into two sub-problems; their aim is to minimize re-handles and the number of bays occupied by the containers at each port.

Pacino et al. (2011) solve the multi-port stowage planning problem by a two phase approach, in which computationally efficient heuristics are able to solve quite large size practical instances.

Delgado et al. (2012) present a constraint programming approach for dealing with multi-port routes, focusing the attention on the loading problem at each port. They decompose the problem and present a model for stowing containers in each bay sections of the ship; the stowage concerns standard 20′ and 40′ containers, either reefer or not reefer. The objectives of the model are the minimization of overstows, the number of stacks of containers with different discharge ports and the number of used stacks.

Following the decomposition approach proposed by Wilson and Roach (2000), this paper presents two mixed integer programming (MIP) models for solving MP-MBPP at a strategic level. The proposed models can be considered an extension of that proposed in Ambrosino et al. (2009); they take into account the hatches and the irregular keels of a containership. In this way, all the available spaces of a containership can be considered for the stowage thus being able to maximize the number of loaded containers. Differently from Delgado et al. (2012), our model is related to the whole ship and, from an operative point of view, it allows the loading of re-handled containers in slots different from where they are unloaded.

The paper reports an extensive computational experimentation concerning some relaxations of the proposed models. It is worth noting that the proposed models have been tested with many instances with different levels of loading of the containerships. The results obtained prove the applicability of the models in real operations.

The remaining of the paper is organized as follows: in the next section the multi-port stowage planning problem is introduced in more details. The mathematical formulations for this NP-hard problem are given in Sect. 3, whereas the solution approaches, based on relaxations of the proposed models, are described in Sect. 4. Results of an extensive computational experimentation are reported in Sect. 5. Finally, some conclusions and an outline of future works are drawn in Sect. 6.

2 Problem description

MP-MBPP is to find the stowage plan for a containership assigned to a specific route by the owner line operator; the objective is to satisfy the service demand and to minimize the berthing time at each port. The route consists of a set of ports P = {1, …, P max }, where P max denotes the index of the last port visited in the voyage of the ship. Here, only linear routes are considered; note that this is not a limiting assumption as circular routes can be viewed as linear ones with several occurrences of the same ports.

For each port p ∈ P a set C pd of containers must be loaded for shipping to port d, ∀d ∈ P such that d > p. At each port p two sets of terminal operations are performed; first, the containers bound for p are unloaded, so freeing ship stowage slots, then the containers departing from p to successive destinations (in the following referred as the transportation demand at p) are loaded.

This paper introduces two simplifying assumptions, which do not actually affect the applicability of the proposed approaches. More precisely it is assumed that: (1) at the first port of the trip, i.e. p = 1, are considered only the loading operations; this implies that the stowage planning starts as soon as the unloading operations at the first port are completed; (2) at the last port of the trip, i.e., p = P max , are considered only the relevant unloading operations; this implies that the stowage planning ends as soon as the unloading operations at the last port are completed. Note that the ship may not be empty after unloading at the last port of its route.

The transportation demand at port p can be further partitioned into several sets, in accordance with the type of container t, class of weight g and destination d, d ∈ P. Here t ∈ {20′, 40′} and g ∈ {light, medium, heavy}.

The unloading and loading operations at each port p are performed by a set of quay cranes (QCs) working in parallel. As common practice, it is assumed that the subsets of bays served by each crane in all ports of the route are a priori defined and fixed. In general, the assignment of QCs to vessels and the scheduling of QC operations are closely related to the stowage plans (see e.g., Bierwirth and Meisel 2010) and they all impact on the berthing time. In this work, it is assumed that a given number of QCs is assigned to homogeneous portions of the ship. Note that this assumption reflects rules usually adopted to satisfy some operational and security constraints when unloading and loading operations are executed (i.e. weight balancing, spatial constraints, bays distance between cranes working on a vessel, etc.). Moreover, this assumption allows the minimization of the berthing time by balancing the work load of the quay cranes, as it will be described in the following.

MP-MBPP provides aggregate decisions for line planners, which concern the assignment of containers to groups of hold/deck slots, positioned under and above the hatches of the ship, respectively, in order to satisfy the transportation demand along the ship route. Structural and operative constraints have to be satisfied too. Each slot of the ship is identified by means of its exact position with respect to its bay, tier and row address (see Fig. 1). As shown in Fig. 1, each stack (set of slots identified by a fixed bay and row) can be used for stowing either 20′ or 40′ standard containers. Therefore, when defining stowage plans it is necessary to select the type associated to each stack. In addition, stability conditions relevant to horizontal and cross ship equilibrium must be imposed. Further details about structural and operative constraints can be found in (Ambrosino et al. 2004).

Fig. 1
figure 1

The structure of a ship with hatches

Full size image

As a consequence of the presence of hatches in the structure of the ship, in order to properly define stowage plans, it is natural to distinguish hatch hold from hatch deck slots. It is assumed that hatch slots, either on the deck or in the hold, can be assigned to a single destination. Even though an apparent limitation, this hypothesis can be considered a reasonable assumption for the line shipper planning level and, in addition, it corresponds to an operational practice quite often adopted in many Italian terminals. Moreover, many authors [i.e. Kang and Kim (2002), Delgado et al. (2012)] prefer to have containers with the same destination port in the same stacks or bays. Otherwise, there may be overstows which means non-productive movements (unloading and re-loading of containers in deck hatch slots are necessary for accessing hold slots below the same hatch). As an example, a situation in which re-handles are performed is depicted in Fig. 2. Note that re-handled containers are not necessarily re-loaded into the same deck slots. Of course, re-handles should be avoided as much as possible, as they increase both the berthing time and the handling costs.

Fig. 2
figure 2

Non-productive movements (re-handles) at port p

Full size image

When dealing with real ship planning problems there is the possibility of having irregular keels; in these cases particular stowage conditions must be satisfied. For instance, in the stowage plan reported in Fig. 3, a 20′ container must be located at the bottom of a stack of 40′ container for granting the stack stability.

Fig. 3
figure 3

Example of stowage of containers into irregular keel

Full size image

Several objectives can be considered for MP-MBPP. This multi-objective problem is modelled by introducing a scalar objective function including three components. The first component penalizes the unmet demand at each port of the route, that is, the number of containers that cannot be loaded due to either slot availability or weight and stability constraints. The second component of the objective function penalizes the number of re-handles, while the last component aims to balance the workload of the quay cranes available at ports. Since loads and unloads at each port are performed in parallel by a set of quay cranes, the total operation time at a port corresponds to the longest one among the cranes; therefore, the difference between the operation time of each pair of cranes (in the following referred as crane imbalance) at each port is penalised.

3 Mixed integer programming models for MP-MBPP

This section presents two MIP models for MP-MBPP, denoted M1 and M2, respectively. For the sake of clarity, the required notation is summarized in the following.

Sets

P :

set of ports (1 = first port, P max  = last port)

I :

set of bays of the ship (I = E ∪ O, E set of even bays and O set of odd bays)

J :

set of rows of the ship

K :

set of tiers of the ship

H :

set of hatches of the ship

H A /H P :

subset of aft/prow hatches

H R /H L :

subset of right/left hatches

I h :

subset of bays included in hatch h

R h :

subset of rows included in hatch h

Y p :

set of quay cranes serving the ship in parallel at port p

I pc :

subset of bays served by crane c at port p

H pc :

subset of hatches served by crane c at port p

G :

set of weight classes of the containers (1 = light, 2 = medium, 3 = heavy)

T :

set of types of containers (20′ and 40′)

Parameters

CH tij /CD tij :

number of hold/deck slots of type t available in bay i row j

CAPH h /CAPD h :

number of available slots (capacity) in the hold/deck of hatch h

CAPH ht /CAPD ht :

number of available slots of type t (capacity) in the hold/deck of hatch h

TEUH h /TEUD h :

capacity in TEU in the hold/deck of hatch h

N ptgd :

number of containers of type t, weight class g to be loaded at port p with destination port d

W g :

weight for a container of class g

Q 1 :

maximum cross equilibrium tolerance

Q 2 :

maximum horizontal equilibrium tolerance

PW f :

penalization weight of the objective function components, f = 1, …, 3

Variables

$$x\_h_{phtgd} \in {\mathbf{Z}}_{ + } ,x\_d_{phtgd} \in {\mathbf{Z}}_{ + } \quad \forall p \in P,h \in H,t \in T, \, g \in G,d \in P,d > p$$

Hatch hold/deck state variables; x_h phtgd (x_d phtgd ) is the number of containers of type t, weight class g with destination port d located in the hold (on the deck) below (above) hatch h after the completion of loading operations at port p;

$$l\_h_{phtgd} \in {\mathbf{Z}}_{ + } ,l\_d_{phtgd} \in {\mathbf{Z}}_{ + } \quad \forall p \in P,h \in H,t \in T,g \in G,d \in P,d > p$$

Hatch hold/deck loading variables; l_h phtgd (l_d phtgd ) is the number of containers of type t, weight class g with destination port d loaded in the hold (on the deck) below (above) hatch h at port p;

$$y\_h_{phd} \in \left\{ {0,1} \right\},y\_d_{phd} \in \left\{ {0,1} \right\}\quad \forall p \in P,h \in H,d \in P,d > p$$

Hatch assignment variables for hold/deck slots; y_h phd  = 1 (y_d phd  = 1) if at port p the slots in hold (on deck) below (above) hatch h are assigned to containers bound for d, y_h phd  = 0 (y_d phd  = 0) otherwise;

$$u\_h_{pij} \in \left\{ {0,1} \right\},u\_d_{pij} \in \left\{ {0,1} \right\}\quad \forall p \in P,i \in I, \, j \in J$$

Use of bay-row; u_h pij  = 1 (u_d pij  = 1) if at port p the stack of bay i and row j in the hold (deck) is used. Note that if i is even then 40′ containers can be loaded, otherwise 20′ ones can be loaded;

$$r_{phtgd} \in {\mathbf{Z}}_{ + } \quad \forall p \in P,h \in H,t \in T,g \in G,d \in P,d > p$$

Non-productive movement variables; r phtgd is the number of re-handles executed at port p for unloading and successively reloading, the containers bound for d > p over hatch h on the deck for unloading containers in the hold below h bound for p;

$$f_{ph} \in \left\{ {0,1} \right\}\quad \forall p \in P,h \in H$$

Need to free deck slots over hatch (non-productive movements); f ph  = 1 if the containers on the deck over hatch h must be removed at port p to unload other containers from the hold below h, f ph  = 0 otherwise;

$$v_{ptgd} \in {\mathbf{Z}}_{ + } \quad \forall p \in P,t \in T,g \in G,d \in P,d > p$$

Number of not served containers; v ptgd represents the unsatisfied transportation demand at port p, that is the number of containers of type t, weight class g with destination port d not loaded at port p;

$$\varDelta_{pce} \in \varvec{R} \quad \forall p, \forall c,e \in Y_{p} ,c \ne e$$

Absolute difference between the number of unloading and loading operations executed by cranes c and e at port p;

$$t_{pc} \in \varvec{R}\quad \forall p \in P,c \in Y_{p}$$

Total number of loading and unloading operations of crane c at port p;

$$\varDelta max \in \varvec{R}$$

Maximum difference of the number of handling operations between each pair of cranes over all the considered ports.

The objective function components previously described can be then expressed as:

  • \(U(v) = \sum\limits_{ptgd} {v_{ptgd} }\) number of unloaded containers (unsatisfied transportation demand);

  • \(NP(r) = \sum\limits_{phtgd} {r_{phtgd} }\) number of non-productive movements (re-handles).

  • \(MTV(\varDelta ) = \varDelta max\) maximum absolute variation between the number of operations performed by each pair of cranes at the ports (crane imbalance).

3.1 First model: model M1

The proposed formulation M1 for MP-MBPP is the following:

$$\hbox{min} \;PW_{1} \cdot U(v) + PW_{2} \cdot NP(r) + PW_{3} \cdot MTV(\varDelta )$$
(1)

subject to

$$\sum\limits_{h} {(l\_h_{phtgd} + l\_d_{phtgd} )} = N_{ptgd} + \sum\limits_{h} {r_{phtgd} } - v_{ptgd} \quad \forall p,t,g,d$$
(2)
$$x\_h_{phtgd} = x\_h_{p - 1htgd} + l\_h_{phtgd} \quad \forall p,h,t,g,d$$
(3)
$$x\_d_{phtgd} = x\_d_{p - 1htgd} - r_{phtgd} + l\_d_{phtgd} \quad \forall p,h,t,g,d$$
(4)
$$\sum\limits_{tgd} {l\_h_{phtgd} } \le CAPH_{h} \cdot \left( {1 - \sum\limits_{d > p} {y\_d_{p - 1hd} } } \right)\quad \forall 1 < p < P,h$$
(5)
$$\sum\limits_{d} {y\_h_{phd} } \le 1\quad \forall p,h$$
(6)
$$\sum\limits_{d} {y\_d_{phd} } \le 1\quad \forall p,h$$
(7)
$$\sum\limits_{g} {x\_h_{phtgd} } \le CAPH_{ht} \cdot y\_h_{phd} \quad \forall p,h,t,d$$
(8)
$$\sum\limits_{g} {x\_d_{phtgd} } \le CAPD_{ht} \cdot y\_d_{phd} \quad \forall p,h,t,d$$
(9)
$$y\_h_{phd} \ge y\_h_{p - 1,hd} \quad \forall p,h,d\left( {d > p} \right)$$
(10)
$$y\_d_{phd} \ge y\_d_{p - 1,hd} - f_{ph} \quad \forall p,h,d\left( {d > p} \right)$$
(11)
$$y\_h_{ph,p + 1} + y\_d_{phd} \le 1 + f_{p + 1,h} \quad \forall h,\forall p,d > p + 1$$
(12)
$$r_{phtgd} \le CAPD_{ht} \cdot f_{ph} \quad \forall p,h,t,g,d$$
(13)
$$r_{phtgd} \ge x\_d_{p - 1,htgd} - CAPD_{ht} \cdot (1 - f_{ph} )\quad \forall p,h,t,g,d$$
(14)
$$\sum\limits_{g} {x\_h_{ph20gd} } + 2 \cdot \sum\limits_{g} {x\_h_{ph40gd} } \le TEUH_{h} \cdot y\_h_{phd} \quad \forall p,h,d > p$$
(15)
$$\sum\limits_{g} {x\_d_{ph20gd} } + 2 \cdot \sum\limits_{g} {x\_d_{ph40gd} } \le TEUD_{h} \cdot y\_d_{phd} \quad \forall p,h,d > p$$
(16)
$$u\_d_{pij} + u\_d_{pi + 1j} = 1\quad \forall p,i \in E,j \in J$$
(17)
$$u\_d_{pij} + u\_d_{pi - 1j} = 1\quad \forall p,i \in E,j \in J$$
(18)
$$u\_h_{pij} + u\_h_{pi + 1j} = 1\quad \forall p,i \in E,j \in J$$
(19)
$$u\_h_{pij} + u\_h_{pi - 1j} = 1\quad \forall p,i \in E,j \in J$$
(20)
$$\sum\limits_{gd} {x\_h_{phtgd} } \le \sum\limits_{{i \in I_{h} }} {\sum\limits_{{j \in R_{h} }} {CH_{tij} \cdot u\_h_{pij} } } \quad \forall p,h,t$$
(21)
$$\sum\limits_{gd} {x\_d_{phtgd} } \le \sum\limits_{{i \in I_{h} }} {\sum\limits_{{j \in R_{h} }} {CD_{tij} \cdot u\_d_{pij} } } \quad \forall p,h,t$$
(22)
$$|\sum\limits_{{h \in H_{L} ,tgd}} {W_{g} (x\_h_{phtgd} + x\_d_{phtgd} )}-\sum\limits_{{h \in H_{R} ,tgd}} {W_{g} (x\_h_{phtgd} + x\_d_{phtgd} )} | \le Q_{1} \quad \forall p \in P$$
(23)
$$|\sum\limits_{{h \in H_{A} ,tgd}} {W_{g} (x\_h_{phtgd} + x\_d_{phtgd} )} - \sum\limits_{{h \in H_{P} ,tgd}} {W_{g} (x\_h_{phtgd} + x\_d_{phtgd} )} | \le Q_{2} \quad \forall p \in P$$
(24)
$$t_{pc} = \sum\limits_{{h \in H_{pc} }} {\sum\limits_{tgd} {(l\_h_{phtgd} + l\_d_{phtgd} + r_{phtgd} ) + } } \sum\limits_{{h \in H_{pc} }} {\sum\limits_{tgd} {(x\_h_{p - 1,htgp} + x\_d_{p - 1,htgp} )\quad } } \forall p,c \in Y_{c}$$
(25)
$$|t_{pc} - t_{pe} | \le \varDelta_{pce} \quad \forall p \in P,\forall c,e \in Y_{p} ,c \ne e$$
(26)
$$\varDelta max \ge \varDelta_{pce} \quad \forall p \in P,\forall c,e \in Y_{p} ,c \ne e$$
(27)
$$\sum\limits_{gd} {x\_h_{ph20gd} } \ge \sum\limits_{{i \in I_{h} \cap E}} {CH_{20ij} \cdot u\_h_{pij} } \quad \forall p,h:\exists CH_{20ij} > 0,i \in I_{h} \cap E$$
(28)
$$\begin{array}{*{20}c} {x\_h_{phtgd} \in {\mathbf{Z}}_{ + } ,x\_d_{phtgd} \in {\mathbf{Z}}_{ + } } \hfill & {\forall p, \, h, \, t, \, g, \, d, \, d > p} \hfill \\ {l\_h_{phtgd} \in {\mathbf{R}}_{ + } ,l\_d_{phtgd} \in {\mathbf{R}}_{ + } } \hfill & {\forall p, \, h, \, t, \, g, \, d, \, d > p} \hfill \\ {r_{phtgd} \in {\mathbf{R}}_{ + } } \hfill & {\forall p, \, h, \, t, \, g, \, d, \, d > p} \hfill \\ {y\_h_{phd} \in \left\{ {0,1} \right\},y\_d_{phd} \in \left\{ {0,1} \right\}} \hfill & {\forall p, \, h, \, d, \, d > p} \hfill \\ {f_{ph} \in \left\{ {0,1} \right\}} \hfill & {\forall p,h} \hfill \\ {v_{pgd} \in {\mathbf{R}}_{ + } } \hfill & {\forall p,g,d,d > p} \hfill \\ {u\_h_{pij} \in \left\{ {0,1} \right\},u\_d_{pij} \in \left\{ {0,1} \right\}} \hfill & {\forall p,i, \, j} \hfill \\ {t_{pc} \in {\mathbf{R}}_{ + } } \hfill & {\forall p,c \in Y_{p} } \hfill \\ {\varDelta_{pce} \in {\mathbf{R}}_{ + } } \hfill & {\forall p,\forall c,e \in Y_{p} ,c \ne e} \hfill \\ {\varDelta \hbox{max} \in {\mathbf{R}}_{ + } } \hfill & {} \hfill \\ \end{array}$$
(29)

Equation (1) is the objective function. Equations (2) are the demand constraints, defining, for each port and subset of containers, the number of loaded and unloaded containers. Note that, at each port, the number of containers to be loaded also includes the unloaded containers due to re-handles. Constraints (3) and (4) represent the state continuity conditions; such constraints force the number of homogeneous containers, located into a hatch at port p, to be updated, taking into account both the containers already located there at port p-1 and those loaded at p. Note that containers are considered homogeneous if they have the same value of t, g and d (i.e. type, class of weight and destination). Note that, for the deck slots in (4), the containers possibly removed due to re-handles are considered too. Constraints (5) are related to the hold accessibility; in particular, such constraints enable stowing containers in the hold slots of hatch h (according to the destination assigned to the hatch), only if the deck above h is free.

Constraints (6) and (7) impose that the hold and the deck slots corresponding to a hatch are assigned only to one destination; constraints (8) and (9) link the variables y_h phd and y_d phd , respectively, to hold and deck state variables. These latter capacity constraints, combined with (6) and (7), force at each port p some x_h phtgd and x_d phtgd variables to be equal to zero.

Constraints (10) impose that the hold slots of hatch h assigned to d remain assigned to such destination until port d is reached. Differently, constraints (11) allow freeing the slots on the deck before the assigned destination by executing re-handles.

Constraints (12) fix f ph  = 1 if the containers on the deck over hatch h must be removed at port p to unload other containers from the hold below h. Constraints (13) guarantee that the containers are removed from the deck slots in hatch h only if hatch h must be freed at p (i.e., if f ph  = 1), and in this case, constraints (14) impose that all the containers located in the deck slots are re-handled.

Constraints (15) and (16) are the TEU capacity conditions and impose that the sum of the TEUs located in a hold/deck hatch slots for the assigned destination must not exceed the maximum available TEU capacity for that hold/deck hatch. In particular, note that TEUH h  = CAPH 20h . Constraints (17)–(20) are related to the usage of the slots of each stack in a bay. More precisely, a stack in an even bay (i) can be used for 40′ containers, otherwise the corresponding two stacks in the odd bays (i − 1, i + 1) can be used for 20′ containers. These usage decisions are separated for the hold and the deck stacks. Note that, if a stack in an even bay and the two stacks in the corresponding odd bays are not used, the assignment imposed by (17)–(20) is not relevant. Constraints (21) and (22) are the capacity constraints, taking into account the bay usage decisions fixed by constraints (17)–(20). Since 40′ containers cannot be stored in odd bays, C 20ij is equal to 0 for index i corresponding to even bays.

Constraints (23) and (24) represent the stability conditions, which are related to the horizontal and cross equilibrium. Constraints (25)–(27) refer to the crane utilization. In particular, constraints (25) define variable t pc ; constraints (26) define the absolute difference between the number of unloading and loading operations at port p executed by cranes c and e; constraints (27) give the maximum difference of loading and unloading operations between any pair of cranes over all the considered ports.

Constraints (28) take into account the presence of an irregular keel, since they force the loading of the required number of 20′ containers to avoid that 40′ containers are positioned over empty 20′ slots (see Fig. 3).

Finally, (29) define the decision variables.

3.2 The second model: model M2

This section briefly describes model M2. It is a different formulation for MP-MBPP, derived from M1 considering a TEU relaxation. In particular, in this new simplified formulation the transportation demand, assignments, loading operations and re-handles are expressed in terms of TEUs, instead of number of containers. As a first consequence, in M2 variables u_h pij and u_d pij are not necessary. Further, all variables in M1 related to the number of containers of a given type are replaced in M2 by similar variables, which specify the number of TEUs. The new variables are listed in the following.

Variables different from model M1

$$x\_h_{phgd} \in {\mathbf{Z}}_{ + } ,x\_d_{phgd} \in {\mathbf{Z}}_{ + } \quad \forall p \in P,h \in H,g \in G,d \in P,d > p$$

Hatch hold/deck state variables giving the number of TEUs of weight class g with destination port d located in hold and on deck corresponding to hatch h after the completion of loading operations at port p;

$$l\_h_{phgd} \in {\mathbf{Z}}_{ + } ,l\_d_{phgd} \in {\mathbf{Z}}_{ + } \quad \forall p \in P,h \in H,g \in G,d \in P,d > p$$

Hatch loading variables giving the number of TEUs of weight class g with destination port d loaded in hold and on deck corresponding to hatch h at port p;

$$r_{phgd} \in {\mathbf{Z}}_{ + } \quad \forall p \in P,h \in H,g \in G,d \in P,d > p$$

Non-productive movement variables giving the number of TEUs re-handled at port p;

$$v_{pgd} \in {\mathbf{Z}}_{ + } \quad \forall p \in P,t \in T,g \in G,d \in P,d > p$$

Number of not served TEUs demand at port p;

Variables as in model M1

$$y\_h_{phd} \in \left\{ {0, 1} \right\},y\_d_{phd} \in \left\{ {0, 1} \right\}\quad \forall p \in P,h \in H,d \in P,d > p$$
$$f_{ph} \in \left\{ {0, 1} \right\}\quad \forall p \in P,h \in H$$
$$\varDelta_{pce} \in {\text{R}}\quad \forall p,\forall c,e \in Y_{p} ,c \ne e$$
$$t_{pc} \in {\text{R}}\quad \forall p \in P,c \in Y_{p}$$
$$\varDelta max \in {\text{R}}$$

Note that, in M2 Δ pce , t pc and Δmax refer to numbers of operations in term of TEUs instead of containers. As a consequence, in M2 two out of three objective function components of M1 have to be redefined as follows:

  • \(U(v) = \sum\limits_{pgd} {v_{pgd} }\) number of not served TEUs;

  • \(NP(r) = \sum\limits_{phgd} {r_{phgd} }\) number of re-handles.

Constraints (6), (7), (10) (11) (12), (26) and (27) from M1 are used in M2 together with the following constraints on demand satisfaction (30), state continuity conditions (31) and (32), hold accessibility (33), capacity (34) and (35), re-handling (36) and (37), ship stability (38) and (39), and number of quay crane operations (40), that are redefined in term of TEU instead of containers.

$$\sum\limits_{h} {(l\_h_{phgd} + l\_d_{phgd} )} = N_{pgd} + \sum\limits_{h} {r_{phgd} } - v_{pgd} \quad \forall p,g,d$$
(30)
$$x\_h_{phgd} = x\_h_{p - 1hgd} + l\_h_{phgd} \quad \forall p,h,g,d$$
(31)
$$x\_d_{phgd} = x\_d_{p - 1hgd} - r_{phgd} + l\_d_{phgd} \quad \forall p,h,g,d$$
(32)
$$\sum\limits_{gd} {l\_h_{phgd} } \le TEUH_{h} \cdot \left( {1 - \sum\limits_{d > p} {y\_d_{p - 1hd} } } \right)\quad \forall 1 < p < P,h$$
(33)
$$\sum\limits_{g} {x\_h_{phgd} } \le TEUH_{h} \cdot y\_h_{phd} \quad \forall p,h,d > p$$
(34)
$$\sum\limits_{g} {x\_d_{phgd} } \le TEUD_{h} \cdot y\_d_{phd} \quad \forall p,h,d > p$$
(35)
$$r_{phgd} \le TEUD_{h} \cdot f_{ph} \quad \forall p,h,g,d$$
(36)
$$r_{phgd} \ge x\_d_{p - 1,hgd} - TEUD_{h} \cdot (1 - f_{ph} )\quad \forall p,h,g,d$$
(37)
$$|\sum\limits_{{h \in H_{L} ,gd}} {W_{g} (x\_h_{phgd} + x\_d_{phgd} )} - \sum\limits_{{h \in H_{R} ,gd}} {W_{g} (x\_h_{phgd} + x\_d_{phgd} )} | \le Q_{1} \quad \forall p \in P$$
(38)
$$|\sum\limits_{{h \in H_{A} ,gd}} {W_{g} (x\_h_{phgd} + x\_d_{phgd} )} - \sum\limits_{{h \in H_{P} ,gd}} {W_{g} (x\_h_{phgd} + x\_d_{phgd} )} | \le Q_{2} \quad \forall p \in P$$
(39)
$$t_{pc} = \sum\limits_{{h \in H_{pc} }} {\sum\limits_{gd} {(l\_h_{phgd} + l\_d_{phgd} + r_{phgd} ) + } } \sum\limits_{{h \in H_{pc} }} {\sum\limits_{gd} {(x\_h_{p - 1,hgp} + x\_d_{p - 1,hgp} )} \quad } \forall p,c \in Y_{c}$$
(40)

Note that the objective function of M2 is not directly comparable to the one of M1, since M2 considers TEUs, while M1 focuses on the number of containers. However, formulation M2 has been developed in order to simplify the resolution process (as described in the following section).

4 Solution approaches derived from M1 and M2

Since model M1 can be solved up to optimality only for small instances, two different heuristic approaches denoted, respectively, HM1 and HM2M1 are proposed. These approaches are based on the solution of relaxations of models M1 and M2. In both cases, the idea is to handle MP-MBPP in two steps, decomposing the original complex planning problem into two simpler ones, which are sequentially solved.

Heuristic HM1 is based on model M1. In the first step, a continuous relaxation of M1 is solved; all general integer variables are relaxed to assume real values, whereas the binary variables, in particular the ones determining the assignment of destinations to hatch slots and the usage of the bays, remain constrained to be 0/1. In the second step, model M1 is then solved by fixing the binary variables to the optimal values of its relaxation, obtained in the first step. Note that the solution obtained in the second step is a feasible solution for MP-MBPP. Heuristic HM1 is summarized in Fig. 4a.

Fig. 4
figure 4

a Steps of heuristic HM1, b Steps of heuristic HM2M1

Full size image

As it will be shown in more details in the next section, the computational tests performed with heuristic HM1 provide appreciable results. However, the first step of HM1 may require a high computational effort. Thus, heuristic HM2M1, based on both models M1 and M2 is devised. In the first step of HM2M1 all general integer variables of model M2 are relaxed and the resulting model is solved (i.e. with only continuous and binary variables). In the second step, as in HM1, model M1 is solved by fixing binary variables to the optimal values obtained in the first step. Heuristic HM2M1 is summarized in Fig. 4b.

As already said in the previous section, solutions of models M1 and M2 cannot be compared. As a matter of facts, model M2 is only used in the first step of solution approach HM2M1 to determine suitable values for the y_h phd and y_d phd variables (which are in common with M1) and not to find a feasible solution for MP-MBPP.

5 Experimental results

This section reports the main results obtained through an extensive computational. These tests were performed on both real size instances and randomly generated ones of MP-MBPP. More precisely, two sets of 18 instances were defined considering two containerships:

  • the “European Senator” (ES), that is a medium sized ship client of the terminal SECH, located in Genoa, Italy; ES has a capacity of 2,028 TEUs, including 17 odd bays, 10 rows and 6 tiers in the hold and 21 odd bays, 12 rows and 5 tiers in the upper deck, 33 hatches;

  • a fictitious “Large Ship” (LS), having capacity of 5,280 TEUs, including 40 odd bays, 12 rows and 6 tiers in the hold and 40 odd bays, 12 rows and 5 tiers in the upper deck, 60 hatches.

Just to give an idea of the different dimension of the containerships under investigation, the reader can refer to the sketches in Fig. 5.

Fig. 5
figure 5

A comparison among ships ES and LS

Full size image

Each instance has a route of 7 ports, in which loading operations are executed at ports 1–5, starting with the ship empty at port 1, whilst unloading operations are executed at ports 2–7. At each port either 2 or 4 cranes are used for ES and LS, respectively.

The tested instances reflect the real cases occurring at the Terminal SECH in the port of Genoa (Italy). The main characteristics of instances, related both to the ES and the LS ship, are detailed in Table 1. In particular, instances are partitioned into three subsets, corresponding, respectively, to low, medium and high load level (instances 1–6, 7–12 and 13–18). Each subset considers two different percentages of 20′ containers: 50 and 70 %. An equal distribution of containers (33 %) for the three classes of weight is considered.

Table 1 The main characteristics of the tested instances for ES and LS
Full size table

The occupancy level (Occupancy), that is the average percentage of loading with respect to the ship capacity, is on average 50, 70 and 85 %, respectively for low, medium and high load level instances. The average transportation demand (Avg TEU) to load at each port is on average 1,000, 1,400 and 1,750 for ES and 2,600, 3,700 and 4,500 for LS, respectively for low, medium and high level load instances.

Models M1 and M2 were implemented in Ilog OplStudio 5.2, with MIP solver Cplex 11.0.1, and executed on a 2.4 GHz Intel Core 2 Duo E6600 computer with 4 GB RAM. Tests on model M1 were performed by setting a CPU time limit bound of 1,800 s, for ES instances, and 3,600 s for LS ones. Model M1 requires 30,829 variables (including 7,104 binaries and 11,088 integers) and 36,096 constraints for ES instances; 56,732 variables (including 13,680 binaries and 20,160 integers) and 66,071 constraints are required for LS instances.

The MIP solver was unable to solve model M1 for any instance of the large ship (LS) within the chosen CPU time limit, whereas, as showed in Table 2, some instances of the medium ship (ES) were solved up to optimality within 1,800 s. Column Obj of Table 2 reports the objective function value (note that “no” denotes no solution found in the available CPU time), while the last three columns report the components of (1), i.e., the number of unloaded containers (unsatisfied transportation demand), the re-handled and the imbalance of cranes. The decision makers (shipping line operators) usually consider the minimization of the unsatisfied transportation demand the main purpose of the stowage planning, since they aim to serve the demand as much as possible. Therefore, they do not accept to compensate a worsening in this first objective component with any improvement in the other two objective components. A similar argument hold between the number of re-handles and the crane imbalance: in fact, both these objective components affect the berthing time, but re-handles usually have a greater negative impact on the handling operations than the crane workload has. For these reasons, the multi-objective problem was faced by a lexicographic approach, giving a higher weight to the first objective component, then penalising unproductive movements. In particular, the weights of the objective function were fixed to PW1 = 100, PW2 = 10, PW3 = 1, respectively.

Table 2 Computational results of ES instances obtained by solving model M1
Full size table

Finally, it is important to note that in all instances the lower bound determined by the MIP solver for model M1 is always equal to zero.

Tables 3 and 4 show the results for ES and LS, respectively, obtained by HM1. Readers can observe that, within the given CPU time limit, quite good results were obtained for ES instances, whereas the results for LS ones are not so good. In particular, Table 4 shows that many containers are not served in those instances having high ship load (13–18) when a 1,800 s is imposed as CPU time limit; more precisely, the number of not served containers ranges from 113 (instance 17) to 204 (instance 15).

Table 3 Computational results of ES instances obtained by heuristic HM1
Full size table
Table 4 Computational results of LS instances obtained by heuristic HM1
Full size table

Furthermore, in instances 10 and 13–18, the relaxed version of model M1, used in step 1, cannot be solved up to optimality within 1,800 s and it is needed a large number of re-handles (164 on the average). For this reason, the last seven rows of Table 4, corresponding to the most difficult LS instances, report the results obtained by extending the CPU time limit to 3,600 s. Note that in this way an acceptable solution was found for four more instances (10, 13, 15 and 18).

Tables 5 and 6 show the results for ES and LS, respectively, obtained by HM2M1. Observing such tables, HM2M1 is very fast in both phases; in fact, final solutions were obtained on the average in 162 s for ES instances and in 393 s for LS ones. In addition, results obtained by HM2M1 appear outstanding in terms of objective function (1). In particular, note that values in PF-M1 obj column are always very close to zero.

Table 5 Computational results of ES instances obtained by heuristic HM2M1
Full size table
Table 6 Computational results of LS instances obtained by heuristic HM2M1
Full size table

In particular, it is worth observing that: (1) such results clearly dominate the ones obtained by HM1; (2) the absolute gaps from the lower bound of M1, which is zero in all instances, are very small and correspond to the values given in column PF-M1 obj of Tables 5 and 6. Note that, apart from instance 6 (Table 5), for which 3 re-handles are required, always all handling operations are performed without any re-handles and having at most 2 operations of the crane imbalance.

In order to compare better the performances of the proposed heuristics, Table 7 summarizes the obtained results. In particular, column CPU time saving shows the percentage of CPU time savings when applying HM2M1 versus HM1; columns Deviations report the values of the differences between the unloaded containers, the re-handles and the crane imbalance obtained by HM1 and HM2M1 (i.e., deviation = HM1 value − HM2M1 value); in particular, the positive numbers denote that HM2M1 outperforms HM1. From Table 7 it can also be observed that HM2M1 is less computational time consuming than HM1. Moreover, HM2M1 can allocate all the demand for both sets of instances without re-handles, apart from instance 6 of ES, and can operate the ships with a negligible workload imbalance of the cranes.

Table 7 Performance’s comparison of the proposed solution approaches
Full size table

Finally, HM2M1 obtains the optimal solution in 5 over 7 instances, corresponding to instances 1–4 and 7, that were solved up to optimality by M1 (see Table 2).

To give an idea of how the proposed approaches can be really applied as a supporting tool for the liner shipper, Fig. 6 reports an example of a graphical visualization of a feasible solution of MP-MBPP obtained by the presented methods. This graphic tool can visualize how containers are assigned to the slots of the hold and the deck and how many containers of each type (i.e. weight, size and destination) are stowed in a single portion of the ship for each port of the ship route.

Fig. 6
figure 6

Visualization of a feasible stowage plan

Full size image

6 Conclusions

The MP-MBPP analysed in this paper is a complex planning problem whose solution can support line operators in defining aggregate stowage plans in order to satisfy the customer transportation demand at the ports of a ship route. The MP-MBPP takes into account the available ship slots and the operational constraints regarding the slot usage as well as the ship stability.

An exact MIP formulation and a relaxed one, based on TEU capacity constraints, have been proposed. Moreover, two solution methods, able to solve the problem using a two-step decomposition approach, have also been developed.

The proposed heuristics have been tested on both real life instances and fictitious ones. The obtained results show that the second method, HM2M1, is able to find nearly optimal stowage plans for a 5,600 TEU containership on a 7 port route in a quite reduced computation time also when realistic load capacity requirements have been considered.

Future extensions of this research are to improve the proposed approach for dealing with larger instances and to develop a rolling horizon procedure in order to solve the planning problems including circular routes.