A joint quay crane assignment and scheduling problem: formulation, solution algorithm and computational results

Quay cranes constitute a significant determinant of container handling efficiency and for this reason the quay crane assignment problem (QCAP) and the quay crane scheduling problem (QCSP) have received great attention in research streams. However, these interdependent problems are usually solved sequentially, due to the high complexity of integration, leading to a potentially inefficient utilization of resources. This paper presents a simple approach for the integrated quay crane assignment and scheduling problem (QCASP), by transforming it into a crane-to-bay assignment problem, and develops a Lagrangian relaxation algorithm to solve it. In order to ensure feasibility, a restoration technique is also developed and this Lagrangian relaxation based heuristic is evaluated as a whole. The choice of constraints to be relaxed is justified and the sub- and master problems are derived. The relaxed problem is solved using the constraint generation method and computational results are conducted in order to evaluate the performance of the Lagrangian heuristic, in terms of computational time, Lagrangian bounds and gaps.