Abstract: The modern logistics sector heavily depends on maritime transportation. Ports are key hubs connecting sea and land, and with the boom of international transoceanic trade, a variety of real-world issues in managing and operating ports have arisen and been extensively studied by experts from the operations research and optimization community. In order to achieve maximum profit, port managers strive to complete the loading and unloading of containers for the vessels within the shortest possible time, and a critical factor affecting the loading and unloading time of vessels is the arrangement and scheduling of quay cranes, which is referred to as the quay crane scheduling problem (QCSP) and has received intensive studies in the literature.
Due to the advancement of international trade integration, the volume of commodity transportation has grown enormously, and an increasing number of larger and larger ships are being used in maritime transportation. If container terminals are unable to shorten the service time, long dwell time of ships in port will result in tremendous financial losses. Two counter measures are often used to reduce such a cost, one is to keep purchasing new cranes to work on the quay, and the other is to extend the length of the berth. All along, one container is operated at a time because a quay crane only has one trolley. Recently, this restriction has been lifted with the coming of next-generation quay cranes. Up to four containers can be operated simultaneously by a next-generation quay crane. It has two parallel girders and each girder has two lifting trolleys. The average service time is anticipated to be reduced by roughly 65% by using next-generation quay cranes compared to using traditional ones. The handling capacity of the port terminal side can thus be greatly enhanced, as well the rate of vessel turnover.
The new generation of cranes has a wide range of benefits in addition to increased processing efficiency. To name a few, their energy efficiency increases, emissions decrease, life cycle is longer, and repair and maintenance costs are lower. However, to meet the operating criteria for the next-generation quay cranes, the terminal infrastructure must also be rebuilt, which is expensive. So, the associated cost should be taken into account. Hence, during the transitional period, traditional quay cranes will continue to serve ships, alongside with the new coming next-generation quay cranes.
Due to the NP-hardness of the problem, in this paper, the coordinating scheduling of traditional and next-generation quay cranes is modeled as an integer programming problem, taking into account both non-crossing constraints and safety clearance constraints. However, even for moderate size problems, the computation time required to obtain accurate solutions is usually intolerable by using commercial solvers such as Gurobi. To this end, we propose a two-stage solution approach. In the first stage, an initial solution is obtained by applying a “move-forward” approach, which is a heuristic of combinatorial nature, and then in the second stage, with an integer linear programming model for the problem proposed by the initial solution obtained from the “move-forward” heuristic and a branch and price approach, the optimal scheduling is obtained.
More specifically, in the first stage we present a container allocation technique for two trolleys in a bay, based on which a “move-forward” heuristic is proposed to produce an initial solution. Although the “move-forward” heuristic quickly obtains a good first result, the solution is not always optimal. In the second stage, we reformulate the problem as a set cover model, and a branch and price technique with column generation is employed to solve the model. According to the numerical experiments, the restricted master problem can be quickly solved by using commercial solvers such as Gurobi. After each node finishes its pricing loop, it is solved as an integer linear programming problem. The value is utilized as an upper bound for the branching node to speed up the algorithm.
The numerical experiments show that our solution approach is efficient, effective and robust. The branch and price algorithm completes all test cases in less than 5 seconds, while Gurobi in general requires much longer computation time. Also, the “move-forward” heuristic is very helpful for finding a good upper bound for the second stage, which significantly reduces the problem size and speeds up the solution approach. Furthermore, according to the numerical results, the branch and price algorithm is insensitive both to the number of traditional and next-generation quay cranes and to the safety clearance parameter. The findings of this study can serve as a guideline for coordinating scheduling of traditional and next-generation quay cranes at port.
The purchase of next-generation quay cranes requires significant funding for infrastructure preparation, which may outweigh the advantages of reducing service time for utilizing next-generation quay cranes. To make our work more relevant, a careful analysis of the return from investment is required in the follow-up study.

Key words: container terminal, next-generation quay cranes, quay crane scheduling, branch and price

摘要： 码头的工作效率与码头起重机的调度过程直接相关。在同时考虑非交叉约束和安全间距约束的情况下,本文研究下一代码头起重机和传统码头起重机共同为码头船舶工作的调度问题,即码头起重机协同调度问题。传统起重机有一辆起重小车,一次只能装卸一个集装箱;下一代起重机有两根主梁,每根主梁上有两辆起重小车,因此一次最多可以同时装卸4个集装箱。本文先为该问题构建一个整数规划模型,然后设计一类启发式算法—“顺延”算法来求解该问题的近似解,最后利用“顺延”算法给出的近似解作为初始解启动分支定价算法,来获得该问题的最优解。数值计算结果表明,分支定价算法求解速度明显优于商业软件Gurobi,所有测试算例均可以在5秒内完成求解。同时,分支定价算法对下一代起重机和传统起重机的数量以及安全间距的敏感度较低。本研究的成果可为港口运营过程中码头起重机的调度提供理论依据和实践指导。

关键词: 集装箱码头, 下一代码头起重机, 码头起重机调度, 分支定价