Learning and Combinatorial Optimization for Efficient Container Vessel Stowage Planning

Container shipping plays an essential role in the global transportation of internationally 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 combinationally 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 optimization (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 industry 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 review, (2) novel problem formulations of the MPP, (3) scalable CO and ML-based solutions methods, (4) theoretical analysis on computational complexity and mathematical 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 problem 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 addressed 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 feasibility, 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 constraints, 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 introducing 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.