双向航道集装箱港口船舶调度优化算法

doi:10.11772/j.issn.1001-9081.2020121973

计算机应用 ›› 2021, Vol. 41 ›› Issue (10): 3049-3055.DOI: 10.11772/j.issn.1001-9081.2020121973

所属专题：前沿与综合应用

双向航道集装箱港口船舶调度优化算法

郑红星^1,2, 朱徐涛¹, 李振飞²

1. 大连海事大学交通运输工程学院, 辽宁大连 116026;
2. 大连海事大学航运经济与管理学院, 辽宁大连 116026

收稿日期:2020-12-15 修回日期:2021-04-30 出版日期:2021-10-10 发布日期:2021-07-14
通讯作者: 郑红星
作者简介:郑红星(1971-),男,河北迁安人,教授,博士,主要研究方向:物流系统优化与仿真;朱徐涛(1996-),男,浙江宁波人,硕士研究生,主要研究方向:物流系统优化与仿真;李振飞(1995-),男,山东东营人,硕士研究生,主要研究方向:物流系统优化与仿真。
基金资助:
国家自然科学基金资助项目（71872025）。

Optimization algorithm of ship dispatching in container terminals with two-way channel

ZHENG Hongxing^1,2, ZHU Xutao¹, LI Zhenfei²

1. College of Transportation Engineering, Dalian Maritime University, Dalian Liaoning 116026, China;
2. School of Maritime Economics and Management, Dalian Maritime University, Dalian Liaoning 116026, China

Received:2020-12-15 Revised:2021-04-30 Online:2021-10-10 Published:2021-07-14
Supported by:
This work is partially supported by the National Natural Science Foundation of China (71872025).

摘要/Abstract

摘要： 针对拥有双向航道的集装箱港口中船舶进出港所遇到的会遇和追越等问题，提出了一种重点考虑服务规则的新型船舶调度优化算法。首先，同时考虑双向航道的现实约束和港口夜航的安全规定；然后，构建了以所有船舶在港总等待时间最小为目标的混合整数规划模型来得出最佳的船舶进出港次序；最后，设计了嵌入聚合策略的分支切割算法对模型进行求解。通过数值实验可知，运用嵌入聚合策略的分支切割算法所得结果与下界值的平均相对偏差为2.59%。同时，与模拟退火算法与量子差分进化算法的对比结果表明，所提的分支切割算法所得的目标函数值相较于两个对比算法所得目标函数值分别减少了23.56%和17.17%，验证了该算法的有效性。在用所提算法得到方案的敏感性分析中比较了不同抵港安全时间间隔和船舶类型比例对方案结果的影响，为双向航道集装箱港口的船舶调度优化提供了决策支持。

关键词: 双向航道, 集装箱港口, 船舶调度, 嵌入式聚合, 分支切割算法

Abstract: For the problems of encountering and overtaking in the process of in-and-out port of ships in the container terminals with two-way channel, a new ship dispatching optimization algorithm focusing on the service rules was proposed. Firstly, the realistic constraints of two-way channel and the safety regulations of port night sailing were considered at the same time. Then, a mixed integer programming model with the goal of minimizing the total waiting time of ships in the terminal was constructed to obtain the optimal in-and-out port sequence of ships. Finally, the branch-cut algorithm with embedded polymerization strategy was designed to solve the model. The numerical experimental results show that, the average relative deviation between the result of the branch-cut algorithm using embedded polymerization strategy and the lower bound is 2.59%. At the same time, compared with the objective function values obtained by the simulated annealing algorithm and quantum differential evolution algorithm, the objective function values obtained by the proposed branch-cut algorithm are reduced by 23.56% and 17.17% respectively, which verifies the effectiveness of the proposed algorithm. The influences of different safe time intervals of ship arriving the port and ship type proportions were compared in the sensitivity analysis of the scheme obtained by the proposed algorithm, providing the decision and support for ship dispatching optimization in container terminals with two-way channel.

Key words: two-way channel, container terminal, ship dispatching, embedded polymerization, branch-cut algorithm

中图分类号:

U692.4+3

郑红星, 朱徐涛, 李振飞. 双向航道集装箱港口船舶调度优化算法[J]. 计算机应用, 2021, 41(10): 3049-3055.

ZHENG Hongxing, ZHU Xutao, LI Zhenfei. Optimization algorithm of ship dispatching in container terminals with two-way channel[J]. Journal of Computer Applications, 2021, 41(10): 3049-3055.

参考文献

[1] IMAI A, NISHIMURA E, PAPADIMITRIOU S. Berth allocation with service priority[J]. Transportation Research Part B:Methodological, 2003, 37(5):437-457.
[2] XIANG X, LIU C C, MIAO L X. A bi-objective robust model for berth allocation scheduling under uncertainty[J]. Transportation Research Part E:Logistics and Transportation Review, 2017, 106:294-319.
[3] MAURI G R, RIBEIRO G M, LORENA L A N, et. al. An adaptive large neighborhood search for the discrete and continuous berth allocation problem[J]. Computers and Operations Research, 2016, 70:140-154.
[4] DULEBENETS M A, GOLIAS M M, MISHRA S. A collaborative agreement for berth allocation under excessive demand[J]. Engineering Applications of Artificial Intelligence, 2018, 69:76-92.
[5] TING C J, WU K C, CHOU H. Particle swarm optimization algorithm for the berth allocation problem[J]. Expert Systems with Applications, 2014, 41(4, Pt 1):1543-1550.
[6] BUDIPRIYANTO A, WIRJODIRDJO B, PUJAWAN I N, et. al. A simulation study of collaborative approach to berth allocation problem under uncertainty[J]. The Asian Journal of Shipping and Logistics, 2017, 33(3):127-139.
[7] KORDIĆ S, DAVIDOVIĆ T, KOVAČ N, et al. Combinatorial approach to exactly solving discrete and hybrid berth allocation problem[J]. Applied Mathematical Modelling, 2016, 40(21/22):8952-8973.
[8] QIN T B, DU Y Q, SHA M. Evaluating the solution performance of IP and CP for berth allocation with time-varying water depth[J]. Transportation Research Part E:Logistics and Transportation Review, 2016, 87:167-185.
[9] CORRECHER J F, ÁLVAREZ-VALDÉS R, TAMARIT J M. New exact methods for the time-invariant berth allocation and quay crane assignment problem[J]. European Journal of Operational Research, 2019, 275(1):80-92.
[10] XIANG X, LIU C C, MIAO L X. Reactive strategy for discrete berth allocation and quay crane assignment problems under uncertainty[J]. Computers and Industrial Engineering, 2018, 126:196-216.
[11] AGRA A, OLIVEIRA M. MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem[J]. European Journal of Operational Research, 2018, 264(1):138-148.
[12] 韩骏, 孙晓娜, 靳志宏. 集装箱码头泊位与岸桥协调调度优化[J]. 大连海事大学学报, 2008, 34(2):117-121.(HAN J, SUN X N, JIN Z H. Coordinated optimization method for berth and quay crane allocation in container terminal[J]. Journal of Dalian Maritime University, 2008, 34(2):117-121.)
[13] 周鹏飞, 康海贵. 面向随机环境的集装箱码头泊位-岸桥分配方法[J]. 系统工程理论与实践, 2008, 28(1):161-169. (ZHOU P F, KANG H G. Study on berth and quay-crane allocation under stochastic environments in container terminal[J]. Systems Engineering-Theory and Practice, 2008, 28(1):161-169.)
[14] 张新宇, 李瑞杰, 张加伟, 等. 多种航道条件下的港口船舶交通组织优化[C]//第十三届中国智能交通年会大会论文集. 北京:电子工业出版社, 2018:708-717.(ZHANG X Y, LI R J, ZHANG J W, et al. Vessel scheduling optimization in different types of waterway[C]//Proceedings of the 13th China Intelligent Transportation Annual Conference. Beijing:Publishing House of Electronics Industry, 2018:708-717.)
[15] 郑红星, 刘保利, 邓春远, 等. 单向航道散货港口船舶调度优化[J]. 运筹与管理, 2018, 27(12):28-37.(ZHENG H X, LIU B L, DENG C Y, et al. Ship scheduling optimization in one-way channel bulk harbor[J]. Operations Research and Management Science, 2018, 27(12):28-37.)
[16] ZHANG X Y, LIN J, GUO Z J, et al. Vessel transportation scheduling optimization based on channel-berth coordination[J]. Ocean Engineering, 2016, 112:145-152.
[17] 何春华. 大数据分析下双向通航港口船舶自适应调度算法[J]. 舰船科学技术, 2018, 40(5A):43-45.(HE C H. Adaptive ship scheduling algorithm for two-way navigation port based on big data analysis[J]. Ship Science and Technology, 2018, 40(5A):43-45.)

双向航道集装箱港口船舶调度优化算法

Optimization algorithm of ship dispatching in container terminals with two-way channel

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	王永航, 张天宇, 郑红星. 考虑恶劣天气的班轮多阶段重调度方法[J]. 计算机应用, 2021, 41(1): 286-294.
[2]	郑红星, 王泉慧, 任亚群. 考虑潮汐影响的班轮多船型船舶调度[J]. 计算机应用, 2019, 39(2): 611-617.
[3]	毕娅李文锋. 集装箱港口集群下多港口多泊位联合调度方法[J]. 计算机应用, 2012, 32(02): 448-451.