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

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