A fill-and-reduce greedy algorithm for the container pre-marshalling problem

We address the Container Pre-Marshalling Problem (CPMP). The CPMP consists in ordering containers in stacks such that the retrieval of these containers is carried out without additional movements. The ordering has to be done in a minimum number of steps. Target-guided constructive heuristics report very good results in a short time. At each step, they select one poorly located container and rearrange it to an adequate position by a sequence of movements. The sequence of movements is generally generated by following a set of rules. In this work, we propose a different and more direct approach. Whenever possible, ordered stacks are filled by directly moving badly placed containers into them such that the containers become well placed. If it is not possible, then a stack is emptied or reduced to have more available slots, and the process is repeated. Unlike target-guided algorithms which rigidly adhere to a predefined sequence of movements for each badly placed container, our fill-and-reduce approach maintains the capacity to adapt to the evolving situation making choices based on the current state of the container stacks. The algorithm has shown superior performance compared to traditional target-guided heuristics, particularly in larger instances of classical benchmark sets. Furthermore, when embedded in a beam search algorithm, it reports the best results compared to traditional techniques that do not use machine learning.