A Study on the Block Relocation Problem: Lower Bound Derivations and Strong Formulations

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 article, to advance our understanding of this problem and to provide substantial assistance to practice, we adopt the following: 1) introduce a classification scheme and present a rather comprehensive review on all 16 BRP variants; 2) develop a general framework to derive lower bounds on the number of necessary relocations and demonstrate its connection to existing lower bounds on the unrestricted BRP variants; 3) propose and employ a couple of new critical substructure concepts to analyze the BRP and obtain a lower bound that dominates all existing ones; 4) build a new and strong mixed integer programming (MIP) formulation that is adaptable to compute eight BRP variants, and design a novel MIP-formulation-based iterative procedure to compute exact BRP solutions; and 5) extend the MIP formulation to address four typical industrial considerations. Computational results on standard and practical test instances show that the new lower bound is significantly stronger, and our new MIP computational methods have superior performances over the state-of-the-art formulation and a heuristic adopted in a steel plant. Note to Practitioners-This article was motivated by a practical operational problem which occurs in container yards, steel slab yards, and many other warehouses. In a container yard, containers are stored vertically in stacks. Cranes are employed to move containers and can access only the topmost ones. If the container to be retrieved is not at the top of a stack, containers above it have to be relocated to other stacks. As relocations are very time- and energy-consuming, minimizing the number of relocations involved in a retrieval process is a serious concern. Similar situations can also be found in steel slab yards. In this article, in addition to theoretical derivations, we propose a strong MIP formulation and an MIP-formulation-based iterative procedure to compute optimal relocation plans with the least number of relocations. Both methods have superior performances over state-of-the-art formulation. Moreover, we demonstrate that the MIP formulation can be flexibly customized to address additional industrial considerations, for example, stacking restrictions and the energy cost. Hence, we believe that the presented results are powerful management tools and can provide substantial decision-making support to practitioners.