0.   引言

泊位和岸桥是集装箱码头重要的作业资源, 其合理、高效的分配和调度关乎整个码头作业系统的作业效率和运营成本。但泊位和岸桥之间复杂的协作关系与装卸效率的局限性对二者的联合分配和协调调度具有较大的影响。因而, 如何根据现实需求, 快速制定合理的泊位-岸桥联合分配方案, 成为集装箱码头装卸作业中的重要问题。

有关集装箱码头作业调度的优化问题, 国内外学者已有较多研究。在泊位或岸桥单独分配方面, Imai等针对集装箱泊位的动态调度问题, 建立了船舶在港时间最小化的优化模型^[1]; Zhen等研究了潮汐影响下的码头泊位分配问题, 提出了一种基于集合划分的优化模型^[2]; Lee等使用特制的时间-空间表格, 提出连续泊位调度问题的两阶段启发式算法^[3]; Tavakkoli-Moghaddam等以改进的遗传算法解决了岸桥的调度优化问题^[4]; 常祎妹等研究了考虑作业干扰和安全距离限制的岸桥调度问题^[5]。以上学者对泊位分配或岸桥分配进行了独立研究, 给出了较好的优化方法, 但是未深入考虑泊位分配和岸桥分配之间的系统关联性。在泊位-岸桥联合分配方面, Park等将泊位分配和岸桥分配分为2个阶段, 建立相应的混合整数优化模型, 利用次梯度法和动态规划法对模型进行求解^[6]; 范丽先等建立了以船舶在港时间最短为目标的优化模型, 并设计了先指定泊位再分配岸桥的改进遗传算法^[7]; Liang等以船舶在港时间与离港延迟时间最小为优化目标, 建立了泊位与岸桥联合优化模型, 提出了基于岸桥移动策略的混合遗传算法^[8]; Li等提出了一种基于时空冲突的启发式算法, 研究了先分配泊位再安排岸桥的两阶段问题^[9]; 张睿等研究了同贝同步模式下的集装箱装卸作业, 建立了以作业时间最小为目标的优化模型^[10]; 周鹏飞等针对船舶到港时间和装卸时间的随机性, 建立了船舶等待时间最小化的泊位-岸桥联合分配模型^[11]; 曾庆成等设计了退火与神经网络相结合的混合算法, 研究了码头装卸设备集成优化问题^[12]; 孙彬等研究了不确定情况下泊位-岸桥联合分配问题, 建立了先制定泊位计划再优化岸桥分配的分配策略^[13]; 郑斐峰等针对码头临时插船情况, 基于有限预知信息, 以最小化完工时间为目标建立了侧重泊位安排的联合优化模型^[14]; Shang等考虑了岸桥启动时间对泊位分配和作业时间的不确定影响, 建立了鲁棒优化模型^[15]。以上研究虽然考虑了岸桥作业冲突对泊位分配的影响, 但其优化策略本质上仍以泊位分配为主, 未能综合兼顾作业成本和作业效率。

杨春霞等对泊位分配和岸桥分配分别建立子模型, 将二者进行耦合, 并利用遗传算法进行了求解^{[16, 17]}; 张红菊等提出了一种倾向于作业成本的泊位-岸桥分配多目标粒子群算法^[18]; 杨华龙等提出了基于图论的挤压算法, 对以船舶在港时间最小和岸桥利用率最大为目标的模型进行了优化^[19]; Li等采用粒子编码规则和粒子可行解处理模块改进粒子群算法, 对考虑船舶移动距离最小和在港时间最短的多目标模型进行求解^[20]。以上研究均通过建立多目标模型, 将泊位和岸桥分配问题统筹在一起考虑, 但其求解算法存在一定的局限性, 即只获得了一个偏向于成本或偏向于作业效率的满意解。在实践中, 港方可能面临多种不同的调度需求, 例如, 出现台风造成班轮大量晚班时, 港方将面临船方提出的加快完成船舶在港作业尽早离港的特殊要求; 淡季箱量较少时, 港方将考虑在保证船舶按时离港的前提下, 尽可能降低作业成本等, 因此, 对于泊位-岸桥联合分配的多目标问题, 其求解结果应该是一个Pareto解集, 以供决策者按照不同的情况进行选择。杨春霞等设计的算法能够得到泊位-岸桥联合分配的Pareto解集^[21], 但其研究对象为离散泊位, 不完全适用于当前集装箱码头柔性靠泊的运营方式, 因此, 在柔性靠泊方式下, 对于求解泊位-岸桥联合分配Pareto解集的优化算法方面, 还缺少相关研究。

目前, 关于多目标整数规划的Pareto寻优算法^[22], 最具代表性的为非支配排序遗传算法(NSGA-Ⅱ)^{[23, 24]}和多目标粒子群算法^[25]。NSGA-Ⅱ法本身的参数设置较为复杂, 会出现收敛性较差以及计算结果未必是Perato最优解等问题; 多目标粒子群算法对于离散型问题处理情况欠佳, 容易陷入局部最优。

综上, 针对柔性靠泊方式下的泊位-岸桥联合分配问题, 本文以分别构建子模型, 并设置联合约束条件的方式构建了多目标联合优化模型, 根据模型中2个目标的系统关联性和相互制约关系, 提出一种模拟植物生长交替进化算法(Alternate Evolution Algorithm Based on Plant Growth Simulation, AEA-PGS) 对模型进行求解, 得到了可供决策者根据不同调度需求进行选择的Pareto满意解集, 经与多目标遗传算法的结果对比, 证明所得到的Pareto满意解集中非支配解数量更多, 优化效果更好。

1.   优化模型

泊位和岸桥是集装箱港口的2种码头资源, 二者在各自的分配上是相互独立的, 即当某艘船舶作业的岸桥数量确定时, 可单独对码头泊位的分配进行优化; 当泊位的分配确定时, 也可单独对岸桥的分配进行优化。但从整体的角度分析发现, 泊位和岸桥实际上还蕴含着相互制约的关系, 即某艘船舶作业岸桥数量的改变不仅对作业成本产生影响, 也会对该船舶的作业时间产生影响, 进而影响后续船舶的泊位分配; 同样, 某艘船舶靠泊位置的改变不仅对靠泊时间产生影响, 也将影响该船舶长度范围内的可用岸桥数量, 进而影响岸桥移动次数和作业成本, 因此, 泊位和岸桥的分配既具有相互独立性, 又具有系统关联性。杨春霞等针对泊位分配和岸桥分配分别建立了子模型, 描述了二者的相互独立性^{[16, 17]}, 在此基础上, 本文为了描述二者的系统关联性, 对模型进行了改进, 即通过构建联合约束条件描述作业过程中泊位分配和岸桥分配的相互影响, 进而在优化的过程中, 既考虑了二者各自的作业特点, 又实现了将二者统筹考虑的目的。

为便于分析, 在不影响正常作业的情况下, 提出以下假设。

(1) 每艘船舶的装卸任务可以在多个岸桥之间均匀分配。

(2) 将岸桥移动计入装卸作业过程, 并平均至岸桥装卸作业效率中, 不单独考虑岸桥移动时间。

(3) 岸桥移动是不可跨越的。

(4) 只有当船舶所需岸桥全部准备完毕时才能开始装卸作业。

1.1   基于在港时间的泊位分配子模型

设S为到港船舶编号的集合; s为到港船舶数量; L为岸线长度; a_i为船舶i的到港时间, i=1, 2, …, s; b_i为船舶i占用泊位时间; l_i为船舶i靠泊所需岸线长度(已考虑船舶之间的安全距离); 决策变量y_i为船舶i的靠泊时间; d_i为船舶i的离港时间; 决策变量φ_i为船舶i靠泊时船头的位置; z_{i, j}为0-1变量, 若船舶i在船舶j的左侧岸线靠泊, z_{i, j}为1, 否则为0;z_{j, i}为0-1变量, 若船舶j在船舶i的左侧岸线靠泊, z_{j, i}为1, 否则为0;h_{i, j}为0-1变量, 若船舶i的靠泊时间在船舶j之前, 则h_{i, j}为1, 否则为0;h_{j, i}为0-1变量, 若船舶j的靠泊时间在船舶i之前, 则h_{j, i}为1, 否则为0;M为一个无穷大的常数; f₁为船舶平均在港时间。建立的泊位分配子模型为

式中: 式(1) 表示船舶平均在港时间最小; 式(2) 保证任何船舶在靠泊时不超过岸线范围; 式(3) ~ (5) 表示在同一时间装卸作业船舶的靠泊位置不能重合; 式(6) 表示船舶靠泊时间应在到港时间之后; 式(7) 表示船舶在港时间按约定不得超过16h。

1.2   基于作业成本的岸桥分配子模型

设R为码头岸桥编号的集合; r为岸桥数量; T为时间段集合; t为时间段数量; e_i为船舶i的作业箱量; δ_i为船舶i的最大可获得分配岸桥数量; q为岸桥装卸作业效率; 决策变量w_i为船舶i的装卸作业岸桥数量; u_i为船舶i作业所需岸桥准备时间; v_i为船舶i的作业完成时间; c₁为岸桥作业的启动成本; c₂为岸桥每小时的作业成本; c₃为岸桥的移动成本; ϕ_{i, g, k}为0-1变量, 若岸桥k在时间段g对船舶i进行作业则为1, 否则为0;α_{i, g, k}为0-1变量, 若岸桥k在时间段g移动至船舶i范围内进行作业, 则为1, 否则为0;f₂为作业总成本。建立的岸桥分配子模型为

式中: 式(8) 表示船舶作业岸桥启动成本、装卸作业成本与等待作业时岸桥移动成本之和最小; 式(9) 表示船舶分配岸桥数量不得超过其取值范围; 式(10) 表示开始作业后岸桥数量保持不变; 式(11)、(12) 表示岸桥必须在指定时间窗内进行作业; 式(13) 表示1台岸桥在同一时间只能为1艘船舶提供服务; 式(14) 保证任意时间作业岸桥数不超过岸桥总数。

1.3   联合约束条件

根据泊位和岸桥分配的系统关联性, 建立约束条件

式中: 式(15) 表示占用泊位时间, 包括岸桥准备时间和装卸作业时间; 式(16) 表示船舶靠泊后才能开始装卸作业; 式(17) 表示作业完成后船舶才能离港。

2.   算法设计

2.1   基本思想

基于以上模型, 可利用2个优化对象的相互独立性, 分别建立优化模块; 同时通过系统的关联性建立2个模块之间的呼应关系, 达到2个目标之间的交替优化, 进而实现参与演算个体的进化。由此, AEA-PGS的具体设想为: 针对种群中的所有个体, 利用2个子模型交替优化的方式实现个体进化; 当每次种群进化完成后, 根据非支配性排序选出种群中的非支配解, 经过多次种群进化和非支配解筛选, 直到非支配解数量和拥挤度情况达到设定标准, 则输出Pareto满意解集。

2.2   基于模拟植物生长算法的交替进化算子

模拟植物生长算法(Plant Growth Simulation Algorithm, PGSA)^[26]是一种仿生类算法, 以目标规划的可行域作为植物的生长环境, 将全局最优解当作光源, 模拟植物生长的向光性机理(形态素浓度理论), 实现人工模拟植物在规划问题可行域中从初始状态到最终状态(没有新的树枝产生) 的寻优过程。通过研究模拟植物生长算法的迭代方式, 发现PGSA具有每次保留的生长点都优于初始生长基点的特性, 因而利用这一算法进行泊位分配模型与岸桥分配模型之间的交替优化, 进而使种群中的个体不断进化, 最终逼近非劣解。

交替进化(Alternate Evolution, AE) 算子的具体步骤如下。

Step 1:读取某个体的泊位分配情况X和岸桥分配情况Y, 设泊位分配优化模块和岸桥分配优化模块的过程最优解为X_max和Y_max, 令X_max=X, Y_max=Y, 设置泊位分配优化模块的最大生长次数为ξ₁, 岸桥分配优化模块的最大生长次数为ξ₂, 交替优化次数为η。

Step 2:根据岸桥分配优化模块的过程最优解Y_max, 将各船舶岸桥分配情况传递给泊位分配优化模块, 并按照岸桥分配情况更新作业时间窗约束和泊位分配的可行域。

Step 3:设泊位分配优化模块的初始生长基点为X₀=X_max, 计算初始生长基点的目标函数f₁ (X₀)。

Step 4:以X_m为生长点, m=0, 1, …, ξ₁-1, 即第1次生长时m=0, 第2次生长时m=1, 以此类推。设以10m (码头系缆桩间距) 为步长分别向2s个方向生长出2s个新生长点, 再根据交换任意2艘船舶靠泊顺序的方式生长出s个新生长点, 删除新生长点中不符合约束条件的解, 将可行解生长点加入生长点集合Ω₁。计算生长点集合Ω₁中所有生长点的目标函数, 删除目标函数劣于f₁ (X₀) 的生长点, 更新生长点总数λ₁和过程最优解X_max。

Step 5:计算生长点集合Ω₁中所有生长点的形态素浓度, 即生长概率, 设X_τ为集合Ω₁中第τ个生长点, τ=1, 2, …, λ₁, P_τ为生长点X_τ的生长概率, ρ为无限小的数, 有

Step 6:根据Step 5计算所得各生长点生长概率, 建立在[0, 1]之间各生长点的概率空间, 以随机数选择下次迭代的生长点X_m+1。

Step 7:以Steps 4~6为一个生长循环, 经过多次生长, 若达到最大生长次数ξ₁或不再产生新生长点, 则输出泊位分配优化模块的过程最优解X_max, 否则返回Step 4。

Step 8:根据泊位分配优化模块的过程最优解X_max, 将船舶靠泊顺序与靠泊位置等信息传递给岸桥分配优化模块, 进而更新该模块的约束条件和可行域。

Step 9:设岸桥分配优化模块的初始生长基点为Y₀=Y_max, 计算初始生长点的目标函数f₂ (Y₀)。

Step 10:以Y_n为生长点, n=0, 1, …, ξ₂-1, 以1为步长分别向2s个方向生长出2s个新生长点, 删除新生长点中不符合约束条件的解, 将可行解生长点加入生长点集合Ω₂。计算生长点集合Ω₂中所有生长点的目标函数, 删除目标函数劣于f₂ (Y₀) 的生长点, 更新生长点总数λ₂和过程最优解Y_max。

Step 11:计算生长点集合Ω₂中所有生长点的形态素浓度, 即生长概率, 设Y_β为集合Ω₂中第β个生长点, β=1, 2, …, λ₂, P_β为生长点Y_β的生长概率, 有

Step 12:根据Step 11计算所得各生长点生长概率, 建立在[0, 1]之间各生长点的概率空间, 以随机数选择下次迭代生长点Y_n+1。

Step 13:以Steps 10~12为一个生长循环, 经过多次生长, 若达到最大生长次数ξ₂或不再产生新生长点, 则输出泊位分配优化模块的过程最优解Y_max, 否则返回Step 10。

Step 14:以Steps 2~13为一个交替优化循环, 经过多次交替优化循环, 若该个体的2个目标函数都完成收敛, 则停止计算, 记录该个体通过交替优化得出的非劣解, 否则返回Step 2。

2.3   AEA-PGS框架

AEA-PGS框架的主要功能为通过支配系数计算、拥挤距离评价和循环计算, 得出Pareto满意解集。为此, 首先需对初始种群进行进化操作, 得到非劣解种群, 随后对非劣解种群进行支配系数计算, 选出所有非支配解组成非支配解集, 并对非支配解集进行拥挤距离评价, 若达到结束条件, 则输出Pareto满意解集, 若未满足标准, 则对种群中支配系数大于0的个体进行退化操作, 随后再次对种群中的劣解进行进化操作, 反复进行直至结束(图 1), 具体步骤如下。

Step 1:生成初始种群。

Step 2:利用AE算子对种群中的所有劣解个体进行进化操作, 得到非劣种群。

Step 3:计算种群中所有个体的支配系数, 选出所有非支配解组成非支配解集。

Step 4:对非支配解集中的所有解按照目标函数大小进行排序, 计算相邻非支配解之间的拥挤距离。

Step 5:若非支配解集规模达到设定值, 且所有相邻非支配解之间的拥挤距离都小于设定值时, 则输出泊位-岸桥联合优化问题的Pareto满意解集, 算法结束, 否则进入Step 6。

Step 6:对种群中支配系数大于0的个体进行退化操作, 即随机产生若干可行新个体替换种群中支配系数大于0的个体, 转Step 2。

3.   算例分析

3.1   基本数据

以大连港集装箱码头2011年10月1日0时0分至2011年10月3日22时30分3d中共计31艘船舶到港的真实记录为算例进行分析。码头岸线长度为800m, 配备岸桥为12台, 岸桥平均装卸效率为20TEU·h^-1。根据实际情况, 设每台岸桥启动成本c₁为160元, 岸桥每小时作业成本c₂为300元, 岸桥每次移动成本c₃为50元。到港船舶数据见表 1。

图  1  算法流程

Figure  1.  Flow of algorithm

下载: 全尺寸图片 幻灯片

表  1  到港船舶数据

Table  1.  Data of arriving vessels

下载: 导出CSV 

| 显示表格

3.2   优化结果

设AEA-PGS框架最大的进化代数为100, AE算子最大交替迭代次数为30, 泊位分配优化模块和岸桥分配优化模块的最大生长次数均为20。采用MATLAB对AEA-PGS进行编程, 得到由13个Pareto满意解组成的Pareto满意解集, 选取其中3个Pareto满意解进行分析, 得到满意解1的船舶平均在港时间为9.44h, 使用岸桥85台, 作业总成本为20.868万元; 满意解2的船舶平均在港时间为8.07 h, 使用岸桥89台, 作业总成本为20.962万元; 满意解3的船舶平均在港时间为7.47h, 使用岸桥96台, 作业总成本为21.114万元。图 2~4分别为上述3个满意解的船舶平均在港时间、使用岸桥次数和作业总成本的对比情况。各满意解具体情况见表 2, 其中, 靠泊位置以码头端点起按延米进行度量。满意解1~3的泊位-岸桥分配与作业安排分别见图 5~7, 1^#~12^#表示分配给船舶作业岸桥的编号。

图  2  船舶平均在港时间

Figure  2.  Average times of vessels in port

下载: 全尺寸图片 幻灯片

图  3  使用岸桥数量

Figure  3.  Numbers of using quay cranes

下载: 全尺寸图片 幻灯片

图  4  作业总成本

Figure  4.  Total operating costs

下载: 全尺寸图片 幻灯片

图  5  满意解1的Gantt图

Figure  5.  Gantt chart of satisfactory solution 1

下载: 全尺寸图片 幻灯片

图  6  满意解2的Gantt图

Figure  6.  Gantt chart of satisfactory solution 2

下载: 全尺寸图片 幻灯片

图  7  满意解3的Gantt图

Figure  7.  Gantt chart of satisfactory solution 3

下载: 全尺寸图片 幻灯片

由图 2~4可见: 满意解1的作业总成本最小, 但船舶平均在港时间最长, 因而该方案符合淡季箱量较少时, 港方在保证船舶按时离港的前提下, 尽可能降低作业成本的调度需求; 满意解2的船舶平均在港时间和作业总成本相对平衡, 因而方案符合常规情况下港方的调度需求; 满意解3的作业总成本虽然较高, 但船舶平均在港时间最小, 因而符合出现台风造成班轮大量晚班时, 港方需加快完成装卸作业, 让船舶尽早离港的调度需求。由图 5~7可见: 由于满意解1~3使用岸桥数量逐渐增加, 因而各Gantt图的排布越来越紧密。

表  2  满意解

Table  2.  Satisfactory solutions

下载: 导出CSV 

| 显示表格

3.3   算法对比

为评价AEA-PGS的性能, 利用杨春霞等提出的多目标遗传算法^[21]同时求解上述算例, 结果见表 3。图 8为本文算法与多目标遗传算法所得Pareto满意解的分布, 经对比可以看到: AEA-PGS所得到的Pareto满意解集中共有非支配解13个, 比多目标遗传算法多4个, 增加幅度为30.76%, 且比多目标遗传算法所得结果更趋近于Pareto前沿(图 3)。由此可见, 针对本文问题, AEA-PGS能够得到比多目标遗传算法更优的Pareto满意解集。

实际上, 剖析计算的具体过程, 可以发现本文算法对比多目标遗传算法的优势是: 多目标遗传算法中的种群进化是通过交叉变异实现的, 交叉操作是在个体之间进行的, 该操作有可能将种群进化限制在一定范围内, 难以突破局部最优空间, 虽然在变异操作时可能会使种群有机会突破局部最优空间, 但由于变异操作存在相当的随机性, 会导致变异产生的解大部分为较劣解, 降低了收敛速度; AEA-PGS的种群进化是利用AE算子对每个个体分别进行2个目标的交替优化, 在种群进化过程中个体之间相互独立, 使得种群中的个体能更好地逼近非劣解, 因而求得的Pareto满意解更多, 优化程度更高。对照图 3能够看到: AEA-PGS所得Pareto满意解集分布在多目标遗传算法的左下方, 说明AEA-PGS中的AE算子能提高种群的进化质量和效率, 因而性能更优。

表  3  两种算法计算结果对比

Table  3.  Computation result comparison of two algorithms

下载: 导出CSV 

| 显示表格

图  8  两种算法的Pareto满意解分布

Figure  8.  Distribution of two algorithms'Pareto satisfactory solutions

下载: 全尺寸图片 幻灯片

4.   结语

(1) 根据泊位分配和岸桥分配的相互独立性和系统关联性, 通过分别构建子模型与联合约束的方式, 建立了泊位-岸桥多目标联合优化模型。针对该模型, 提出了模拟植物生长交替进化算法。算法利用交替进化算子对种群中的个体进行多目标之间的交替优化, 能够使其快速进化, 逼近非劣解, 并由算法框架对解的非支配性和拥挤度进行评价, 经多次种群进化, 进而得到Pareto满意解集。通过实际算例与多目标遗传算法对比, 表明本文算法所得的Pareto满意解集具有较高的非劣性, 且非支配解更多, 因而优化效果更好。

(2) 研究仅讨论了泊位和岸桥分配的联合优化, 但实际中, 港口装卸作业还涉及到其他设备如场桥和集卡等, 因而应延伸考虑更多相关设备的分配问题, 有关此类更为复杂的多目标优化有待于下一步深入研究。