Abstract
Container shipping plays an essential role in the global transportation of interna-
tionally traded goods, making it a crucial component of the world economy. Due
to the large volume of cargo moved by each vessel, container shipping is also one
of the most environmentally friendly modes of transport, resulting in significantly
lower emissions per tonne of cargo per kilometer compared to alternatives.
A key operational challenge in container shipping is deciding how to efficiently
place containers onto vessels, a task known as stowage planning. This task is critical
yet challenging, involving many factors and constraints that interact in combina-
tionally difficult ways. Due to its complexity, stowage planning is usually split into
two phases: (1) the master planning problem (MPP), which broadly determines how
containers are grouped and placed onboard, and (2) the slot planning problem (SPP),
which assigns individual containers to specific slots.
This PhD research explores how advanced techniques from combinatorial optimiza-
tion (CO) and machine learning (ML) can accelerate decision-making for stowage
planning, especially at the master planning level. The goal is to develop efficient and
practical solutions that bridge the gap between theoretical models and real-world in-
dustry needs, leading to faster and better planning decisions that result in reliable
and efficient supply chains with implications for global trade and environmental
sustainability.
The research comprises four main contributions: (1) a comprehensive literature re-
view, (2) novel problem formulations of the MPP, (3) scalable CO and ML-based
solutions methods, (4) theoretical analysis on computational complexity and math-
ematical soundness.
First, a literature review classifies the single-port and multi-port container stowage
planning problem (CSPP), highlighting key issues such as oversimplified problem
formulations and limited industrial validation. A research agenda is proposed to
address challenges, such as the need for scalable algorithms to solve realistic prob-
lem definitions on benchmark instances, with particular attention to the MPP.
Second, building on these insights, novel problem formulations are provided in the
form of a 0-1 integer program (IP) model that searches in the space of valid paired
block stowage and a Markov decision process and its extension that both decompose
the decision process into sequential steps. Furthermore, this thesis includes paired
block stowage patterns and demand uncertainty in the MPP, which are features to
consider in the MPP.
Third, the findings indicate that the 0-1 IP model outperforms a traditional mixed-
integer programming (MIP) model in terms of optimality and runtime. Regardless,
larger problem instances require more than 10 minutes to solve, which is considered
intractable given the dynamic nature of stowage planning. In contrast, the MDPs ad-
dressed by deep reinforcement learning (DRL) can construct solutions for the MPP
within this timeframe. However, the MDPs do not offer guarantees on optimality
and feasibility, which need to be learned through extensive training. Especially on
feasibility, it is shown that differentiable projection layers are needed to ensure fea-
sibility, while alternatives as reward scaling and feasibility regularization can work
but are hard to balance with other objectives. In the case of specific non-convex con-
straints, action masking in combination with feasibility projection can be applied.
Fourth, this thesis shows that searching in the space of valid block stowage pattern
is an NP-hard task but also demonstrates how a differentiable projection layer based
on violation gradients can minimize the violations of convex inequality constraints.
This research advances both theory and practice in stowage planning by introduc-
ing scalable optimization techniques. It highlights the value of improved problem
formulations and learning-based heuristics for real-world planning problems. These
contributions show how decision-support systems can be enhanced, paving the way
for more resilient and efficient container shipping.
tionally traded goods, making it a crucial component of the world economy. Due
to the large volume of cargo moved by each vessel, container shipping is also one
of the most environmentally friendly modes of transport, resulting in significantly
lower emissions per tonne of cargo per kilometer compared to alternatives.
A key operational challenge in container shipping is deciding how to efficiently
place containers onto vessels, a task known as stowage planning. This task is critical
yet challenging, involving many factors and constraints that interact in combina-
tionally difficult ways. Due to its complexity, stowage planning is usually split into
two phases: (1) the master planning problem (MPP), which broadly determines how
containers are grouped and placed onboard, and (2) the slot planning problem (SPP),
which assigns individual containers to specific slots.
This PhD research explores how advanced techniques from combinatorial optimiza-
tion (CO) and machine learning (ML) can accelerate decision-making for stowage
planning, especially at the master planning level. The goal is to develop efficient and
practical solutions that bridge the gap between theoretical models and real-world in-
dustry needs, leading to faster and better planning decisions that result in reliable
and efficient supply chains with implications for global trade and environmental
sustainability.
The research comprises four main contributions: (1) a comprehensive literature re-
view, (2) novel problem formulations of the MPP, (3) scalable CO and ML-based
solutions methods, (4) theoretical analysis on computational complexity and math-
ematical soundness.
First, a literature review classifies the single-port and multi-port container stowage
planning problem (CSPP), highlighting key issues such as oversimplified problem
formulations and limited industrial validation. A research agenda is proposed to
address challenges, such as the need for scalable algorithms to solve realistic prob-
lem definitions on benchmark instances, with particular attention to the MPP.
Second, building on these insights, novel problem formulations are provided in the
form of a 0-1 integer program (IP) model that searches in the space of valid paired
block stowage and a Markov decision process and its extension that both decompose
the decision process into sequential steps. Furthermore, this thesis includes paired
block stowage patterns and demand uncertainty in the MPP, which are features to
consider in the MPP.
Third, the findings indicate that the 0-1 IP model outperforms a traditional mixed-
integer programming (MIP) model in terms of optimality and runtime. Regardless,
larger problem instances require more than 10 minutes to solve, which is considered
intractable given the dynamic nature of stowage planning. In contrast, the MDPs ad-
dressed by deep reinforcement learning (DRL) can construct solutions for the MPP
within this timeframe. However, the MDPs do not offer guarantees on optimality
and feasibility, which need to be learned through extensive training. Especially on
feasibility, it is shown that differentiable projection layers are needed to ensure fea-
sibility, while alternatives as reward scaling and feasibility regularization can work
but are hard to balance with other objectives. In the case of specific non-convex con-
straints, action masking in combination with feasibility projection can be applied.
Fourth, this thesis shows that searching in the space of valid block stowage pattern
is an NP-hard task but also demonstrates how a differentiable projection layer based
on violation gradients can minimize the violations of convex inequality constraints.
This research advances both theory and practice in stowage planning by introduc-
ing scalable optimization techniques. It highlights the value of improved problem
formulations and learning-based heuristics for real-world planning problems. These
contributions show how decision-support systems can be enhanced, paving the way
for more resilient and efficient container shipping.
| Original language | English |
|---|---|
| Supervisor(s) |
|
| Publication status | Published - 14 May 2025 |