The Stochastic Container Relocation Problem

V. Galle (), V. H. Manshadi (), S. Borjian Boroujeni (), C. Barnhart () and P. Jaillet ()
Additional contact information
V. Galle: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
V. H. Manshadi: Yale School of Management, Yale University, New Haven, Connecticut 06511
S. Borjian Boroujeni: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
C. Barnhart: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142; Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
P. Jaillet: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142; Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142

Transportation Science, 2018, vol. 52, issue 5, 1035-1058

Abstract: The container relocation problem (CRP) is concerned with finding a sequence of moves of containers that minimizes the number of relocations needed to retrieve all containers, while respecting a given order of retrieval. However, the assumption of knowing the full retrieval order of containers is particularly unrealistic in real operations. This paper studies the stochastic CRP, which relaxes this assumption. A new multistage stochastic model, called the batch model , is introduced, motivated, and compared with an existing model (the online model ). The two main contributions are an optimal algorithm called Pruning-Best-First-Search (PBFS) and a randomized approximate algorithm called PBFS-Approximate with a bounded average error. Both algorithms, applicable in the batch and online models, are based on a new family of lower bounds for which we show some theoretical properties. Moreover, we introduce two new heuristics outperforming the best existing heuristics. Algorithms, bounds, and heuristics are tested in an extensive computational section. Finally, based on strong computational evidence, we conjecture the optimality of the “leveling” heuristic in a special “no information” case, where, at any retrieval stage, any of the remaining containers is equally likely to be retrieved next.

Keywords: container relocation problem; block relocation problem; combinatorial optimization; multistage stochastic models; decision trees (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0828 (application/pdf)

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:inm:ortrsc:v:52:y:2018:i:5:p:1035-1058

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().