A Study on the Block Relocation Problem: Lower Bound Derivations and Strong Formulations
Chao Lu, Bo Zeng, Shixin Liu
Abstract
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.