@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.}
}

@article{CASERTA201296,
title = {A mathematical formulation and complexity considerations for the blocks relocation problem},
journal = {European Journal of Operational Research},
volume = {219},
number = {1},
pages = {96-104},
year = {2012},
issn = {0377-2217},
doi = {https://doi.org/10.1016/j.ejor.2011.12.039},
url = {https://www.sciencedirect.com/science/article/pii/S0377221711011337},
author = {Marco Caserta and Silvia Schwarze and Stefan Voß},
keywords = {Integer programming, Blocks relocation, Logistics, Heuristics},
abstract = {The blocks relocation problem (BRP) may be defined as follows: given a set of homogeneous blocks stored in a two-dimensional stock, which relocations are necessary to retrieve the blocks from the stock in a predefined order while minimizing the number of those relocations? In this paper, we first prove NP-hardness of the BRP as well as a special case, closing open research questions. Moreover, we propose different solution approaches. First, a mathematical model is presented that provides optimal solutions to the general BRP in cases where instances are small. To overcome such limitation, some realistic assumption taken from the literature is introduced, leading to the definition of a binary linear programming model. In terms of computational time, this approach is reasonably fast to be used to solve medium-sized instances. In addition, we propose a simple heuristic based upon a set of relocation rules. This heuristic is used to generate “good” quality solutions for larger instances in very short computational time, and, consequently, is proposed for tackling problem instances where solutions are required (almost) immediately. Solution quality of the heuristic is measured against optimal solutions obtained using a state-of-the-art commercial solver and both of them are compared with reference results from literature.}
}

@article{2f72235d-ba9f-3f5d-9c63-8a9ceb147049,
 ISSN = {00411655, 15265447},
 URL = {https://www.jstor.org/stable/48748022},
 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.},
 author = {V. Galle and V. H. Manshadi and S. Borjian Boroujeni and C. Barnhart and P. Jaillet},
 journal = {Transportation Science},
 number = {5},
 pages = {pp. 1035--1058},
 publisher = {INFORMS},
 title = {The Stochastic Container Relocation Problem},
 urldate = {2025-08-01},
 volume = {52},
 year = {2018}
}

@misc{borjian2015containerrelocationproblemapproximation,
      title={Container Relocation Problem: Approximation, Asymptotic, and Incomplete Information}, 
      author={Setareh Borjian and Virgile Galle and Vahideh H. Manshadi and Cynthia Barnhart and Patrick Jaillet},
      year={2015},
      eprint={1505.04229},
      archivePrefix={arXiv},
      primaryClass={cs.DS},
      url={https://arxiv.org/abs/1505.04229}, 
}

@article{JIN2023494,
title = {An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules},
journal = {European Journal of Operational Research},
volume = {304},
number = {2},
pages = {494-514},
year = {2023},
issn = {0377-2217},
doi = {https://doi.org/10.1016/j.ejor.2022.04.006},
url = {https://www.sciencedirect.com/science/article/pii/S0377221722002946},
author = {Bo Jin and Shunji Tanaka},
keywords = {Combinatorial optimization, Container relocation problem, Branch-and-bound, Lower bounds, Dominance rules},
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.}
}

@article{LERSTEAU2022108529,
title = {A survey of optimization methods for Block Relocation and PreMarshalling Problems},
journal = {Computers & Industrial Engineering},
volume = {172},
pages = {108529},
year = {2022},
issn = {0360-8352},
doi = {https://doi.org/10.1016/j.cie.2022.108529},
url = {https://www.sciencedirect.com/science/article/pii/S0360835222005381},
author = {Charly Lersteau and Weiming Shen},
keywords = {Optimization methods, Block relocation, Premarshalling, Container stacking},
abstract = {Problems of stacking items or goods occur in a plenty of applications, such as container terminals, warehouses, and steel plants. A lot of research has been done in this area in recent years. In this survey, we provide an overview of the Block Relocation Problem (BRP) and the PreMarshalling Problem (PMP) and review optimization methods for these two problems. Due to common properties between these problems, solutions and methods applicable to one problem can often be applied to the other, and vice-versa. We distinguish four categories of optimization methods and propose future directions for each of them.}
}

@article{FENG2022102921,
title = {Service fairness and value of customer information for the stochastic container relocation problem under flexible service policy},
journal = {Transportation Research Part E: Logistics and Transportation Review},
volume = {167},
pages = {102921},
year = {2022},
issn = {1366-5545},
doi = {https://doi.org/10.1016/j.tre.2022.102921},
url = {https://www.sciencedirect.com/science/article/pii/S1366554522002988},
author = {Yuanjun Feng and Dong-Ping Song and Dong Li and Ying Xie},
keywords = {OR in port operations, Stochastic container relocation, Truck service policy, Service fairness, Value of information},
abstract = {This paper considers the optimization of service efficiency and service fairness in a Stochastic Container Relocation Problem (SCRP) under flexible service policies at a container terminal. Under the flexible service policy, the external trucks arriving within the same time window can be served out of sequence, which may raise a concern of service fairness. We incorporate the concept of service fairness into the SCRP in two phases. In phase 1, we propose a multiple sub-time windows-based flexible service policy, under which each time window will be divided into multiple sub-time windows and the flexible service policy is only applied to each individual sub-time window. In phase 2, the SCRP is formulated as a dynamic programming model with two lexicographically ordered objectives representing both relocation efficiency and service fairness, which is solved via a hierarchical iterative approach. In addition, we investigate whether the information of trucks’ arrival probability over the time window (which represents the customer preference information) would add value to the terminal operators. Extensive computational experiments are conducted to evaluate the impacts of the number of sub-time windows and to examine the impacts and value of customer preference information in various scenarios. The results show interesting trade-offs between efficiency and fairness. As the number of sub-time windows increases, the service fairness is generally improving (but not guaranteed) while the expected number of relocations is increasing. It is found that the customer preference information can be valuable in some circumstances, especially when each truck indicates a certain arrival sub-time window.}
}

@article{Corridor,
author = {Caserta, Marco and Voss, Stefan and Sniedovich, Moshe},
year = {2011},
month = {01},
pages = {915-929},
title = {Applying the corridor method to a blocks relocation problem},
volume = {33},
journal = {Operations Research-Spektrum},
doi = {10.1007/s00291-009-0176-5}
}

@article{FIAT1991685,
title = {Competitive paging algorithms},
journal = {Journal of Algorithms},
volume = {12},
number = {4},
pages = {685-699},
year = {1991},
issn = {0196-6774},
doi = {https://doi.org/10.1016/0196-6774(91)90041-V},
url = {https://www.sciencedirect.com/science/article/pii/019667749190041V},
author = {Amos Fiat and Richard M Karp and Michael Luby and Lyle A McGeoch and Daniel D Sleator and Neal E Young},
abstract = {The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for the paging problem. We prove that its expected cost on any sequence of requests is within a factor of 2Hk of optimum. (Where Hk is the kth harmonic number, which is roughly ln k.) The best such factor that can be achieved is Hk. This is in contrast to deterministic algorithms, which cannot be guaranteed to be within a factor smaller than k of optimum. An alternative to comparing an on-line algorithm with the optimum off-line algorithm is the idea of comparing it to several other on-line algorithms. We have obtained results along these lines for the paging problem. Given a set of on-line algorithms and a set of appropriate constants, we describe a way of constructing another on-line algorithm whose performance is within the appropriate constant factor of each algorithm in the set.}
}

@article{SILVA2018931,
title = {The Block Retrieval Problem},
journal = {European Journal of Operational Research},
volume = {265},
number = {3},
pages = {931-950},
year = {2018},
issn = {0377-2217},
doi = {https://doi.org/10.1016/j.ejor.2017.08.048},
url = {https://www.sciencedirect.com/science/article/pii/S0377221717307798},
author = {Marcos de Melo da Silva and Güneş Erdoğan and Maria Battarra and Vitaly Strusevich},
keywords = {Combinatorial optimization, Container terminals, Import containers, Branch-and-bound},
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.}
}