An exact approach to the restricted block relocation problem based on a new integer programming formulation

Shunji Tanaka and Stefan Voß

European Journal of Operational Research, 2022, vol. 296, issue 2, 485-503

Abstract: This study addresses the block(s) relocation problem (BRP), also known as the container relocation problem. This problem considers individually retrieving blocks piled up in tiers according to a predetermined order. When the block to be retrieved next is not at the top, we have to relocate the blocks above it because we can access only the topmost blocks. The objective is to retrieve all the blocks with the smallest number of relocations. In this study, a novel exact algorithm is proposed for the restricted BRP, a class of the problem where relocatable blocks are restricted. The proposed algorithm computes lower and upper bounds iteratively by solving the corresponding integer programming problems until the optimality gap is reduced to zero. The novelty of the algorithm lies in the formulations based on complete and truncated relocation sequences of the individual blocks. We examine the effectiveness of the proposed algorithm through computational experiments for benchmark instances from the literature. In particular, we report that, for the first time, all the instances with up to 100 blocks are solved to proven optimality.

Keywords: OR in maritime industry; Combinatorial optimization; Block relocation problem; Integer programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721002927
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:296:y:2022:i:2:p:485-503

DOI: 10.1016/j.ejor.2021.03.062

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().