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

Container vessel stowage is a combinatorial optimization problem with
both high economic and environmental impact. The most successful
approaches to tackle this problem use hierarchical decompositions in
which the sub-problems of these decompositions assign containers to
slots in individual vessel bays. Due to the large number of
sub-problems, they must each be solved fast to generate complete
stowage plans within the time requirements and computational resource
limits of the shipping industry. In this paper we present the first
independent study of these sub-problems. We introduce an accurate
representative model of them developed with our industrial partner and
a constraint programming (CP) and integer programming approach to
solve them optimally. Our experimental evaluation of 236 instances
extracted from real stowage plans shows that, even though these
sub-problems are theoretically hard, they are often easy to solve in
practice. Using state-of-the-art CP software on our CP model, we were
able to solve 92% of the instances to optimality within one
second. Thus, somewhat to our surprise, it is possible to define an
optimal model that can be solved fast enough to be used directly in a
stowage planning tool.