An exact algorithm for the unrestricted block relocation problem

• 田中, 俊二

  Institute for Liberal Arts and Sciences, Kyoto University

• 水野, 史崇

  Department of Electrical Engineering, Kyoto University

抄録

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.

収録刊行物

• Computers & Operations Research

  Computers & Operations Research 95 12-31, 2018-07

  Elsevier Ltd

キーワード

• Block relocation problem
• Container relocation problem
• Exact algorithm
• Dominance properties
• Lower bound

詳細情報

• CRID: 1050001338209195136
• NII論文ID: 120006551743
• ISSN: 03050548
• HANDLE: 2433/236096
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles