The Bounded Beam Search algorithm for the Block Relocation Problem

In this paper we deal with the restricted Block Relocation Problem. We present a new lower boundand a heuristic approach for the problem. The proposed lower bound can be computed in polynomialtime and it is provably better than some previously known lower bounds. We use it within a boundedbeam search algorithm to solve the Block Relocation Problem and show that the considered heuristicapproach outperforms the other existing algorithms on most of the instances in the literature. Inorder to test the approaches on real-size dimensions, new large instances of the Block RelocationProblem are also introduced.