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

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.