A faster branch-and-bound algorithm for the block relocation problem

The block relocation problem, which is also known as the container relocation problem, is to find an optimal sequence of operations for retrieving blocks (containers) from a container bay composed of several stacks. The primary contribution of this study is that a lower bound better than those in the existing studies is proposed. This enables us to construct a faster branch-and-bound algorithm than the exact algorithms in the literature. Its effectiveness will be demonstrated by extensive numerical experiments.