This paper proposed a liner programming model to deal with the Quay Crane (QC) allocation and scheduling problem for single ship under the circumstance of fixed berth allocation. With the aim of minimizing the working time of the ship at berth, the model considered not only the disruptive waiting time when the quay cranes were working, but also the workload balance between the cranes. And an Improved Ant Colony Optimization (IACO) algorithm with the embedding of a solution space split strategy was presented to solve the model. The experimental results show that the proper allocation and scheduling of quay cranes from the model in this paper can averagely save 31.86% of the crane resource compared with full application of all available cranes. When comparing to the solution solved by Lingo, the results from IACO algorithm have an average deviation of 5.23%, while the average CPU (Central Processing Unit) computational time is reduced by 78.7%, which shows the feasibility and validity of the proposed model and the algorithm.
郑红星, 吴岳, 涂闯, 刘进平. 单船岸桥分配与调度集成优化模型[J]. 计算机应用, 2015, 35(1): 247-251.
ZHENG Hongxing, WU Yue, TU Chuang, LIU Jinping. Quay crane allocation and scheduling joint optimization model for single ship. Journal of Computer Applications, 2015, 35(1): 247-251.
[1] KIM K H, PARK Y-M. A crane scheduling method for port container terminals [J]. European Journal of Operational Research, 2004, 156 (3): 752-768. [2] MOCCIA L, CORDEAU J F, GAUDIOSO M, et al. A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal [J]. Naval Research Logistics, 2006, 53 (1): 45-59. [3] BIERWIRTH C, MEISEL F. A fast heuristic for quay crane scheduling with interference constraints [J]. Journal of Scheduling, 2009, 12(4): 345-360. [4] NATHAN N. An efficient genetic algorithm for solving the quay crane scheduling problem [J]. Expert Systems with Applications, 2012, 39 (2): 13108-13117. [5] MEISEL F, BIERWIRTH C. A unified approach for the evaluation of quay crane scheduling models and algorithms [J]. Computers & Operations Research, 2011, 38(3): 683-693. [6] LEGATO P, TRUNFIO R, MEISEL F. Modeling and solving rich quay crane scheduling problems [J]. Computers & Operations Research, 2012, 39(9): 2063-2078. [7] LE M, ZHAO Y, LIU X. Shore-mounted gantry crane scheduling for single vessel under time window-using mathematical programming and rule heuristic algorithm [J]. Computer Engineering and Applications, 2014, 50(9): 242-248.(乐美龙,赵彦营,刘秀玲.时间窗下单船岸桥调度——基于数学规划和规则的启发式算法[J].计算机工程与应用,2014,50(9):242-248.) [8] MEISEL F. The Quay crane scheduling problem with time windows [J]. Naval Research Logistics, 2011, 58(7): 619-636. [9] LEGATO P, MAZZA R M, TRUNFIO R. Simulation-based optimization for discharge/loading operations at a maritime container terminal [J]. OR Spectrum, 2010, 32(3): 543-67. [10] CHUNG S H, CHOY K L. A modified genetic algorithm for quay crane scheduling operations [J]. Expert Systems with Applications, 2012, 39(4): 4213-4221. [11] SU N, ZHANG M, JOHNSTON M, et al. Hybrid evolutionary computation methods for quay crane scheduling problems [J]. Computers & Operations Research, 2013, 40(8): 2083-2093. [12] LU Z, HAN X, XI L, et al. A heuristic for the quay crane scheduling problem based on contiguous bay crane operations [J]. Computers & Operations Research, 2012, 39(12): 2915-2928. [13] CHEN J, LEE D-H, CAO J. Heuristics for quay crane scheduling at indented berth [J]. Transportation Research Part E: Logistics and Transportation Review, 2011, 47(6): 1005-1020. [14] FAN Z, LE M. A genetic algorithm to minimize the makespan and waiting time for the bi-objective quay crane scheduling problem [J]. Journal of Systems and Management, 2013, 22(1): 120-127.(范志强,乐美龙.最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法[J].系统管理学报,2013,22(1):120-127.) [15] DIABAT A, THEODOROU E. An integrated quay crane assign-ment and scheduling problem [J]. Computers & Industrial Engineering, 2014, 73: 115-123. [16] CAI G, DONG E. Comparison and analysis of generation algorithm and ant colony optimization on TSP [J]. Computer Engineering and Applications, 2007, 43(10): 96-98.(蔡光跃,董恩清.遗传算法和蚁群算法在求解TSP问题上的对比分析[J].计算机工程与应用,2007,43(10):96-98.)