The Block Retrieval Problem

Marcos Melo, Güneş Erdoğan, Maria Battarra, Vitaly Strusevich

Research output: Contribution to journalArticlepeer-review

11 Citations (SciVal)
53 Downloads (Pure)


Retrieving containers from a bay in a port terminal yard is a time consuming activity. The Block Retrieval Problem (BRTP) aims at minimizing the number of relocations, the unproductive moves of hindering containers, while retrieving target containers belonging to a customer. The choice of relocations leads to alternative bay configurations, some of which would minimize the relocations of forthcoming retrievals. The Bi-objective Block Retrieval Problem (2BRTP) includes a secondary objective, the minimization of the expected number of relocations for retrieving the containers of the next customer. This paper provides NP-Hardness proofs for both the BRTP and 2BRTP. A branch-and-bound algorithm and a linear time heuristic are developed for the BRTP; a branch-and-bound algorithm and a beam search algorithm are presented for the 2BRTP. Extensive computational tests on randomly generated instances as well as instances adapted from the literature are performed, and the results are presented.
Original languageEnglish
Pages (from-to)931-950
Number of pages20
JournalEuropean Journal of Operational Research
Issue number3
Early online date8 Sep 2017
Publication statusPublished - 16 Mar 2018


Dive into the research topics of 'The Block Retrieval Problem'. Together they form a unique fingerprint.

Cite this