岸桥故障下考虑邻近岸桥共享作业的集装箱码头调度多目标优化

吴 暖，吴 迪，王 诺+

(1.大连交通大学 交通运输工程学院，辽宁 大连 116028；2.大连海事大学 交通运输工程学院，辽宁 大连 116026)

0 引言

岸桥是集装箱码头装卸作业最主要的装卸设备，一旦在作业过程中发生故障，将会直接导致船舶装卸作业中断，延误船舶离港时间，严重影响港口的作业效率。因此，如何在岸桥发生故障后，迅速调整作业计划，尽可能减少对船舶航程的影响，降低码头作业成本确定符合港口和船公司利益的最终方案，对于提高码头管理水平具有重要意义。

关于非正常情况下集装箱码头调度的优化，国内外学者已进行了诸多研究，如不确定环境下的泊位—岸桥调度[1]，集装箱码头的干扰应对调度[2]，港口临时停产后恢复的应急调度[3]等。关于码头作业系统中设备故障的影响，已有少数研究从不同角度进行过分析，如岸桥故障情况下单船装卸的多阶段再调度[4]，基于前景理论的岸桥受干扰重调度[5]等，但考虑以岸桥共享方式来降低设备故障影响的研究很少。实际中，码头调度会采用邻近泊位的岸桥共享作业方式以减少岸桥的启动数量实现降低成本的目的[6]。岸桥出现故障后对船舶靠泊和码头作业的计划都会受影响，因而需兼顾港口和船公司的利益[7]，建立多目标优化模型予以解决，求解时将多目标转换成单目标是最常用的求解方法[8-9]，若直接求解多目标优化模型，则需额外补充决策偏好[10-11]，或在Pareto非劣解集中寻优，确定最终方案[12-13]。理论上，岸桥故障下的集装箱码头调度包含了泊位调度、岸桥分配等NP-Hard问题[14]，精确算法已无法满足求解要求，需利用启发式算法予以解决。对此，快速非支配排序遗传算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)具有收敛快、计算效果良好等优点[15]，已成功应用于集装箱码头港口与泊位协同调度[16]、多目标连续泊位分配[17]等优化中，但该算法收敛精度不佳，且算法编码无法直接满足岸桥共享的求解需求，因而还需要做进一步改进。

综合以上研究特点和存在问题，本文针对岸桥故障的集装箱码头调度问题，从兼顾港口方和船公司共同利益出发，开展了岸桥故障下考虑邻近岸桥共享作业的集装箱码头调度多目标优化研究，主要工作包括：①针对岸桥故障问题以最小化船舶作业时间和最小化码头作业成本为目标，建立多目标优化模型；②针对研究问题和模型特点，以混合式多点交叉和混合式单点变异改进NSGA-Ⅱ算法，融入考虑岸桥共享作业的邻域搜索策略予以求解，得到Pareto非劣解；③利用Pareto前沿分布信息，求解各Pareto非劣解的偏向度，结合决策者偏好，得到满足决策者需求的最终方案。最后，以我国某集装箱码头为背景，验证了所提模型和算法的有效性。

1 模型构建

1.1 问题描述及假设

当岸桥发生故障时，其所服务船舶的作业便会受到影响，有可能因此延迟船舶离港时间，同时，后续到港船舶因前序延误船舶无法按时离港，也会受到影响。对于港口方，为抢回被耽误的时间，则可能需要“外借”邻近泊位的岸桥进行共享作业。岸桥共享作业是指岸桥在作业过程中，所作业船舶未离开泊位便接着移至临近泊位为其他船舶提供服务的作业过程。因为岸桥共享作业是一种接续过程，所以可以节省设备启动成本，但由于对不同船舶实行接续作业在时间上安排过于紧凑，容易耽误船期，降低船公司服务满意度，需要谨慎决策。

本文面临的选择是：由于重新开动备用岸桥，港口需要付出额外的启封、开机、温车等启动成本，当出现岸桥故障影响生产时，是按照船公司的愿望立即调动备用岸桥补位尽快完成装卸作业，还是在满足船舶按时离港的前提下，利用已工作岸桥作业的时间差对不同船舶实现共享作业，以减少港口额外作业成本便成为港口面临的决策问题。对此，要同时兼顾船公司方和港口方的利益调整调度方案，就需构建多目标优化模型分析解决。

为简化分析，本文作如下假设：①各岸桥的作业互相独立，即故障岸桥不会影响其他岸桥的作业效率；②船舶作业效率与配备的岸桥数量成正比；③岸桥的调动不发生跨越；④岸桥的启动时间和移动时间忽略不计。

1.2 模型建立

1.2.1 符号定义

为便于表达，有关参数变量定义如下：

(1)参数

(2)决策变量

1.2.2 数学模型

基于前文分析，当岸桥发生故障后，码头可考虑采用邻近岸桥共享作业的方式，综合权衡船公司和港口方的利益损失制定新的调度方案。

(1)考虑船公司利益，以作业时间最短为目标之一。考虑到集装箱班轮特点，船公司希望自身运输计划不受岸桥故障的影响，希望尽快完成装卸作业，故该目标可表达为：

(1)

(2)考虑港口方利益，以作业成本最低为另一目标。由于岸桥发生故障后，港口方需要重新调整作业计划，其措施包括船舶移泊、增加作业设备、岸桥共享等，故该目标可表达为：

(2)

式中：第一项为船舶移泊的额外成本，第二项为设备启动成本，第三项综合装卸作业成本，第四项为岸桥移动成本。

结合实际工况，其相关约束条件如下：

si≥ai,∀i∈I；

(3)

ei≥di,∀i∈I；

(4)

(5)

(6)

(7)

pi+li+l0

(8)

(9)

(10)

(11)

(12)

∀i∈I,t∈T；

(13)

∀i∈I,t∈T；

(14)

(15)

其中：式(3)限制船舶作业时间，即到港后方可开始作业；式(4)保障船舶在预期内离港；式(5)～式(7)保证所有船舶在时间和位置维度上均无冲突；式(8)限制船舶靠泊需在有效岸桥范围内；式(9)保证无故障条件下，任一时刻作业岸桥数量不超过岸桥总量；式(10)保证岸桥故障后，作业岸桥数量不超过无故障岸桥数量；式(11)和式(12)保证一台岸桥在同一时刻只服务一条船舶；式(13)限制船舶配备的岸桥数量；式(14)保证船舶在完成装卸任务后才能离港；式(15)限制参数取值。

2 模型求解

考虑到前文所建立的多目标优化模型特点，可利用改进的NSGA-Ⅱ算法直接求解，得到Pareto非劣解集；为进一步兼顾船公司和港口方利益，利用Pareto前沿的分布信息，采用最优解选择的方法，确定能使船公司和港口方均满意的调度方案。

2.1 Pareto非劣解计算

带精英策略的快速非支配排序遗传算法(NSGA-Ⅱ)是在NSGA算法基础上，引入了快速非支配排序、拥挤距离比较算子和精英选择策略。为求解本文模型，实现岸桥在作业过程中的移动和共享问题，还需进一步对算法进行改进，以便融入岸桥共享策略，提高算法运行效率。

2.1.1 算法设计和改进

结合前文分析，对NSGA-Ⅱ算法进行如下改进：

(1)编码和解码

(2)初始种群

(3)遗传操作

在NSGA-Ⅱ算法中，遗传操作包括选择、交叉和变异。在本文算法构建中，选择操作仍采用精英选择策略。为减少交叉、变异过程中产生的不可行解，对传统方式进行如下改进：

1)交叉操作。

考虑到模型所对应的染色体取值特点，保证各船相关决策的联动性，交叉操作采用混合式多点交叉，即前N位基因采用颠倒交叉点之间基因顺序的方式；第N+1～3N位基因为保留传统两点交叉方式，具体操作如下：首先，在染色体长度N范围内生成随机数r1和r2(其中r1

2)变异操作。

参照交叉操作，变异操作采用混合式单点变异方式，即第一层采取调换变异点与随机任一其他位置基因的方式；其余层采用传统单点变异操作方式，具体操作如下：首先，在染色体长度N范围内生成随机数r1，确定为变异点，并生成另一个随机数r2(r1≠r2且r1,r2≤N)；其次，前N位交换r1和r2位置基因(如图3a)，第N+1～3N位按取值范围随机生成满足条件的基因替换原基因(如图3b)。

(4)邻近岸桥共享策略

为降低码头作业成本，考虑相邻泊位岸桥对不同船舶装卸进行共享作业，对作业过程中的岸桥重新调度，为此，需在NSGA-Ⅱ算法基础上融入岸桥共享策略的邻域搜索，具体方法如下：

1)选择参与岸桥共享的船舶，即在所配备岸桥数量超过1台的船舶中随机选择船舶i；2)判断相邻泊位船舶靠泊时间上是否满足共享条件，即判断船舶i′靠泊相邻泊位的船舶到港时间是否早于船舶i离港时间，若ai′

2.1.2 计算步骤

综上分析，结合本文模型特点，合理设置染色体编码和解码，改进交叉、变异操作，融入岸桥共享策略的邻域搜索，实现多目标优化模型的求解，获得Pareto非劣解集，具体计算步骤如下：

步骤1算法初始化，确定NSGA-Ⅱ算法基本参数，输入船舶信息，以及岸桥故障情况信息；

步骤2依据船舶信息，对染色体进行编码，随机生成初始种群P1；

步骤3对种群中所有个体进行非支配分层排序，并计算拥挤距离；

步骤4依据选择规则，在种群Pt选择合适个体，利用本文所提出的混合式两点交叉和混合式单点变异方式进行交叉和变异，得到子种群B；

步骤5选择合适船舶，对种群B进行邻域搜索，考虑船舶的岸桥共享，得到新子种群B′；

步骤6合并种群Pt和子代B′，利用精英策略确定下一代种群Pt+1；

步骤7判断算法终止条件，若不满足条件，转步骤3；

步骤8算法结束，得到Pareto非劣解集。

2.2 Pareto最优解选择

利用上述改进NSGA-Ⅱ算法求解多目标模型后，可得到一组无法直接比较优劣的Pareto非劣解[18]。按前文分析，岸桥故障下需要寻求船公司和港口方的平衡，即在满足船舶按时离港的同时降低作业成本。依据文献[19]的求解思路，依托Pareto前沿分布特征，得到各Pareto非劣解对各优化目标的偏向度，结合决策者对于各优化目标的偏好，求解对各优化目标偏向度最接近，即偏向度差值最小的解，便是能使船公司和港口方均满意的调度方案，在满足船公司尽可能按时离港的前提下降低港口方作业成本。

m∈{2,3,…,M0-1},n,n′∈{1,2},n≠n′。

(16)

对于只有一个相邻点的m=1、M0，其平均变化率为：

(17)

(18)

进一步可得到灵敏比，即：

m∈{1,2，…,M0},n∈{1,2}。

(19)

考虑到作业时间和作业成本的不同量纲，对灵敏比作进一步无量化处理，得到：

m∈{1,2，…,M0},n∈{1,2}。

(20)

统一各目标量纲后，可量化对各目标的偏向程度，有

m∈{1,2，…,M0},n∈{1,2}。

(21)

依据市场情况和决策者的偏好特点，便可得到不同决策偏好下的偏向度差值，有

(22)

式中：Δω(m)为偏向度差值；γ1，γ2分别表示决策者相对于作业时间和作业成本的决策偏好权重，有γ1，γ2∈(0,1),且γ1+γ2=1。

综上，依据决策者决策偏好和计算得到的偏向度量化值便可计算出偏向度差值最小的解，此解为该决策偏好下满足决策者要求的最优方案，即(Δω(m))min所对应的Pareto非劣解便是决策者所希望的最终方案。

3 实例分析

3.1 基础数据

现以我国北方某集装箱码头(岸线800 m，岸桥10台)的现场实际数据验证本文模型算法，具体背景为：装卸作业过程中7#岸桥发生故障，故障时间为02∶00～14∶00，此时正在作业和即将到达的船舶有9条，其信息如表1所示。为便于求解和分析，假定模型中船舶偏离最佳靠泊位置的单位作业成本c1、岸桥启动成本c2、岸桥单位时间的作业成本c3和岸桥移动成本c4等参数分别为180元、2 000元、300元和5元。

表1 到港船舶信息

3.2 算例求解

针对所述案例，采用MATLAB程序编写改进NSGA-Ⅱ算法，在选择计算参数时，利用正交实验进行了测试，其计算程序在P4 CPU、内存为2 G、主频为2.81 GHz的环境下运行后，得到当种群数量为25，交叉和变异概率分别为0.8和0.02时的组合能取得更好的结果(如表2)。利用上述参数计算本文算例，得到8个Pareto非劣解(如图4和表3)。依据Pareto最优解选择的计算过程，由式(16)～式(21)可得到各Pareto非劣解相对于作业时间和作业成本目标的偏向度量化值(如表3)，依据偏向度量化值，决策者能清楚地了解各Pareto非劣解相对于各目标的偏向情况，以利于做出科学的决策。

表2 计算参数

表3 各Pareto非劣解参数表

为尽可能同时满足船公司按时离港和港口方作业成本最低的需求，决策者需要尽可能平衡双方利益，对双方持相同的决策偏好，即取γ1∶γ2=0.5∶0.5。由该决策偏好信息，结合表2中的偏向度，依据式(28)，便可求得最小偏向度差值(Δw(m))min=Δw(4)=0.04(如图5)，即4*Pareto非劣解(亦即图5中的4*Pareto非劣解)为兼顾船公司和港口方利益最好的方案。按此调度方案实施作业，其船舶作业时间为6.89 h，作业成本为5 328元。这一作业计划需作调整如下：所有船舶靠泊位置按原计划靠泊，船舶1～9实际配备岸桥数量分别为2、3、2、2、2、1、1、2和1台，其中，利用2#和5#岸桥分别在船舶2和船舶3到港后实行岸桥共享作业，这样便可以在7#岸桥发生故障的情况下，并不调用待命岸桥补位，而是寻求其他邻近岸桥装卸完成后的时间差连续作业，这样可以降低港口作业成本，同时仍可保证先后到达的9条船正常完成装卸作业，具体调度方案如图6所示。

3.3 算法比较

为进一步检验模型和算法有效性，采取在前文3.1节算例规模(简称规模1)基础上，再进一步扩大问题规模进行求解：①规模2：岸桥故障为2台，故障持续时间分别为8 h和12 h，影响船舶14条；②规模3：岸桥故障为2台，故障持续时间分别为12 h和14 h，影响船舶18条。结果显示，在不同程度的岸桥故障情况下，船舶平均作业时间区间为5.69 h～6.89 h，港口平均作业成本区间为4 574元～6 114元，表明改进NSGA-Ⅱ算法在不同故障情况下均取得较好结果。

以上述算例为基础，根据张红菊等[20]参数设置的粒子群算法及NSGA-Ⅱ算法求解的结果进行对比，计算结果表明，从计算时间分析，使用改进NSGA-Ⅱ算法所用的平均计算时间用时更短，较其他算法缩短了16.01%～27.31%，如表4所示；从Pareto非劣解结果分析，使用改进NSGA-Ⅱ算法得到的解的结果均更优(如图7)，说明本文模型均具有良好适用性，因此本文提出的改进NSGA-Ⅱ算法获得的解更好，计算运行更快，且具有较好的适应性。

表4 不同规模下计算结果

4 结束语

针对集装箱码头常见的岸桥故障实际情况，对邻近船舶采用岸桥共享作业是一种有效的方法，为此需要重新调整调度方案，降低船公司作业时间的同时减少因调整船舶靠泊位置、增加作业岸桥等增加的作业成本，以期达到兼顾船公司和港口方利益的目的。本文以船舶作业时间和港口作业成本最低为目标建立了双目标优化模型，利用改进NSGA-Ⅱ算法进行求解，得到Pareto非劣解集。为寻求不同决策偏好下的调度方案，利用Pareto前沿的分布特点，采用计算各Pareto非劣解对不同目标偏向程度的方法，得到了满足决策者偏好的最终方案。以我国某集装箱码头实例为背景，通过算法对比，显示改进NSGA-Ⅱ算法所求结果更好，计算更快，适应性良好，可为港口面临岸桥故障等问题下优化调度方案的决策提供技术支撑。

本文研究是基于个别岸桥出现故障、其他岸桥可正常作业的理想情况下开展的，但在实际中，还可能存在多台岸桥作业时相互干扰等问题，而且岸桥故障的持续时间也存在不确定性，因此在对不同船舶采用共享岸桥的调度方案时其情况会更加复杂，对于此类问题如何进行建模和计算，是下一步需深入研究的内容。