An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules

Bo Jin and Shunji Tanaka

European Journal of Operational Research, 2023, vol. 304, issue 2, 494-514

Abstract: The container relocation problem, also known as the block(s) relocation problem, is one of the most studied optimization problems in container terminals. The problem aims at minimizing the total number of relocations for retrieving containers from a storage yard according to a specific order. The purpose of this study is to develop an efficient iterative deepening branch-and-bound algorithm for exactly solving one of the most practical variants of the problem, namely the unrestricted container relocation problem with duplicate priorities, which has received less attention in the literature. To improve the search efficiency of the proposed algorithm, we design two new lower bounds that can be computed quickly to incorporate them into the branch-and-bound algorithm. We also present a set of mutually consistent dominance rules to reduce the search space while avoiding over-pruning. The performance of the proposed algorithm is evaluated by extensive computational experiments on three commonly used benchmark datasets. The results show that the proposed algorithm outperforms the state-of-the-art exact algorithm for the unrestricted container relocation problem with distinct priorities, although our algorithm is applicable to a more general variant of the problem. Moreover, it can still provide competitive results for small- and medium-sized instances under a strict time limit of one second in comparison to existing metaheuristic approaches.

Keywords: Combinatorial optimization; Container relocation problem; Branch-and-bound; Lower bounds; Dominance rules (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722002946
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:304:y:2023:i:2:p:494-514

DOI: 10.1016/j.ejor.2022.04.006

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 ().