Next-generation quay crane scheduling

摘要

Quay crane scheduling is considered one of the most complex seaside operations in container terminals, and is directly correlated with vessel service and waiting times. Traditionally, quay cranes can handle one container at a time. However, this is expected to change with the recently patented next-generation quay crane: The Ship to Shore Multi-trolley Portal Gantry Container Crane. These next-generation cranes can access two bays simultaneously and can operate on four containers at a time. In this work, we introduce a mixed integer programming (MIP) formulation and an exact solution approach to solve the next-generation quay crane scheduling problem. The solution technique breaks the main problem into two sequential stages. The first stage uses a fast set-partitioning formulation to solve the general case and a closed form analytic approach to solve specific cases, while the second stage uses a partitioning heuristic combined with a branch-and-price algorithm. A real-workload case study and simulated-workload case studies are used to assess the performance of the next-generation cranes versus traditional ones. Results show that the use of two to three next-generation cranes can generally reduce the service time beyond the best possible service time achieved by traditional cranes. Moreover, average service times can be reduced by up to 65%. Finally, results of a computational study and sensitivity analyses show that the proposed solution approach has low sensitivity to the different parameters and clearly outperforms CPLEX in that it can solve real-sized cases rapidly; in the computational study all cases were solved in less than 20 s.