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

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

作　　者：郑红星 朱徐涛 李振飞 ZHENG Hongxing;ZHU Xutao;LI Zhenfei(College of Transportation Engineering,Dalian Maritime University,Dalian Liaoning 116026,China;School of Maritime Economics and Management,Dalian Maritime University,Dalian Liaoning 116026,China)

机构地区：[1]大连海事大学交通运输工程学院,辽宁大连116026 [2]大连海事大学航运经济与管理学院,辽宁大连116026

出　　处：《计算机应用》2021年第10期3049-3055,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(71872025)。

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

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

分 类 号：U692.43[交通运输工程—港口、海岸及近海工程]