基于船时效率的岸桥配置优化

毛敏俐，梁承姬，胡筱渊

（上海海事大学物流科学与工程研究院，上海201306）

（∗通信作者电子邮箱2669597085@qq.com）

0 引言

在经济全球化的背景下，运输物流正在迅速发展，集装箱运输业已成为运输和物流的支柱。集装箱码头在多式联运网络中发挥着不可或缺的作用，船舶沿码头停泊，集装箱由岸桥装卸，泊位和岸桥是码头最关键的两种资源。由于资源有限以及集装箱吞吐量的增加，有效和高质量的管理可以提高码头的运营效率，从而提高集装箱码头的经济实力和核心竞争力。

集装箱码头运营中的典型优化问题包括泊位分配问题（Berth Allocation Problem，BAP）和岸桥分配问题（Quay Crane Assignment Problem，QCAP）。在初始研究阶段，BAP和QCAP被认为是相互独立的，但是实际上BAP 和QCAP 是相互关联的:船舶的在泊作业时间取决于被分配的岸桥数量，而岸桥分配中已知的靠离泊时间是泊位分配的结果。

泊位分配和岸桥配置的联合优化（BAP-QCAP）是最常见的集成模式，Park 等［1］最先提出连续泊位与岸桥分配的联合优化问题，以船舶在港时间最短为目标建立模型，同时决策了停泊时间、靠泊位置以及分配给船舶的岸桥数量和特定岸桥。Oguz 等［2］以最小化船舶的最大完工时间为目标建立模型，通过引入干扰系数来应对岸桥的边际生产率下降，但并未提及靠泊位置和停泊时间的确定方式。李娜等［3］针对船舶动态到港的情况，以待分配船舶的总在港时间最小为目标建立模型，基于改变船舶配置次序的思想，设计启发式算法对问题进行求解。Imai 等［4］考虑了离散泊位中的联合优化问题，首先使用遗传算法（Genetic Algorithm，GA）生成船舶的泊位分配，然后提出了一种启发式来安排岸桥的转移；但是研究假设每艘船的指定岸桥数量预先确定。杨春霞等［5］以最小化船舶在港时间和岸桥移动次数为优化目标，建立了基于泊位分配子模型和岸桥分配子模型的耦合模型，并提出一种嵌套循环进化算法进行求解。Türkoğulları 等［6］最小化包括因偏离偏好泊位、延迟靠泊、延迟离泊以及变更服务岸桥数量所产生的总成本建立了混合整数规划模型，通过割平面法从BACAP（Berth Allocation and quay Crane Assignment（number）Problem）的可行解中构造出BACASP（Berth Allocation and quay Crane Assignment（Specific）Problem）的可行解。杨劼等［7］考虑了离散型泊位布局下的动态泊位岸桥协调调度问题建立模型，设计了遗传算法求解，并对不可行解采用逐时刻基因调整策略进行修复。

上述文献都是基于分配岸桥组不变的情况进行的研究，而基于岸桥组可随时间变化的假设条件的研究较为复杂。Meisel 等［8］考虑了随时间变化的岸桥配置和由干扰引起的岸桥生产效率损失，同时将靠泊位置对岸桥效率的影响纳入考虑，以最小化由船舶加速所产生的服务质量成本和延迟离港而增加的码头运营成本为目标建立模型，并利用squeaky wheel 法和禁忌搜索进行求解。Zhang 等［9］在文献［1］的基础上，假设在装卸过程中分配给船舶的岸桥是可变的，建立了混合整数规划模型，提出了基于拉格朗日松弛和次梯度优化的算法对模型求解。Liang 等［10］研究了与文献［4］类似的问题，提出一种带启发式的组合遗传算法进行求解，确定每艘船舶的靠泊位置、靠泊时间和岸桥的作业计划，然而并没有考虑岸桥的移动时间和提供用于岸桥调度的详细算法。Han 等［11］考虑了船舶到港和作业时间的不确定影响，应用基于仿真的遗传算法搜索程序来生成稳健的泊位和岸桥计划。彭丽姣等［12］研究连续型泊位分配与岸桥动态调度的联合优化问题，以最小化延迟完工任务量、偏离偏好泊位和岸桥移动的惩罚费用最小化为目标，最终得到船舶靠泊和岸桥分派的可行计划，但并未给出求解算法。梁承姬等［13］综合考虑泊位的连续性和船舶的泊位偏好性建立了以船舶剩余作业量、船舶偏离偏好泊位的距离和岸桥移动次数之后最小为目标的混合整数线性规划模型，并通过CPLEX 求解。Türkoğulları 等［14］在文献［6］的基础上，在模型中引入重新设置岸桥成本，将BACASP 分解为主问题和子问题，结合使用分枝定界法、割平面法和动态规划法解决该问题。郑红星等［15］在考虑大型船舶需要乘潮进出港的约束的现实，考虑泊位分配、岸桥分配和岸桥调度三者集成，构建泊位分配—岸桥分配主模型、岸桥调度子模型，设计三阶段混合遗传算法求解。

梳理现有的研究发现，虽然泊位和岸桥配置的集成思想已被广泛应用，岸桥可跨船调度的现实也被一同考虑，但未能针对性合理分配。船时效率是码头监控船舶作业的重要指标，以实时船时效率与基准线的偏差为触点，同时综合考虑其他在泊船舶的现况从而调整岸桥配置可时刻将作业效率控制在计划水平并保证整体方案的最优性。因此本文考虑岸桥配置可基于船时效率进行动态调整，在船舶动态到港且相关信息已知的情况下，对连续泊位分布下的船舶泊位分配和岸桥配置集成优化问题进行进一步研究，以最小化包括船舶延迟靠泊成本、偏离偏好泊位成本、延迟离港成本和岸桥重新配置成本在内的总成本为目标建立模型，基于每时段的船时效率监控设计相应岸桥调度规则，并将其嵌入遗传算法对问题进行求解。

1 问题描述

在码头的实际岸边作业过程中，船舶作业情况会被监控，若实时船时效率与基准线产生偏差，则需及时调整资源配置以便船舶按时完成装卸任务。船时效率由船时量表示，代表了船舶单位时间内平均完成的装卸作业量，计划船时量作为生产作业基准线，是根据总装卸任务量和期望在泊时间计算所得。由于船时效率受岸桥配置影响，当实时船时量低于基准线时则代表应添置岸桥；反之，则可调离岸桥。而目标船时量由剩余作业量和剩余作业时间计算所得，为剩余作业时间内应配置的平均岸桥数量提供了参考。例如，某船舶靠泊后配置了3 台时效率固定为24 箱/h 的岸桥开始作业，如图1 所示:第4 小时时，实时船时量不足，船舶面临滞期应增设岸桥，根据目标船时量剩余时间应设4 台岸桥，由于资源充足，实际增设至5 台岸桥；在第12 小时时，实时船时量过剩可调离岸桥，根据目标船时量剩余3 台岸桥作业；最终在第19 小时时，实时船时量与计划船时量重叠，目标船时量为0，船舶全部装卸任务完成可按时离泊。

图1 船时效率Fig. 1 Ship efficiency chart

基于上述岸桥配置动态调整思路，同时为充分利用岸边资源，尽可能降低岸桥闲置，最小化损失成本，达到岸边作业效益最大化，本文在船舶的泊位分配和岸桥配置的集成优化基础上，提出了基于船时效率的岸桥配置动态调整方法。

图2表示V2（Vessel 2）在泊作业第若干个时段末的场景，此时有4 台岸桥对V2 进行装卸作业，实时船时量不足，以当前岸桥配置无法保证V2 的正常离港；而此刻V3 的船时量过剩，根据目标船时量，剩余作业量只需2 台岸桥即可按时完成。因此可将QC5（Quay Crane 5）调度至V2服务。

图2 某时段基于船时效率的岸桥配置调整Fig. 2 Adjustment chart of quay crane assignment based on ship efficiency in a certain period of time

当有船舶请求靠泊时，为使船舶尽早靠泊，船舶只需达到最小岸桥数量即可开始装卸作业。如图3（a）所示，某时刻V4按预计时间入港且指定岸线空闲，但此时岸线范围内只有QC6空闲，可用岸桥数量不足。根据各船舶目标船时量，其中V3若调离1台岸桥则将面临滞期费用，但远低于V4在锚地继续等待的成本，因此可将QC7从V3调度至V4。

当有船舶请求离泊时，岸桥配置应基于各船舶船时效率进行全岸线调整。如图3（b）所示，某时刻V2 离泊，QC3、QC4、QC5 分别调度至V1 和V4，同时原本在V4 作业的QC7 调度回V3作业，所有船舶面临的在泊总成本得以减少。

图3 船舶靠离泊时基于船时效率的岸桥配置调整示意图Fig.3 Adjustment chart of quay crane assignment based on ship efficiency when a ship berths or leaves

因此，本文以包括船舶靠泊时刻、离泊时刻在内的每隔一固定时段为触发点，基于船时效率对船舶的岸桥配置进行动态调整优化，使岸桥在具有不同紧急程度的船舶间进行合理分配，并以最小化所有船舶在泊成本为目标构建模型，设计启发式规则，结合遗传算法对问题进行求解。

2 模型建立

2.1 模型假设

a）每条船舶能且只能靠泊一次；

b）每条船舶都有一个偏好泊位；

c）船舶预计到离港时间及相关数据已知；

d）所有岸桥的台时量相同且固定不变；

e）岸桥作业时不可以交叉跨越；

f）不考虑装卸过程中船舶的平衡问题；

g）船舶装卸时间与分配的岸桥数成反比；

h）每艘船都有最大和最小岸桥数量限制；

i）船舶装卸过程中岸桥数量以及具体的岸桥可以变动；

j）不考虑泊位的物理限制；

k）船舶一经靠泊不可移泊；

l）不考虑岸桥移动时间，考虑每台岸桥重新配置固定本。

2.2 模型参数及决策变量建立

2.2.1 索引和集合

2.2.4 决策变量

zks:0-1 变量，若船舶k 在船舶s 靠泊前离港且具有重叠的靠泊区域，则为1；否则，为0。

yks:0-1 变量，若船舶s 在船舶k 右边靠泊且具有重叠的靠泊时间段，则为1；否则，为0。

xkqt:0-1 变量，若岸桥q 在时段t 为船舶k 服务，则为1；否则，为0。

wkqt:0-1 变量，若船舶k 在时段t具有一台新的岸桥q 的设置，则为1；否则，为0；

βk:船舶k的靠泊位置。

2.2.5 从属变量

θk:船舶k的靠泊时刻；δk:船舶k的完成任务时刻。

2.3 目标函数及约束

其中:目标函数（1）表示最小化船舶总服务成本，包括船舶延迟靠泊成本、偏离偏好泊位成本、延迟离港成本和岸桥重新配置成本；式（2）表示船舶到港才能靠泊；式（3）表示所有船舶必须停靠在码头岸线以内；式（4）表示确保每艘船的装卸任务都被全部完成；式（5）表示任意时刻作业的岸桥数不超过码头岸桥总数；式（6）表示避免时间上重叠的船舶在靠泊位置上有重叠；式（7）表示限制给每条船舶的岸桥数量；式（8）表示每个岸桥在同一时段最多只能服务一艘船舶；式（9）表示船k 在船s的右边靠泊且游重叠的靠泊时间，q 为船k 作业，q′为船s 作业，必须q＜q′，即保证岸桥之间不可跨越；式（10）表示确保船舶作业使用连续的岸桥；式（11）-（13）定义变wkqt；式（14）～（17）定义0-1变量。

3 算法与规则设计

本文研究的问题属于NP-hard 问题，需要在建立的非线性整数规划模型基础上对目标函数进行优化求解最佳泊位和岸桥配置方案，随着问题规模的增大，计算复杂度将呈指数增长。在以往此类问题的研究中，多采用群智能算法，而遗传算法简单通用，并行处理广，其无向导性的遗传操作使其有着良好的全局优化能力。针对本文提出的动态调整策略，将其与遗传算法进行结合能将约束嵌入算法结构中，降低问题复杂度，增加解的多样性的同时获取高质量的全局最优解。因此本文采用遗传算法，并基于岸桥配置根据船时效率动态调整的思想设计一种启发式算法嵌套于遗传算法的评价阶段，最终通过循环优化求得最优解，算法流程如图4所示。

图4 本文算法流程Fig. 4 Flow chart of the proposed algorithm

3.1 染色体编码和种群初始化

本文采用基于自然数的多级染色体编码，将计划期内所有到港船舶按其预计到港时间进行排序编码，如图5 所示，染色体的每一列对应一艘船的分配方案。其中，染色体的第一行表示船舶的编号，从左到右依次表示船舶的靠泊顺序；第二行表示船舶的靠泊位置，本文把岸线每1 m 作为一个单位；第三、四行表示分配给船舶的岸桥组编号始末。以第一列为例，V2 第一个靠泊，靠泊位置为95 m 处，由QC1、QC2、QC3、QC4和QC5为其服务。

图5 染色体编码图Fig. 5 Chromosome coding chart

根据上述规则生成初始种群的所有染色体，当染色体的数量达到种群大小时初始化结束。

3.2 解码和基因修复

本文染色体编码中，采用决策变量βk和xkqt描述船k 的状态，而θk和δk可基于以上决策变量依据解码规则和约束条件计算。基于泊位岸桥集成分配的思想，本文使用以下解码算法:

在染色体序列中从左到右访问基因，对于每个基因所对应的船舶k，结合ek，若船舶k 的靠泊区域[ βk，βk+ lk]空闲且指定岸桥组全部可用，则ek即可赋值给θk；而若靠泊区域[ βk，βk+ lk]有船舶作业或指定岸桥组并非全部空闲时，则等占用靠泊区域和岸桥组的船舶完成作业，船舶k 才可以靠泊，并更新θk，这样才不会违反任何约束。当岸桥配置方案确定时，δk即可通过计算得到。

在解码过程中，考虑到由于给船舶分配的岸桥组为随机生成，若规定只有在原分配岸桥组全部空闲时才可以服务船舶，则船舶一定会出现大量的等待。为减少单纯由于指定岸桥组的不可行而造成的等待，在泊位空闲的前提下，可对指定岸桥组进行修复，替换为相同数量的可行连续岸桥组。

3.3 启发式调整和适应度计算

本节基于船舶的岸桥配置根据船时效率进行动态调整的思想，设计了启发式规则，以船舶靠、离泊时刻以及在船舶作业过程中每隔一固定时段为触发点，在原靠泊方案的基础上，对船舶的岸桥配置进行调整，从而进一步优化，具体规则如下:

若此刻为船舶k开始作业后的第r时段末:

当有船舶离泊时，全岸线在泊船舶依次进行基于上述规则的调整。当有船舶靠泊时，计算船舶因岸桥数量不足最小限制而产生的继续等待成本，若大于从旁调度岸桥后岸线产生的总新增滞期成本，则可提前靠泊；否则继续等待。

根据启发式规则调整后的方案，计算目标函数值，适应度值取目标函数值的倒数:Fitness= 1/f。

3.4 选择

根据一定的选择概率，从父代群体中选择新的群体，其优于父代种群。本文采用轮盘赌的方法选择单个染色体作为新一代种群个体。

3.5 交叉和变异

交叉操作决定了被选择的个体如何进行基因交换。对选择出的父代个体以交叉概率进行顺序交叉（Order-Based Crossover），在选择的两个父代中，随机选择两个相同交叉列，以船舶编号为准进行相应位置的列复制和补齐，以产生新的子代；染色体的变异策略为随机选择个体的某一基因位，将其更改为满足变动范围条件下的随机值，以保证染色体的合法性。

4 算例分析

为了验证本文提出的模型和算法的可行性，本文参考上海某集装箱港口的实际运营数据设计算例进行研究，通过与未考虑岸桥配置进一步调整的传统遗传算法的优化结果进行对比，从而验证上述所提模型和算法的有效性和适用性。运行环境为Intel Core i5 处理器、内存8 GB、硬盘500 GB 的个人计算机，使用Matlab2018a运行本文算法来求解算例。

4.1 输入数据

某集装箱码头拥有连续岸线1 400 m，共配备岸桥16 台，从左起编号依次为1～16，岸桥效率为40 箱/时，岸桥重新设置成本为100 元/台，单个集装箱偏离偏好泊位1 m 的成本为0.01 元，每艘船单位偏离成本如表1 所示。该码头半天到港船舶共计9 艘，并且其预计到/离港时刻、偏好位置、每艘船舶单位延迟靠泊费用和滞期费用提前可知，每艘船的装箱任务箱量已知，如表1 所示，船舶最大最小岸桥数由船长决定，小于200～300 m 船 舶 为3～5 台，船 长 大 于300 m 岸 桥 限 制 为5～7台。

4.2 结果分析

针对本文模型和算法规则，在算法中设置了相应的参数:种群大小N=50，迭代数MAXGEN=700，交叉概率Pc=0.7，变异概率Pm=0.1，并设定除船舶靠离、泊时刻外，每隔60 min 对船时效率进行监控。在Matlab 平台中运行求解，得到遗传算法的结果收敛图，如图6 所示。由结果收敛图可以看到，迭代到380 代时结果收敛至最优解，所有船舶的实际靠泊时间、离港时间和靠泊位置如表2所示。

图6 结果收敛图Fig. 6 Convergence diagram of results

各船舶不同时段的岸桥配置情况如表3 所示，数据为a［b］结构，其中:a 表示岸桥编号，b 表示岸桥作业的起止时刻。

表1 算例数据Tab. 1 Data of examples

以V2 为例，结合图7～8 解释各船舶每时段基于船时效率的岸桥配置调整:03:00为V2在泊作业的第3个时段末，此时已完成440 箱装卸任务，其计划船时量、实时船时量和目标船时量分别为160 箱、147 箱和200 箱，实时船时量小于计划船时量，面临滞期。若V2 继续以当前3 台岸桥配置下的120 箱/时段的平均效率继续作业，04:40 才可完成剩余装卸任务，将会产生滞期费用972.40 元。由于此时V4 已达到最小岸桥数量，只能考虑从V3 调度岸桥至V2，在保证V3 最小作业岸桥数量的前提下，所有方案中调度1 台岸桥是当前优化效果最大的方案:V3 新增289.13 元滞期成本，V2 减少607.75 元滞期成本，在泊船舶总成本降低，因此将QC12调度至V2可达到整体优化目的。

表2 算例决策变量结果数据Tab. 2 Decision variable results of examples

为验证本文提出的规则的优化效果，本文在泊位分配和岸桥配置集成优化的基础上，分别用结合基于船时效率的启发式岸桥配置调整规则的遗传算法与未考虑岸桥配置动态调整的传统遗传算法对相同算例进行优化求解，结果如表4 所示，使用未考虑岸桥配置动态调整的传统遗传算法优化得到的总成本为64 788.76 元，而相比之下，利用本文模型和算法得到的最优结果为44 935.39 元，优化了30.64%，其中，偏离偏好泊位、延迟靠泊和延迟离泊成本分别改进了40.12%、26.98%和39.46%，虽然岸桥设置成本因岸桥配置的多次调整而有所提高，但整体上仍具有明显的优化效果。

图7 V2船时效率Fig. 7 Ship efficiency chart of V2

图8 V3船时效率Fig. 8 Ship efficiency chart of V3

表3 岸桥作业计划Tab. 3 Quay crane operation schedule

表4 各项成本数据对比Tab. 4 Comparison of various cost data

同时，为更加直观地体现优化效果，岸桥作业计划对比如图9所示，其中图9（a）为传统遗传算法的结果。

图9 岸桥作业计划甘特图（n=9）Fig.9 Gantt chart of quay crane operation schedule（n=9）

为验证大规模算例下基于船时效率的岸桥配置优化方法的有效性，在上述算例的基础上，将时间延长为一天24 h，船舶数量由9艘增至15艘，基于本文模型和算法完成优化，最终结果的岸桥作业计划如图10 所示。最终优化结果为81 440.00 元，相对于未加入启发式调整的遗传算法优化结果为113 047.03元，优化了27.95%，优化效果明显。

图10 岸桥作业计划甘特图（n=15）Fig. 10 Gantt chart of quay cranes operation schedule（n=15）

对于船舶岸桥配置的调整优化问题，从不同算例规模下两种算法优化结果的对比分析可以看出，本文提出的模型和算法具有明显且稳定的优化效果。

4.3 不同规模算例结果

为验证本文算法在解决港口实际问题中的普遍有效性和稳定性，随机选取5 例船舶数量不同规模的实际运营数据与上文算例进行相同处理，每例算例优化结果均取10 次实验内最优，并与传统遗传算法优化结果进行对比分析，具体结果如表5所示。

表5 不同规模算例结果对比Tab. 5 Result comparison of examples at different scales

根据实验结果分析可见，本文提出算法在不同规模的多个算例中均保持着20%以上的优化效果，验证了本文提出算法的优化效果稳定性。

4.4 算法有效性分析

为验证算法的有效性，本节针对4.3 节中的5 组算例，采用本文所提出的结合启发式规则的遗传算法和粒子群优化（Particle Swarm Optimization，PSO）算法分别求解并对结果进行对比分析。本文算法各参数沿用前文设置，PSO 算法的种群规模设置为50，最大迭代次数为700，惯性权重ω = 0.729 8，学习因子c1= c2= 1.149 618，每例算例优化结果均取10 次实验内最优结果，CPU 时间取10 次实验结果平均值，结果如表6所示。

表6 本文算法与PSO实验结果对比Tab. 6 Experimental result comparison ofthe proposed algorithm and PSO

从表6 可知:当船舶数量较少时，本文算法的结果稍优于PSO 算法，且运行时间相差不大；但随着算例规模的增大，本文算法的优势更加明显，无论是在收敛速度还是计算结果上，其均明显优于PSO算法。由此验证了本文所提出的结合启发式规则的遗传算法在求解泊位分配和岸桥配置集成优化模型上的有效性和算法优势。

5 结语

本文针对连续泊位分布下船舶的泊位分配和岸桥配置集成优化问题进行了研究，结合对船时效率的实时监测和岸桥配置动态调整的思路，提出了一种基于船时效率动态调整岸桥配置的优化方法，以最小化包括船舶延迟靠泊成本、偏离偏好泊位成本、延迟离港成本和岸桥重新配置成本在内的总成本为目标建立模型，并设计了基于船时效率动态调整岸桥配置的启发式算法，将其嵌套于遗传算法的评价阶段对问题进行求解。根据某集装箱港口的运营数据进行算例分析，分别应用本文提出的算法与传统解决泊位分配和岸桥配置集成优化的遗传算法对不同规模的算例进行优化和对比分析，实验结果表明:1）相对于岸桥固定的配置，根据本文模型和算法求解可达到20%以上的优化效果，使岸桥资源得以更加充分利用的同时船舶在泊成本进一步降低；2）随着船舶数量增加，算法优化效果稳定。而通过将本文提出算法与粒子群算法对比分析的结果则验证了本文提出算法的求解有效性与优越性。船时效率是由船舶配置的各岸桥台时量共同决定的，而在集装箱码头的实际作业过程中，岸桥台时量会受到各种现实情况影响而产生波动，本文的研究尚未能将岸桥作业效率的变化考虑在内，未来关于集装箱码头船舶靠泊及装卸作业的研究可以将这些不确定性因素考虑在内，使研究更具有现实意义。