IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v201y2025ics1366554525002959.html

The bay-based quay crane scheduling problem considering time-varying handling capacities in automated container terminals

Author

Listed:
  • Tan, Runzhi
  • Wang, Peixiang
  • Tao, Jinghan
  • Zhou, Yaoming
  • Qin, Wei
  • Huang, Heng
  • Zou, Ying

Abstract

The scheduling of quay cranes at automated container terminals is a critical component of efficient seaside operations, particularly with the advent of ultra-large container ships. These massive vessels necessitate extended service times and present distinct challenges to quay crane scheduling, emphasizing the need for advanced models that accommodate temporal changes in task handling capacities. This study develops a mixed-integer linear programming (MILP) model specifically tailored for the bay-based quay crane scheduling problem (QCSP) associated with ultra-large container ships, incorporating two time-varying handling rates derived from Terminal Operating System (TOS) data. To enhance computational efficiency, a time-incremental solution framework is introduced to approximate the original problem. This framework transforms the optimization problem into a series of decision problems, specifically verifying whether all tasks can be completed within an incrementally refined time span. Correspondingly, a novel branch-and-price algorithm is designed to identify near-optimal solutions, employing column generation to derive upper bounds for pruning infeasible nodes, alongside tailored branching schemes for handling fractional solutions. Furthermore, a recursive heuristic algorithm integrated with an exact model is proposed to warm-start the column generation process and provide a precisely determined time interval for the algorithm. Computational experiments demonstrate the superiority of the proposed framework and algorithm, especially for large-scale instances, with significant performance improvements over the MILP model. The study also validates the effectiveness of incorporating time-varying rates, showing an 8.45% efficiency improvement by considering container arrival rates in QCSP models. Managerial insights indicate that prioritizing yard resources to better-stacked areas can more effectively enhance loading efficiency when resources are limited.

Suggested Citation

  • Tan, Runzhi & Wang, Peixiang & Tao, Jinghan & Zhou, Yaoming & Qin, Wei & Huang, Heng & Zou, Ying, 2025. "The bay-based quay crane scheduling problem considering time-varying handling capacities in automated container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 201(C).
    • Handle: RePEc:eee:transe:v:201:y:2025:i:c:s1366554525002959
    DOI: 10.1016/j.tre.2025.104254
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554525002959
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2025.104254?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Chargui, Kaoutar & Zouadi, Tarik & El Fallahi, Abdellah & Reghioui, Mohamed & Aouam, Tarik, 2021. "Berth and quay crane allocation and scheduling with worker performance variability and yard truck deployment in container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    2. Wang, Peixiang & Xu, Qihang & Li, Yufei & Chen, Qunlong & Tao, Jinghan & Qin, Wei & Huang, Heng & Zou, Ying, 2025. "Learning-based hybrid algorithms for container relocation problem with storage plan," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 197(C).
    3. Andrew Lim & Brian Rodrigues & Fei Xiao & Yi Zhu, 2004. "Crane scheduling with spatial constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(3), pages 386-406, April.
    4. 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.
    5. Jiyin Liu & Yat‐wah Wan & Lei Wang, 2006. "Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(1), pages 60-74, February.
    6. 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.
    7. 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.
    8. 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.
    9. Chen, Jiang Hang & Lee, Der-Horng & Goh, Mark, 2014. "An effective mathematical formulation for the unidirectional cluster-based quay crane scheduling problem," European Journal of Operational Research, Elsevier, vol. 232(1), pages 198-208.
    10. Filom, Siyavash & Amiri, Amir M. & Razavi, Saiedeh, 2022. "Applications of machine learning methods in port operations – A systematic literature review," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    11. 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.
    12. 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.
    13. 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.
    14. Zhen, Lu & Liang, Zhe & Zhuge, Dan & Lee, Loo Hay & Chew, Ek Peng, 2017. "Daily berth planning in a tidal port with channel flow control," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 193-217.
    15. Zhen, Lu & Zhuge, Dan & Wang, Shuaian & Wang, Kai, 2022. "Integrated berth and yard space allocation under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 1-27.
    16. 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.
    17. Shawn Choo & Diego Klabjan & David Simchi-Levi, 2010. "Multiship Crane Sequencing with Yard Congestion Constraints," Transportation Science, INFORMS, vol. 44(1), pages 98-115, February.
    18. 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.
    19. Lu Zhen & Qian Sun & Wei Zhang & Kai Wang & Wen Yi, 2021. "Column generation for low carbon berth allocation under uncertainty," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 72(10), pages 2225-2240, October.
    20. Jiang, Xinjia & Lee, Loo Hay & Chew, Ek Peng & Han, Yongbin & Tan, Kok Choon, 2012. "A container yard storage strategy for improving land utilization and operation efficiency in a transshipment hub port," European Journal of Operational Research, Elsevier, vol. 221(1), pages 64-73.
    21. 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.
    22. Kai Wang & Lu Zhen & Shuaian Wang, 2018. "Column Generation for the Integrated Berth Allocation, Quay Crane Assignment, and Yard Assignment Problem," Transportation Science, INFORMS, vol. 52(4), pages 812-834, August.
    23. 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.
    24. M. Rodriguez-Molins & M. A. Salido & F. Barber, 2014. "Robust Scheduling for Berth Allocation and Quay Crane Assignment Problem," Mathematical Problems in Engineering, Hindawi, vol. 2014, pages 1-17, December.
    25. Daganzo, Carlos F., 1989. "The crane scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 23(3), pages 159-175, June.
    26. 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.
    27. Jian Gang Jin & Der-Horng Lee & Jin Xin Cao, 2016. "Storage Yard Management in Maritime Container Terminals," Transportation Science, INFORMS, vol. 50(4), pages 1300-1313, November.
    28. Abou Kasm, Omar & Diabat, Ali & Chow, Joseph Y.J., 2023. "Simultaneous operation of next-generation and traditional quay cranes at container terminals," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1110-1125.
    29. Zhang, An & Zhang, Wenshuai & Chen, Yong & Chen, Guangting & Chen, Xufeng, 2017. "Approximate the scheduling of quay cranes with non-crossing constraints," European Journal of Operational Research, Elsevier, vol. 258(3), pages 820-828.
    30. 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.
    31. Giallombardo, Giovanni & Moccia, Luigi & Salani, Matteo & Vacca, Ilaria, 2010. "Modeling and solving the Tactical Berth Allocation Problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 232-245, February.
    32. Zhang, Chuqian & Liu, Jiyin & Wan, Yat-wah & Murty, Katta G. & Linn, Richard J., 2003. "Storage space allocation in container terminals," Transportation Research Part B: Methodological, Elsevier, vol. 37(10), pages 883-903, December.
    33. 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.
    34. Ilaria Vacca & Matteo Salani & Michel Bierlaire, 2013. "An Exact Algorithm for the Integrated Planning of Berth Allocation and Quay Crane Assignment," Transportation Science, INFORMS, vol. 47(2), pages 148-161, May.
    35. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    36. 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.
    37. 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.
    38. Defeng Sun & Lixin Tang & Roberto Baldacci & Zihan Chen, 2024. "A Decomposition Method for the Group-Based Quay Crane Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 543-570, March.
    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. Dragović, Branislav & Dragović, Andro & Dulebenets, Maxim A., 2025. "The quay crane operation problem at marine container terminals: bibliometric analysis, emerging trends, and future research opportunities," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 201(C).
    2. 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.
    3. 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.
    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. 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.
    6. 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.
    7. 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.
    8. 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).
    9. Abou Kasm, Omar & Diabat, Ali & Chow, Joseph Y.J., 2023. "Simultaneous operation of next-generation and traditional quay cranes at container terminals," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1110-1125.
    10. 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.
    11. Defeng Sun & Lixin Tang & Roberto Baldacci & Zihan Chen, 2024. "A Decomposition Method for the Group-Based Quay Crane Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 543-570, March.
    12. 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.
    13. Haoqi Xie & Daniela Ambrosino, 2025. "Operations Research, Machine Learning, and Integrated Techniques for Decision Problems in the Seaside Area of Container Terminals," SN Operations Research Forum, Springer, vol. 6(2), pages 1-51, June.
    14. Xiang, Xi & Liu, Changchun, 2021. "An almost robust optimization model for integrated berth allocation and quay crane assignment problem," Omega, Elsevier, vol. 104(C).
    15. Zhen, Lu & Zhuge, Dan & Wang, Shuaian & Wang, Kai, 2022. "Integrated berth and yard space allocation under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 1-27.
    16. 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.
    17. Kong, Lingrui & Ji, Mingjun & Gao, Zhendi, 2022. "An exact algorithm for scheduling tandem quay crane operations in container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    18. 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.
    19. 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.
    20. 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.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:201:y:2025:i:c:s1366554525002959. 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.