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

doi:10.11772/j.issn.1001-9081.2015.01.0247

计算机应用 ›› 2015, Vol. 35 ›› Issue (1): 247-251.DOI: 10.11772/j.issn.1001-9081.2015.01.0247

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

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

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

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

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

摘要/Abstract

摘要：

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

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

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

中图分类号:

F224
TP18

郑红星, 吴岳, 涂闯, 刘进平. 单船岸桥分配与调度集成优化模型[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[J]. 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.)

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

Quay crane allocation and scheduling joint optimization model for single ship

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

[1]	林东东, 李曼曼, 陈少真. 基于神经区分器的KATAN48算法条件差分分析方法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2462-2470.
[2]	石一鹏, 刘杰, 祖锦源, 张涛, 张国群. 基于混合整数线性规划模型的SPONGENT S盒紧凑约束分析[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1504-1510.
[3]	徐周波, 陈浦青, 刘华东, 杨欣. 基于自注意力网络的深度图匹配模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1005-1012.
[4]	刘宗甫, 袁征, 赵晨曦, 朱亮. 对PICO算法基于可分性的积分攻击[J]. 计算机应用, 2020, 40(10): 2967-2972.
[5]	杨晓华, 郭健全. 模糊环境下多周期多决策生鲜闭环物流网络[J]. 计算机应用, 2019, 39(7): 2168-2174.
[6]	康鲲鹏. 基于核算法解决多维多选择背包问题[J]. 计算机应用, 2012, 32(08): 2168-2175.
[7]	彭利民刘浩王伟兵. WDM光网络动态虚拟拓扑重构算法[J]. 计算机应用, 2009, 29(1): 21-24.
[8]	彭利民刘浩. 多信道无线Mesh网络信道分配算法[J]. 计算机应用, 2009, 29(07): 1849-1851.
[9]	陈锦源彭利民. 多信道无线网状网自适应路由算法[J]. 计算机应用, 2009, 29(05): 1211-1213.