Dominance properties for the unrestricted block relocation problem and their application to a branch-and-bound algorithm

The block (container) relocation problem is an optimization problem to minimize the number of relocation operations necessary for retrieving blocks (containers) stacked in tiers, according to a given order. Most of the existing exact approaches for this problem considered the restricted version of the problem where the block to be relocated next is uniquely determined. However, the unrestricted version of the problem without such a restriction is more preferable in order to reduce the number of required relocation operations. The purpose of this study is to derive dominance properties for the unrestricted block relocation problem, which enable us to exclude some of feasible solutions. Their effectiveness will be demonstrated by embedding them in a branch-and-bound algorithm and applying it to benchmark instances.