Share:


A three-stage heuristic for optimizing container relocations in maritime container terminals

    Qianwen Zhu Affiliation
    ; Bo Jin Affiliation

Abstract

The Container Relocation Problem (CRP) is one of the most important optimization problems in maritime container terminals. The objective is to minimize the number of relocation operations for retrieving containers in a sequence. If the container to be retrieved next is not at the top of a stack, unproductive relocations have to be carried out. Due to the large number of containers handled by busy terminals, a slight reduction in relocation rates can result in significant savings in operating costs. Most of the existing heuristics make relocation decisions for the blocking containers one by one, based on simple indicators. In this article, we propose a Three-Stage Heuristic (3SH) that extends the decision horizon to multiple containers to achieve a higher-quality solution. Computational experiments are conducted on 3 sets of benchmark instances, and the results show that the proposed heuristic outperforms the state-of-the-art heuristics documented in the research literature.

Keyword : logistics, optimization, maritime container terminal, container relocation problem, heuristic

How to Cite
Zhu, Q., & Jin, B. (2024). A three-stage heuristic for optimizing container relocations in maritime container terminals. Transport, 39(2), 146–160. https://doi.org/10.3846/transport.2024.21668
Published in Issue
Oct 29, 2024
Abstract Views
52
PDF Downloads
33
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

References

Bacci, T.; Mattia, S.; Ventura, P. 2020. A branch-and-cut algorithm for the restricted block relocation problem, European Journal of Operational Research 287(2): 452–459. https://doi.org/10.1016/j.ejor.2020.05.029

Bacci, T.; Mattia, S.; Ventura, P. 2019. The bounded beam search algorithm for the block relocation problem, Computers & Operations Research 103: 252–264. https://doi.org/10.1016/j.cor.2018.11.008

Carlo, H. J.; Vis, I. F. A.; Roodbergen, K. J. 2014. Storage yard operations in container terminals: literature overview, trends, and research directions, European Journal of Operational Research 235(2), 412–430. https://doi.org/10.1016/j.ejor.2013.10.054

Caserta, M.; Schwarze, S.; Voß, S. 2012. A mathematical formulation and complexity considerations for the blocks relocation problem, European Journal of Operational Research 219(1): 96–104. https://doi.org/10.1016/j.ejor.2011.12.039

Caserta, M.; Voß, S.; Sniedovich, M. 2011. Applying the corridor method to a blocks relocation problem, OR Spectrum 33(4): 915–929. https://doi.org/10.1007/s00291-009-0176-5

Expósito-Izquierdo, C.; Melián-Batista, B.; Moreno-Vega, J. M. 2014. A domain-specific knowledge-based heuristic for the blocks relocation problem, Advanced Engineering Informatics 28(4): 327–343. https://doi.org/10.1016/j.aei.2014.03.003

Expósito-Izquierdo, C.; Melián-Batista, B.; Moreno-Vega, J. M. 2015. An exact approach for the blocks relocation problem, Expert Systems with Applications 42(17–18): 6408–6422. https://doi.org/10.1016/j.eswa.2015.04.021

Feillet, D.; Parragh, S. N.; Tricoire, F. 2019. A local-search based heuristic for the unrestricted block relocation problem, Computers & Operations Research 108: 44–56. https://doi.org/10.1016/j.cor.2019.04.006

Galle, V.; Barnhart, C.; Jaillet, P. 2018. A new binary formulation of the restricted container relocation problem based on a binary encoding of configurations, European Journal of Operational Research 267(2): 467–477. https://doi.org/10.1016/j.ejor.2017.11.053

Jin, B.; Tanaka, S. 2023. An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules, European Journal of Operational Research 304(2): 494–514. https://doi.org/10.1016/j.ejor.2022.04.006

Jin, B.; Zhu, W.; Lim, A. 2015. Solving the container relocation problem by an improved greedy look-ahead heuristic, European Journal of Operational Research 240(3): 837–847. https://doi.org/10.1016/j.ejor.2014.07.038

Jovanovic, R.; Tuba, M.; Voß, S. 2019. An efficient ant colony optimization algorithm for the blocks relocation problem, European Journal of Operational Research 274(1): 78–90. https://doi.org/10.1016/j.ejor.2018.09.038

Jovanovic, R.; Voß, S. 2014. A chain heuristic for the blocks relocation problem, Computers & Industrial Engineering 75: 79–86. https://doi.org/10.1016/j.cie.2014.06.010

Kim, K. H.; Hong, G.-P. 2006. A heuristic rule for relocating blocks, Computers & Operations Research, 33(4): 940–954. https://doi.org/10.1016/j.cor.2004.08.005

Kim, K. H.; Park, Y. M.; Ryu, K.-R. 2000. Deriving decision rules to locate export containers in container yards, European Journal of Operational Research 124(1): 89–101. https://doi.org/10.1016/S0377-2217(99)00116-2

Ku, D.; Arthanari, T. S. 2016. On the abstraction method for the container relocation problem, Computers & Operations Research 68: 110–122. https://doi.org/10.1016/j.cor.2015.11.006

Lee, Y.; Hsu, N.-Y. 2007. An optimization model for the container pre-marshalling problem, Computers & Operations Research 34(11): 3295–3313. https://doi.org/10.1016/j.cor.2005.12.006

Lehnfeld, J.; Knust, S. 2014. Loading, unloading and premarshalling of stacks in storage areas: survey and classification, European Journal of Operational Research 239(2): 297–312. https://doi.org/10.1016/j.ejor.2014.03.011

Lersteau, C.; Shen, W. 2022. A survey of optimization methods for block relocation and premarshalling problems, Computers & Industrial Engineering 172: 108529. https://doi.org/10.1016/j.cie.2022.108529

Maglić, Li.; Gulić, M.; Maglić, Lo. 2020. Optimization of container relocation operations in port container terminals, Transport 35(1): 37–47. https://doi.org/10.3846/transport.2019.11628

Murty, K. G.; Wan, Y.-W.; Liu, J.; Tseng, M. M.; Leung, E.; Lai, K.-K.; Chiu, H. W. C. 2005. Hongkong international terminals gains elastic capacity using a data-intensive decision-support system, Interfaces 35(1): 61–75. https://doi.org/10.1287/inte.1040.0120

Petering, M. E. H.; Hussein, M. I. 2013. A new mixed integer program and extended look-ahead heuristic algorithm for the block relocation problem, European Journal of Operational Research 231(1): 120–130. https://doi.org/10.1016/j.ejor.2013.05.037

Quispe, K. E. Y.; Lintzmayer, C. N.; Xavier, E. C. 2018. An exact algorithm for the Blocks Relocation Problem with new lower bounds, Computers & Operations Research 99: 206–217. https://doi.org/10.1016/j.cor.2018.06.021

Tanaka, S.; Takii, K. 2016. A faster branch-and-bound algorithm for the block relocation problem, IEEE Transactions on Automation Science and Engineering 13(1): 181–190. https://doi.org/10.1109/tase.2015.2434417

Tanaka, S.; Voß, S. 2022. An exact approach to the restricted block relocation problem based on a new integer programming formulation, European Journal of Operational Research 296(2): 485–503. https://doi.org/10.1016/j.ejor.2021.03.062

Ting, C.-J.; Wu, K.-C. 2017. Optimizing container relocation operations at container yards with beam search, Transportation Research Part E: Logistics and Transportation Review 103: 17–31. https://doi.org/10.1016/j.tre.2017.04.010

Tricoire, F.; Scagnetti, J.; Beham, A. 2018. New insights on the block relocation problem, Computers & Operations Research 89: 127–139. https://doi.org/10.1016/j.cor.2017.08.010

Ünlüyurt, T.; Aydın, C. 2012. Improved rehandling strategies for the container retrieval process, Journal of Advanced Transportation 46(4): 378–393. https://doi.org/10.1002/atr.1193

Wu, K.-C.; Ting, C.-J. 2010. A beam search algorithm for minimizing reshuffle operations at container yards, in LOGMS 2010: the 1st International Conference on Logistics and Maritime Systems, 15–17 September 2010, Busan, Korea, 703–710.

Wu, K.-C.; Ting, C. J. 2012. Heuristic approaches for minimizing reshuffle operations at container yard, in Proceedings of the 13th Asia Pacific Industrial Engineering & Management Systems Conference, 2–5 December 2012, Phuket, Thailand, 1407–1451.

Zehendner, E.; Caserta, M.; Feillet, D.; Schwarze, S.; Voß, S. 2015. An improved mathematical formulation for the blocks relocation problem, European Journal of Operational Research 245(2): 415–422. https://doi.org/10.1016/j.ejor.2015.03.032

Zhang, C.; Guan, H.; Yuan, Y.; Chen, W.; Wu, T. 2020. Machine learning-driven algorithms for the container relocation problem, Transportation Research Part B: Methodological 139: 102–131. https://doi.org/10.1016/j.trb.2020.05.017

Zhu, W.; Qin, H.; Lim, A.; Zhang, H. 2012. Iterative deepening A* algorithms for the container relocation problem, IEEE Transactions on Automation Science and Engineering 9(4): 710–722. https://doi.org/10.1109/tase.2012.2198642