Solving the container premarshalling problem with an auxiliary bay

The relocation of containers is essential at port terminals to increase operational efficiency during container retrieval from the yard. When a container must be retrieved, any container placed on top of it must be moved to another stack, delaying the retrieval process. The container premarshalling problem (CPMP) aims to tackle this issue by finding a sequence of minimal container relocations to achieve a bay arrangement where no container needs to be moved during retrieval. The classical formulation of this problem assumes that all premarshalling relocations occur within the bay being arranged. However, this study demonstrates that practical applications of premarshalling can benefit from more efficient use of available resources. We introduce a novel problem variant that allows the use of an auxiliary bay as additional space for relocating containers during the arrangement process. We present constraint programming solution methods for this variant that reveal a significant reduction in premarshalling relocations when an auxiliary bay is used. The results demonstrate that bays where high occupancy rates prevent premarshalling can be successfully arranged with an auxiliary bay. Additionally, we propose two alternative formulations allowing different rates of relocations between bays, offering adaptability to varying port terminal requirements. • The number of premarshalling relocations can be reduced by using an auxiliary bay. • An auxiliary bay can allow the arrangement of bays with little space for relocation. • Constraint programming methods are effective in solving the novel problem proposed. • Two alternative formulations make the problem flexible for practical application.