IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v203y2013i1p119-13910.1007-s10479-010-0765-3.html
   My bibliography  Save this article

The crane scheduling problem: models and solution approaches

Author

Listed:
  • Yongpei Guan
  • Kang-Hung Yang
  • Zhili Zhou

Abstract

In this paper, we study the crane scheduling problem for a vessel after the vessel is moored on a terminal and develop both exact and heuristic solution approaches for the problem. For small-sized instances, we develop a time-space network flow formulation with non-crossing constraints for the problem and apply an exact solution approach to obtain an optimal solution. For medium-sized instances, we develop a Lagrangian relaxation approach that allows us to obtain tight lower bounds and near-optimal solutions. For large-sized instances, we develop two heuristics and show that the error bounds of our heuristics are no more than 100%. Finally, we perform computational studies to show the effectiveness of our proposed solution approaches. Copyright Springer Science+Business Media, LLC 2013

Suggested Citation

  • Yongpei Guan & Kang-Hung Yang & Zhili Zhou, 2013. "The crane scheduling problem: models and solution approaches," Annals of Operations Research, Springer, vol. 203(1), pages 119-139, March.
    • Handle: RePEc:spr:annopr:v:203:y:2013:i:1:p:119-139:10.1007/s10479-010-0765-3
    DOI: 10.1007/s10479-010-0765-3
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-010-0765-3
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-010-0765-3?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. Andrew Lim & Brian Rodrigues & Zhou Xu, 2007. "A m‐parallel crane scheduling problem with a non‐crossing constraint," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 115-127, March.
    2. Jean-François Cordeau & Gilbert Laporte & Pasquale Legato & Luigi Moccia, 2005. "Models and Tabu Search Heuristics for the Berth-Allocation Problem," Transportation Science, INFORMS, vol. 39(4), pages 526-538, November.
    3. Peterkofsky, Roy I. & Daganzo, Carlos F., 1990. "A branch and bound solution method for the crane scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 24(3), pages 159-172, June.
    4. Hansen, Pierre & Oguz, Ceyda & Mladenovic, Nenad, 2008. "Variable neighborhood search for minimum cost berth allocation," European Journal of Operational Research, Elsevier, vol. 191(3), pages 636-649, December.
    5. Luigi Moccia & Jean‐François Cordeau & Manlio Gaudioso & Gilbert Laporte, 2006. "A branch‐and‐cut algorithm for the quay crane scheduling problem in a container terminal," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 45-59, February.
    6. Hansen, Pierre & Mladenovic, Nenad & Moreno Pérez, Jos´e A., 2008. "Variable neighborhood search," European Journal of Operational Research, Elsevier, vol. 191(3), pages 593-595, December.
    7. Daganzo, Carlos F., 1989. "The crane scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 23(3), pages 159-175, June.
    8. M. Flavia Monaco & Marcello Sammarra, 2007. "The Berth Allocation Problem: A Strong Formulation Solved by a Lagrangean Approach," Transportation Science, INFORMS, vol. 41(2), pages 265-280, May.
    9. Imai, Akio & Sun, Xin & Nishimura, Etsuko & Papadimitriou, Stratos, 2005. "Berth allocation in a container port: using a continuous location space approach," Transportation Research Part B: Methodological, Elsevier, vol. 39(3), pages 199-221, March.
    10. Y Zhu & A Lim, 2006. "Crane scheduling with non-crossing constraint," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(12), pages 1464-1471, December.
    11. Lee, Der-Horng & Wang, Hui Qiu & Miao, Lixin, 2008. "Quay crane scheduling with non-interference constraints in port container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(1), pages 124-135, January.
    12. Kim, Kap Hwan & Park, Young-Man, 2004. "A crane scheduling method for port container terminals," European Journal of Operational Research, Elsevier, vol. 156(3), pages 752-768, 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. Vibhuti Dhingra & Debjit Roy & René B. M. Koster, 2017. "A cooperative quay crane-based stochastic model to estimate vessel handling time," Flexible Services and Manufacturing Journal, Springer, vol. 29(1), pages 97-124, March.
    2. H. L. Ma & S. H. Chung & H. K. Chan & Li Cui, 2019. "An integrated model for berth and yard planning in container terminals with multi-continuous berth layout," Annals of Operations Research, Springer, vol. 273(1), pages 409-431, February.
    3. 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.
    4. Noura Al-Dhaheri & Ali Diabat, 2017. "A Lagrangian relaxation-based heuristic for the multi-ship quay crane scheduling problem with ship stability constraints," Annals of Operations Research, Springer, vol. 248(1), pages 1-24, January.
    5. 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.
    6. Yanling Chu & Xiaoju Zhang & Zhongzhen Yang, 2017. "Multiple quay cranes scheduling for double cycling in container terminals," PLOS ONE, Public Library of Science, vol. 12(7), pages 1-19, July.
    7. 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.
    8. Abdellah Salhi & Ghazwan Alsoufi & Xinan Yang, 2019. "An evolutionary approach to a combined mixed integer programming model of seaside operations as arise in container ports," Annals of Operations Research, Springer, vol. 272(1), pages 69-98, January.
    9. Sun, Defeng & Tang, Lixin & Baldacci, Roberto, 2019. "A Benders decomposition-based framework for solving quay crane scheduling problems," European Journal of Operational Research, Elsevier, vol. 273(2), pages 504-515.
    10. Ma, Hoi-Lam & Wong, Collin Wai-Hung & Leung, Lawrence C. & Chung, Sai-Ho, 2020. "Facility sharing in business-to-business model: A real case study for container terminal operators in Hong Kong port," International Journal of Production Economics, Elsevier, vol. 221(C).
    11. Yuan, Yuan & Tang, Lixin, 2017. "Novel time-space network flow formulation and approximate dynamic programming approach for the crane scheduling in a coil warehouse," European Journal of Operational Research, Elsevier, vol. 262(2), pages 424-437.
    12. T. R. Lalita & G. S. R. Murthy, 2022. "Compact ILP formulations for a class of solutions to berth allocation and quay crane scheduling problems," OPSEARCH, Springer;Operational Research Society of India, vol. 59(1), pages 413-439, March.
    13. Sun, Defeng & Tang, Lixin & Baldacci, Roberto & Lim, Andrew, 2021. "An exact algorithm for the unidirectional quay crane scheduling problem with vessel stability," European Journal of Operational Research, Elsevier, vol. 291(1), pages 271-283.
    14. Lu Zhen & Shucheng Yu & Shuaian Wang & Zhuo Sun, 2019. "Scheduling quay cranes and yard trucks for unloading operations in container ports," Annals of Operations Research, Springer, vol. 273(1), pages 455-478, February.

    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. Bierwirth, Christian & Meisel, Frank, 2010. "A survey of berth allocation and quay crane scheduling problems in container terminals," European Journal of Operational Research, Elsevier, vol. 202(3), pages 615-627, May.
    2. J Blazewicz & T C E Cheng & M Machowiak & C Oguz, 2011. "Berth and quay crane allocation: a moldable task scheduling model," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1189-1197, July.
    3. Fanrui Xie & Tao Wu & Canrong Zhang, 2019. "A Branch-and-Price Algorithm for the Integrated Berth Allocation and Quay Crane Assignment Problem," Transportation Science, INFORMS, vol. 53(5), pages 1427-1454, September.
    4. T. R. Lalita & G. S. R. Murthy, 2022. "Compact ILP formulations for a class of solutions to berth allocation and quay crane scheduling problems," OPSEARCH, Springer;Operational Research Society of India, vol. 59(1), pages 413-439, March.
    5. Shucheng Yu & Shuaian Wang & Lu Zhen, 2017. "Quay crane scheduling problem with considering tidal impact and fuel consumption," Flexible Services and Manufacturing Journal, Springer, vol. 29(3), pages 345-368, December.
    6. Abdellah Salhi & Ghazwan Alsoufi & Xinan Yang, 2019. "An evolutionary approach to a combined mixed integer programming model of seaside operations as arise in container ports," Annals of Operations Research, Springer, vol. 272(1), pages 69-98, January.
    7. Shoufeng Ma & Hongming Li & Ning Zhu & Chenyi Fu, 2021. "Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty," Journal of Scheduling, Springer, vol. 24(2), pages 137-174, April.
    8. Sun, Defeng & Tang, Lixin & Baldacci, Roberto, 2019. "A Benders decomposition-based framework for solving quay crane scheduling problems," European Journal of Operational Research, Elsevier, vol. 273(2), pages 504-515.
    9. Liu, Baoli & Li, Zhi-Chun & Sheng, Dian & Wang, Yadong, 2021. "Integrated planning of berth allocation and vessel sequencing in a seaport with one-way navigation channel," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 23-47.
    10. Zhen, Lu & Lee, Loo Hay & Chew, Ek Peng, 2011. "A decision model for berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 212(1), pages 54-68, July.
    11. Feng Li & Jiuh-Biing Sheu & Zi-You Gao, 2015. "Solving the Continuous Berth Allocation and Specific Quay Crane Assignment Problems with Quay Crane Coverage Range," Transportation Science, INFORMS, vol. 49(4), pages 968-989, November.
    12. Wu, Lingxiao & Ma, Weimin, 2017. "Quay crane scheduling with draft and trim constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 97(C), pages 38-68.
    13. Frank Meisel & Christian Bierwirth, 2013. "A Framework for Integrated Berth Allocation and Crane Operations Planning in Seaport Container Terminals," Transportation Science, INFORMS, vol. 47(2), pages 131-147, May.
    14. Nils Boysen & Malte Fliedner & Florian Jaehn & Erwin Pesch, 2013. "A Survey on Container Processing in Railway Yards," Transportation Science, INFORMS, vol. 47(3), pages 312-329, August.
    15. Liu, Changchun, 2020. "Iterative heuristic for simultaneous allocations of berths, quay cranes, and yards under practical situations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    16. Zhen, Lu, 2015. "Tactical berth allocation under uncertainty," European Journal of Operational Research, Elsevier, vol. 247(3), pages 928-944.
    17. Qin, Tianbao & Du, Yuquan & Chen, Jiang Hang & Sha, Mei, 2020. "Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel," European Journal of Operational Research, Elsevier, vol. 285(3), pages 884-901.
    18. Lu Zhen & Ek Peng Chew & Loo Hay Lee, 2011. "An Integrated Model for Berth Template and Yard Template Planning in Transshipment Hubs," Transportation Science, INFORMS, vol. 45(4), pages 483-504, November.
    19. Imai, Akio & Yamakawa, Yukiko & Huang, Kuancheng, 2014. "The strategic berth template problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 77-100.
    20. Xiang, Xi & Liu, Changchun & Miao, Lixin, 2017. "A bi-objective robust model for berth allocation scheduling under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 294-319.

    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:annopr:v:203:y:2013:i:1:p:119-139:10.1007/s10479-010-0765-3. 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.