Quay crane allocation and scheduling joint optimization model for single ship

doi:10.11772/j.issn.1001-9081.2015.01.0247

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (1): 247-251.DOI: 10.11772/j.issn.1001-9081.2015.01.0247

Previous Articles Next Articles

Quay crane allocation and scheduling joint optimization model for single ship

ZHENG Hongxing, WU Yue, TU Chuang, LIU Jinping

Transportation Management College, Dalian Maritime University, Dalian Liaoning 116026, China

Received:2014-07-31 Revised:2014-09-20 Online:2015-01-26 Published:2015-01-01

单船岸桥分配与调度集成优化模型

郑红星, 吴岳, 涂闯, 刘进平

大连海事大学交通运输管理学院, 辽宁大连116026

通讯作者: 郑红星
作者简介:郑红星(1971-),男,河北迁安人,副教授,博士,主要研究方向:物流系统仿真与优化;吴岳(1990-),男,河北沧州人,硕士研究生,主要研究方向:物流系统仿真与优化;涂闯(1989-),男,辽宁葫芦岛人,硕士研究生,主要研究方向:物流系统仿真与优化;刘进平(1976-),女,辽宁海城人,讲师,博士研究生,主要研究方向:供应链管理.
基金资助:
国家自然科学基金资助项目(71371037, 71473024).

Abstract

Abstract:

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.

Key words: Quay Crane (QC) allocation and scheduling, integer linear programming, workload balance, disruptive waiting time, working time of ship at berth, Improved Ant Colony Optimization (IACO) algorithm

摘要：

针对集装箱码头泊位确定条件下的单船岸桥(QC)分配和调度问题,建立了线性规划模型.模型以船舶在泊作业时间最短为目标,考虑多岸桥作业过程中的干扰等待时间与岸桥间的作业量均衡,并设计了嵌入解空间切割策略的改进蚁群优化(IACO)算法进行模型求解.实验结果表明:与可用岸桥全部投放使用的方法相比,所提模型与算法求得结果平均能够节省31.86%的岸桥资源;IACO算法与Lingo求得的结果相比,船舶在泊作业时间的平均偏差仅为5.23%,但CPU处理时间平均降低了78.7%,表明了所提模型与算法的可行性和有效性.

关键词: 岸桥分配和调度, 整数线性规划, 作业量均衡, 干扰等待时间, 船舶在泊作业时间, 改进蚁群优化算法

CLC Number:

F224
TP18

ZHENG Hongxing, WU Yue, TU Chuang, LIU Jinping. Quay crane allocation and scheduling joint optimization model for single ship[J]. Journal of Computer Applications, 2015, 35(1): 247-251.

郑红星, 吴岳, 涂闯, 刘进平. 单船岸桥分配与调度集成优化模型[J]. 计算机应用, 2015, 35(1): 247-251.

References

[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.)

Quay crane allocation and scheduling joint optimization model for single ship

单船岸桥分配与调度集成优化模型

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

[1]	Dongdong LIN, Manman LI, Shaozhen CHEN. Conditional differential cryptanalysis method of KATAN48 algorithm based on neural distinguishers [J]. Journal of Computer Applications, 2023, 43(8): 2462-2470.
[2]	Yipeng SHI, Jie LIU, Jinyuan ZU, Tao ZHANG, Guoqun ZHANG. Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model [J]. Journal of Computer Applications, 2023, 43(5): 1504-1510.
[3]	Zhoubo XU, Puqing CHEN, Huadong LIU, Xin YANG. Deep graph matching model based on self-attention network [J]. Journal of Computer Applications, 2023, 43(4): 1005-1012.
[4]	LIU Zongfu, YUAN Zheng, ZHAO Chenxi, ZHU Liang. Integral attack on PICO algorithm based on division property [J]. Journal of Computer Applications, 2020, 40(10): 2967-2972.
[5]	YANG Xiaohua, GUO Jianquan. Multi-period multi-decision closed-loop logistics network for fresh products with fuzzy variables [J]. Journal of Computer Applications, 2019, 39(7): 2168-2174.
[6]	SHEN Li, LI Jie, ZHU Huayong. Task coordination and workload balance method for multi-robot based on trading-tree [J]. Journal of Computer Applications, 2016, 36(11): 3127-3130.
[7]	GAO Chaofeng XIAO Ling HU Zhihua. Hub-and-spoke network design with constraint of hub cost for less-than-truckload logistics [J]. Journal of Computer Applications, 2014, 34(10): 3034-3038.
[8]	KANG Kun-peng. Core-based multidimensional multiple-choice knapsack solution [J]. Journal of Computer Applications, 2012, 32(08): 2168-2175.
[9]	CHEN Rong-xin CHEN Wei-bin LIAO Hu-sheng. Fractal computing parallelization and implementation in TBB [J]. Journal of Computer Applications, 2011, 31(03): 839-842.
[10]	Yun-Ji SONG Sheng WANG Xiong WANG. Network coding traffic design using column generation techniques [J]. Journal of Computer Applications, 2008, 28(8): 1951-1953.