An exact algorithm for the unrestricted block relocation problem. (July 2018)

• Record Type: Journal Article
• Authors: Tanaka, Shunji; Mizuno, Fumitaka
• Is Part Of: Computers & operations research. Volume 95(2018)
• Page Start: 12
• Page End: 31
• Publication Date: 2018-07
• Subjects: Block relocation problem -- Container relocation problem -- Exact algorithm -- Dominance properties -- Lower bound; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.02.019
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The unrestricted block relocation problem with distinct priorities is considered. Dominance properties and a new lower bound are proposed to improve the efficiency of a branch-and-bound algorithm. The previous branch-and-bound algorithm for the restricted block relocation problem is also improved. The effectiveness of the algorithms is demonstrated by the computational experiments for benchmark instances in the literature. 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.