The block relocation problem (BRP) considers a set of blocks randomly distributed into stacks. All blocks have to be retrieved in a predefined sequence and at a given time, only those blocks which are on top of a stack may be retrieved. Otherwise, relocations are required. The aim of the BRP is then to retrieve all blocks in the predefined sequence while minimising the total number of relocations. Applications include the management of containers at container terminals, as well as the handling of steel slabs in steel production factories. A common assumption is that a block can only be relocated if it is above the next block to be retrieved according to the sequence, resulting in the restricted BRP. We introduce new heuristics and exact algorithms for the unrestricted BRP, which yields more opportunities for optimisation.

Our contributions include fast heuristics able to tackle very large instances within seconds, a new fast metaheuristics that provide very competitive performance on benchmark data sets as well as a branch-and-bound algorithm that outperforms the best existing exact method and provides new optimal solutions. The heuristics use known lower bounds to determine which moves should be performed. The branch-and-bound algorithm relies on a look-ahead mechanism using the same lower bounds. It is also adapted to tackle the restricted BRP, again outperforming existing methods for that problem.