基于柔性靠泊的港口疏船调度多目标优化及最优解选择

吴 暖，王 诺，于安琪，吴 迪

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

1 问题的提出

与按泊位位置逐一对应的方式安排船舶靠泊不同[1]，柔性靠泊[2]是在连续的码头岸线上，依据到港船舶的船长接续进行靠泊的一种灵活方式(如图1)。这种调度方式可以最大限度地利用岸线，增加靠泊船舶数量，提高作业效率，但对调度方案的优化提出了更高的要求。在实际中，港口生产经常会受突发事件(如恶劣天气、生产事故等)的影响，使按计划到港的船舶无法在预定时间靠泊作业，有时会出现大批船舶在港外锚地等待的现象。在突发事件结束后，为尽快恢复港口生产秩序，港口方需要开展疏船作业，以尽可能减少船方损失，但同时也希望不过高地加大为此付出的额外成本，如何平衡两者关系，是港口调度组织优化的重要内容。

港口的疏船调度实际上是一种应急管理，此类研究大都以船公司或者港口方中的某一方利益为主[3-4]，例如以港口方为主时追求作业成本最低或经济效果最好[5]，以船公司为主时追求船舶在港时间最短[6]。实际中出现疏船调度等特殊情况时，需要从问题实际矛盾出发，兼顾船公司和港口方的共同利益，得到能让双方都满意的调度方案。若建立多目标优化模型后又将其转换成单目标进行求解，则会使决策者难以了解更多的有用信息[7-8]。如果直接建立多目标优化模型进行求解，则需在优化过程中额外增加新的决策信息[9-10]，或者在求解得到Pareto非劣解集后继续寻优[11-12]，最常见的方法是引入决策者的主观偏好后得到最优解[13-15]。

泊位分配问题在理论上属于NP-Hard问题[16]，需要通过优化算法得到较优方案。已有研究表明，粒子群优化(Particle Swarm Optimization, PSO)算法的设计适用于求解连续问题，该算法具有概念简单、参数较少等特征，能在求解连续问题时得到较优解[17]，且已成功应用于求解泊位调度优化问题，效果良好[18-19]。另外，PSO算法在求解多目标优化问题中得到了广泛应用[20]，缺点是容易陷入局部最优，需做一定改进。

针对上述问题，本文在已有研究基础上[21]突出集装箱码头柔性靠泊的特点，兼顾港口方和船公司的共同利益，建立了多目标优化模型和最优解选择方法，其主要工作和贡献为：①基于柔性靠泊的疏船调度问题，建立了船舶等待时间最短和港口作业成本最低的双目标优化模型；②改进自适应PSO算法，以增减岸桥和减少偏移最优位置距离的方式构造邻域，嵌入邻域搜索进行求解，得到Pareto非劣解集；③依托Pareto前沿分布特点，以船方等待时间最小和港口方应急作业成本最小为目标，得到对两个目标偏向度差值最小的最优解，解决了在Pareto非劣解直接寻优的问题。最后，以大连港集装箱码头实际案例为背景，验证了本文所建模型的合理性；通过与常规PSO算法和带精英策略的快速非支配排序遗传算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)对比，验证了改进算法在求解时的收敛速度更快，具有良好的精确度和稳定性。

2 模型构建

2.1 问题描述和假设

假设因突发事件导致大量船舶等待靠泊，此时码头调度会打乱原有计划，重新安排，并打破先到先服务的原则。港口方既希望加大投入尽快恢复至正常生产秩序，又不希望为此付出过多的额外成本，因此是一个双目标优化问题。为了既简化优化模型又符合现场作业的实际情况，需做如下基本假设：①靠泊位置的水深条件均能满足船舶的安全需求；②船舶在连续岸线上按柔性方式靠泊，直至装卸作业全部完成后方可离开；③忽略岸桥的启动时间和移动时间；④各岸桥只能按原排序作业，不跨越。

2.2 模型的建立

2.2.1 符号定义

为便于表达，先将有关符号定义如下：

n为到港船舶数量；

I为等待靠泊的船舶集合，i为船舶编号，i′为除i外任意船舶的编号，i≠i′且i，i′∈I；

ai为船舶i的原计划到港时刻；

di为船舶i的实际离港时刻；

Ei为船舶i的集装箱装卸量；

L为岸线长度；

bi为船舶i的计划靠泊位置；

li为船舶i的长度，包括船舶靠泊的安全距离；

qi为船舶i计划配备的岸桥数量；

oi为船舶i的在港辅助作业时间，指海关检验检疫等作业准备工作；

Q为岸桥总数；

M为足够大的正数；

u为岸桥每小时的装卸量；

vi为船舶i的实际作业速度；

α1为船舶偏离最优靠泊位置所增加的单位作业成本；

α2为船舶因增加岸桥而增加的单位作业成本；

t为调度作业期内的某一具体时刻，Tt为调度作业时间集合，t∈Tt；

th为恢复作业时刻；

pi为船舶i的实际靠泊位置；

Qi为船舶i实际配备的岸桥数量；

si为船舶i的实际开始作业时刻；

wi为船舶i持续作业所需的时间；

Xit为0-1变量，当Xit=1时，表示船舶i在t时刻正在接受装卸服务，否则Xit=0，i∈I，t∈Tt；

2.2.2 数学模型

按照所提问题构建的双目标优化模型如下：

(1)

α2·wi·(Qi-qi)]。

(2)

s.t.

si≥th,∀i∈I；

(3)

(4)

(5)

(6)

pi+li

(7)

(8)

wi=Ei/vi=Ei/uQi,∀i∈I；

(9)

di=si+wi+oi,∀i∈I；

(10)

si-ai≥0,∀i∈I；

(11)

(12)

其中：式(1)为目标函数1，要求船舶平均等待靠泊的时间最短；式(2)为目标函数2，即港口方希望因应急调度增加的平均额外作业成本最低；约束条件(3)为计划内船舶的作业开始时刻不早于码头恢复生产时刻；约束条件(4)～(6)为按照柔性靠泊，保证在相同时刻相同位置只允许有一条船舶接受服务，即各船舶在时间和空间上均无重叠作业；约束条件(7)为船舶的靠泊位置均在有效的岸线范围内；约束条件(8)为任何时刻正在服务的岸桥数量不超过码头前沿配备的岸桥总量；约束条件(9)定义了船舶在港作业时间与装卸量和实际配备的岸桥数量的关系；约束条件(10)为船舶离港时刻与船舶开始接受作业时刻、作业时间和辅助作业时间的关系；约束条件(11)为船舶实际作业开始时刻不早于船舶计划到港时刻，即船舶只有到港后才能接受服务；约束条件(12)为模型中的变量取值。

3 算法设计

3.1 粒子群优化算法

3.1.1 粒子群优化算法基本思路

PSO算法是一种基于鸟群觅食行为而提出的一种智能算法，不妨设群体规模为N，每个粒子在D维空间内搜索，各粒子都有位置和速度两个不同属性，则某一时刻粒子i的位置和速度分别为xi=(xi1,xi2,…,xiD)，vi=(vi1,vi2,…,viD)，该粒子的个体最优位置和全局最优位置分别为pi=(pi1,pi2,…,piD)，pg=(pg1,pg2,…,pgD)，粒子速度和位置更新如下：

(13)

(14)

为了使PSO算法能够求解本文的疏船调度问题，需先对粒子进行编码和解码。为满足柔性靠泊的要求，每个粒子在编码过程中需要包括靠泊优先级、靠泊位置和参与岸桥数量3部分信息，3部分均采用整数编码方式。其中：靠泊优化级数值为其优先级的大小，数值越小表明靠泊优先级越高，当数值相等时，船舶编号小的船舶优先靠泊；靠泊位置数值为岸线延米标识；岸桥数量数值为参与作业的岸桥数量，如图2所示。例如，船舶2的优先等级最高，最先靠泊，作业开始时间为码头恢复生产的作业时间，靠泊位置是以自岸线端点起30 m处为起点进行靠船，配备作业的岸桥数量为3台。

在PSO算法计算过程中，粒子的初始速度为0，粒子速度按式(13)更新。粒子的初始位置为其靠泊优先级、靠泊位置和参与岸桥数量3部分的初始信息，粒子位置的更新在式(14)计算的基础上，为保证其符合计算和约束条件的要求，仍需做如下处理：①当计算得到粒子位置为非整数时，采用取整函数进行修正；②当更新的靠泊位置超出岸线长度时，将超出部分从0 m位置重新安排；③当更新的岸桥数量超出船舶最大岸桥数量时，岸桥配备数量应为超出部分与最小岸桥数量之和(在不超过最大岸桥数量的情况下)。

3.1.2 算法改进

为改进算法的适应性和计算效果，结合本文问题的特点引入新的计算规则。

(1)改造惯性因子

考虑到在求解过程中，算法需要同时具备较强的全局搜索能力和局部搜索能力，因而对惯性因子进行改造，使其能够自适应变化，具体为

ωR=ωmax-r(ωmax-ωmin)/rmax。

(15)

式中：r为当前的迭代次数；ωr为当前的惯性因子；ωmax为最大惯性因子；ωmin为最小惯性因子；rmax为最大迭代次数。

(2)增加邻域搜索规则

考虑到本文求解问题的特点，在PSO算法过程中增加了邻域搜索规则。基于不同的搜索策略，将邻域构造分为两类：

1)以增减岸桥为变量构造邻域

考虑到不同岸桥数量对船舶作业时间的影响，本文采用增减岸桥方式构造邻域，即得到某一代调度方案后，随机选择某一粒子中的某一船舶进行岸桥增减搜索；同时，随机选择增加或减少岸桥数量，并比较前后方案的优劣，若新配备方案优于原配备方案，则保留该岸桥配备结果，更新粒子信息，否则保留原配备方案。

2)以减少船舶偏移最优位置的距离为变量构造邻域

在疏船调度过程中，因为船舶偏离最优位置会增加额外的作业成本，所以优化时需考虑减少偏离距离的情况，即在得到某一代调度方案后，随机选择某一粒子中的某一船舶，比较该船舶的实际靠泊位置与最优靠泊位置，在不影响其他船舶靠泊的前提下，尽可能减少偏离，保留新的靠泊位置并更新粒子信息。

在改造惯性因子和增加新的邻域搜索规则后，改进PSO算法的具体步骤调整如下：

步骤1算法初始化。设置PSO算法基本参数，根据到港船舶的数据随机生成初始种群。

步骤2计算适应度。对初始种群得到的个体分别计算船舶平均等待时间和港口额外作业成本两个目标。

步骤3筛选初始非劣解。根据适应度筛选初始非劣解，记录所有非劣解，并在非劣解集中采取随机选择的方式确定初始种群的最优个体和全局最优个体。

步骤4粒子更新。用式(13)和式(14)更新所有粒子的速度和位置，并按照调整规则对产生的不可行粒子位置进行调整。

步骤5重新计算适应度。对更新后得到的所有粒子重新计算适应度。

步骤6搜索邻域。随机生成一个(0,1)之间的随机数，若随机数大于0.5，则以增减岸桥方式构造邻域，否则以减少偏移最优位置距离构造邻域，并更新种群。

步骤7筛选非劣解。根据适应度筛选当前种群中的非劣解，记录所有非劣解；将当前种群得到的非劣解与之前记录的非劣解合并，重新筛选新的非劣解，确定新的非劣解集，并更新个体最优和全局最优记录。

步骤8调整惯性因子。按式(15)对惯性因子进行自适应更新。

步骤9若计算结果未达到预定终止条件，则返回步骤4；否则，终止计算，输出计算结果。

步骤10结束。

3.2 Pareto最优解的求解

利用以上计算方法求解，可得一组Pareto非劣解集，若要寻求最优解，则需根据决策者的偏好进行选取。体现在本问题中，就是要寻找同时兼顾船公司和港口方利益的最优解，但在市场竞争下，无论偏向船公司还是偏向港口方都不公平，因此在实践中可供选择的最优方案显然是对两个目标的优化均无偏向的解。基于上述认识，利用Pareto前沿分布的特点选择相对于两个目标无偏向的最优解。该方法的基本思想是，根据Pareto前沿几何分布的特点，Pareto非劣解平均变化率相对于两个优化目标最灵敏的交点所对应的解即为无偏向的最优解[22]，如图3所示。

基于上述思路，设M为由优化模型得到的Pareto非劣解集中解的数量，各Pareto非劣解按目标函数T由小到大的顺序依次编号，T(m)为第m个Pareto非劣解的船舶平均等待时间，m∈{1,2,…,M}，C(m)为第m个Pareto非劣解的平均额外作业成本，则Pareto非劣解平均变化率为：

m∈{2,3,…,M-1}；

(16)

m∈{2,3,…,M-1}。

(17)

(18)

(19)

(20)

(21)

在此基础上得到相对于各目标的灵敏比，即：

(22)

(23)

考虑到船舶平均等待时间和平均额外作业成本的单位不统一，无法有效比较，需对上述结果进行无量纲化处理，有：

(24)

(25)

根据无量化后的灵敏比结果得到各非劣解对各目标的偏向度，有：

(26)

(27)

在上述偏向度的基础上得到各Pareto非劣解相对于各目标函数偏向度的差值

(28)

式中Δw(m)为编号为m的Pareto非劣解相对于各目标函数偏向度的差值，其他符号意义同上。

由以上分析可知，偏向度差值的最小值(Δw)min所对应的Pareto非劣解即为对各目标偏向最小的解。

4 算例分析

4.1 基础数据

以大连港集装箱码头案例为研究背景，该码头岸线长800 m，配备有岸桥12台。本文用2011年11月11日～11月14日船舶到港记录验证本文模型和算法的有效性。具体情况为：码头于11月11日12时遇大风停止作业，11月12日0时恢复生产，其间港口停产12 h。停产时段内已到达锚地等待作业的船舶有4条，此时若仍按原装卸作业计划实行调度，则将影响后续到港作业的12条船舶及原计划正常靠泊作业的3条船舶，具体如表1所示，原计划调度方案如图4所示。现需根据变化的情况重新调整调度方案，为简化计算，取船舶在港辅助作业时间o=1 h；船舶偏离最优靠泊位置时港口增加的单位作业成本α1=2 000 元/m，因增加岸桥而增加的港口单位作业成本α2=1 000 元/h。

表1 到港船舶信息

4.2 算例求解

以上述船舶到港数据为基础，设置PSO算法的种群数量为30个，迭代次数为200代，算法参数c1=0.8，c2=0.8，惯性因子ωmax=1.2，ωmin=0.1，利用MATLAB编程，计算程序在P4CPU、内存为2 G、主频为2.81 GHZ的环境下运行，最终得到满足条件的Pareto非劣解8个(如图5)。由式(16)～式(27)得到各非劣解对应的偏向度差值，如表2和图6所示。由式(28)求得(Δw(m))min=Δw(7)，即图6中最小值的7#(即图5中的7#)所对应的方案为最优。

表2 Pareto非劣解集对应的参数表

与原调度计划相比，优化后得到的7#方案采取的措施是：对4#和10#船舶分别临时增加作业岸桥1台，指定2#船舶的靠泊位置为比原计划位置向左移10 m，如表3和图7所示。该方案虽然使船舶的平均额外作业成本增加了506.26 元，但是却可以将所有船舶的平均等待时间从原来的6.97 h减少至5.38 h，减少幅度为22.8%，从而缩短恢复港口正常生产的时间。

表3 优化得到的7#方案及与原计划调度方案的对比

续表3

4.3 算法比较

为验证本文改进算法的有效性，将停产时间由12 h延长到18 h，24 h，30 h分别求解，得到不同情况的最优解并进行对比，如表4和图8所示。结果显示，在不同停产时间下，平均额外作业成本增加的区间为506.3元～5 583.1元，各种情况的船舶平均等待时间均得到改善，缩短比例为14.6%～32.8%，表明本文算法在不同停产时间下均能得到合理的优化结果。

表4 不同停产时间算例的计算结果

以上述算例的船舶到港数据为基础，设计相同算法参数的常规PSO算法和种群数量为30、交叉概率为0.8、变异概率为0.05、迭代次数为200代的NSGA-Ⅱ，与本文算法求解的结果进行对比，结果显示：①从得到的Pareto前沿分布可知(如图8)，改进算法得到的解分布得更分散，且存在改进算法所得的Pareto非劣解能够支配改进前算法和NSGA-Ⅱ所得的Pareto非劣解情况，说明算法改进后得到的结果均更优；②从算法的平均运行时间看，改进后算法的平均运行时间比改进前分别缩短17.4%，21.3%，25.4%，32.3%，比NSGA-Ⅱ分别缩短33.2%，46.0%，41.0%，31.4%，说明改进算法运行均更快，如表4所示；③从不同停产时间算例的结果可知，改进算法的优化效果均较稳定。综上，本文所提改进的PSO算法获得解的优化结果更好，所用时间更短且具有良好的稳定性。

5 结束语

不同于按泊位位置的靠泊方式，柔性靠泊可以最大限度地利用岸线来增加靠泊船舶数量，提高作业效率，因此对调度方案的优化要求更高，特别是港口停产恢复后，还要同时平衡港口方和船方利益的疏船调度，情况更加复杂。为有效地求解此类问题，本文以兼顾船方利益的船舶平均等待时间最短和港口方利益的码头额外作业成本最低建立双目标优化模型，并利用嵌入邻域搜索的自适应PSO算法进行求解，得到了满足条件的Pareto非劣解集。为寻找同时兼顾船公司和港口方利益的无偏向解，本文根据Pareto前沿的分布规则，采用目标比的概念和量化方法进行寻优。为验证模型和算法的合理性与有效性，选用大连港集装箱码头实例，得到了对船方平均等待时间最短目标和港口方额外作业成本最低目标偏向度最低的调度方案。通过与常规PSO算法和NSGA-Ⅱ进行对比，本文改进算法对不同停产时间在计算速度、稳定性和优化效果等各项指标上均优于常规PSO算法和NSGA-Ⅱ，显示了该算法在解决此类问题时的合理性与有效性，表明本文研究对解决港口疏船调度问题具有理论和实用价值，可为港口科学制定调度方案提供参考。

本文仅考虑了泊位—岸桥的配备，实际中还将面临泊位—岸桥—集卡共同作业的调度问题，而且疏船调度问题需要在较短时间内完成决策，如何选用性能更为优越的算法是下一步需要讨论的内容。