An ML-Driven Large Neighborhood Search Framework for Container Vessel Stowage Planning

In maritime logistics, the representative container vessel stowage planning problem (RCSPP) is a complex yet crucial combinatorial optimization challenge [1]. Solving realistic instances requires navigating large search spaces subject to numerous operational constraints. Search-based heuristics, including large neighborhood search (LNS), have been employed to find feasible or near-optimal solutions in reasonable time limits. However, the RCSPP involves a large and diverse set of competing constraints and objectives. As a result, LNS approaches have a large number of modifiers (i.e., destructors and constructors) that make modifier selection challenging, as the likelihood of choosing a promising modifier is low. This underscores the need for intelligent selection strategies to drive the search process more effectively.

In this work in progress, we propose a machine learning (ML) model that selects modifiers in an LNS search framework to solve instances of the RCSPP. The search process is formulated as a Markov decision process, where the state captures characteristics of the current solution, actions correspond to modifier selections, stochastic transitions reflect the effects of modifiers, and rewards are based on objective value and feasibility satisfaction. Additionally, we employ an actor-critic neural architecture with graph-based feature embeddings to exploit the structural properties of the vessel and voyage. The proposed ML-assisted search framework will be evaluated on real-world problem instances. Its performance will be benchmarked against general and problem-specific baselines to assess gains in solution quality and computational efficiency.

References
[1] A. Sivertsen, L. Reinhardt, and RM Jensen. “A representative model and benchmark suite for the container stowage planning problem”. In: Transportation Research Part E: Logistics and Transportation Review (Accepted) (2025).