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

doi:10.1016/j.ejor.2021.03.062

Return

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

2022-01-01

PRE

Shunji Tanaka *

Stefan Voß

DOI：10.1016/j.ejor.2021.03.062

Original

Original request for help

Save

Abstract

En 中文

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. (c) 2021 Elsevier B.V. All rights reserved.

Keywords:

OR in maritime industry

Combinatorial optimization

Block relocation problem

Integer programming

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.