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

TR-2010-133, Authors: Alberto Delgado Ortegón, Rune Møller Jensen, Kira Janstrup, Trine Høyer Rose and Kent Høl Andersen

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

Alberto Delgado Ortegón
Rune Møller Jensen
Kira Janstrup
Trine Høyer Rose
Kent Høl Andersen

October 2010

Abstract

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.

Technical report TR-2010-133 in IT University Technical Report Series, October 2010.

Available as PDF.