On the Complexity of Container Stowage Planning Problems

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.