不确定环境下泊位—岸桥多目标联合调度仿真

赵 旭，索 浩，苗雨莹

(大连海事大学交通运输工程学院，辽宁 大连 116026)

1 引言

随着经济全球化与国际贸易的发展，集装箱运输已成为货物运输的主要方式。集装箱码头作为集装箱运输的缓冲地，在整个运输过程中占有重要地位，而港口运营效率和服务质量的发展对提升港口核心竞争力有着至关重要的作用。因此，如何合理分配集装箱码头资源，进一步提高码头作业效率和客户满意度，成为了码头运营商的首要任务。

目前已有许多学者对集装箱码头泊位—岸桥调度问题进行了研究，Imai等[1]以整个过程的总服务时间最短为目标建立模型，并利用遗传算法对问题进行求解；桂小娅等[2]以最小化船舶总在港时间为目标分析泊位与岸桥资源的分配问题，并设计了一种双层循环迭代算法对模型进行求解；乐美龙[3]以船舶在港时间最短为目标，构建泊位岸桥调度混合整数规划模型，并设计两阶段启发式算法对模型进行了求解；吴迪等[4]为缩短船舶平均在港时间和码头作业成本构建了两个优化子模型，利用其系统关联性建立出完整的泊位—岸桥联合分配模型，设计了模拟植物生长交替进化算法进行求解；杨春霞等[5]同时考虑船舶在港时间和码头生产成本最小建立了优化模型，并提出一种多目标遗传算法对模型进行求解，获得了综合收益较大的满意解；宋云婷等[6]以离港保证率最大和码头作业成本最低为目标，构建了泊位岸桥联合调度多目标模型，并利用遗传算法求解，得到Pareto非劣解集。

综上所述，已有研究中多以船舶在港时间最小为目标，考虑因素较为单一，而在多目标优化方法的研究中，大多数研究针对确定性环境，不确定环境下的多目标泊位—岸桥联合调度问题仍有待深入研究。对此，本文基于连续泊位条件，综合考虑船舶偏离偏好靠泊位置和岸桥同时作业干扰的影响，以船舶延迟离港时间最小和缓冲时间最大以及最小化集装箱码头作业成本为目标，建立了不确定环境下集装箱码头泊位—岸桥多目标优化模型。

2 模型建立

2.1 问题描述与基本假设

泊位-岸桥联合调度的目的是解决到港船舶靠泊位置、靠泊时间的指派以及具体岸桥分配的问题。在本文的研究主要针对连续型泊位，即在满足物理约束的前提下，船舶可以在码头任意位置靠泊(如图1所示)，这种方式可以更有效的利用泊位空间资源，提高港口的作业效率，但同时也增加了调度方案优化的难度。此外，一方面到港船舶都有一个偏好的靠泊位置，此时水平集卡运输距离和岸桥等待时间最短。另一方面，为同一艘船舶服务的岸桥之间会有不可互相跨越及安全距离等因素的干扰，因此会造成作业效率的降低。所以分配泊位和岸桥时，不仅要考虑问题的现实约束，还必须考虑船舶偏离偏好靠泊位置和岸桥同时作业干扰的影响[7]。

在不确定方面，泊位-岸桥联合调度问题中最常见的不确定因素是到港时间的不确定和岸桥作业时间的不确定。而相对来说，岸桥作业时间的不确定性影响较小[8]，故本文主要研究船舶到港时间的不确定性，假设船舶的实际到港时间是一个服从以船舶的预到港时间为均值的均匀分布，并采用设置缓冲时间的方法来吸收不确定性，其中缓冲时间的取值范围与船舶到港时间的变动范围有关[9]，即θmax=2μ，其中，θmax为缓冲时间最大值，μ为船舶到港时间的标准差。基于以上内容，模型假设如下：

1)连续泊位各处水深等物理条件相同且均满足船舶靠泊条件。

2)到港船舶作业过程中不能移动。

3)每艘船的船舶装卸量和偏好靠泊位置已知。

4)两船之间的安全距离为10m。

5)每艘船的作业岸桥数都有最大最小值限制。

6)岸桥位于同一轨道，从左至右依次编号，不同岸桥之间不能互相跨越。

图1 靠泊方式示意图

2.2 参数定义

1)常数变量

L：码头岸线总长度；

T：计划期内若干时间段的集合；

V：表示待分配的船舶集合，V={1，2，…V}；

H：正在被服务的岸桥集合；

Q：码头岸桥总数；

li：船i的长度；

ai：船舶i的预到港时间；

di：船舶i的预离港时间；

mi：完成船i装卸任务所需的岸桥装卸台时；

ωi：船舶i的优先服务系数；

λ：目标函数权重系数；

ωi：客户服务系数，由船舶i的装卸量决定；

c1：由于船舶i偏离偏好靠泊位置产生的偏移单位距离成本；

c2：岸桥单位时间作业成本；

c3：单位泊位占用成本；

α：岸桥同时作业的干扰系数，即当n台岸桥同时为船舶i作业一个单位时间时，只能产生nα个有效作业时间段；

M：一个充分大的正整数。

(2)决策变量

xi：船舶i的靠泊位置；

yi：船舶i的计划靠泊时间；

bi：船舶i的装卸时间；

θi：添加给船舶i的缓冲时间；

rit：为0-1变量，当t时刻船舶i在港作业时，rit=1，否则rit=0；

2.3 多目标优化模型

(1)

minf2

(2)

模型约束：

(3)

(4)

xi+li≤L

(5)

(6)

(7)

yi≥ai

(8)

(9)

(10)

(11)

(12)

xi，Δxi≥0，∀i∈V

(13)

∀k∈Q，i≠j

(14)

式(1)第一部分表示船舶延迟离港时间最小，第二部分表示设置缓冲时间最大。式(2)表示集装箱码头作业成本最小，其中包括由于船舶未停靠在最佳位置造成的运输成本、岸桥装卸作业成本以及泊位占用成本。式(3)保证分配给船舶的岸桥有效单位时间段数满足考虑船舶偏离系数的情况下船舶所需的作业时间段数。式(4)定义Δbi的值。式(5)保证每艘船都靠泊在岸线之内。式(6)保证同时作业的岸桥数量不超过码头的总岸桥数量。式(7)确保每艘船舶配置的岸桥数量在该船舶允许的作业岸桥数量范围之内。式(8)规定计划靠泊时间的下界。式(9)规定缓冲时间的取值范围。式(10)约束船舶的靠泊位置关系。式(11)约束船舶的靠泊时间关系。式(12)保证所有船舶在靠泊位置和靠泊时间上没有冲突。式(13)和式(14)规定参数取值范围。

3 基于NSGA-II算法的模型求解

本文研究的连续泊位-岸桥分配问题属于NP-hard问题[10]，传统优化算法很难对其进行快速求解，多采用智能算法进行求解；并且本文所建模型为多目标规划模型，在针对多目标优化算法的研究中，带精英策略非支配排序的遗传算法(non-dominatedsorted genetic algorithm-II，NSGA-II)因其随机性、鲁棒性等特点，应用较为广泛[11]。故本文设计了启发式算法和NSGA-II算法相结合的方法对问题进行求解。启发式算法用于生成初始可行解与基因修复，以减少问题维度，减少算法计算时间，NSGA-II算法用于优化决策变量，以得到Pareto解集。算法流程如图2所示。

图2 算法流程

3.1 染色体编码与适应度的计算

采用整数编码的方式对染色体进行编码，设染色体长度为4k，其中1到k位基因表示船舶1到船舶k的靠泊时间，第k+1至2k的基因位表示船舶1到船舶k的靠泊位置，第2k+1到3k的基因位表示配置的岸桥，而第3k+1到4k的基因位表示添加的缓冲时间。如靠泊船舶为5艘时，染色体编码为图3所示。通过式(1)与式(2)计算出个体的目标函数值，作为个体的适应度函数值。

图3 泊位—岸桥联合调度染色体编码方式

3.2 初始解的生成

根据1.4节中的模型约束，为每艘船舶设置靠泊位置、靠泊时间、岸桥数量和缓冲时间，依次在泊位-时间时空图上置入待分配船舶，作为算法的初始可行解。具体步骤如下：

Step1：更新决策点，输入已靠泊船舶的靠泊位置、靠泊时间、岸桥数量和缓冲时间。

Step2：初始化所有待分配船舶，以预计到港时间顺序分配其靠泊顺序，设船舶靠泊顺序为i，船舶i的靠泊时间为Si，靠泊位置为bi；

Step3：判断Si时刻未被占用的岸线中，是否可以停靠船舶i，判断原则为剩余连续岸线长度不小于船舶长度，如果可以停靠，从可用岸线中随机选取一个可行的靠泊位置，转Step5，否则转Step4。

Step4：如果Si时刻未被占用的岸线中，没有可以停靠船舶i的靠泊位置，则将船舶i的靠泊时间推迟一个单位，即Si=Si+1，转Step3。

Step5：判断Si时刻可用岸桥是否大于船舶i开工作业的最小岸桥数量，若是，则从可用岸桥中分配任意数量岸桥给船舶i，否则Si=Si+1，转Step3。

Step6：令i=i+1，对下一艘船舶设置靠泊位置、靠泊时间、岸桥数量和缓冲时间。

3.3 快速非支配排序和拥挤距离的计算

在计算出个体适应度值后，通过快速非支配排序算法对种群进行分层，得到不同的非支配解集及其非支配序(即第几层)，其中非支配序较小的个体支配非支配序大的个体，即前者两个目标的适应度值均优于后者；而非支配序相等的个体互不支配，之后对每个非支配层的个体进行拥挤距离的计算，拥挤距离大代表更好的多样性。

3.4 选择操作

选择操作采取规模为2的锦标赛选择法，选出非支配序较小的个体进行交叉操作，对于非支配序相等的个体，则选取拥挤距离较大的个体。

3.5 交叉操作

选择模拟二进制交叉的方法来进行交叉操作，通过模拟二进制的单点交叉工作原理，随机选出交叉点，交换父代个体位于交叉点两侧的编码，以产生新的子代染色体。

p1j=0.5[(1+γj)x1j+(1-γj)x2j]

(15)

p2j=0.5[(1-γj)x1j+(1+γj)x2j]

(16)

(17)

其中φj∈U(0，1)，p1j和p2j是子代个体，x1j和x2j是父代个体，ζ≻0为分布指数，通常ζ=20。

3.6 变异操作

变异操作采用多项式变异的方法，其表示为：

选取随机数ψi∈[0，1)，计算

(18)

(19)

3.7 基因修复

根据模型判断子代的可行性，若不可行则启动基因修复，步骤如下：

Step1：检查船舶i的靠泊位置是否在[0，L-li]之内，如不是则转到2.2节启发式算法的第3-5步重新生成可行的靠泊位置；否则转Step2。

Step2：检查船舶i的靠泊时间是否在到港时间之前，如是则令靠泊时间等于船舶到港时间，转Step3；否则，直接转Step3。

Step3：检查船舶i与己配置完毕的船舶是否在时间和岸线上有冲突，如不冲突，转Step4；否则，为船舶i重新选择靠泊位置，如果找不到可行靠泊位置，则将船舶靠泊时间推后一个单位，直到找到可行的泊位位置为止，转Step4。

Step4：检查分配给船舶i的岸桥数是否可行，如不可行，重新生成分配岸桥数，转Step1。

4 算例仿真与分析

4.1 算例生成

现根据洋山港区某日船舶到港情况设计算例进行数值仿真，设岸线长1200米，配置岸桥25台，计划期内，到港船舶15艘，岸桥作业效率为25TEU/h，具体信息如表1。船舶的偏好靠泊位置在可靠泊范围内随机生成，设船舶到港时间服从均值为2的均匀分布，由船舶到港时间标准差可计算出θmax=2。取岸桥同时作业干扰系数α为0.9，船舶靠泊位置偏离系数β为0.0001。λ、c1、c2、c3分别为0.6、0.001、0.035、0.01。

表1 到港船舶相关信息

4.2 结果分析

以MATLAB为平台对算法进行实现，设NSGA-II算法中种群规模为50，最大迭代次数1000，交叉概率0.7，变异概率0.02。通过优化算法可以得到问题Pareto最优解集(如图4所示)。

图4 多目标优化模型的Pareto最优解集

为了解决实际问题，港口仍需确定选择策略以确定最终的调度方案。为提高港口运营效率，本文以最小化最大完工时间为选择标准，选出最终调度方案(如表2所示)，其甘特图表示如图5所示，每个矩形代表靠泊的船舶，横坐标表示靠泊时间，纵坐标表示靠泊位置，添加的矩形表示分配的缓冲时间，V表示船舶的序号，括号内数值表示为船舶分配的岸桥数目，所选方案相关数据如表所示。

图5 最终调度方案示意图

表2 最终调度方案

表3 相关数据

根据表3相关数据分析可以看出，本文选取的最终调度方案在船舶准时到港的情况下，所有船舶均可在期望离港时间前离港，在船舶延迟到港时间小于缓冲时间的情况下，可以使其中10艘船舶准时离港，不影响码头作业计划，增强了作业计划的鲁棒性。此外，本文以最小化最大完工时间为选择标准，码头可根据运营策略的不同设置其它选择标准，调整调度方案。

5 结论

本文针对到港时间不确定条件下的泊位岸桥联合调度问题，通过设置缓冲时间的方式吸收了泊位岸桥联合调度中的不确定因素，并在兼顾码头运营商与客户利益均衡的情况下，加入了对码头运营成本的考量，建立了不确定条件下集装箱码头泊位—岸桥多目标优化模型。接着，针对模型设计了嵌套启发式算法的NSGA-II算法进行求解，并应用算例对模型与算法的有效性进行了验证，获得了Pareto最优解集，提高了作业计划的鲁棒性。在实际应用过程中，码头运营商可以根据港口运营策略的不同，及时调整对调度方案的决策，具有一定的实用价值与可操作性。

在研究中，本文仅考虑船舶到港时间的不确定问题，而在实际中，码头作业面临多种突发事件，如何更加全面的考量不确定条件下集装箱码头作业问题，寻求更优的调度方案，是下一步将要研究的内容。