  The block relocation problem (BRP) is a fundamental operational issue in
modern warehouse and yard management, which, however, is very challenging to
solve. In this paper, to advance our understanding on this problem and to
provide a substantial assistance to practice, we (i) introduce a classification
scheme and present a rather comprehensive review on all 16 BRP variants; (ii)
develop a general framework to derive lower bounds on the number of necessary
relocations and demonstrate its connection to existing lower bounds of the
unrestricted BRP variants; (iii) propose and employ a couple of new critical
substructures concepts to analyze the BRP and obtain a lower bound that
dominates all existing ones; (iv) build a new and strong mixed integer
programming (MIP) formulation that is adaptable to compute 8 BRP variants, and
design a novel MIP-formulation-based iterative procedure to compute exact BRP
solutions; (v) extend the MIP formulation to address four typical industrial
considerations. Computational results on standard test instances show that the
new lower bound is significantly stronger, and our new MIP computational
methods have superior performances over a state-of-the-art formulation.
