On the complexity of container stowage planning problems

Kevin Tierney, Dario Pacino, Rune Møller Jensen

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

Abstract

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

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