Literature Survey on the Container Stowage
Planning Problem

inst1]Jaike van Twiller

[inst1]organization=IT University of Copenhagen,
addressline=Rued Langgaards Vej 7,

inst2]Agnieszka Sivertsen
inst3]Dario Pacinocor1

inst1]Rune Møller Jensen

[inst2]organization=Roskilde University,
addressline=Universitetsvej 1,

[inst3]organization=Technical University of Denmark,
addressline=Bygningstorvet 116B,
city=Kgs. Lyngby,

Container shipping drives the global economy and is an eco-friendly mode of transportation. A key objective is to maximize the utilization of vessels, which is challenging due to the NP-hardness of stowage planning. This article surveys the literature on the Container Stowage Planning Problem (CSPP). We introduce a classification scheme to analyze single-port and multi-port CSPPs, as well as the hierarchical decomposition of CSPPs into the master and slot planning problem. Our survey shows that the area has a relatively small number of publications and that it is hard to evaluate the industrial applicability of many of the proposed solution methods due to the oversimplification of problem formulations. To address this issue, we propose a research agenda with directions for future work, including establishing a representative problem definition and providing new benchmark instances where needed.

* Literature review and classification scheme for the Container Stowage Planning Problem

* Identification of four significant groups of research: single-port, multi-port, master planning, and slot planning

* Comparison of problem formulations and solution approaches

* Description of minimal representative problem definition

* Publication of benchmarks instances

* Research agenda and discussion on the state of the art

OR in maritime industry Literature survey Container Stowage Planning Benchmarks

§ INTRODUCTION

§ THE CONTAINER STOWAGE PLANNING PROBLEM

§ CLASSIFICATION SCHEME

§ RESEARCH AGENDA

§ CONCLUSION

This paper provides a review of the literature that studies the Container Stowage Planning Problem. The studies are summarized according to a classification scheme that outlines the fundamental characteristics of the problem and the applied solution approaches. As there is a lack of a common understanding of the problem characteristics, this paper provided a description of a representative problem definition based on several years of academic and industrial collaborations. In light of this definition, a research agenda is proposed for each of the major branches of research in the Container Stowage Planning Problem (single-port planning, multi-port planning, master planning, and slot planning). Moreover, this paper identifies, and in one case, provides publicly available benchmark sets in the hope that future research will make use of them as a reference point and a way to compare results. Where possible, these benchmarks have been used to compare recent research results, and provide some computational comparison. It is our hope that this survey will help improve the field and acts as inspiration for future developments.

§ ACKNOWLEDGEMENTS

This work is partially funded by the Danish Maritime Fund (grant nr. 2021-069) and the Innovation Fund Denmark (grant no. 1044-00145A).

§ CLASSIFICATION TABLES

§ COLLECTED RESULT TABLES

§ MASTER PLANNING FORMULATIONS

The master planning problem aims to allocate cargo to subsections of bays. Those are often called locations <cit.> or blocks <cit.>. A block can either be a logical grouping of containers or be defined by the position of the hatch covers. The assignment of containers to blocks must ensure that the vessel is seaworthy while minimizing the handling time of the vessel. This appendix briefly presents the master planning formulations used for the computational comparison of Section <ref>. We refer the reader to the original publications for a more in-depth description. Tables <ref> and <ref> show the sets and parameters shared between the <cit.> and <cit.> formulations.

$B$    The set of bays

$BL$     The set of blocks

$BL_b$     The set of blocks in bay $b\in B$

$BL^O$     The set of blocks over deck

$BL^U_l$     The set of blocks below deck under block $l\in L^O$

$Bin$     The set of adjacent bays $(b_1,b_2) \in B\times B$

$T$     The set of container types

$T^{\{20,40,R\}}$     The set of 20-, 40-foot and Reefer container types

$P$     The set of ports

$TR$     The set of transports (port pairs $(o,d) \in P\times P,o<p$)

$TR^{ON}_p$     The set of transports $(o,d) \in TR$ where $o<p$ and $d>p$

$TR^{A}_p$     The set of active transports at port $p\in P$ where $(o,d) \in TR$ where $o=p$ or $d=p$

$TR^{OV}_p$     The set of overstowing transports at port $p\in P$ where $(o,d) \in TR$ where $o<p$ and $d>p$

Common Sets

$K^{\{20,40,R\}}_l$     The 20-,40-foot, and Reefer capacity of block $l\in L$

$TEU^\tau$     The Twenty-Foot Equivalent units of container type $\tau \in T$

$W_\tau$     The weight of container type $\tau \in T$

$L_\tau$     The length of container type $\tau \in T$

$LD^{\tau}_t$     The number of container of type $\tau \in T$ to be loaded for transport $t\in TR$

$R^\tau_{p,l}$     The number of containers of type $\tau \in T$, already on board the vessel with destination $p\in P$.

$W^K_b$     The lightship weight at bay $b\in B$

$W^{\max}_l$     The maximum weight limit of block $l\in L$

$D_p$     The total displacement of the vessel leaving port $p\in P$

$CG^{\alpha}_l$     The centre of gravity components $\alpha \in {L=LCG, V=VCG, T=TCG}$ of block $l \in BL$

$\overline{CG}^{\alpha}_b$     The centre of gravity components $\alpha \in {L=LCG, V=VCG, T=TCG}$ of bay $b \in B$

$LCG^{\{Min,Max\}}$     The limits for the vessel's longitudinal centre of gravity

$VCG^{\{ax\}}$     The maximum vertical centre of gravity of the the vessel

$TCG^{\{Min,Max\}}$     The limits for the vessel's transversal centre of gravity

$Shear^{\{Min,Max\}}_b~\quad~\quad$     The shear limits at bay $b\in B$

Common Paremeters

§.§ <cit.> formulation

The formulation is based on a main set of decision variables indicating the number of containers of a specific type to be stowed on a block during a transport leg. Other indicator variables are used for the calculation of the objective value. A description of the variables follows.

$x^\tau_{tl}~\in~\mathbb{Z}^+~\quad $     The number of containers of type $\tau \in T$ stowed in block $l\in L$ during transport $t \in TR$.

$\delta_{pl}~\in~\mathbb{B}~\quad $     Stowage indicator equal to 1 if any load or discharge containers are present in block $l \in L$ at port $p\in P$.

$y^O_{pl}~\in~\mathbb{R}^+$     The number of hatch-overstow containers in block $l\in L$ at port $p\in P$

$y^T_p~\in~\mathbb{R}^+$     The long-crane (or makespan lower bound) at port $p\in P$.

Following is the mathematical formulation and its description.

\begin{align}
& \text{\bf min} \sum_{p\in P} \left(\mathcal{C}^Ty^T_p + \sum_{l\in L} \mathcal{C}^Oy^O_pl \right) \label{pacino:obj}\\
& \text{\bf s.t.}\nonumber \\
& \sum_{l\in L} x^\tau_{tl} = LD^\tau_t \quad \forall \tau \in T, t \in TR \label{pacino:loadall}\\
& x^\tau_{(1,p)l} = R^\tau_p \quad \forall \tau \in T, p\in P \label{pacino:release}\\
& \sum_{t \in TR^{ON}_p}\sum_{\tau \in T} TEU^\tau x^\tau_{tl} \leq K^{20}_l \quad \forall p\in P, l\in L\label{pacino:capTEU}\\
& \sum_{t \in TR^{ON}_p}\sum_{\tau \in T^\alpha} x^\tau_{tl} \leq K^{\alpha}_l \quad \forall p\in P, l\in L, \alpha\in \{20,40,R\}\label{pacino:cap}\\
&\sum_{t \in TR^{ON}_p}W_\tau x^\tau_{tl} \leq W^{\max}_l \quad \forall p\in P, l\in L \label{pacino:weight}\\
&\sum_{b\in B}W^K_b\overline{CG}^L_b +\!\! \sum_{t \in TR^{ON}_p}\sum_{l\in L}CG^L_lW_\tau x^\tau_{tl} \geq LCG^{Min}D_p \quad \forall p\in P\label{pacino:minLCG}\\
&\sum_{b\in B}W^K_b\overline{CG}^L_b +\!\! \sum_{t \in TR^{ON}_p}\sum_{l\in L}CG^L_lW_\tau x^\tau_{tl} \leq LCG^{Max}D_p \quad \forall p\in P\label{pacino:maxLCG}\\
&\sum_{b\in B}W^K_b\overline{CG}^T_b +\!\! \sum_{t \in TR^{ON}_p}\sum_{l\in L}CG^T_lW_\tau x^\tau_{tl} \geq TCG^{Min}D_p \quad \forall p\in P\label{pacino:minTCG}\\
&\sum_{b\in B}W^K_b\overline{CG}^T_b +\!\! \sum_{t \in TR^{ON}_p}\sum_{l\in L}CG^T_lW_\tau x^\tau_{tl} \leq TCG^{Max}D_p \quad \forall p\in P\label{pacino:maxTCG}\\
&\sum_{b\in B}W^K_b\overline{CG}^V_b +\!\! \sum_{t \in TR^{ON}_p}\sum_{l\in L}CG^V_lW_\tau x^\tau_{tl} \leq VCG^{Max}D_p \quad \forall p\in P\label{pacino:maxVCG}\\
& \sum_{b'=1}^b\left( W^K_{b'} +\!\! \sum_{l\in BL_{b'}}\sum_{\tau\in T}\sum_{t \in TR^{ON}_p}\!\!W_\tau x^\tau_{tl} \right)\geq Shear^{Min}_b \quad \forall p \in P, b \in B\label{pacino:shearMin}\\
& \sum_{b'=1}^b\left( W^K_{b'} +\!\! \sum_{l\in BL_{b'}}\sum_{\tau\in T}\sum_{t \in TR^{ON}_p}\!\!W_\tau x^\tau_{tl} \right)\leq Shear^{Max}_b \quad \forall p \in P, b \in B\label{pacino:shearMax}\\
&\sum_{\tau \in T}\sum_{t\in TR^A_p}\sum_{l' \in BL^U_l}x^\tau_{tl'} M\delta_{pl} \quad \forall p\in P, l \in BL^O \label{pacino:delta}\\
& \sum_{\tau \in T}\sum_{t\in TR^{OV}_p}x^\tau_{tl} - M(1-\delta_{pl})\leq y^O_p \quad \forall p\in P, l \in BL^O\label{pacino:hatch}\\
&\sum_{b \in N}\sum_{\tau \in T}\sum_{t \in TR^{ON}_p}\sum_{l\in B} x^\tau_{tl} \leq y^T_p\quad \forall p\in P, N \in Bin \label{pacino:makespan}
\end{align}

The formulation minimizes the makespan and the hatch overstowage at each port (<ref>). Constraint (<ref>) ensures that all cargo must be stowed on the vessel, while constraint (<ref>) enforces that cargo already on board does not change position. The total block capacity, the type-specific block capacity, and the block weight capacity are constrained by (<ref>), (<ref>), (<ref>), respectively. To ensure vessel stability, the longitudinal, transversal, and vertical centers of gravity are constrained within the given limits by constraints (<ref>) - (<ref>).Constraints (<ref>) and (<ref>) impose minimum and maximum levels for the shear forces that act on the vessel.

Using an indicator variable, constraint (<ref>) identifies, for each port, blocks below deck that require container moves. Should those container moves be blocked by containers on-deck, they will be captured in constraint (<ref>) as overstowing. Finally, the bay pair with the maximum number of movements at each port is identified with constraint (<ref>), representing the makespan.

§.§ <cit.> formulation

The model is based on a network-flow formulation. For a detailed description of the network structure, we refer the reader to the original publication  <cit.>. Following is an extension of the common sets and parameters needed for this formulation.

$N$     The set of all nodes

$P$     The set of ports

$\mathcal{A}$     The set of all arcs

$\mathcal{A}^-_i, \mathcal{A}^+_i$     The set of outgoing and incoming arcs of node $i\in N$

$OD$     The set of transports (origin/destination port pairs) $(o,d) \in P \times P$

$OD^{ON}$     The set of transports $t=(o,d) \in OD$ for which $o\leq p$ and $d>p$

$OD^{A}$     The set of transports $t=(o,d) \in OD$ for which $o=p$ or $d=p$

$A^{TR}_{t}$     The set of all arcs belonging to the transport $t \in OD$

$A^{\tau}_t$     The set of arcs connecting the transport nodes and the container type nodes

$A^{L}_{tl}$     The set of arcs connecting the container type nodes and the block nodes

$K_t$     The number of containers in transport $t\in OD$

$E_{ij}$     The number of containers flowing through the type nodes

$S$     The source node

$T$     The sink node

$q_i$     Is equal to $q$ for $i=S$, $-q$ for $i=T$ and zero for all other nodes, where $q$ is the total number of containers to be stowed

$\tau^L(i)$     The length of container type node $i\in T$

$\tau^W(i)$     The weight of container type node $i\in T$

$TEU_i$     The TEU value of container type node $i\in T$

As the following is a network-flow formulation, the decision variables $x_{ij} \in \mathbb{R}^+$ represent the flow (the number) of containers from the source to the sink node, through the arcs $(i,j)\in A$.

\begin{align}
%& \text{\bf min} \sum_{p\in P} \left(\mathcal{C}^Ty^T_p + \sum_{l\in L} \mathcal{C}^Oy^O_pl \right) \\
& \text{\bf min} \sum_{p\in P}\mathcal{C}^Ty^T_p \label{chao:obj}\\
& \text{\bf s.t.}\nonumber \\
& \sum_{(i,j) \in \mathcal{A}^-_i}\!\! x_{ij} -\!\! \sum_{(i,j)\in \mathcal{A}^+_i}\!\! x_{ij} = q_i \quad \forall i \in N \label{chao:flow}\\
& x_{ij} = K_t \quad \forall t \in OD, (i,j) \in A^{TR}_{t} \label{chao:od_pairs}\\
& x_{ij} = E_{ij} \quad \forall t \in OD, (i,j) \in A^{\tau}_{t}\label{chao:types}\\
%& x_{ij} \geq R^{\tau(i)}_{ij} \quad \forall p\in P, t \in OD^{ON}_p, l\in L, (i,j)\in A^L_{tl}\\
& \sum_{t\in OD^{ON_p}}\sum_{(i,j)\in A^L_{tl}} TEU_i x_{ij} \leq C^{20}_l \quad \forall p\in P, l\in L\label{chao:cap_teu}\\
& \sum_{t\in OD^{ON_p}}\sum_{(i,j)\in A^L_{tl},\tau(i)=\alpha}x_{ij} \leq C^\alpha_l \quad \forall p\in P, l\in L, \alpha \in \{20,40,R\}\label{chao:cap}\\
& \sum_{t\in OD^{OD}_p}\sum_{(i,j)\in A^L_{tl}}\tau^W(i)x_{ij}\leq W^{Max}_l \quad \forall p\in P, l\in L \label{chao:cap_weight}\\
%&\sum_{t\in OD^{ON}_p}\sum_{(i,j)\in A^L_{tl}}CG^L(i)\tau^W(i)x_{ij}+\sum_{b\in B}\overline{CG}^L_bW^K_b\leq LCG^{Max}_pD_p \quad \forall p\in P\\
%&\sum_{t\in OD^{ON}_p}\sum_{(i,j)\in A^L_{tl}}CG^L(i)\tau^W(i)x_{ij}+\sum_{b\in B}\overline{CG}^L_bW^K_b\geq LCG^{Min}_pD_p \quad \forall p\in P\\
%&\sum_{t\in OD^{ON}_p}\sum_{(i,j)\in A^L_{tl}}CG^T(i)\tau^W(i)x_{ij}+\sum_{b\in B}\overline{CG}^T_bW^K_b\leq TCG^{Max}_pD_p \quad \forall p\in P\\
%&\sum_{t\in OD^{ON}_p}\sum_{(i,j)\in A^L_{tl}}CG^T(i)\tau^W(i)x_{ij}+\sum_{b\in B}\overline{CG}^T_bW^K_b\geq TCG^{Min}_pD_p \quad \forall p\in P\\
%&\sum_{t\in OD^{ON}_p}\sum_{(i,j)\in A^V_{tl}}CG^T(i)\tau^W(i)x_{ij}+\sum_{b\in B}\overline{CG}^T_bW^K_b\geq VCG^{Min}_pD_p \quad \forall p\in P\\
%&\sum_{b=1}^b\left(W^K_b+\sum_{l\in BL_{b'}}\sum_{t \in OD^{ON}_p}\sum_{(i,j)\in A^L_{tl}}\tau^W(i)x_{ij} - W^B_{bp}\right) \geq Shear^{Min}_{bp} \quad \forall p\in P\\
%&\sum_{b=1}^b\left(W^K_b+\sum_{l\in BL_{b'}}\sum_{t \in OD^{ON})_p}\sum_{(i,j)\in A^L_{tl}}\tau^W(i)x_{ij} - W^B_{bp}\right) \leq Shear^{Max}_{bp} \quad \forall p\in P\\
&x_{ij} \leq M y_{ij} \quad \forall p\in P, t \in OD^A_p, (i,j)\in A^{LU}_{tl}\label{chao:delta}\\
%&\sum_{t\in OD^O_p}\sum_{(i,j)\in A^{LO}_{tl}} x_{ij} \leq M(1- y_{ij})+y^O_p \quad \forall p\in P, t \in OD^A_p, (i,j)\in A^{LU}_{tl}\\
&\sum_{t\in OD^O_p}\sum_{(i,j)\in A^{LO}_{tl}} x_{ij} \leq M(1- y_{ij}) \quad \forall p\in P, t \in OD^A_p, (i,j)\in A^{LU}_{tl}\label{chao:hatch}\\
&\sum_{b\in N}\sum_{l\in BL_b}\sum_{A^L_{tl}} x_{ij}\leq y^T_p \quad \forall p\in P, N \in Bin \label{chao:makespan}
\end{align}

The model's objective is the minimization of the makespan at each port (<ref>). This objective differs from the original publication, but this change was necessary for the sake of the comparison. Constraint (<ref>) is the classic flow-conservation constraint between the source and the sink node. To ensure that cargo is correctly routed through the network, it is necessary to constraint containers within their respective origin-destination arcs (<ref>), and the correct container type arcs (<ref>). Constraints (<ref>), (<ref>), and (<ref>) are the revised capacity and weight constraints. The absence of hatch=overstowage is ensured by constraints (<ref>), which indicate the presents of container moves in below deck locations, and constraint (<ref>) which imposes that no hatch-overstowage is allowed. Finally, constraint (<ref>) calculates the makespan at each port.