@article{ZEHENDNER201748,
title = {An algorithm with performance guarantee for the Online Container Relocation Problem},
journal = {European Journal of Operational Research},
volume = {259},
number = {1},
pages = {48-62},
year = {2017},
issn = {0377-2217},
doi = {https://doi.org/10.1016/j.ejor.2016.09.011},
url = {https://www.sciencedirect.com/science/article/pii/S0377221716307470},
author = {Elisabeth Zehendner and Dominique Feillet and Patrick Jaillet},
keywords = {Container terminal, Algorithm with performance guarantee, Container relocation, Online algorithm},
abstract = {This paper introduces and investigates the Online Container Relocation Problem, where containers have to be retrieved from a bay in a container terminal so as to minimize the number of relocations. Unlike the offline version of the problem, the order of container retrievals is revealed one at a time in an online fashion. We analyze the so-called leveling heuristic using the perspective of worst-case competitive analysis of online algorithms and derive its competitive ratio. We then provide some computational experiments which give insights on the actual average performance of the heuristic.}
}