Optimization of container relocation operations in port container terminals
Abstract
The relocation of containers is a crucial operation in container ports all around the world. The Container Relocation Problem (CRP) is focused upon to find a sequence of container retrievals in a defined order from a single yard container bay with a minimum number of relocations. The goal of this paper is to find out if Genetic Algorithm (GA) can give new insights in the problem of solving the CRP. In this paper we focus on the two-dimensional, static, offline and restricted CRP of real-world yard container bays. Four rules are proposed for determining the position of relocated containers. We applied GA to find the best sequence of container retrievals according to these four rules in order to minimize the number of relocations within the bay. The experimental testing was run on a total of 800 different instances with varying bay sizes and number of containers. The given results are compared with the results of different authors using other heuristic methods. The results show that the proposed model solves CRP and achieves near optimal solutions.
First published online 9 December 2019
Keyword : logistics, port, container terminal, stacking area, container relocation problem, discrete optimization, genetic algorithm, performance analysis
How to Cite
Maglić, L., Gulić, M., & Maglić, L. (2020). Optimization of container relocation operations in port container terminals. Transport, 35(1), 37-47. https://doi.org/10.3846/transport.2019.11628
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Avriel, M.; Penn, M.; Shpirer, N.; Witteboon, S. 1998. Stowage planning for container ships to reduce the number of shifts, Annals of Operations Research 76: 55–71. https://doi.org/10.1023/A:1018956823693
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.; Schwarze, S.; Voß, S. 2009. A new binary description of the blocks relocation problem and benefits in a look ahead heuristic, Lecture Notes in Computer Science 5482: 37–48. https://doi.org/10.1007/978-3-642-01009-5_4
Caserta, M.; Voß, S. 2009. A corridor method-based algorithm for the pre-marshalling problem, Lecture Notes in Computer Science 5484: 788–797. https://doi.org/10.1007/978-3-642-01129-0_89
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
Da Silva, M. M.; Erdoğan, G.; Battarra, M.; Strusevich, V. 2018. The block retrieval problem, European Journal of Operational Research 265(3): 931–950. https://doi.org/10.1016/j.ejor.2017.08.048
De Castillo, B.; Daganzo, C. F. 1993. Handling strategies for import containers at marine terminals, Transportation Research Part B: Methodological 27(2): 151–166. https://doi.org/10.1016/0191-2615(93)90005-U
De Koster, R. B. M.; Le-Duc, T.; Yugang, Y. 2008. Optimal storage rack design for a 3-dimensional compact AS/RS, International Journal of Production Research 46(6): 1495–1514. https://doi.org/10.1080/00207540600957795
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
Forster, F.; Bortfeldt, A. 2012. A tree search procedure for the container relocation problem, Computers & Operations Research 39(2): 299–309. https://doi.org/10.1016/j.cor.2011.04.004
Ghomri, L.; Sari, Z.; Guezzen, A.; Sari, T. 2009. Continuous models for single and dual cycle times of a multi aisle automated storage and retrieval system, IFAC Proceedings Volumes 42(4): 1061–1066. https://doi.org/10.3182/20090603-3-ru-2001.0144
Gupta, N.; Nau, D. S. 1992. On the complexity of blocks-world planning, Artificial Intelligence 56(2–3): 223–254. https://doi.org/10.1016/0004-3702(92)90028-V
Hachemi, K.; Alla, H. 2008. Pilotage dynamique d’un système automatisé de stockage/déstockage à convoyeur gravitationnel, Journal Européen des Systèmes Automatisés 42(5): 487–508. (in French).
Hamzaoui, M. A.; Sari, Z. 2015. Optimal dimensions minimizing expected travel time of a single machine flow rack AS/RS, Mechatronics 31: 158–168. https://doi.org/10.1016/j.mechatronics.2014.10.006
Holland, J. H. 1992. Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press. 211 p. https://doi.org/10.7551/mitpress/1090.001.0001
Hu, Y.-H.; Huang, S. Y.; Chen, C.; Hsu, W.-J.; Toh, A. C.; Loh, C. K.; Song, T. 2005. Travel time analysis of a new automated storage and retrieval system, Computers & Operations Research 32(6): 1515–1544. https://doi.org/10.1016/j.cor.2003.11.020
Hussein, M.; Petering, M. E. H. 2012. Genetic algorithm-based simulation optimization of stacking algorithms for yard cranes to reduce fuel consumption at seaport container transshipment terminals, in 2012 IEEE Congress on Evolutionary Computation, 10–15 June 2012, Brisbane, Australia, 1–8. https://doi.org/10.1109/CEC.2012.6256471
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.; 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. 1997. Evaluation of the number of rehandles in container yards, Computers & Industrial Engineering 32(4): 701–711. https://doi.org/10.1016/S0360-8352(97)00024-7
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.; Kim, H. B. 1999. Segregating space allocation models for container inventories in port container terminals, International Journal of Production Economics 59(1–3): 415–423. https://doi.org/10.1016/S0925-5273(98)00028-0
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
Lerher, T.; Potrč, I.; Šraml, M.; Tollazzi, T. 2010. Travel time models for automated warehouses with aisle transferring storage and retrieval machine, European Journal of Operational Research 205(3): 571–583. https://doi.org/10.1016/j.ejor.2010.01.025
Liu, T.; Xu, X.; Qin, H.; Lim, A. 2016. Travel time analysis of the dual command cycle in the split-platform AS/RS with I/O dwell point policy, Flexible Services and Manufacturing Journal 28(3): 442–460. https://doi.org/10.1007/s10696-015-9221-7
Malmborg, C. J. 2002. Conceptualizing tools for autonomous vehicle storage and retrieval systems, International Journal of Production Research 40(8): 1807–1822. https://doi.org/10.1080/00207540110118668
Mitchell, M. 1998. An Introduction to Genetic Algorithms. MIT Press. 221 p.
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
Rei, R.; Pedroso, J. P. 2013. Tree search for the stacking problem, Annals of Operations Research 203(1): 371–388. https://doi.org/10.1007/s10479-012-1186-2
Sari, Z.; Saygin, C.; Ghouali, N. 2005. Travel-time models for flow-rack automated storage and retrieval systems, The International Journal of Advanced Manufacturing Technology 25(9–10): 979–987. https://doi.org/10.1007/s00170-003-1932-3
Sari, Z. 2010. Performance evaluation of flow-rack and unit load automated storage and retrieval systems, in International Science and Technology Conference 2010 (ISTEC 2010): Proceedings Book, 27–29 October 2010, Cyprus, 605–616.
Sculli, D.; Hui, C. F. 1988. Three dimensional stacking of containers, Omega 16(6): 585–594. https://doi.org/10.1016/0305-0483(88)90032-1
Steenken, D.; Voß, S.; Stahlbock, R. 2004. Container terminal operation and operations research – a classification and literature review, OR Spectrum 26(1): 3–49. https://doi.org/10.1007/s00291-003-0157-z
Tanaka, S.; Mizuno, F. 2018. An exact algorithm for the unrestricted block relocation problem, Computers & Operations Research 95: 12–31. https://doi.org/10.1016/j.cor.2018.02.019
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
Tang, L.; Zhao, R.; Liu, J. 2012. Models and algorithms for shuffling problems in steel plants, Naval Research Logistics 59(7): 502–524. https://doi.org/10.1002/nav.21503
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
Van den Berg, J. P. 2002. Analytic expressions for the optimal dwell point in an automated storage/retrieval system, International Journal of Production Economics 76(1): 13–25. https://doi.org/10.1016/S0925-5273(01)00149-9
Wan, Y.-W.; Liu, J.; Tsai, P.-C. 2009. The assignment of storage locations to containers for a container stack, Naval Research Logistics 56(8): 699–713. https://doi.org/10.1002/nav.20373
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.; Hernández, R. 2009. Appling tabu search for minimizing reshuffle operations at container yards, Proceedings of the Eastern Asia Society for Transportation Studies 7: 435–449. https://doi.org/10.11175/eastpro.2009.0.435.0
Xu, X.; Gong, Y.; Fan, X.; Shen, G.; Zou, B. 2018. Travel-time model of dual-command cycles in a 3D compact AS/RS with lower mid-point I/O dwell point policy, International Journal of Production Research 56(4): 1620–1641. https://doi.org/10.1080/00207543.2017.1361049
Yang, J. H.; Kim, K. H. 2006. A grouped storage method for minimizing relocations in block stacking systems, Journal of Intelligent Manufacturing 17(4): 453–463. https://doi.org/10.1007/s10845-005-0018-5
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. 2000. Resource Planning in Container Storage Yard. PhD Thesis. The Hong Kong University of Science and Technology, Hong Kong. 342 p.
Zhang, H.; Guo, S.; Zhu, W.; Lim, A.; Cheang, B. 2010. An investigation of IDA* algorithms for the container relocation problem, Lecture Notes in Computer Science 6096: 31–40. https://doi.org/10.1007/978-3-642-13022-9_4
Zhao, W.; Goodchild, A. V. 2010. The impact of truck arrival information on container terminal rehandling, Transportation Research Part E: Logistics and Transportation Review 46(3): 327–343. https://doi.org/10.1016/j.tre.2009.11.007
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
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.; Schwarze, S.; Voß, S. 2009. A new binary description of the blocks relocation problem and benefits in a look ahead heuristic, Lecture Notes in Computer Science 5482: 37–48. https://doi.org/10.1007/978-3-642-01009-5_4
Caserta, M.; Voß, S. 2009. A corridor method-based algorithm for the pre-marshalling problem, Lecture Notes in Computer Science 5484: 788–797. https://doi.org/10.1007/978-3-642-01129-0_89
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
Da Silva, M. M.; Erdoğan, G.; Battarra, M.; Strusevich, V. 2018. The block retrieval problem, European Journal of Operational Research 265(3): 931–950. https://doi.org/10.1016/j.ejor.2017.08.048
De Castillo, B.; Daganzo, C. F. 1993. Handling strategies for import containers at marine terminals, Transportation Research Part B: Methodological 27(2): 151–166. https://doi.org/10.1016/0191-2615(93)90005-U
De Koster, R. B. M.; Le-Duc, T.; Yugang, Y. 2008. Optimal storage rack design for a 3-dimensional compact AS/RS, International Journal of Production Research 46(6): 1495–1514. https://doi.org/10.1080/00207540600957795
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
Forster, F.; Bortfeldt, A. 2012. A tree search procedure for the container relocation problem, Computers & Operations Research 39(2): 299–309. https://doi.org/10.1016/j.cor.2011.04.004
Ghomri, L.; Sari, Z.; Guezzen, A.; Sari, T. 2009. Continuous models for single and dual cycle times of a multi aisle automated storage and retrieval system, IFAC Proceedings Volumes 42(4): 1061–1066. https://doi.org/10.3182/20090603-3-ru-2001.0144
Gupta, N.; Nau, D. S. 1992. On the complexity of blocks-world planning, Artificial Intelligence 56(2–3): 223–254. https://doi.org/10.1016/0004-3702(92)90028-V
Hachemi, K.; Alla, H. 2008. Pilotage dynamique d’un système automatisé de stockage/déstockage à convoyeur gravitationnel, Journal Européen des Systèmes Automatisés 42(5): 487–508. (in French).
Hamzaoui, M. A.; Sari, Z. 2015. Optimal dimensions minimizing expected travel time of a single machine flow rack AS/RS, Mechatronics 31: 158–168. https://doi.org/10.1016/j.mechatronics.2014.10.006
Holland, J. H. 1992. Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press. 211 p. https://doi.org/10.7551/mitpress/1090.001.0001
Hu, Y.-H.; Huang, S. Y.; Chen, C.; Hsu, W.-J.; Toh, A. C.; Loh, C. K.; Song, T. 2005. Travel time analysis of a new automated storage and retrieval system, Computers & Operations Research 32(6): 1515–1544. https://doi.org/10.1016/j.cor.2003.11.020
Hussein, M.; Petering, M. E. H. 2012. Genetic algorithm-based simulation optimization of stacking algorithms for yard cranes to reduce fuel consumption at seaport container transshipment terminals, in 2012 IEEE Congress on Evolutionary Computation, 10–15 June 2012, Brisbane, Australia, 1–8. https://doi.org/10.1109/CEC.2012.6256471
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.; 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. 1997. Evaluation of the number of rehandles in container yards, Computers & Industrial Engineering 32(4): 701–711. https://doi.org/10.1016/S0360-8352(97)00024-7
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.; Kim, H. B. 1999. Segregating space allocation models for container inventories in port container terminals, International Journal of Production Economics 59(1–3): 415–423. https://doi.org/10.1016/S0925-5273(98)00028-0
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
Lerher, T.; Potrč, I.; Šraml, M.; Tollazzi, T. 2010. Travel time models for automated warehouses with aisle transferring storage and retrieval machine, European Journal of Operational Research 205(3): 571–583. https://doi.org/10.1016/j.ejor.2010.01.025
Liu, T.; Xu, X.; Qin, H.; Lim, A. 2016. Travel time analysis of the dual command cycle in the split-platform AS/RS with I/O dwell point policy, Flexible Services and Manufacturing Journal 28(3): 442–460. https://doi.org/10.1007/s10696-015-9221-7
Malmborg, C. J. 2002. Conceptualizing tools for autonomous vehicle storage and retrieval systems, International Journal of Production Research 40(8): 1807–1822. https://doi.org/10.1080/00207540110118668
Mitchell, M. 1998. An Introduction to Genetic Algorithms. MIT Press. 221 p.
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
Rei, R.; Pedroso, J. P. 2013. Tree search for the stacking problem, Annals of Operations Research 203(1): 371–388. https://doi.org/10.1007/s10479-012-1186-2
Sari, Z.; Saygin, C.; Ghouali, N. 2005. Travel-time models for flow-rack automated storage and retrieval systems, The International Journal of Advanced Manufacturing Technology 25(9–10): 979–987. https://doi.org/10.1007/s00170-003-1932-3
Sari, Z. 2010. Performance evaluation of flow-rack and unit load automated storage and retrieval systems, in International Science and Technology Conference 2010 (ISTEC 2010): Proceedings Book, 27–29 October 2010, Cyprus, 605–616.
Sculli, D.; Hui, C. F. 1988. Three dimensional stacking of containers, Omega 16(6): 585–594. https://doi.org/10.1016/0305-0483(88)90032-1
Steenken, D.; Voß, S.; Stahlbock, R. 2004. Container terminal operation and operations research – a classification and literature review, OR Spectrum 26(1): 3–49. https://doi.org/10.1007/s00291-003-0157-z
Tanaka, S.; Mizuno, F. 2018. An exact algorithm for the unrestricted block relocation problem, Computers & Operations Research 95: 12–31. https://doi.org/10.1016/j.cor.2018.02.019
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
Tang, L.; Zhao, R.; Liu, J. 2012. Models and algorithms for shuffling problems in steel plants, Naval Research Logistics 59(7): 502–524. https://doi.org/10.1002/nav.21503
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
Van den Berg, J. P. 2002. Analytic expressions for the optimal dwell point in an automated storage/retrieval system, International Journal of Production Economics 76(1): 13–25. https://doi.org/10.1016/S0925-5273(01)00149-9
Wan, Y.-W.; Liu, J.; Tsai, P.-C. 2009. The assignment of storage locations to containers for a container stack, Naval Research Logistics 56(8): 699–713. https://doi.org/10.1002/nav.20373
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.; Hernández, R. 2009. Appling tabu search for minimizing reshuffle operations at container yards, Proceedings of the Eastern Asia Society for Transportation Studies 7: 435–449. https://doi.org/10.11175/eastpro.2009.0.435.0
Xu, X.; Gong, Y.; Fan, X.; Shen, G.; Zou, B. 2018. Travel-time model of dual-command cycles in a 3D compact AS/RS with lower mid-point I/O dwell point policy, International Journal of Production Research 56(4): 1620–1641. https://doi.org/10.1080/00207543.2017.1361049
Yang, J. H.; Kim, K. H. 2006. A grouped storage method for minimizing relocations in block stacking systems, Journal of Intelligent Manufacturing 17(4): 453–463. https://doi.org/10.1007/s10845-005-0018-5
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. 2000. Resource Planning in Container Storage Yard. PhD Thesis. The Hong Kong University of Science and Technology, Hong Kong. 342 p.
Zhang, H.; Guo, S.; Zhu, W.; Lim, A.; Cheang, B. 2010. An investigation of IDA* algorithms for the container relocation problem, Lecture Notes in Computer Science 6096: 31–40. https://doi.org/10.1007/978-3-642-13022-9_4
Zhao, W.; Goodchild, A. V. 2010. The impact of truck arrival information on container terminal rehandling, Transportation Research Part E: Logistics and Transportation Review 46(3): 327–343. https://doi.org/10.1016/j.tre.2009.11.007
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