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

Noura Al-Dhaheri and Ali Diabat ()
Additional contact information
Noura Al-Dhaheri: Masdar Institute of Science and Technology
Ali Diabat: Masdar Institute of Science and Technology

Annals of Operations Research, 2017, vol. 248, issue 1, No 1, 24 pages

Abstract: 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.

Keywords: Quay crane scheduling; Container terminals; Ship stability; Lagrangian relaxation; Maritime logistics (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-016-2239-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:248:y:2017:i:1:d:10.1007_s10479-016-2239-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-016-2239-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().