ITU

On the complexity of container stowage planning problems

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

View graph of relations

The optimization of container ship and depot operations embeds the k-shift problem, in which containers must be stowed in stacks such that at most k 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
Close

    Research areas

  • Container stowage, Overstowage, Computational complexity, Liner shipping

ID: 66821752