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

Alberto Delgado-Ortegon, Rune Møller Jensen, Kira Janstrup, Trine Rose, Kent Andersen

Research output: Book / Anthology / Report / Ph.D. thesisReportResearch

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.
Original languageEnglish
PublisherIT-Universitetet i København
Number of pages21
ISBN (Electronic)9788779492264
Publication statusPublished - Oct 2010

Fingerprint

Dive into the research topics of 'A Constraint Programming Model for Fast Optimal Stowage of Container Vessel Bays'. Together they form a unique fingerprint.

Cite this