Share:


Optimization of container relocation operations in port container terminals

    Livia Maglić Affiliation
    ; Marko Gulić Affiliation
    ; Lovro Maglić Affiliation

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
Published in Issue
Feb 26, 2020
Abstract Views
2340
PDF Downloads
1290
Creative Commons License

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