An exact algorithm for the unrestricted block relocation problem

Abstract

The purpose of this study is to propose an exact algorithm for the unrestricted block relocation problem with distinct priorities. In this problem, a storage area is considered where blocks of the same size are stacked vertically in tiers. Because we can access only topmost blocks, relocations of blocks are required when other blocks are retrieved. The objective is to minimize the total number of such relocations necessary for retrieving all the blocks one by one according to a specified order. In the restricted version of this problem, only the topmost block above the target block is relocatable. On the other hand, no such restriction is imposed on the unrestricted problem, which is considered in this study. We also assume that each block is assigned a distinct retrieval priority and the retrieval order of blocks is unique. To improve the efficiency of a branch-and-bound algorithm for this problem, we propose several dominance properties to eliminate unnecessary nodes in the search tree. Furthermore, we propose a new lower bound of the total number of relocations. The effectiveness of the proposed exact algorithm is verified by numerical experiments for benchmark instances in the literature.