A Self-Adaptive Monte Carlo Tree Search Algorithm for Generalized Quay Crane Scheduling Problem

Efficient quay crane (QC) handling is crucial for enhancing service levels and competitiveness in container terminals, particularly with the advent of ultra-large vessels necessitating rapid container turnover. As the complexity of terminal operations escalates, this paper addresses the generalized quay crane scheduling problem (GQCSP), aiming to minimize the makespan for discharging and loading operations. In this problem, both 20-ft and 40-ft containers are mixed and stacked above and below the hatch covers, and QCs operate multidirectionally under safety distance and noncrossing constraints. A solution approach is proposed that delivers swift, feasible solutions over protracted optimal ones, which is essential for adapting to last-minute operational changes. The problem is formulated as a Markov decision process model, and a self-adaptive Monte Carlo tree search (MCTS) algorithm is proposed that can handle up to 11 QCs and 280 container groups. For algorithm acceleration, problem-specific methods are developed, achieving an improvement of approximately 1.2% of the makespan and a reduction of two-thirds of the computation time. Specifically, an adaptive lower bound is introduced for node selection and subtree pruning, accompanied by a lower-bound-based reward function to facilitate backpropagation. The experiments demonstrate that the proposed MCTS algorithm significantly outperforms existing heuristic algorithms, achieving average improvements of 20.84%, 14.40%, and 11.02% in terms of makespan compared with the strategy-based approach, while also surpassing the dynamic programming algorithm by 12.88% and the memetic algorithm by 72.79%. Furthermore, compared with the most recent Benders decomposition method assuming a homogeneous container size, the proposed MCTS algorithm also demonstrates comparable performance where the difference is less than 0.4%. The significance of the results demonstrates that the proposed approach has great universality, thus improving terminal productivity and responsiveness. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72471190]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2025.0016 .