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

Models and algorithms for a yard crane scheduling problem in container ports

Author

Listed:
  • Vallada, Eva
  • Belenguer, Jose Manuel
  • Villa, Fulgencia
  • Alvarez-Valdes, Ramon

Abstract

This paper addresses the scheduling of a yard crane in an automated container block, considering its relationships with the other terminal subsystems. Containers coming into the block to be stored have release times, indicating the moment at which they arrive from ships or trucks. Containers being retrieved have due times, indicating when they will be required by other subsystems. The problem can be seen as a pickup routing problem and also as a one-machine scheduling problem. As a starting point, integer linear models were developed for both approaches. Then, to obtain good solutions for large instances, several heuristic algorithms, coupled with a local search, were proposed. An extensive computational study, based on a newly generated benchmark, shows the limits of the exact methods and the quality of the solutions obtained by the heuristics.

Suggested Citation

  • Vallada, Eva & Belenguer, Jose Manuel & Villa, Fulgencia & Alvarez-Valdes, Ramon, 2023. "Models and algorithms for a yard crane scheduling problem in container ports," European Journal of Operational Research, Elsevier, vol. 309(2), pages 910-924.
    • Handle: RePEc:eee:ejores:v:309:y:2023:i:2:p:910-924
    DOI: 10.1016/j.ejor.2023.01.047
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172300084X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2023.01.047?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. Gharehgozli, Amir Hossein & Yu, Yugang & de Koster, René & Udding, Jan Tijmen, 2014. "An exact method for scheduling a yard crane," European Journal of Operational Research, Elsevier, vol. 235(2), pages 431-447.
    2. Ulf Speer & Kathrin Fischer, 2017. "Scheduling of Different Automated Yard Crane Systems at Container Terminals," Transportation Science, INFORMS, vol. 51(1), pages 305-324, February.
    3. Xing, Zheng & Liu, Haitao & Wang, Tingsong & Chew, Ek Peng & Lee, Loo Hay & Tan, Kok Choon, 2023. "Integrated automated guided vehicle dispatching and equipment scheduling with speed optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(C).
    4. 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.
    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. 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. Ananthapadmanabhan Narasimhan & Udatta S. Palekar, 2002. "Analysis and Algorithms for the Transtainer Routing Problem in Container Port Operations," Transportation Science, INFORMS, vol. 36(1), pages 63-78, February.
    8. Ki Young Kim & Kap Hwan Kim, 2003. "Heuristic algorithms for routing yard‐side equipment for minimizing loading times in container terminals," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(5), pages 498-514, August.
    9. Feifeng Zheng & Xiaoyi Man & Feng Chu & Ming Liu & Chengbin Chu, 2019. "A two-stage stochastic programming for single yard crane scheduling with uncertain release times of retrieval tasks," International Journal of Production Research, Taylor & Francis Journals, vol. 57(13), pages 4132-4147, July.
    10. Amir Hossein Gharehgozli & Gilbert Laporte & Yugang Yu & René de Koster, 2015. "Scheduling Twin Yard Cranes in a Container Block," Transportation Science, INFORMS, vol. 49(3), pages 686-705, August.
    11. Li, Wenkai & Goh, Mark & Wu, Yong & Petering, M.E.H. & de Souza, R. & Wu, Y.C., 2012. "A continuous time model for multiple yard crane scheduling with last minute job arrivals," International Journal of Production Economics, Elsevier, vol. 136(2), pages 332-343.
    12. Li, Wenkai & Wu, Yong & Petering, M.E.H. & Goh, Mark & Souza, Robert de, 2009. "Discrete time model and algorithms for container yard crane scheduling," European Journal of Operational Research, Elsevier, vol. 198(1), pages 165-172, October.
    13. Kap Hwan Kim & Ki Young Kim, 1999. "An Optimal Routing Algorithm for a Transfer Crane in Port Container Terminals," Transportation Science, INFORMS, vol. 33(1), pages 17-33, February.
    14. Boysen, Nils & Stephan, Konrad, 2016. "A survey on single crane scheduling in automated storage/retrieval systems," European Journal of Operational Research, Elsevier, vol. 254(3), pages 691-704.
    15. Boysen, Nils & Briskorn, Dirk & Meisel, Frank, 2017. "A generalized classification scheme for crane scheduling with interference," European Journal of Operational Research, Elsevier, vol. 258(1), pages 343-357.
    16. Yong Wu & Wenkai Li & Matthew E. H. Petering & Mark Goh & Robert de Souza, 2015. "Scheduling Multiple Yard Cranes with Crane Interference and Safety Distance Requirement," Transportation Science, INFORMS, vol. 49(4), pages 990-1005, November.
    17. Shell Ying Huang & Ya Li, 2017. "Yard crane scheduling to minimize total weighted vessel loading time in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 689-720, December.
    Full references (including those not matched with items on IDEAS)

    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 & 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.
    2. Shell Ying Huang & Ya Li, 2017. "Yard crane scheduling to minimize total weighted vessel loading time in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 689-720, December.
    3. 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.
    4. Gharehgozli, Amir & Xu, Chao & Zhang, Wenda, 2021. "High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system," European Journal of Operational Research, Elsevier, vol. 289(2), pages 495-507.
    5. 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.
    6. Dirk Briskorn, 2021. "Routing two stacking cranes with predetermined container sequences," Journal of Scheduling, Springer, vol. 24(4), pages 367-380, August.
    7. Amelie Eilken, 2019. "A decomposition-based approach to the scheduling of identical automated yard cranes at container terminals," Journal of Scheduling, Springer, vol. 22(5), pages 517-541, October.
    8. 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.
    9. Wang, Mengyao & Zhou, Chenhao & Wang, Aihu, 2022. "A cluster-based yard template design integrated with yard crane deployment using a placement heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 160(C).
    10. 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.
    11. Dirk Briskorn & Lennart Zey, 2020. "Interference aware scheduling of triple-crossover-cranes," Journal of Scheduling, Springer, vol. 23(4), pages 465-485, August.
    12. Jin, Bo & Yu, Zhishan & Yu, Mingzhu, 2022. "Inbound container remarshaling problem in an automated container terminal," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    13. Boysen, Nils & Briskorn, Dirk & Meisel, Frank, 2017. "A generalized classification scheme for crane scheduling with interference," European Journal of Operational Research, Elsevier, vol. 258(1), pages 343-357.
    14. 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.
    15. Sumin Chen & Qingcheng Zeng & Yushan Hu, 2022. "Scheduling optimization for two crossover automated stacking cranes considering relocation," Operational Research, Springer, vol. 22(3), pages 2099-2120, July.
    16. Xiao-Ming Yang & Xin-Jia Jiang, 2020. "Yard Crane Scheduling in the Ground Trolley-Based Automated Container Terminal," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 37(02), pages 1-28, March.
    17. Jiang, Xin Jia & Jin, Jian Gang, 2017. "A branch-and-price method for integrated yard crane deployment and container allocation in transshipment yards," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 62-75.
    18. Zhou, Chenhao & Lee, Byung Kwon & Li, Haobin, 2020. "Integrated optimization on yard crane scheduling and vehicle positioning at container yards," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    19. Lashkari, Shabnam & Wu, Yong & Petering, Matthew E.H., 2017. "Sequencing dual-spreader crane operations: Mathematical formulation and heuristic algorithm," European Journal of Operational Research, Elsevier, vol. 262(2), pages 521-534.
    20. Hang Yu & Yiyun Deng & Leijie Zhang & Xin Xiao & Caimao Tan, 2022. "Yard Operations and Management in Automated Container Terminals: A Review," Sustainability, MDPI, vol. 14(6), pages 1-24, March.

    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:309:y:2023:i:2:p:910-924. 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.