On the complexity of container stowage planning problems

Kevin Tierney, Dario Pacino, Rune Møller Jensen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    The optimization of container ship and depot operations embeds the kk-shift problem, in which containers must be stowed in stacks such that at most kk containers must be removed in order to reach containers below them. We first solve an open problem introduced by Avriel et al. (2000) by showing that changing from uncapacitated to capacitated stacks reduces the complexity of this problem from NP-complete to polynomial. We then examine the complexity of the current state-of-the-art abstraction of container ship stowage planning, wherein containers and slots are grouped together. To do this, we define the hatch overstow problem, in which a set of containers are placed on top of the hatches of a container ship such that the number of containers that are stowed on hatches that must be accessed is minimized. We show that this problem is NP-complete by a reduction from the set-covering problem, which means that even abstract formulation of container ship stowage planning is intractable.
    Original languageEnglish
    JournalDiscrete Applied Mathematics
    Volume169
    Pages (from-to)225-230
    Number of pages6
    ISSN0166-218X
    DOIs
    Publication statusPublished - 31 May 2014

    Keywords

    • Container stowage
    • Overstowage
    • Computational Complexity
    • Liner shipping

    Fingerprint Dive into the research topics of 'On the complexity of container stowage planning problems'. Together they form a unique fingerprint.

    Cite this