IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v248y2017i1d10.1007_s10479-016-2239-8.html
   My bibliography  Save this article

A Lagrangian relaxation-based heuristic for the multi-ship quay crane scheduling problem with ship stability constraints

Author

Listed:
  • Noura Al-Dhaheri

    (Masdar Institute of Science and Technology)

  • Ali Diabat

    (Masdar Institute of Science and Technology)

Abstract

The quay crane scheduling problem is one of the major problems of quayside operational planning in container terminals. The operational efficiency of quay cranes is a large determinant of the overall container terminal efficiency; thus, in an effort to maximize throughput, more and more emphasis is placed on systematically addressing and improving quay crane operations. However, the resulting formulations are highly complex and thus not solvable using commercial software. In the first part of the present paper, we develop a formulation that overcomes this challenge. This allows for solving the model using CPLEX, even for large size instances, which other notable work from the literature fails to solve. The second part of this paper addresses a crucial point which has rarely been accounted for, which is ship stability. A heuristic is developed to solve the extended problem, as it is no longer solvable in CPLEX. The remaining objective of this work is to extend this problem to the multi-ship case. However, once again the problem is insolvable for large instances using CPLEX, even without accounting for stability constraints. We develop a Lagrangian relaxation based algorithm that decomposes the problem by ship, which is solved efficiently as a single ship case. The Lagrangian multipliers are updated using the cutting plane method and the solution of the Lagrangian master problem provides an upper bound on the optimal value of the Lagrangian lower bound. Upper bounds on the optimal value of the original problem are obtained using a constructive heuristic, and through computational experiments we demonstrate the performance of the Lagrangian relaxation-based procedures.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:248:y:2017:i:1:d:10.1007_s10479-016-2239-8
    DOI: 10.1007/s10479-016-2239-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-016-2239-8
    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/s10479-016-2239-8?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. Boysen, Nils & Emde, Simon & Fliedner, Malte, 2012. "Determining crane areas for balancing workload among interfering and noninterfering cranes," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 79437, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    2. Unsal, Ozgur & Oguz, Ceyda, 2013. "Constraint programming approach to quay crane scheduling problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 59(C), pages 108-122.
    3. Marshall L. Fisher, 1981. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 27(1), pages 1-18, January.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Tang, Lixin & Zhao, Jiao & Liu, Jiyin, 2014. "Modeling and solution of the joint quay crane and truck scheduling problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 978-990.
    12. 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.
    13. Chen, Jiang Hang & Lee, Der-Horng & Cao, Jin Xin, 2011. "Heuristics for quay crane scheduling at indented berth," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(6), pages 1005-1020.
    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. Lijun Yue & Houming Fan & Chunxin Zhai, 2019. "Joint Configuration and Scheduling Optimization of a Dual-Trolley Quay Crane and Automatic Guided Vehicles with Consideration of Vessel Stability," Sustainability, MDPI, vol. 12(1), pages 1-16, December.
    2. Abou Kasm, Omar & Diabat, Ali & Bierlaire, Michel, 2021. "Vessel scheduling with pilotage and tugging considerations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 148(C).
    3. Omar Abou Kasm & Ali Diabat & T. C. E. Cheng, 2020. "The integrated berth allocation, quay crane assignment and scheduling problem: mathematical formulations and a case study," Annals of Operations Research, Springer, vol. 291(1), pages 435-461, August.
    4. 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.
    5. Diabat, Ali & Jabbarzadeh, Armin & Khosrojerdi, Amir, 2019. "A perishable product supply chain network design problem with reliability and disruption considerations," International Journal of Production Economics, Elsevier, vol. 212(C), pages 125-138.
    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.

    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, 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.
    2. 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.
    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. 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).
    5. 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.
    6. 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.
    7. Nabil Nehme & Bacel Maddah & Isam A. Kaysi, 2021. "An integrated multi-ship crane allocation in Beirut Port container terminal," Operational Research, Springer, vol. 21(3), pages 1743-1761, September.
    8. Omar Abou Kasm & Ali Diabat & T. C. E. Cheng, 2020. "The integrated berth allocation, quay crane assignment and scheduling problem: mathematical formulations and a case study," Annals of Operations Research, Springer, vol. 291(1), pages 435-461, August.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Liu, Ming & Lee, Chung-Yee & Zhang, Zizhen & Chu, Chengbin, 2016. "Bi-objective optimization for the container terminal integrated planning," Transportation Research Part B: Methodological, Elsevier, vol. 93(PB), pages 720-749.
    14. 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.
    15. Agra, Agostinho & Oliveira, Maryse, 2018. "MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem," European Journal of Operational Research, Elsevier, vol. 264(1), pages 138-148.
    16. 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).
    17. Xiang, Xi & Liu, Changchun, 2021. "An expanded robust optimisation approach for the berth allocation problem considering uncertain operation time," Omega, Elsevier, vol. 103(C).
    18. Feifeng Zheng & Yaxin Pang & Ming Liu & Yinfeng Xu, 2020. "Dynamic programming algorithms for the general quay crane double-cycling problem with internal-reshuffles," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 708-724, April.
    19. Guvenc Dik & Erhan Kozan, 2017. "A flexible crane scheduling methodology for container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 29(1), pages 64-96, March.
    20. 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.

    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:248:y:2017:i:1:d:10.1007_s10479-016-2239-8. 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.