A general model formulation applicable to premarshalling, block relocation and stack loading problems

Abstract As space for storing items is frequently scarce, it is a common approach to store items directly on top of each other within stacks, e. g., in a container terminal. Such a storing system is space-saving, but at the expense of the drawback that not every item is accessible at any time. Whenever a required item is not the topmost of its stack, all items located above it must be relocated first by means of time-consuming operations. This paper addresses three typical combinatorial optimization problems associated with this type of storing system: the premarshalling problem which deals with presorting operations of the stored items, the block relocation problem and the stack loading problem which deal with unloading and loading operations, respectively. We propose a novel mixed integer linear model formulation that is applicable to all three selected optimization problems with only minor adjustments. In addition to its flexibility, the proposed model contains significantly fewer decision variables and constraints than existing model formulations for the addressed problems. The performance of the model formulation is examined in a computational study.