Research Article: Multiple quay cranes scheduling for double cycling in container terminals

Date Published: July 10, 2017

Publisher: Public Library of Science

Author(s): Yanling Chu, Xiaoju Zhang, Zhongzhen Yang, Myung-Il Roh.


Double cycling is an efficient tool to increase the efficiency of quay crane (QC) in container terminals. In this paper, an optimization model for double cycling is developed to optimize the operation sequence of multiple QCs. The objective is to minimize the makespan of the ship handling operation considering the ship balance constraint. To solve the model, an algorithm based on Lagrangian relaxation is designed. Finally, we compare the efficiency of the Lagrangian relaxation based heuristic with the branch-and-bound method and a genetic algorithm using instances of different sizes. The results of numerical experiments indicate that the proposed model can effectively reduce the unloading and loading times of QCs. The effects of the ship balance constraint are more notable when the number of QCs is high.

Partial Text

As the global container trade volume continues to grow, the throughput of container terminals continues to increase as well. One of the considerations when choosing ports is the vessel turnaround time, which is mainly affected by the efficiency of quay cranes (QCs). Port managers struggle to find ways to increase operational efficiency to attract more containers in the fiercely competitive environment. Unlike other measures, such as adding equipment and terminal expansion, double cycling is a low-cost method that can efficiently improve the productivity of QCs. Due to this and its other advantages, such as increasing the utilization of trucks and QCs, double cycling has been implemented in numerous ports, such as those in Los Angeles, Norfolk and Rotterdam.

Daganzo [2] first addressed the crane scheduling problem and formulated a linear integer programming to minimize the makespan. Many researchers subsequently began investigating QC scheduling problems to increase port productivity. Among the strategies applied in container terminals, double cycling operation has been implemented in the ports of Los Angeles, Shanghai, and Tianjin for its ability to increase the equipment utilization and productivity of QCs. Many studies have proven that its application in Ningbo Port reduced the terminal operation cost and increased the unloading and loading efficiency [3].

The proposed model is an integer program that can be solved by the branch-and-bound (B&B) method. However, for a complex problem, it may not be solved in polynomial time. The Lagrangian relaxation method provides an upper bound to the original problem. The main idea is to remove complex constraints to the objective function, and then, the new problem is easy to solve. The objective of the proposed model is to optimize the sequence of the QCs with the ship balance constraint. Obviously, if the ship balance constraint is removed, each QC works independently, and several algorithms have been developed to solve the single-QC sequencing problem. Therefore, the ship balance constraint is relaxed, and then, the model is decomposed by QCs. An algorithm based on Lagrangian relaxation is designed to obtain a feasible solution. In addition, we also design a GA to solve the model to compare the efficiency of the Lagrangian relaxation based heuristic.

This section presents the computation results optimized by the model and algorithm. First the validity of the model is tested with one example using the LRH. Then, the LRH is compared with the B&B method and GA in terms of solution quality and computational time. The B&B method was implemented using CPLEX 12.61.

In this paper, an optimization model of the sequence of multiple QCs with double cycling strategies is developed to increase the operational efficiency in a container terminal. The proposed model considers the ship balance constraint with multiple QCs unloading a ship simultaneously. Our objective is to minimize the makespan of the ship berthing. The Lagrangian relaxation method is used to obtain an upper bound of the original problem. Then, a Lagrangian relaxation algorithm is proposed to obtain a feasible solution based on the LRP. Finally, numerical experiments indicate that the optimization model can efficiently reduce the QC’s operation time, and Lagrangian relaxation can provide a tight upper bound. In addition, for small-scale problems, the B&B method can provide an exact solution in a reasonable amount of time. For large-scale problems, the performance of the Lagrangian relaxation based heuristic is also compared with that of the GA. The results show that the GA solves the problem faster, but the solution quality of the LRH is higher. The impact of the numbers of QCs, rows and time periods on the computation time of the proposed heuristics is also analysed. As expected, the computation time of the heuristics is not significantly influenced by these three parameters.




0 0 vote
Article Rating
Notify of
Inline Feedbacks
View all comments