On the Complexity of Container Stowage Planning
TR-2010-137, Author: Rune Møller Jensen
On the Complexity of Container Stowage Planning
Rune Møller Jensen December 2010
Abstract
In this report we examine the complexity of stowage planning problems. A stowage planning problem is to stow containers in stacks such that the number of containers to remove in order to reach containers to retrieve is minimal. We first define and discuss an open problem called the capacitated zero-shift problem, where a set of containers must be placed in a set of stacks with fixed capacity without blocking each other. We then define the hatch overstow problem for container ships. The problem is to place a set of containers on top of hatches of a container vessel avoiding that containers are stowed on hatches that must be accessed. We prove the decision version of this problem to be NP-complete by a reduction from the set cover problem.
Technical report TR-2010-137 in IT University Technical Report Series, December 2010.
Available as PDF.