IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v25y2019i2d10.1007_s10732-018-9390-0.html
   My bibliography  Save this article

A reactive GRASP metaheuristic for the container retrieval problem to reduce crane’s working time

Author

Listed:
  • Andresson Silva Firmino

    (Universidade Federal de Pernambuco)

  • Ricardo Martins Abreu Silva

    (Universidade Federal de Pernambuco)

  • Valéria Cesário Times

    (Universidade Federal de Pernambuco)

Abstract

The container retrieval problem (CRP) is a very important issue for container terminals. The CRP seeks to find an optimal sequence of operations for the crane to retrieve all the containers from the bay according to a predefined order. An optimal sequence of operations is obtained by either reducing the number of container relocations or reducing any kind of working cost performed by the crane, i.e., energy, time, etc. Although the former is the main objective function discussed in the literature, minimizing the number of relocations does not ensure the solution with the minimal working cost, as evidenced in this paper. Therefore, in this study, a crane’s trajectory is defined to better measure the crane’s working cost, and the optimization goal is to minimize the crane’s working time considering the crane’s trajectory. Moreover, it proposes exact methods and a reactive GRASP algorithm for the CRP. The experimental results show that the proposed algorithm is able to provide better solutions for both the number of container relocations and the crane’s working time, when compared to heuristic approaches in the recent literature.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joheur:v:25:y:2019:i:2:d:10.1007_s10732-018-9390-0
    DOI: 10.1007/s10732-018-9390-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-018-9390-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-018-9390-0?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. Florian Forster & Andreas Bortfeldt, 2012. "A tree search heuristic for the container retrieval problem," Operations Research Proceedings, in: Diethard Klatte & Hans-Jakob Lüthi & Karl Schmedders (ed.), Operations Research Proceedings 2011, edition 127, pages 257-262, Springer.
    2. Diethard Klatte & Hans-Jakob Lüthi & Karl Schmedders (ed.), 2012. "Operations Research Proceedings 2011," Operations Research Proceedings, Springer, edition 127, number 978-3-642-29210-1, March.
    3. 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.
    4. 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.
    5. 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.
    6. M. Hakan Akyüz & Chung‐Yee Lee, 2014. "A mathematical formulation and efficient heuristics for the dynamic container relocation problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(2), pages 101-118, March.
    7. Yat‐wah Wan & Jiyin Liu & Pei‐Chun Tsai, 2009. "The assignment of storage locations to containers for a container stack," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(8), pages 699-713, December.
    8. 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.
    9. Silva, Marcos de Melo da & Erdoğan, Güneş & Battarra, Maria & Strusevich, Vitaly, 2018. "The Block Retrieval Problem," European Journal of Operational Research, Elsevier, vol. 265(3), pages 931-950.
    10. 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.
    11. 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.
    12. 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.
    13. Zehendner, Elisabeth & Caserta, Marco & Feillet, Dominique & Schwarze, Silvia & Voß, Stefan, 2015. "An improved mathematical formulation for the blocks relocation problem," European Journal of Operational Research, Elsevier, vol. 245(2), pages 415-422.
    14. B Casey & E Kozan, 2012. "Optimising container storage processes at multimodal terminals," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(8), pages 1126-1142, August.
    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. 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.
    3. Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon & Ruiz, Rubén & Tierney, Kevin, 2020. "Minimizing crane times in pre-marshalling problems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 137(C).
    4. 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.
    5. Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon & Parreño, Francisco, 2022. "A beam search algorithm for minimizing crane times in premarshalling problems," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1063-1078.
    6. 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.
    7. Lüer-Villagra, Armin & Marianov, Vladimir & Eiselt, H.A. & Méndez-Vogel, Gonzalo, 2022. "The leader multipurpose shopping location problem," European Journal of Operational Research, Elsevier, vol. 302(2), pages 470-481.
    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.

    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. 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. 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. 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.
    4. 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).
    5. Azab, Ahmed & Morita, Hiroshi, 2022. "The block relocation problem with appointment scheduling," European Journal of Operational Research, Elsevier, vol. 297(2), pages 680-694.
    6. Galle, Virgile & Barnhart, Cynthia & Jaillet, Patrick, 2018. "Yard Crane Scheduling for container storage, retrieval, and relocation," European Journal of Operational Research, Elsevier, vol. 271(1), pages 288-316.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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).
    13. 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.
    14. 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.
    15. Huiling Zhu, 2022. "Integrated Containership Stowage Planning: A Methodology for Coordinating Containership Stowage Plan and Terminal Yard Operations," Sustainability, MDPI, vol. 14(20), pages 1-18, October.
    16. 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.
    17. 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.
    18. 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.
    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. Raka Jovanovic & Shunji Tanaka & Tatsushi Nishi & Stefan Voß, 2019. "A GRASP approach for solving the Blocks Relocation Problem with Stowage Plan," Flexible Services and Manufacturing Journal, Springer, vol. 31(3), pages 702-729, September.

    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:spr:joheur:v:25:y:2019:i:2:d:10.1007_s10732-018-9390-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.