The Block Retrieval Problem

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

Research output: Contribution to journalArticle

  • 2 Citations

Abstract

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.
LanguageEnglish
Pages931-950
Number of pages20
JournalEuropean Journal of Operational Research
Volume265
Issue number3
Early online date8 Sep 2017
DOIs
StatusPublished - 16 Mar 2018

Fingerprint

Relocation
Containers
Retrieval
Container
Branch and Bound Algorithm
Port terminals
Customers
Beam Search
Hardness
Search Algorithm
Linear Time
Heuristics
Minimise
Configuration
Target
Alternatives

Cite this

The Block Retrieval Problem. / Melo, Marcos; Erdoğan, Güneş; Battarra, Maria; Strusevich, Vitaly.

In: European Journal of Operational Research, Vol. 265, No. 3, 16.03.2018, p. 931-950.

Research output: Contribution to journalArticle

Melo, Marcos ; Erdoğan, Güneş ; Battarra, Maria ; Strusevich, Vitaly. / The Block Retrieval Problem. In: European Journal of Operational Research. 2018 ; Vol. 265, No. 3. pp. 931-950
@article{f3d225cd9cd04bed9d2da5d655ea5fac,
title = "The Block Retrieval Problem",
abstract = "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.",
author = "Marcos Melo and G{\"u}neş Erdoğan and Maria Battarra and Vitaly Strusevich",
note = "Ref.: Ms. No. EJOR-D-17-00027R1 The Block Retrieval Problem European Journal of Operational Research Dear Dr. Gunes Erdogan, I am pleased to inform you that your paper has been accepted for publication in the European Journal of Operational Research. The PDF file of the final version of your article will be available on ScienceDirect shortly after the corrections to the proofs have been received by Elsevier. I suggest that you read them carefully and check them once more against the original; you are the only one responsible for doing this. Together with the proofs you will receive an order form for reprints. Your paper from now on is no longer under my control. Please, address queries only to the Journal Manager: Kate Partner E-Mail: K.Partner@elsevier.com",
year = "2018",
month = "3",
day = "16",
doi = "10.1016/j.ejor.2017.08.048",
language = "English",
volume = "265",
pages = "931--950",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

TY - JOUR

T1 - The Block Retrieval Problem

AU - Melo,Marcos

AU - Erdoğan,Güneş

AU - Battarra,Maria

AU - Strusevich,Vitaly

N1 - Ref.: Ms. No. EJOR-D-17-00027R1 The Block Retrieval Problem European Journal of Operational Research Dear Dr. Gunes Erdogan, I am pleased to inform you that your paper has been accepted for publication in the European Journal of Operational Research. The PDF file of the final version of your article will be available on ScienceDirect shortly after the corrections to the proofs have been received by Elsevier. I suggest that you read them carefully and check them once more against the original; you are the only one responsible for doing this. Together with the proofs you will receive an order form for reprints. Your paper from now on is no longer under my control. Please, address queries only to the Journal Manager: Kate Partner E-Mail: K.Partner@elsevier.com

PY - 2018/3/16

Y1 - 2018/3/16

N2 - 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.

AB - 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.

U2 - 10.1016/j.ejor.2017.08.048

DO - 10.1016/j.ejor.2017.08.048

M3 - Article

VL - 265

SP - 931

EP - 950

JO - European Journal of Operational Research

T2 - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -