IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v256y2017i1p90-101.html
   My bibliography  Save this article

A feasibility-based heuristic for the container pre-marshalling problem

Author

Listed:
  • Wang, Ning
  • Jin, Bo
  • Zhang, Zizhen
  • Lim, Andrew

Abstract

This paper addresses the container pre-marshalling problem (CPMP) which rearranges containers inside a storage bay to a desired layout. By far, target-driven algorithms have relatively good performance among all algorithms; they have two key components: first, containers are rearranged to their desired slots one by one in a certain order; and second, rearranging one container is completed by a sequence of movements. Our paper improves the performance of the target-driven algorithm from both aspects. The proposed heuristic determines the order of container rearrangements by the concepts of state feasibility, container stability, dead-end avoidance and tier-protection proposed in this paper. In addition, we improve the efficiency of performing container rearrangements by discriminating different task types. Computational experiments showcase that the performance of the proposed heuristic is considerable.

Suggested Citation

  • Wang, Ning & Jin, Bo & Zhang, Zizhen & Lim, Andrew, 2017. "A feasibility-based heuristic for the container pre-marshalling problem," European Journal of Operational Research, Elsevier, vol. 256(1), pages 90-101.
    • Handle: RePEc:eee:ejores:v:256:y:2017:i:1:p:90-101
    DOI: 10.1016/j.ejor.2016.05.061
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716304155
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.05.061?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. Bierwirth, Christian & Meisel, Frank, 2015. "A follow-up survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 244(3), pages 675-689.
    3. 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.
    4. 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.
    5. Kap Hwan Kim & Hoon Lee, 2015. "Container Terminal Operation: Current Trends and Future Challenges," International Series in Operations Research & Management Science, in: Chung-Yee Lee & Qiang Meng (ed.), Handbook of Ocean Container Transport Logistics, edition 127, chapter 2, pages 43-73, Springer.
    6. 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.
    7. Wang, Ning & Jin, Bo & Lim, Andrew, 2015. "Target-guided algorithms for the container pre-marshalling problem," Omega, Elsevier, vol. 53(C), pages 67-77.
    8. 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.
    9. Lee, Yusin & Chao, Shih-Liang, 2009. "A neighborhood search heuristic for pre-marshalling export containers," European Journal of Operational Research, Elsevier, vol. 196(2), pages 468-475, 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. 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).
    3. 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.
    4. 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.
    5. Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon & Ruiz, Rubén, 2019. "Integer programming models for the pre-marshalling problem," European Journal of Operational Research, Elsevier, vol. 274(1), pages 142-154.
    6. 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.
    7. 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.
    8. 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.
    9. Tanaka, Shunji & Tierney, Kevin, 2018. "Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm," European Journal of Operational Research, Elsevier, vol. 264(1), pages 165-180.
    10. Tanaka, Shunji & Tierney, Kevin & Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon & Ruiz, Rubén, 2019. "A branch and bound approach for large pre-marshalling problems," European Journal of Operational Research, Elsevier, vol. 278(1), pages 211-225.

    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. 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.
    3. 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.
    4. 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.
    5. 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.
    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. 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.
    8. 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.
    9. Kevin Tierney & Dario Pacino & Stefan Voß, 2017. "Solving the pre-marshalling problem to optimality with A* and IDA," Flexible Services and Manufacturing Journal, Springer, vol. 29(2), pages 223-259, June.
    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. 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).
    12. 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.
    13. Raeesi, Ramin & Sahebjamnia, Navid & Mansouri, S. Afshin, 2023. "The synergistic effect of operational research and big data analytics in greening container terminal operations: A review and future directions," European Journal of Operational Research, Elsevier, vol. 310(3), pages 943-973.
    14. Lennart Zey & Dirk Briskorn & Nils Boysen, 2022. "Twin-crane scheduling during seaside workload peaks with a dedicated handshake area," Journal of Scheduling, Springer, vol. 25(1), pages 3-34, February.
    15. 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.
    16. 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.
    17. Tanaka, Shunji & Tierney, Kevin, 2018. "Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm," European Journal of Operational Research, Elsevier, vol. 264(1), pages 165-180.
    18. 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.
    19. Park, Jaehun & Lee, Byung Kwon, 2020. "Liner-dedicated manageability estimation for port operational reliability," Reliability Engineering and System Safety, Elsevier, vol. 198(C).
    20. Tanaka, Shunji & Tierney, Kevin & Parreño-Torres, Consuelo & Alvarez-Valdes, Ramon & Ruiz, Rubén, 2019. "A branch and bound approach for large pre-marshalling problems," European Journal of Operational Research, Elsevier, vol. 278(1), pages 211-225.

    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:ejores:v:256:y:2017:i:1:p:90-101. 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/locate/eor .

    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.