考虑船舶碳排放的集装箱船舶进港靠泊调度问题研究

曾庆光，董明望，辜 勇

（武汉理工大学，湖北 武汉 430063）

1 引言

温室气体排放引起全球变暖，作为其最主要的发生来源，二氧化碳成为环境领域关注的重点。预计到2050年，航运业碳排放量将达到18%。考虑低碳因素，对港口内部机械作业流程优化，寻求港口资源的合理配置，对于实行节能减排、发展绿色港口航运、提升港口群整体的竞争力等具有重要价值[1]。

许欢等以船舶到港时间作为决策变量，区别于传统的泊位分配问题，提出基于港口与船方协调调度的新的泊位分配策略（Variable Arrival Time，VAT），以船舶油耗量最小和船舶离港延迟时间最短为目标函数，建立了双目标优化模型[2]；韩晓龙等分别建立了船舶到港时间可变（VAT）和到港时间固定策略（CAT）下的泊位—岸桥联合调度模型，以最小化船舶延迟离港时间、航行油耗和整个码头碳排放为目标进行多方面多层次对比分析，VAT相较于CAT，不仅可保证船舶的服务水平。而且还可以大幅度减少船公司航行油耗和整个码头的碳排放[3]；靳玉基于船舶的偏好停泊泊位，考虑碳排放成本对码头作业的影响，以提升码头服务质量和降低码头作业成本两方面为目标，建立泊位岸桥联合配置多目标优化模型，并运用改进的自适应遗传算法求解[4]；王旭等以最小化船舶碳排放和平均延迟时间为目标，考虑到港时间不确定性和集卡运输能力受限等约束，建立多目标非线性混合整数规划模型，采用高效非支配排序的遗传算法求解[5]；彭云等通过系统仿真的方法计算出船舶、岸桥、集卡等碳排放量，结果显示船舶的总排放占比80%，且港内航行占50%左右[6]。

本文研究基于船舶碳排放最小的集装箱码头调度问题，先对船舶计划到港时间进行有效预测，形成合理的船舶到港时间统计表。考虑船舶船长、集装箱装卸量、连续型泊位分配情况、岸桥分配调度过程约束等条件，建立以船舶在港时间最小化和船舶港内油耗最小为目标的双目标函数模型，在此基础上，进一步考虑船舶到港时间可协调情况下的作业调度计划，并用遗传算法求解该模型，进而比较不同策略下船舶港内油耗情况，为降低船舶港内排放提供理论基础。

2 船舶进港靠泊作业调度问题分析

2.1 船舶进港排放分析

船舶作为港口内主要的排放源，其中港内航行的排放占到船舶总排放的60%—80%，航行时船舶的主机和辅机一同运转，主机功率通常为辅机十几倍，因此，港内航行的排放占据较大部分，而船舶除外的集卡、岸桥和场桥，加起来仅仅占到20%—30%，从能耗上来看，船舶依然是能耗主体，根据以上描述，船舶航行时，主机与辅机同时运转，其油耗见式（1）。

根据式（1）可知，选取天津港某段时间的15艘船，具体数据见表1，假设为单辅机作业，航行距离设置为30海里，通过Matlab编写函数寻优，绘制油耗和航速之间的关系，如图1所示，该船舶的最佳航速约为11.3节，油耗约为3 411.2kg，而以航速为30节行驶时，油耗量可达到7 500kg以上，由此可见，以经济航速可以大幅度减少油耗。

表1 某港口入港船舶信息表

图1 船舶1航速与油耗关系分布图

2.2 泊位分配和装箱理论

连续泊位问题是指无固定泊位，船舶可根据实际岸线和与其他船舶的约束，在任意岸线坐标上靠泊，该问题就如同装箱问题。鉴于连续型泊位不仅提高泊位利用率，还可以减少船舶总在港时间，本文采用连续型泊位分配。图2表示15艘船的连续型泊位动态作业调度，在不考虑岸桥数量分配和调取情况下而衍生出二维装箱问题，横轴表示岸线固定长度，以50m为一个船区进行划分，分为30个船区，纵轴表示时间维度，图中N1—N15表示15艘船舶的作业计划，根据二维矩形的长度大致判断其作业时间段和所在岸线的坐标。

图2 船舶靠泊问题装箱图

装箱问题是一种复杂的离散组合优化问题，也是一种NP-Hard问题。装箱问题是随着计算机技术而产生的，可应用于汽车、造船、货物装载和大规模集成电路等行业，也应用于运筹学、人工智能等领域，在物流生产领域中，集装箱的配载问题较为明显。

2.3 船舶作业与岸桥分配调度

岸桥作为集装箱码头岸边作业系统中实现集装箱垂直和水平位移的机械作业工具，是泊位之外的另一项核心资源。通常岸桥数量的确定由岸线长度来决定，船舶进入港汊内，成功靠泊并完成相关准备作业工作后，岸桥开始对船舶上的集装箱进行装卸操作。分配给某船舶的岸桥数量对作业时间影响很大，通常需要考虑船舶集装箱贝位数量以及不同岸桥作业人员的装卸技能指数，有时某些岸桥在作业中途出现故障，甚至无法行动，那么该岸桥下的贝位集装箱无法作业，将会导致该船舶因为该贝位区域未完成作业而大大延期，如果尝试船舶沿岸线进行泊位移动，将会增加船舶本身与岸线之间碰撞的可能性而带来安全隐患，因此，船舶通常不进行移动泊位。

3 作业调度模型建立

3.1 船舶到港时间固定调度模型

模型假设：

（1）每艘船到港时间可提前预知；

（2）船舶港内行驶航速满足最大最小值约束；

（3）每艘船舶有且仅有一次停泊机会，并且停泊后坐标不能改变；

（4）每艘船的岸桥作业数量满足其约束；

（5）不考虑潮汐对船舶吃水深度的约束；

（6）不考虑其他类型船舶和集装箱船舶的避让影响；

（7）船舶作业完毕后，按照经济航速进行行驶，不计入排放范围；

（8）集卡数量充足且能够完全配合岸桥实现堆场转运；

（9）船舶到港时间为船舶从港外水域到达锚地时间，入港时间是从锚地出发向港内水域行驶时的时间。

使用数学符号如下：

V ：到港船舶集合（i=1，2，…，N）；T ：作业最大期限；ATi：船舶i预计到港时间；LVi：船舶i的长度；Ci：船舶i的集装箱装卸量；vi：船舶i锚地至泊位航速；QZ：码头岸桥总数；BL：泊位总长度；F：船舶在港总油耗；LD：锚地至泊位航线路程；F1i：船舶i主机在港油耗；F2i：船舶i辅机在港油耗：船舶i岸桥作业数量上限；：船舶i岸桥作业数量下限；qv：单个岸桥装卸速度；M：足够大的整数；T2i：船舶作业完毕离泊时间；TDi：船舶锚地等待时间。

决策变量：

TVi：船舶i的靠泊时间；ZVi：船舶i的靠泊岸线坐标；Wi：船舶i的装卸作业时间；qi：船舶i的实际分配岸桥数。

式（3）表示船舶总靠泊作业时间最小；式（4）表示船舶总油耗最小；式（5）和式（6）分别表示船舶靠泊作业过程中主机和辅机的油耗；式（7）表示船舶从锚地至泊位港内航行时段的航速范围；式（8）表示靠泊坐标的约束范围；式（9）表示靠泊时间与到港时间的约束关系；式（10）表示每艘船的作业调度岸桥数的约束范围；式（11）—式（13）表示任意两艘船之间存在的时间空间上的约束关系；式（14）表示遍历任意时刻的岸桥数总和不超过总岸桥数；式（15）表示作业时间与作业量、岸桥数量、岸桥装卸速度的关系；式（16）与（17）表示选取的判定因子为0-1变量；式（18）表示装卸作业时间与靠泊时间、离开泊位时间的关系。

3.2 到港时间可协调机制下的作业调度模型

针对船舶到港时间可协调情况下的作业调度问题，其决策变量新增船舶到港时间，目标函数新增船舶离港延迟时间，新增数学符号：LTi：船舶i预计离港时间（完成装卸作业后立刻离开的时刻）。

决策变量：

ASTi：船舶i协调机制下的到港时间；TVi：船舶i的靠泊时间；ZVi：船舶i的靠泊岸线坐标；Wi：船舶i的装卸作业时间；qi：船舶i的实际分配岸桥数

到港时间可协调情况下的建模与非协调机制下的建模大体相似，只需要将式（19）替换式（3），式（20）替换式（6），式（21）替换式（9）。

当目标函数为船舶离港延迟时间时，目标函数见式（22），其中单个船舶离港延迟时间为见式（23）。

4 算法流程

4.1 主流程

遗传算法一般流程是生成初始种群、参数初始化，而经过种群中个体的选择交叉变异之后得到新的种群，但是基于船舶作业调度问题，一方面需要规则修复算子，另一方面针对多目标问题，利用快速非支配排序，对多种群中个体进行有效排序，而保留优势个体。

Step1 初始化参数：将种群初始规模定义为PopSize，种群遗传代数为Gen，初始种群序列Fi=Φ，拥挤度为Cd，生成随机初始种群Pop。

Step2 修复算子：初始种群采取随机生成，极可能产生不可行解，对其进行规则修复。

Step3 合并算子：父代与子代进行合并，形成待排序种群集合PopN，计算PopN中每个个体的目标函数值minT、F。

Step4 快速非支配排序：根据步骤3中的双目标函数求解，对PopN中个体先计算其目标值，再进行快速非支配排序并生成新的序列Fi（i=1,2,…,L），提取较为合适的个体组成新的种群。

Step5 交叉算子：对Pop中一部分个体两两配对，针对两个个体对应的等位基因进行交叉操作得到Pop’。

Step6 变异算子：对Pop中交叉之外的另一部分个体进行变异操作得到Pop”，然后再将Pop’与Pop”合并为子代MergePop，并且再次通过修复算子对待定解进行规则修复。

Step7 快速非支配排序及计算拥挤度：对MergePop再次进行非支配排序生成新序列F，并计算种群F中每个个体拥挤度Cd。

Step8生成子代：以MergePop中Fi（i=1,2,…,L）和Cd为基础，提取排序在前Popsize的个体，生成新一代种群数为Pop Size的种群Pop。

Step9 判断终止条件：若未达到迭代代数Gen，转到步骤3，否则终止算法得到最优解。

4.2 规则修复算子

针对类似装箱问题求解过程中存在不可行解，即两条船之间出现时间或者空间上的冲突，当冲突存在时，启动适当的调整程序，即规则修复算子，步骤如下：

Step1 检查靠泊时间是否满足式（9），如果不满足，将船舶靠泊时间改为在约束的时间范围中取随机整数，检查靠泊坐标是否满足式（8），如果不满足，将靠泊坐标改为船区约束范围内的随机整数，检查分配的岸桥数是否满足式（10），若不满足，取某船岸桥约束范围内的随机整数。

Step2 检查遍历任意整数时刻的装卸作业岸桥数量是否超过最大限度QZ，即式（14），若不满足TVi=TVi+1，直到满足总岸桥数量约束为止。

Step3 检查分配完毕的船舶是否满足式（11）—（13），若不满足，则令ZVi=ZVi+1，直到找到可行的靠泊位置，若到岸线终点依然不满足，则TVi=TVi+1 。

Step4 如果步骤3中出现TVi=TVi+1，之后立刻通过步骤2检查分配的岸桥数是否满足式（14），如果不满足式（14），TVi=TVi+1，直到满足为止。

Step5 检查完所有船舶后，条件满足，修复结束。

4.3 NSGA-II

1995年，Srinivas和Deb提出了非支配排序遗传算法（Non-dominated Sorting Genetic Algorithms，NSGA）。这是一种基于Pareto最优概念的遗传算法，NSGA与简单的遗传算法的主要区别在于选择算子执行之前根据个体之间的支配关系进行了分层。

NSGA-II对第一代算法中非支配排序方法进行了改进：对于每个个体i都设有以下两个参数n(i)和S(i)，n(i)为在种群中支配个体i的解个体的数量（别的解支配个体i的数量），S(i)为被个体i所支配的解个体的集合（个体i支配别的解的集合）。

（1）首先，找到种群中所有n(i)=0的个体（种群中所有不被其他个体支配的个体i），将它们存入当前集合F(1)（种群中所有未被其他解支配的个体）

（2）然后对于当前集合F(1)中的每个个体j，考察它所支配的个体集S(j)，将集合S(j)中的每个个体k的n(k)减去1，即支配个体k的解个体数减1（因为支配个体k的个体j已经存入当前集F(1)）；

（3）如n(k)-1=0则将个体k存入另一个集H。最后，将F(1)作为第一级非支配个体集合，并赋予该集合内个体一个相同的非支配序i(rank)，然后继续对H作上述分级操作并赋予相应的非支配序，直到所有的个体都被分级。其计算复杂度为O(mN2)，m为目标函数个数，N为种群大小。

在原来的NSGA中，采用共享函数以确保种群的多样性，引入拥挤度这一因子，用id表示，它表示在个体i周围包含个体i本身但不包含其他个体的最小的长方形，如图3所示。

图3 Pareto平面图

从图3可以看出，id值较小时表示该个体周围有较多的其他相邻个体，说明该个体的拥挤程度比较大。基于个体多样性的需要，保证留下的个体收敛到一个均匀分布的Pareto面上，当两个个体非支配排序等级不同时，选择等级较小的个体；如果排序等级相同，选择拥挤度较小的个体。

4.4 选择交叉变异

遗传算法的一般过程都需要有选择、交叉、变异算子，而该算法所采取的算子规则如下：

（1）确定交配池中的个体数量popsize。

（2）确定交叉概率为PJ1，任意取1个取值范围在（0，1）的随机数，若该数小于PJ1，执行交叉操作，若大于PJ1，小于PJ2执行变异操作。

（3）若执行交叉操作，任意选择两个个体作为亲代，两个个体上所有的基因有一半的概率进行交叉，另外一半的概率保留亲代基因，产生新一代子代。

（4）若执行变异操作，则随机从交配池中选择一个个体作为亲代，有关船舶靠泊时间和靠泊坐标上的基因d'ij变化见式（24）。

表示父代个体i的基因位置j，表示子代个体i的基因位置j，r为[0,1]范围内的随机数，G表示当前迭代数，gen表示最大迭代数，m表示变异分布指数。

5 算例和结果分析

通过对天津港实地调研，以太平洋国际集装箱码头为例，确定入港船舶时间和装卸作业量相关数据，岸桥数为23台，岸线为1 500m，30个船区，装卸量和入港时间以及其他船舶数据参考实际情况，见表2，遗传代数为5 000代，种群规模为300，概率PJ1为0.5，概率PJ2为0.9，变异分布指数为0.5，决策变量方面，船舶泊位分配的岸线坐标和岸桥分配数量均以最小至最大范围内随机生成整数，而初始解中靠泊时间满足范围的不等式见式（25），当以船舶离港时间和船舶油耗作为双目标进行求解时，每艘船离开泊位时间见式（26），离港延迟时间见式（27）。

表2 天津港某段时间入港船舶信息表

（1）入港时间协调情况（目标函数为油耗和总在港时间）。如图4所示，Pareto最优解为（767.3，1.088 4×106），运算时间6 534s。（2）非协调机制情况（目标函数为油耗和总在港时间），该算例下不采取协调到港时间作业措施，以预计时间作为实际入港时间，即不将船舶到港时间作为决策变量而作为已知值进行计算。

如图5所示，Pareto最优解为（805.3，1.110 2×106），运算时间3 663s。（3）入港时间协调情况（目标函数为油耗和总离港延迟时间）。如图6所示，Pareto最优解为（331.6，1.084 9×106），运算时间7 188s。

图4 运算结果1

图5 运算结果2

图6 运算结果3

比较（1）、（2），容易得出基于船舶到港时间可协调机制下作业调度计划不仅可以将船舶总在港时间减少5%左右，还能将船舶油耗（碳排放）降低2%，比较（1）、（3），如果将船舶离港延迟时间和油耗作为双目标函数，要比船舶在港时间和船舶油耗作为双目标函数，油耗略低，并且求得的解是最优解（两目标均最优）。因此该算例以船舶离港延迟时间作为评价港口码头服务水平的指标，更有利于减少船舶港内排放。

6 结语

本文针对船舶入港靠泊作业调度问题，以船舶碳排放为切入点，一方面考虑船舶港内航行时的油耗和时间，另外也考虑船公司与码头之间协调到港时间，以此减少船舶在港时间，有利于作业调度资源的充分利用和船舶等待时间的较小化，从而适当降低船舶港内排放。在算法上，基于调度建立以船舶排放最小和船舶总在港时间（或船舶总离港延迟时间）最小为目标的双目标作业调度问题，以NSGA—II为基础，通过比较不同修复算子下的求解状况，验证算法的有效性，同时，提出船舶到港时间可协调的作业调度问题，并利用该算法验证船舶到港时间可协调机制有利于降低船舶港内排放，即协调机制下船舶的港内排放可减少2%，为绿色港口的建设提供理论基础。