考虑潮汐影响的连续泊位分配策略

徐亚伟 王志明 李芸

摘要：针对潮汐影响下船舶进出港调度中的连续泊位分配策略优化需求，考虑潮汐影响下的船舶进出港时段、船舶靠离泊安全流速、泊位类型与船型相匹配等多因素约束，根据先来先服务原则，构建混合整数规划模型，并采用改进粒子群优化（particle swarm optimization，PSO）算法进行求解。算例结果给出每艘船的靠泊位置和进出港顺序安排，并通过与标准PSO算法求解的调度方案进行对比，验证改进PSO算法的有效性。研究成果可为实际码头泊位分配决策提供参考。

关键词： 连续泊位分配; 粒子群优化（PSO）算法; 潮汐影响; 先来先服务原则

中图分类号： U691+.3    文献标志码： A

Abstract： In view of the demand of the continuous berth allocation strategy optimization in the scheduling of ships entering and leaving a port under the influence of tide， considering the constraints such as the time window of ships entering and leaving a port under the influence of tide， the safe flow rate of ship berthing and unberthing， and the matching of the berth type and the ship type， according to the first-come first-served principle， a mixed integer programming model is constructed， and an improved particle swarm optimization （PSO） algorithm is used to solve the model. The results of the example show the berthing positions and the sequence of entering and leaving a port of ships， and the results are compared with the scheduling scheme solved by the standard PSO algorithm to verify the effectiveness of the improved PSO algorithm. The research results can provide reference for the actual berth allocation decision-making.

Key words： continuous berth allocation; particle swarm optimization （PSO） algorithm; influence of tide; first-come first-served principle

0 引 言

在航海實践中，若船舶提前进港则可能没有泊位靠泊，船舶必须在港口内等待，这不仅对船舶安全不利，而且也有碍港口内其他船舶安全航行;若船舶延迟进港，则港口与船舶的等待时间必将延长，势必造成港口服务效率下降。随着港口吞吐量的增加及船舶数量的增多，合理的船舶进出港安排和泊位分配已经成为港口急需解决的问题。

近年来，由于全球港口吞吐量的增加，船舶进出港调度与泊位分配问题引起了学术界广泛关注。在船舶进出港调度研究方面：张新宇等[1]为提高双向通航港口的船舶调度效率，使用多目标遗传算法获取最佳调度方案;BIERWIRTH等[2]针对船舶调度问题进行了详细的属性分类研究。在离散泊位研究方面：IMAI等[3-4]首先提出了离散型泊位分配模型，然后在此基础上提出了考虑船舶优先权的泊位分配模型;韩笑乐等[5]考虑了具有不同服务优先级别的船舶动态到达情形，以船舶在港总时间与加权延迟时间之和最小为目标，设计结合禁忌深度搜索算法与模拟退火算法的混合算法求解;TING等[6]考虑船舶动态到达情况下的泊位分配问题，以服务总时间最短为目标函数，设计粒子群优化（particle swarm optimization，PSO）算法求解;ZHEN等[7]考虑潮汐时间窗口和航道通行能力约束，建立泊位分配和岸桥分配的综合优化模型，以等待和延误总时间最短为目标函数，提出基于列生成算法的求解方法来求解该模型的最优解;郑红星等[8]针对考虑潮汐影响的泊位分配与船舶集成调度问题，构建了混合整数规划模型，并设计了改进禁忌搜索算法求解。在连续泊位研究方面：童珊[9]针对考虑船舶优先权的泊位分配问题，以提高集装箱船在港口的靠泊效率为目标，建立混合整数规划模型，并利用遗传算法进行求解。乐美龙等[10]在研究泊位和岸桥分配时，侧重考虑泊位偏好和服务优先权两大因素，以最小化所有船舶的在港总时间为目标建模并利用遗传算法求解;SHEIKHOLESLAMI等[11]在研究集装箱码头的动态泊位分配问题时，考虑了船舶优先权以及潮汐对锚地到码头的航道的影响，采用遗传算法结合模式搜索算法求解该问题;DU等[12]考虑了潮汐和船舶虚拟到达策略，以船舶离港延误总时间最短为目标建模，用CPLEX进行求解;张雯钰等[13]考虑了公平措施，以船舶在港时间最短和集装箱码头惩罚成本最小为优化目标建模，并设计了模拟退火算法进行求解。

综上所述，现有关于船舶进出港调度和泊位分配的研究虽力求更加符合实际调度过程，但缺少考虑潮汐对船舶泊位分配的影响的深入研究，相关成果与满足港口实际调度需求还有一定差距。本文针对潮汐影响下的船舶进出港次序与泊位分配问题，以船舶到港至离港的总时间最短为目标，总体上满足先来先服务的原则，侧重分析在安全流速下船舶靠离泊时段和船舶乘潮进出港的时间窗口，并采用改进PSO算法确定船舶进出港次序和泊位分配方案。

1 参数定义及泊位分配问题描述

1.1 参数定义

V表示到港船舶集合，i，j∈V;Vin表示需乘潮进港的船舶集合;Vout表示需乘潮出港的船舶集合;G表示港口泊位集合，b∈G;T表示时间序列集合，t∈T;K表示潮汐周期集合，k=1，2，…，K。ai为船i到港时刻;Touti为船i离开港口时刻;Xi表示船i靠泊的位置;Li表示船i的长度;Ti，w1表示船i等待进港时间;Ti，w2表示船i完成装卸作业后等待离泊时间;Tbi表示船i准备靠泊时刻;T fi表示船i泊位作业完成时刻;Ci表示船i在码头的作业时间;Tini表示船i进港时刻;C表示船舶通过航道的时间;LB表示码头泊位的长度;TDi表示船i准备离泊时刻;TEDi表示预计船i离开泊位的时刻;M表示一个足够大的正数;Sb表示泊位b的类型，其值1、2分别表示普通船泊位、需乘潮进出港船泊位;Hi表示船i的类型，其值1、2分别表示普通船、需乘潮进出港船;Eini表示船i的预计进港时刻;[Wi，k，B1，Wi，k，B3]表示需乘潮船i在第k次潮汐周期中可以乘潮进出港的时间窗口;[Wi，k，d2，Wi，k，d3]和[Wi，k，d4，Wi，k+1，d1]表示船i在第k次潮汐周期中可以靠离泊的时间窗口;[Wi，k，d1，Wi，k，d2]和[Wi，k，d3，Wi，k，d4]表示船i在第k次潮汐周期中不可以靠离泊的时间窗口。XBij，若船i与船j的泊位没有重叠，则为1，否则为0;XTij，若船i与船j的靠泊时间在时间轴上没有重叠，则为1，否则为0;Xi，t，b，若在t时间船i靠泊在泊位b上，则为1，否则为0;Ui，b，若船i延迟进港，则为1，否则为0;Zi，b，若船i延迟出港，则为1，否则为0;δini，k，若需乘潮船i的进港时刻在第k次潮汐周期中可以乘潮进港的时间窗口内，则为1，否则为0;δouti，k，若需乘潮船i的離泊时刻在第k次潮汐周期中可以乘潮出港的时间窗口内，则为1，否则为0。

1.2 泊位分配问题描述

现在国内外大部分码头岸线都具有连续平直型的特点，特别是在集装箱船兴起后，连续平直的码头岸线不仅有利于船舶的靠泊，而且有利于提高码头的利用率。连续性泊位分配的原理是：在码头岸线允许的范围内，船舶可以停靠在任意的泊位上，船舶的安全靠泊转换为图1所示，要保证两艘船不能在时间和空间上出现重叠。

港口调度过程为：在预知船舶的抵港计划、船期和配载计划后，港口为各船舶分配合理数量的岸桥， 并确定其进港时间。在计划期内，当到港船舶数量较少时，每艘船都可以得到及时的服务，这样船舶等待靠泊的时间较短。随着船舶数量的增加，船舶开始等待排队进港，使得船舶等待靠泊的时间开始增加。船舶进出港调度与泊位分配旨在为到港船舶合理地安排进出港顺序以及靠泊的时间和位置。

潮汐可能影响船舶进出港时通过航道的能力，借助图2进一步阐述潮汐对需乘潮进出港船的影响。以图2中的一个潮汐周期[Wi，k，B1，Wi，k+1，B1]进行分析，[Wi，k，B1，Wi，k，B3]是需乘潮进出港船可以通过航道的时间窗口。在低潮时间窗口内，航道内的潮位不满足需乘潮进出港船航行的水深要求。[Wi，k，B3，Wi，k+1，B1]是需乘潮进出港船所对应的低潮时间窗。在地理位置比较特殊的港口，船舶不是通过航道后就可以进行靠泊作业的。潮流一般在转流后的第3、4小时内，其表层处于急涨或急落时段，潮差较大的港口一般流速较大，具体到不同港口有一定的差异性。如图中[Wi，k，d1，Wi，k，d2]和[Wi，k，d3，Wi，k，d4]这两个时段，出于对船舶安全性的考虑也是不允许靠离泊的。需乘潮船的靠离泊时间窗口为[Wi，k，d2，Wi，k，d3]，若离泊时刻不在[Wi，k，d2，Wi，k，d3]期间，那么需要在泊位等待，等到在[Wi，k，d2，Wi，k，d3]时间窗口内进行离泊作业。

本文的问题可描述为：针对连续泊位的集装箱码头，根据船舶到港时间、装卸量等信息，以计划期内到港船舶为研究对象，着重考虑船舶需乘潮进出航道及船舶在安全流速下靠离泊的实际需求。为使模型更加贴合实际，总体上要满足先来先服务的调度规则，且船舶类型与泊位类型相匹配。

2 模型建立

2.1 模型适用基本要求

基于港口服务基本要求，模型适用的约束要素：（1）每艘船都必须进出港靠泊一次;（2）每艘船通过航道的时间相同;（3）泊位岸线视为连续性的，沿码头岸线划分停泊单元;（4）码头岸桥作业效率不变;（5）船舶到港时间已知，且都按时到港;（6）船舶靠离泊时间不计;（7）码头有足够的水域满足船舶掉头的需求。

2.2 数学模型建立

3.3 解的生成策略

步骤1 根据船舶到港时刻先后排序，生成船舶进港次序，作为解的上层编码。

步骤2 当船舶按照进港次序进港后，船舶随机选择一个满足条件的空闲泊位进行靠泊作业。若此时不能满足进港靠泊的约束条件，则等到满足该船进港靠泊条件后再给该船分配泊位。这样得到的船舶靠泊位置作为解的中层编码。

步骤3 依据船舶的进港次序和靠泊位置，以船舶在泊位的作业时间作为解的下层编码，将船舶在泊位的作业时间与等待离泊时间之和作为船舶在泊时间。

步骤4 为保证算法满足实际需求，对上层编码进行适当调整。若两艘船中有一艘船先到达，在先到达的船舶不满足泊位安排时，可以根据需要先安排后到达的船舶进港靠泊。

3.4 进出港流程及编码

按照本文约束对船舶进出港的调度流程及相应编码进行说明，见图4。

4 算例求解与结果分析

4.1 算例求解

设计具体算例，验证模型的可行性。设码头岸线长度为2 000 m，由于船舶靠泊以缆桩系泊且船舶间应留有安全距离，所以沿码头岸线划分40个泊位，每个泊位长度为50 m。设置1～15号泊位为满足大型乘潮船靠泊要求的泊位，普通船没有泊位类型限制。设船舶通过航道的时间为1 h。潮汐周期为12 h，第一个潮汐开始时刻为01：00，结束时刻13：00，以[01：00，7：00]作为满足需乘潮船通过航道的时间窗口。潮流在转流后的第3、4小时内，其表层处于急涨或急落时段，因此为保证船舶靠泊安全与顺利，不允许船舶在该时段进行靠离泊作业。算例采用表2的数据进行求解。

在这一部分，用改进的PSO算法对算例进行测试。算法用MATLAB 2018a进行编码。实验运行在2.3 GHz Intel Core（TM） i5-8300H CPU和16 GB内存的计算机上。改进PSO算法的参数设置为：粒子数N=600;最大迭代次数n=4 000;惯性权重wstart=0.9，wend=0.1;学习因子C1s=2.5，C2s=0.5，C1e=0.5，C2e=2.5;k=0.4。在按照实际需求先来先服务的基础上，最终运行得到船舶进出港调度方案，见表3。

改进PSO算法求解的泊位分配方案见图5。由图5可以看出：需乘潮船进港都有延迟，这主要是因为这种船需要在可以乘潮进出港的时间窗口内进出港，并且船舶类型需要满足码头泊位类型的要求：普通船3、9、10、20进港靠泊都有延迟，这是因为普通船需要在安全流速下靠泊;船舶到达安排总体上满足先来先服务的原则，图中船舶都在安全时间窗口内靠离泊，以及在合适的时间窗口内进出港。根据该模型得出的结果，可以有序地安排船舶进出港及选择相应的泊位。改进PSO算法求解出的目标函数总时间比标准PSO算法求解得出的小，说明采用改进PSO算法能提高解的质量。

潮汐因素影响船舶的进出港次序及船舶靠离泊的时间安排，从而影响后续船舶的泊位分配，因此，在港口服务中需要着重关注潮汐因素对泊位分配的影响。本文所用的模型具有以下特点：考虑先来先服务原则，保证该模型在更大程度上满足航海实践需求，遵循到港船舶服务公平性的原则;更加全面地考虑到实际船舶需要在安全流速下靠离泊，以及在合适的潮汐时间段进出港;考虑不同水深情况下泊位类型的情况，以满足航海实务中船舶停靠的实际泊位需要。本文所得到的结果对于安排船舶进出港及泊位分配有一定的参考价值。

4.2 改进PSO算法有效性驗证

为验证所采用的改进PSO算法在搜索性能上的增强，用标准PSO算法对同样的实验进行对比，参数设置为：粒子数N=600;最大迭代次数n=4 000;惯性权重w=0.8;学习因子C1=1.5，C2=1.5。具体的调度方案见图6。图7是算法求解过程：当改进PSO算法迭代约2 600次时，目标函数值收敛于252 h;当标准PSO算法迭代到约2 400次时，目标函数值收敛于256 h。

为增加实验结果的可靠性，增加几组实验来体现算法改进前后的效果。在其他参数相同的情况下，选取其他20艘船，沿码头岸线分布40个泊位，最大迭代次数n=1 000，算法求解过程见图8。选取其他25艘船，沿码头岸线分布50个泊位，最大迭代次数n=5 000，算法求解过程见图9。

以上一系列数据仿真结果证明，所采用改进PSO算法的求解质量优于标准PSO算法。在改进PSO算法和标准PSO算法求解过程中，随着迭代次数不断增加，目标函数值均不断优化，但是改进PSO算法能在提高算法收敛性的同时能够有效避免陷入局部最优的情况，算法搜索能力更强。因此，上述分析符合预想的情况。

5 结束语

为满足大型船舶顺利进出港及安全靠泊的实际需求，本文在前人研究的基础上考虑潮汐影响下的泊位分配策略。相较于以往的研究，着重分析了在安全流速下船舶靠离泊时段和需乘潮船进出港的时间窗口，建立了以船舶从到港至离港总时间最短为目标的函数，采用改进PSO算法求解该模型。算例结果显示，所提出的船舶泊位分配模型能有效地安排船舶进出港及泊位分配，改进PSO算法求解出的方案优于标准PSO算法求解出的方案。

从本文的研究结果可知，船舶进出港次序与泊位分配受到潮汐因素的影响，因此，在港口服务中需要着重关注潮汐因素对泊位分配的影响。就提高该模型的实际应用价值而言，对多因素综合约束类问题的理论研究还需通过实践优化，才能最终转化成便于用户操作的实用工具。

参考文献：

[1] 张新宇， 郭子坚， 王金涛， 等. 基于航道与泊位资源协调调度的船舶交通优化[J]. 中国航海， 2015， 38（3）： 33-36.

[2] 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. DOI： 10.1016/j.ejor.2014.12.030.

[3] IMAI A， NISHIMURA E， PAPADIMITRIOU S. The dynamic berth allocation problem for a container port[J]. Transportation Research Part B， 2001， 35（4）： 401-417. DOI： 10.1016/s0191-2615（99）00057-0.

[4] IMAI A， NISHIMURA E， PAPADIMITRIOU S. Berth allocation with service priority[J]. Transportation Research Part B， 2003， 35（7）： 437-457. DOI： 10.1016/s0191-2615（02）00023-1.

[5] 韩笑乐， 陆志强， 奚立峰. 具有服务优先级别的动态离散泊位调度优化[J]. 上海交通大学学报， 2009， 43（6）： 902-905. DOI： 10.16183/j.cnki.jsjtu.2009.06.011.

[6] TING C J， WU K C， CHOU Hao. Particle swarm optimization algorithm for the berth allocation problem[J]. Expert Systems with Applications， 2014， 41（4）： 1543-1550. DOI： 10.1016/j.eswa.2013.08.051.

[7] ZHEN Lu， LIANG Zhe， ZHUGE Dan， et al. Daily berth planning in a tidal port with channel flow control[J]. Transportation Research Part B Methodological， 2017， 106： 193-217. DOI： 10.1016/j.trb.2017.10.008.

[8] 郑红星， 吴云强， 邵思杨， 等. 考虑潮汐影响的泊位分配与船舶调度集成优化[J]. 信息与控制， 2020， 49（1）： 95-103. DOI： 10.13976/j.cnki.xk.2020.9091.

[9] 童珊. 基于船舶优先权的集装箱港口泊位分配问题[J]. 交通运输工程与信息学报， 2012， 10（1）： 105-110.

[10] 乐美龙， 刘秀玲. 基于泊位偏好与服务优先级的泊位和岸桥分配[J]. 辽宁工程技术大学学报（自然科学版）， 2013， 32（5）： 709-712.

[11] SHEIKHOLESLAMI A， IIATI G， KOBARI M. The continuous dynamic berth allocation problem at a marine container terminal with tidal constraints in the access channel[J]. International Journal of Civil Engineering， 2014， 12（3）： 344-353.

[12] DU Yuquan， CHEN Qiushuang， LAM J S L， et al. Modeling the impacts of tides and the virtual arrival policy in berth allocation[J]. Transportation Science， 2015， 49（4）： 939-956. DOI： 10.1287/trsc.2014.0568.

[13] 张雯钰， 郝杨杨. 基于船舶作业优先权的靠泊计划仿真优化研究[J]. 计算机仿真， 2020， 37（6）： 130-135.

[14] BABAZADEH A， SHAHBANDI M G， SEYEDALIZADEH-GANJI S R， et al. A PSO algorithm for continuous berth allocation problem[J]. International Journal of Shipping & Transport Logistics， 2015， 7（4）： 479-493. DOI： 10.1504/IJSTL.2015.069687.

[15] 李丽， 牛奔. 粒子群优化算法[M]. 北京： 冶金工业出版社， 2009： 44-59.

[16] 陳水利， 蔡国榕， 郭文忠， 等. PSO算法加速因子的非线性策略研究[J]. 长江大学学报（自科版）理工卷， 2007， 4（4）： 1-4.

（编辑 贾裙平）