基于同贝同步装卸的岸桥与集卡协同调度

张艳伟， 谭永庆， 莫满华， 王 楠

（武汉理工大学 交通与物流工程学院，湖北 武汉 430063）

随着集装箱运输业务的发展，港口集装箱吞吐量持续增长，业务量增长及船舶大型化对集装箱码头作业能力和作业效率产生巨大冲击。同贝同步装卸［1］模式通过对装、卸两类集装箱的装卸顺序优化，实现岸桥及水平搬运设备充分利用，是提高集装箱码头装卸作业效率和资源利用率的有效途径。

国内外学者关于集装箱船舶的装船顺序问题［2-4］已经取得了丰富的研究成果，该问题主要考虑满足装船技术要求前提下以堆场内翻箱次数最少为优化目标，利用遗传算法、启发式算法［5］进行求解；然而针对同贝同步装卸作业模式，装船与卸船配合才是其提升效率的关键所在，Zhang［6］在Goodchild［1］基础上以最大化岸桥的双循环操作次数为优化目标，利用混合启发式算法求解岸桥装卸顺序问题；Wang［7］研究了带舱盖板约束的双循环岸桥调度问题，通过对舱位间作业顺序优化和舱内列之间顺序优化达到减少岸桥空载行程的目的；张文韬［8］基于遗传算法有效求解考虑舱盖板约束的岸桥作业序列优化问题；考虑到集装箱装卸受到岸桥、集卡以及场桥等多作业设备的影响，ALT等［9］设计粒子群算法求解岸桥和集卡联合调度问题以减少岸桥与集卡间双向等待时间；Kaveshgar等［10］结合贪婪算法设计遗传算法求解岸桥与集卡联合调度模型；Vahdani 等［11］针对多个码头间集卡共享情况下岸桥与集卡联合调度，建立以码头运营成本最小和码头溢出工作量最小为目标的双目标优化模型，制定了集卡分配和岸桥匹配方案。

综上，目前已有研究大多考虑先卸后装模式下岸桥与集卡调度或同贝同步装卸船模式下集装箱装卸顺序问题。本文研究同贝同步装卸模式下，船舶贝位内岸桥装卸集装箱作业序列与集卡任务分配及指派联合优化，同时考虑舱盖板等空间约束对同步装卸船顺序的影响，以及集卡双向重载与岸桥同步装卸作业配合等。针对同贝同步装卸模式下，装卸船作业序列空间约束多、集卡调度复杂度大等问题特征，研究设计改进遗传算法-改进非支配排序多目标遗传算法（IGA-INSGA-II）两阶段决策算法。第一阶段，考虑舱盖板约束及堆场翻箱影响，设计基于空间约束算子的改进遗传算法求解船舶贝位内岸桥作业序列优化问题；基于第一阶段装卸船顺序优化序列，第二阶段考虑既定船舶多台岸桥共享集卡，以及最大化集卡双向重载配合岸桥同步装卸，设计基于最早可作业时间优先的分段式编码多目标遗传算法求解集卡水平搬运任务分配与指派问题。

1 问题描述

常规先卸后装情况下，岸桥移动到既定船舶贝位，先完成卸船作业，再进行装船作业。与先卸后装装卸船模式不同，同贝同步装卸是指在集卡及场桥的协同配合下，岸桥对船舶贝位内的集装箱同步进行卸载和装载作业，将集卡上一个出口箱装载到船上后立即卸载一个进口箱到同一辆集卡上，实现岸桥与集卡的双程重载，如图1所示。

图1 同贝同步装卸船模式Fig.1 Dual cycling model of loading /unloading ship

同步装卸的关键在于岸桥装卸、集卡双向搬运及堆场收发箱等多设备多环节的协同配合，其难点在于需要考虑舱盖板等空间约束及堆场翻箱等复杂影响，优化决策同时装、卸集装箱的装卸船作业顺序，并针对装卸作业顺序给出优化的集卡水平搬运调度方案，有效衔接岸桥同贝同步装卸实施。本文以“岸桥-集卡-场桥”装卸工艺集装箱码头同贝同步装卸船系统为研究对象，集卡为单船作业面调度模式，船舶贝位内的装卸过程可分解为单卸船作业、混合装卸作业以及单装船作业三个阶段。船舶既定贝位的积载、配载状态及各阶段岸桥、集卡等设备配置状况已知，以岸桥装卸总次数及堆场翻箱次数最小为岸桥装卸作业序列问题优化目标，综合考虑舱盖板对装卸顺序的影响，确定船舶贝位内集装箱装、卸顺序；基于优化的装卸顺序，以岸桥最大完工时间最小化和集卡总等待时间最小化为目标完成集卡任务分配与指派优化。

2 模型构建

结合生产实际，做出如下假设：

（1）基于严格配载模式，按照积、配载图装卸集装箱。

（2）只考虑40英尺集装箱，不考虑船舶稳定性等因素对船舶贝位内装卸作业顺序的影响。

（3）堆场资源充足，不存在堆场拥堵，集卡在堆场场桥下无排队。

（4）岸桥、场桥不存在带箱等待集卡，集卡完全就位后，岸桥、场桥开始装、卸箱起吊。

2.1 集合

TS为船舶贝位内装卸集装箱集合，TS=TSI∪TSO，其中TSI表示卸载集装箱集合，TSO表示装载集装箱集合；TSf为船舶贝位作业阶段f卸载、装载集装箱的集合，f=1，2，3，TS=TS1∪TS2∪TS3；Kf为船舶贝位作业阶段f配备集卡的集合；R为舱口集合；S为船舶贝位内需装卸所有列的集合，S=Sr，uI∪Sr，uO∪Sr，dI∪Sr，dO，其中Sr，uI表示舱口r舱盖板上需要卸载的列集合；Sr，uO为舱口r舱盖板上需要装载的列集合；Sr，dO为舱口r舱盖板下需要装载的列集合；Sr，dI为舱口r舱盖板下需要卸载的列集合。

2.2 参数

相关参数及含义如表1所示。

表1 参数设定Tab.1 Parameter setting

2.3 决策变量

uij为0-1 变量，当集装箱i和j属于船舶同一贝位，j是i的紧后工序任务，且i和j可由岸桥同步作业时，uij为1，否则为0。zij为0-1 变量，当集装箱i和j由同一台岸桥装卸，且j是i的后序任务时为1，否则为0；xik为0-1 变量，当集装箱i由集卡k搬运时为1，否则为0；yijk为0-1 变量，当集卡k搬运完集装箱i后立即搬运集装箱j时为1，否则为0。

2.4 多目标优化模型

目标函数：

约束：

目标函数式（1）表示最小化岸桥装卸总次数和堆场翻箱次数，目标函数式（2）表示最小化岸桥最大完工时间，目标函数式（3）表示最小化集卡总等待时间；约束式（4）～（7）限制任意一个集装箱在岸桥或集卡的前序和后序作业；式（8）表示任意一个集装箱只由一个集卡搬运；式（9）～（13）根据集装箱在船舶贝位上的空间位置限制其装卸顺序；式（14）表示任意作业任务在岸桥处的开始时间受当前岸桥前序任务的结束时间影响；式（15）～（17）表示任意作业任务在岸桥处的开始时间受当前集卡前序任务结束时间的影响；式（18）～（20）表示任意任务在集卡上的实际开始时间与当前集卡前序任务的结束时间以及岸桥作业完成时间的关系；式（21）～（24）更新当前任务在集卡上的预计作业开始时间；式（25）计算集卡总等待时间。

3 求解算法设计

设计两阶段求解算法，算法流程如图2 所示，其中扰动参数tur计数，TUR为给定扰动阈值。

图2 IGA-INSGA-II算法流程Fig.2 Flowchart of IGA-INSGA-II Algorithm

利用IGA求解同贝同步装卸模式下集装箱岸桥装卸作业序列，其中IGA主要改进包括：设计空间约束算子及种群扰动，空间约束算子与罚函数结合，保证所有解满足舱盖板空间约束、列内上下箱位及同一箱位装卸箱空间约束等，设计种群扰动策略促进种群进化，有效避免陷入局部最优解；设计INSGA-II求解集卡任务分配与指派问题，INSGA-II主要改进包括：根据贝位作业阶段和集卡数量配置约束，设计分段式编码，设计基于岸桥最早可作业时间优先的解码策略等有效减少计算复杂度。

3.1 IGA设计

基于船舶贝位内集装箱装卸顺序空间约束设计空间约束算子，约束算子与罚函数配合，保证所有解均为可行解，设计扰动策略避免算法陷入局部最优。

3.1.1 编码及解码

图3 染色体编码示意图Fig.3 Chromosome coding diagram

基因表示装卸列编号，一条染色体为一个装卸船顺序方案。根据船舶贝位积载图和配载图，划分舱内外并分别统计既定贝位需要装卸的集装箱列的数量，以最大卸船列数量为界限，卸船列用小于该界限值的整数依次编号，装船列用大于该值的整数进行编号，利用贪婪准则初始化种群，使每个列的卸载编号排列在装载编号之前；解码时，根据船舶积载图和配载图信息，以及船舶舱位先卸后装、卸船列从上至下进行卸船作业、装船列从下至上进行装船作业等生产启发信息，交叉读取卸载列和装载列对应的集装箱，得到集装箱作业序列。

3.1.2 罚函数的构建

为保证算法迭代过程中同列集装箱先卸后装，设计惩罚项σP(x)，其中σ为惩罚因子，取很大的正数；P(x)是染色体x的函数，当遍历整条染色体过程中出现同列先装后卸的排列状态时，P(x)加1；F1(x)为目标函数，利用式（26）计算染色体适应度值，即

3.1.3 交叉重组与变异算子

采用顺序交叉算子完成交叉操作。在染色体上的随机生成三个位置，将染色体划分为四段，交换中间两个片段，完成染色体变异操作。

一个股票有没有机构在活动？有没有新资金介入？这些问题应该怎么看？笔者下面介绍一下自己的方法和步骤，分为“动态看盘”和“静态看盘”两种。

3.1.4 空间约束算子

针对集装箱列之间舱盖板上下空间约束，设计空间约束算子约束舱盖板上下集装箱列的装卸顺序，如图4所示。

图4 空间约束算子示意图Fig.4 Schematic diagram of reconstruction operator

（1）遍历染色体中某一舱位上下需要卸载的集装箱列，取出其基因编号和在染色体中的位置，按照升序对取出的基因位置进行排序，形成基因位置排序序列；

（2）将取出的基因按照舱盖板上方卸载列在前，下方卸载列在后的原则排序，形成基因序列；

（3）根据基因序列按照基因位置排序序列对原染色体对应位置的基因进行替换；

（4）根据上述步骤原理，按照舱盖板下集装箱列优先装载原则，对染色体中该舱位需要装载集装箱列的装载顺序进行约束；

（5）重复上述步骤直到染色体中所有舱位的装载顺序都满足约束。

3.1.5 扰动设计

为减少遗传算法陷入局部最优解，设计局部调整和部分初始化扰动策略。当种群进化过程中连续多代目标函数值未改进时，取出其中排序靠后的一半个体进行调整：

（1）利用贪婪策略对取出种群中前一半个体局部调整：当染色体中出现连续两个装船集装箱列基因时，取出后一个装船列对应的卸载编码并将其插入到两个连续装载列基因之间；

（2）采用半初始化策略［12］对取出种群中后一半染色体处理：利用随机生成染色体替换表现最差的染色体。

3.2 INSGA-II设计

基于岸桥最早可作业时间优先指派原则设计分段编码及解码方法，实现集卡水平搬运任务指派。

3.2.1 分段式编码

在已知集装箱装卸作业顺序的基础上，对整条船舶“多岸桥-多集卡”匹配同贝同步装卸，进行集卡任务指派方案优化。以配备2台岸桥同时开始，各装卸一个贝位为例。开始阶段，贝位内2台岸桥仅进行卸船作业，为单卸船阶段；任何一个贝位开始进行同步装卸即进入混合装卸阶段；最后为单装船阶段。已知单卸船阶段配备K1辆集卡，集卡编号分别为1、2、…、K1；混合装卸阶段、单装船阶段分别配备K2辆和K3辆集卡，且均可服务于2台岸桥。对不同作业阶段水平搬运任务进行分段式整数编码，基因表示执行该贝位搬运任务集卡的编号。贝位内配对同步装卸的两个集装箱应该由同一辆集卡搬运，为减少计算复杂度对配对的搬运任务进行标记并简化编码，如图5所示。

图5 分段式编码示意图Fig.5 Schematic diagram of segmented coding

3.2.2 基于岸桥最早可作业时间优先的解码方法

针对任务分配与指派问题，现有研究多采用两段式编码［13］或者多行矩阵式编码［14］，由于1辆集卡可协同服务于多台岸桥，本文设计的染色体编码对多台岸桥对应的所有搬运任务进行分配，不同岸桥作业任务之间没有优先级，基于岸桥最早可作业优先指派原则进行集卡任务指派，解码方案：

（1）初始化岸桥实际作业开始时间tai、集卡搬运计划开始时间ksi、集卡搬运实际开始时间kai，设定集卡位置参数；

（2）读取染色体中每台岸桥的集卡分配方案，比较所有岸桥当前任务最早可作业时间，若相同则随机选择一台岸桥，否则选择计划开始时间最早的岸桥，按照染色体分配的集卡执行其当前集装箱装卸任务，记录集卡作业顺序；

（3）根据式（14）～（24）更新当前集装箱装卸任务的岸桥实际开始作业时间、集卡实际开始作业时间、当前任务序列内后续任务的计划开始作业时间；

（4）根据最优染色体和任务执行顺序输出集卡的任务分配和指派方案。

3.2.3 遗传操作

采用精英策略和拥挤度比较算子进行个体选择，利用模拟二进制交叉算子进行染色体交叉，采用多项式变异算子进行染色体变异操作。

4 算例分析

4.1 算例及参数设定

（1）算例设计

装船顺序优化算例船舶贝位内包含3个舱盖板，小规模算例既定贝位需卸载34个集装箱，装载33个集装箱；大规模算例贝位内卸载130个集装箱，装载125个集装箱，相关积载、配载图及集装箱信息均已知。集卡调度算例，两台岸桥同时对2个贝位进行作业，设计装卸量为14个集装箱、22个集装箱、60个和118个集装箱4个不同规模算例，其中，装箱、卸箱、可同步装卸的集装箱等信息由上层装船顺序优化结果获取。

（2）参数设计

将式（26）中σ设为1 000；考虑堆场的翻箱次数权重系数ω取值范围为（ 0，1 ），取0 ～ 1之间的离散值进行实验，如图6所示。

图6 ω对目标函数的影响Fig.6 ω influence on objective function

结果表明，ω对目标函数值产生线性影响，不影响寻优方向。综合考虑翻箱次数相对于岸桥装卸的重要性，将ω设为0.5进行后续实验。

集卡任务调度算例，参考张笑菊［15］设置设备数量、装卸速度等相关参数，如表2所示。

表2 参数设定Tab.2 Parameter setting

4.2 结果分析

采用Python编程，实验在PC（Intel（R） Core（TM）i5-6200U CPU @ 2.30GHz 2.40 GHz内存8.00 GB）上进行。集装箱装卸作业顺序优化，基于算例对遗传算法（GA），粒子群算法（PSO）以及本文的改进遗传算法（IGA）进行测试，其中，IGA设定种群数量100，精英保存率0.1，交叉概率0.9，变异概率0.1，扰动阈值设为10；GA种群数量为200，其余参数相同，PSO种群数量200，个体最优值保存概率0.9，种群最优值保存概率0.9，迭代次数均为200代。集卡任务分配与指派算例中，算法参数均设置为种群数500，交叉概率0.9，变异概率0.1，进化代数300代。各算法20次实验结果如表3及图7所示，算法收敛状态如图8所示。

表3 算法测试结果对比Tab.3 Comparison of algorithm test

图7 IGA、PSO、GA算法20次最优解对比Fig.7 Comparison of 20 times results of each algorithm

图8 IGA、GA、PSO算法收敛对比Fig.8 Comparison of convergence of different algorithms

（1）集装箱装卸作业顺序结果分析

通过上述2个算例对比可知，本文改进的遗传算法跳出局部最优解及寻优的能力具有明显优势，较常规遗传算法及粒子群算法，运行20次平均结果分别提升约8.51%、13.47%；计算用时较GA有较大幅度减少，较PSO有所增加，且计算时间控制在3min以内。实验结果表明，本文改进遗传算法能有效求解同贝同步装卸作业模式下岸桥作业序列优化问题。

（2）集卡任务分配与指派结果分析

将本文INSGA-II与两段式编码的NSGA-II及参考向量引导多目标优化进化算法（Reference Vector Guided Evolutionary Algorithm，RVEA）对比，求解结果如表4及图9所示。

表4 集卡调度优化求解结果Tab.4 solution of truck dispatching

图9 不同规模算例帕累托前沿解对比Fig.9 Comparison of Pareto front of different scale examples

其中，表4 中平均决策时间为连续运行20 次的平均计算时间，每个案例选择三个帕累托前沿解对应的方案，方案1、方案2 和方案3 的函数值如表4。结果显示，INSGA-II 较两段式编码NSGA-II 及RVEA，岸桥最大完工时间及集卡总等待时间减少明显。表明，采用改进编码解码策略以及岸桥最早可作业时间优先指派策略，解分布比较均匀，不同规模算例优化方案具有优势。

5 结语

本文针对集装箱码头同贝同步装卸作业模式下，船舶贝位内集装箱岸桥装卸作业序列决策优化与集卡联合调度问题，综合考虑舱盖板约束以及堆场翻箱等因素，构建包含岸桥装卸总次数最小化、总作业时间最小化、集卡总等待时间最小化为目标的数学模型。鉴于问题的NP 难特性，设计两阶段IGA-INSGA-II求解算法，利用IGA求解岸桥装卸作业序列决策问题，通过设计空间约束算子和种群扰动策略有效增强IGA 寻优与跳出局部最优解的能力，利用INSGA-II 求解集卡的任务分配与指派问题，通过改进编码与指派策略有效提升了算法的寻优能力，实验验证了算法和模型的有效性。下一步研究将考虑不同箱型同贝同步装卸顺序优化、不确定因素下岸桥和集卡联合调度及优化方案韧性研究。

作者贡献声明：

张艳伟：确定研究方向，指导模型构建，撰写文稿；

谭永庆：构建模型并编程求解，撰写文稿；

莫满华、王楠：文献查阅、文稿修改。