A three-stage heuristic for optimizing container relocations in maritime container terminals
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
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
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