On the Complexity of Container Stowage Planning Problems

Dario Pacino, Kevin Tierney, Rune Møller Jensen

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    Abstract

    The optimization of container ship and depot operations embeds the k-shift problem, in which containers must be stowed with at most k rehandles. We first solve an open problem showing that changing from uncapacitated to capacitated stacks reduces the problem complexity from NP-complete to polynomial. We then examine the complexity of an abstraction of the current state-of-the-art container ship stowage planning, the hatch overstow problem. We show that this problem is NP-complete, which means that even abstract formulation of container ship stowage planning is intractable.
    Original languageEnglish
    Publication date2014
    Number of pages1
    Publication statusPublished - 2014
    EventConference of the International Federation of Operational Research Societies. - Barcelona International Convention Center, Barcelona, Spain
    Duration: 13 Jul 201418 Jul 2014
    Conference number: 20

    Conference

    ConferenceConference of the International Federation of Operational Research Societies.
    Number20
    LocationBarcelona International Convention Center
    CountrySpain
    CityBarcelona
    Period13/07/201418/07/2014

    Cite this

    Pacino, D., Tierney, K., & Jensen, R. M. (2014). On the Complexity of Container Stowage Planning Problems. Abstract from Conference of the International Federation of Operational Research Societies., Barcelona, Spain. http://ifors2014.org/