A Constraint Programming Model for Fast Optimal Stowage of Container Vessel Bays

Container vessel stowage planning is a hard combinatorial optimization
problem with both high economic and environmental impact. We have
developed an approach that often is able to generate near-optimal
plans for large container vessels within a few minutes. It decomposes
the problem into a master planning phase that distributes the
containers to bay sections and a slot planning phase that assigns
containers of each bay section to slots. In this paper, we focus on
the slot planning phase of this approach and present a constraint
programming and integer programming model for stowing a set of
containers in a single bay section. This so-called slot planning
problem is NP-hard and often involves stowing several hundred
containers. Using state-of-the-art constraint solvers and modeling
techniques, however, we were able to solve 90% of 236 real instances
from our industrial collaborator to optimality within one
second. Thus, somewhat to our surprise, it is possible to solve most
of these problems optimally within the time required for practical
application.