Integrated Discrete Berth Allocation and Quay Crane Scheduling Under Tidal Influence at Container Terminal

doi:10.12005/orms.2017.0152

Abstract

Abstract: Since berth and quay crane are limited resources at container ports, berth scheduling and quay crane scheduling are significantly interrelated. When entering in and leaving out container terminal, the large(or mega)vessels should make use of tidal condition. By considering tidal influence, the problems of berth allocation, quay crane assignment and quay crane scheduling are integrated, in order to improve the port operation efficiency and customer satisfaction. Firstly, considering the tidal influence and the reality of the dynamic scheduling in quay crane operation, a mixed integer programming model is proposed to minimize the sum of the quay crane operation cost and the demurrage in the planning period. Then an embedded heuristic rule genetic algorithm is put forward. Finally, the results from numerical experiments show the given quay crane group for each ship at any time and the dynamic working time windows for each crane. In addition, the effectiveness of the integrated solution is verified by contrast with an individual optimization scheme.

Key words: tide, berth allocation, quay crane assignment and scheduling, integrated scheduling, genetic algorithm

摘要： 泊位和岸桥是集装箱港口最紧缺的资源,二者的调度问题存在很强的内在关联。针对大型船需乘潮进出港的离散型泊位,为提高集装箱码头运作效率和客户满意度,将泊位分配、岸桥指派和岸桥调度集成为一体。首先,考虑潮汐的影响以及岸桥作业中可动态调度的现实,以计划期内所有抵港船舶的岸桥作业成本和滞期成本之和最少为目标,建立一个混合整数规划模型,然后设计了一个嵌入启发式规则的遗传算法对其进行求解。最后,算例结果中给出了每艘船舶在确切时刻对应的具体岸桥和每个岸桥的动态作业时间窗,并通过与单独优化的方案对比,验证了集成方案的有效性。

关键词: 潮汐, 泊位分配, 岸桥指派和调度, 集成调度, 遗传算法

CLC Number:

U691+3

ZHENG Hong-xing, YIN Hao, CAO Hong-lei, SHI Yue. Integrated Discrete Berth Allocation and Quay Crane Scheduling Under Tidal Influence at Container Terminal[J]. Operations Research and Management Science, 2017, 26(6): 167-175.

郑红星, 尹昊, 曹红雷, 石岳. 考虑潮汐影响的离散型泊位和岸桥集成调度[J]. 运筹与管理, 2017, 26(6): 167-175.

References

[1] Bierwirth C, Meisel F. A follow-up survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research, 2015, 244(3): 675-689.
[2] Park Y M, Kim K H. A scheduling method for berth and quay cranes[J]. OR Spectrum, 2003, 25(1): 1-23.
[3] Huang Y, Liang C, Yang Y.The optimum route problem by genetic algorithm for loading/unloading of yard crane[J]. Computers & Industrial Engineering, 2009, 56(3): 993-1001.
[4] Zhang C, Zheng L, Zhang Z, et al. The allocation of berths and quay cranes by using a sub-gradient optimization technique[J]. Computers & Industrial Engineering, 2010, 58(1): 40-50.
[5] 李娜,靳志宏.连续泊位调度与岸桥配置协同优化[J].中国航海,2011,34(2):86-90.
[6] 乐美龙,刘秀玲.基于泊位偏好与岸桥干扰的泊位和岸桥分配[J].运筹与管理,2014,(1):90-100.
[7] Han X L, Lu Z Q, Xi L F. A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic handling time[C]. International Conference on Computers & Industrial Engineering. IEEE, 2010. 74-79.
[8] Vacca I, Salani M, Bierlaire M. An exact algorithm for the integrated planning of berth allocation and quay crane assignment[J]. Semaine Thérapeutique, 2013, 47(2): 148-161.
[9] Han X L, Gong X, Jo J. A new continuous berth allocation and quay crane assignment model in container terminal[J]. Computers & Industrial Engineering, 2015, 89(C): 15-22.
[10] Hsu H P. A HPSO for solving dynamic and discrete berth allocation problem and dynamic quay crane assignment problem simultaneously[J]. Swarm & Evolutionary Computation, 2016, 27(default): 156-168.
[11] Lee D H, Wang H Q. Integrated discrete berth allocation and quay crane scheduling in port container terminals[J]. Engineering Optimization, 2010, 42(8): 747-761.
[12] Song L, Cherrett T, Guan W. Study on berth planning problem in a container seaport: using an integrated programming approach[J]. Computers & Industrial Engineering,2012,62(1): 119-128.
[13] Unsal O, Oguz C. Constraint programming approach to quay crane scheduling problem[J]. Transportation Research Part E Logistics & Transportation Review,2013,59(59): 108-122.
[14] Lu Z, Han X, Xi L. Simultaneous berth and quay crane allocation problem in container terminal[J]. Journal of Computational & Theoretical Nanoscience,2011,4(6): 2113-2118.
[15] Rodriguez-Molins M, Ingolotti L, Barber F, et al. A genetic algorithm for robust berth allocation and quay crane assignment[J]. Progress in Artificial Intelligence, 2014, 2(4): 177-192.
[16] Meisel F, Bierwirth C. A framework for integrated berth allocation and crane operations planning in seaport container terminals[J]. Transportation Science, 2013, 47(2): 131-147.
[17] 刘鹏.考虑潮汐影响的离散型泊位和岸桥联合动态调度研究[D]. 大连海事大学,2014.