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 / ReportReportResearch

    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
    Place of PublicationCopenhagen
    PublisherIT-Universitetet i København
    EditionTR-2010-133
    Number of pages21
    ISBN (Electronic)9788779492264
    Publication statusPublished - Oct 2010
    SeriesIT University Technical Report Series
    NumberTR-2010-133
    ISSN1600-6100

    Keywords

    • Container Vessel Stowage
    • Combinatorial Optimization
    • Hierarchical Decomposition
    • Constraint Programming
    • Integer Programming

    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