An exact approach for the Blocks Relocation Problem

• An optimization model from the related literature is corrected.
• A branch and bound algorithm to solve realistic scenarios is developed.
• An α-restricted strategy reduces the burden of the branch and bound.
• Optimality of several solutions from the literature has been corrected.
• Optimal solutions are obtained in short times by the branch and bound.

The Blocks Relocation Problem seeks to find the shortest sequence of movements to retrieve a set of homogeneous blocks placed in a two-dimensional storage according to a predefined order. In this paper we analyze an optimization model recently published in the literature. We illustrate that this model reports infeasible solutions and does not guarantee the optimality of the achieved solutions in some cases. In order to overcome this fact, we propose an alternative optimization model. However, its high computational consumption of temporal and space resources in large environments encourages us to also develop a branch and bound algorithm to solve realistic scenarios to optimality. This algorithm includes an intelligent strategy to explore the most promising nodes in the underlying tree. Additionally, its performance can be easily adapted to report high-quality solutions at the expense of sacrificing the optimality guarantee. In contrast to previous exact proposals, the computational experiments reveal the high efficiency of the branch and bound algorithm, reporting optimal solutions for the most widely extended benchmark suite from the related literature through short computational times.