IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v103y2017icp17-31.html
   My bibliography  Save this article

Optimizing container relocation operations at container yards with beam search

Author

Listed:
  • Ting, Ching-Jung
  • Wu, Kun-Chih

Abstract

Container relocation problem (CRP) involves the retrieval of all containers from the container yard with a minimum number of relocations. The CRP is an NP-hard problem such that the large-scale instances cannot be solved to optimality by exact solution methods within a reasonable computational time. This article proposes a beam search (BS) algorithm embedded with heuristics to evaluate the problems. The proposed beam search is tested on benchmark instances and compared with other leading heuristics from the literature. Computational results demonstrate that the beam search algorithm is compatible with other heuristics and can obtain good solutions in short time.

Suggested Citation

  • Ting, Ching-Jung & Wu, Kun-Chih, 2017. "Optimizing container relocation operations at container yards with beam search," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 17-31.
    • Handle: RePEc:eee:transe:v:103:y:2017:i:c:p:17-31
    DOI: 10.1016/j.tre.2017.04.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554516308134
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2017.04.010?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jin, Bo & Zhu, Wenbin & Lim, Andrew, 2015. "Solving the container relocation problem by an improved greedy look-ahead heuristic," European Journal of Operational Research, Elsevier, vol. 240(3), pages 837-847.
    2. Petering, Matthew E.H. & Hussein, Mazen I., 2013. "A new mixed integer program and extended look-ahead heuristic algorithm for the block relocation problem," European Journal of Operational Research, Elsevier, vol. 231(1), pages 120-130.
    3. Sabuncuoglu, I. & Bayiz, M., 1999. "Job shop scheduling with beam search," European Journal of Operational Research, Elsevier, vol. 118(2), pages 390-412, October.
    4. Lehnfeld, Jana & Knust, Sigrid, 2014. "Loading, unloading and premarshalling of stacks in storage areas: Survey and classification," European Journal of Operational Research, Elsevier, vol. 239(2), pages 297-312.
    5. Carlo, Héctor J. & Vis, Iris F.A. & Roodbergen, Kees Jan, 2014. "Storage yard operations in container terminals: Literature overview, trends, and research directions," European Journal of Operational Research, Elsevier, vol. 235(2), pages 412-430.
    6. Caserta, Marco & Schwarze, Silvia & Voß, Stefan, 2012. "A mathematical formulation and complexity considerations for the blocks relocation problem," European Journal of Operational Research, Elsevier, vol. 219(1), pages 96-104.
    7. Sabuncuoglu, Ihsan & Gocgun, Yasin & Erel, Erdal, 2008. "Backtracking and exchange of information: Methods to enhance a beam search algorithm for assembly line scheduling," European Journal of Operational Research, Elsevier, vol. 186(3), pages 915-930, May.
    8. Bortfeldt, Andreas & Forster, Florian, 2012. "A tree search procedure for the container pre-marshalling problem," European Journal of Operational Research, Elsevier, vol. 217(3), pages 531-540.
    9. Katta G. Murty & Yat-wah Wan & Jiyin Liu & Mitchell M. Tseng & Edmond Leung & Kam-Keung Lai & Herman W. C. Chiu, 2005. "Hongkong International Terminals Gains Elastic Capacity Using a Data-Intensive Decision-Support System," Interfaces, INFORMS, vol. 35(1), pages 61-75, February.
    10. Zhao, Wenjuan & Goodchild, Anne V., 2010. "The impact of truck arrival information on container terminal rehandling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(3), pages 327-343, May.
    11. Kim, Kap Hwan & Park, Young Man & Ryu, Kwang-Ryul, 2000. "Deriving decision rules to locate export containers in container yards," European Journal of Operational Research, Elsevier, vol. 124(1), pages 89-101, July.
    12. Carlo, Héctor J. & Vis, Iris F.A. & Roodbergen, Kees Jan, 2014. "Transport operations in container terminals: Literature overview, trends, research directions and classification scheme," European Journal of Operational Research, Elsevier, vol. 236(1), pages 1-13.
    13. Ji, Mingjun & Guo, Wenwen & Zhu, Huiling & Yang, Yongzhi, 2015. "Optimization of loading sequence and rehandling strategy for multi-quay crane operations in container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 80(C), pages 1-19.
    14. Hwan Kim, Kap & Bae Kim, Hong, 1999. "Segregating space allocation models for container inventories in port container terminals," International Journal of Production Economics, Elsevier, vol. 59(1-3), pages 415-423, March.
    15. Zhang, Canrong & Chen, Weiwei & Shi, Leyuan & Zheng, Li, 2010. "A note on deriving decision rules to locate export containers in container yards," European Journal of Operational Research, Elsevier, vol. 205(2), pages 483-485, September.
    16. Lixin Tang & Wei Jiang & Jiyin Liu & Yun Dong, 2015. "Research into container reshuffling and stacking problems in container terminal yards," IISE Transactions, Taylor & Francis Journals, vol. 47(7), pages 751-766, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jin, Bo & Tanaka, Shunji, 2023. "An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules," European Journal of Operational Research, Elsevier, vol. 304(2), pages 494-514.
    2. Kap Hwan Kim & Sanghyuk Yi, 2021. "Utilizing information sources to reduce relocation of inbound containers," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 23(4), pages 726-749, December.
    3. Feng, Yuanjun & Song, Dong-Ping & Li, Dong & Zeng, Qingcheng, 2020. "The stochastic container relocation problem with flexible service policies," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 116-163.
    4. Damla Kizilay & Deniz Türsel Eliiyi, 2021. "A comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 1-42, March.
    5. Azab, Ahmed & Morita, Hiroshi, 2022. "Coordinating truck appointments with container relocations and retrievals in container terminals under partial appointments information," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 160(C).
    6. Jiménez-Piqueras, Celia & Ruiz, Rubén & Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon, 2023. "A constraint programming approach for the premarshalling problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 668-678.
    7. Azab, Ahmed & Morita, Hiroshi, 2022. "The block relocation problem with appointment scheduling," European Journal of Operational Research, Elsevier, vol. 297(2), pages 680-694.
    8. Mar-Ortiz, Julio & Castillo-García, Norberto & Gracia, María D., 2020. "A decision support system for a capacity management problem at a container terminal," International Journal of Production Economics, Elsevier, vol. 222(C).
    9. Feng, Yuanjun & Song, Dong-Ping & Li, Dong & Xie, Ying, 2022. "Service fairness and value of customer information for the stochastic container relocation problem under flexible service policy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    10. Tanaka, Shunji & Voß, Stefan, 2019. "An exact algorithm for the block relocation problem with a stowage plan," European Journal of Operational Research, Elsevier, vol. 279(3), pages 767-781.
    11. Tanaka, Shunji & Voß, Stefan, 2022. "An exact approach to the restricted block relocation problem based on a new integer programming formulation," European Journal of Operational Research, Elsevier, vol. 296(2), pages 485-503.
    12. Zhang, Canrong & Guan, Hao & Yuan, Yifei & Chen, Weiwei & Wu, Tao, 2020. "Machine learning-driven algorithms for the container relocation problem," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 102-131.
    13. Facchini, F. & Digiesi, S. & Mossa, G., 2020. "Optimal dry port configuration for container terminals: A non-linear model for sustainable decision making," International Journal of Production Economics, Elsevier, vol. 219(C), pages 164-178.
    14. Zhou, Chenhao & Wang, Wencheng & Li, Haobin, 2020. "Container reshuffling considered space allocation problem in container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    15. Andresson Silva Firmino & Ricardo Martins Abreu Silva & Valéria Cesário Times, 2019. "A reactive GRASP metaheuristic for the container retrieval problem to reduce crane’s working time," Journal of Heuristics, Springer, vol. 25(2), pages 141-173, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gharehgozli, Amir & Zaerpour, Nima, 2018. "Stacking outbound barge containers in an automated deep-sea terminal," European Journal of Operational Research, Elsevier, vol. 267(3), pages 977-995.
    2. Feng, Yuanjun & Song, Dong-Ping & Li, Dong & Zeng, Qingcheng, 2020. "The stochastic container relocation problem with flexible service policies," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 116-163.
    3. Jin, Bo & Tanaka, Shunji, 2023. "An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules," European Journal of Operational Research, Elsevier, vol. 304(2), pages 494-514.
    4. Huiling Zhu & Mingjun Ji & Wenwen Guo & Qingbin Wang & Yongzhi Yang, 2019. "Mathematical formulation and heuristic algorithm for the block relocation and loading problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(4), pages 333-351, June.
    5. de Melo da Silva, Marcos & Toulouse, Sophie & Wolfler Calvo, Roberto, 2018. "A new effective unified model for solving the Pre-marshalling and Block Relocation Problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 40-56.
    6. Gharehgozli, A.H. & Roy, D. & de Koster, M.B.M., 2014. "Sea Container Terminals," ERIM Report Series Research in Management ERS-2014-009-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    7. Ku, Dusan & Arthanari, Tiru S., 2016. "Container relocation problem with time windows for container departure," European Journal of Operational Research, Elsevier, vol. 252(3), pages 1031-1039.
    8. Zweers, Bernard G. & Bhulai, Sandjai & van der Mei, Rob D., 2020. "Optimizing pre-processing and relocation moves in the Stochastic Container Relocation Problem," European Journal of Operational Research, Elsevier, vol. 283(3), pages 954-971.
    9. Lehnfeld, Jana & Knust, Sigrid, 2014. "Loading, unloading and premarshalling of stacks in storage areas: Survey and classification," European Journal of Operational Research, Elsevier, vol. 239(2), pages 297-312.
    10. Zhang, Canrong & Guan, Hao & Yuan, Yifei & Chen, Weiwei & Wu, Tao, 2020. "Machine learning-driven algorithms for the container relocation problem," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 102-131.
    11. Jovanovic, Raka & Tuba, Milan & Voß, Stefan, 2019. "An efficient ant colony optimization algorithm for the blocks relocation problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 78-90.
    12. Feng, Yuanjun & Song, Dong-Ping & Li, Dong, 2022. "Smart stacking for import containers using customer information at automated container terminals," European Journal of Operational Research, Elsevier, vol. 301(2), pages 502-522.
    13. Tanaka, Shunji & Voß, Stefan, 2019. "An exact algorithm for the block relocation problem with a stowage plan," European Journal of Operational Research, Elsevier, vol. 279(3), pages 767-781.
    14. Kap Hwan Kim & Sanghyuk Yi, 2021. "Utilizing information sources to reduce relocation of inbound containers," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 23(4), pages 726-749, December.
    15. Ruiyou Zhang & Shixin Liu & Herbert Kopfer, 2016. "Tree search procedures for the blocks relocation problem with batch moves," Flexible Services and Manufacturing Journal, Springer, vol. 28(3), pages 397-424, September.
    16. Gharehgozli, Amir & Yu, Yugang & de Koster, René & Du, Shaofu, 2019. "Sequencing storage and retrieval requests in a container block with multiple open locations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 261-284.
    17. Gharehgozli, Amir Hossein & Vernooij, Floris Gerardus & Zaerpour, Nima, 2017. "A simulation study of the performance of twin automated stacking cranes at a seaport container terminal," European Journal of Operational Research, Elsevier, vol. 261(1), pages 108-128.
    18. Zehendner, Elisabeth & Feillet, Dominique & Jaillet, Patrick, 2017. "An algorithm with performance guarantee for the Online Container Relocation Problem," European Journal of Operational Research, Elsevier, vol. 259(1), pages 48-62.
    19. Galle, Virgile & Barnhart, Cynthia & Jaillet, Patrick, 2018. "A new binary formulation of the restricted Container Relocation Problem based on a binary encoding of configurations," European Journal of Operational Research, Elsevier, vol. 267(2), pages 467-477.
    20. Boge, Sven & Goerigk, Marc & Knust, Sigrid, 2020. "Robust optimization for premarshalling with uncertain priority classes," European Journal of Operational Research, Elsevier, vol. 287(1), pages 191-210.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:103:y:2017:i:c:p:17-31. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.