穿越式自动化轨道吊任务分配与作业序列联合优化

杨小明，徐子奇，张梦天，舒 帆

(1.上海海事大学 离岸工程研究院，上海 201306；2.上海海事大学 物流工程学院，上海 201306)

0 引言

随着吞吐量的增加与船舶大型化的发展，集装箱港口对集装箱装卸系统装卸能力的要求越来越高。对于自动化集装箱码头，通常岸边桥式起重机(岸桥)的数量不变，码头岸线的吞吐能力主要取决于支持岸桥作业的水平运输和箱区装卸系统。水平运输能力可以通过增加运输设备来快速提高，然而承担集装箱装卸、翻捣和堆存多重任务的自动化集装箱码头箱区装卸系统却难以通过简单增加设备来提升能力，必须采用先进的管理手段提高效率。因此，优化自动化集装箱码头箱区自动化轨道吊(Automated Rail Mounted Gantry crane, ARMG)作业调度，对提高码头的整体运作效率和提升港口的竞争力具有十分重要的意义。另一方面，随着自动化技术的发展，近年来自动化集装箱码头得到空前发展，据统计2010年～2015年期间，全球新增自动化集装箱码头的数量超过30个，为2010年前建造自动化码头数量的2倍以上[1]，我国厦门远海、青岛前湾、上海洋山四期自动化集装箱码头也在近年先后投入运营，同时大量传统人工码头的自动化改造，尤其是堆场自动化改造成为当前主要发展方向。因此，自动化集装箱码头箱区ARMG作业调度问题成为港口作业智能化研究领域中的重点。

为适应港口智能化发展、提高码头堆场的作业效率，国内外学者在集装箱码头堆场龙门吊(场桥)调度问题上进行了大量研究。在传统人工集装箱码头中，场桥可以在不同箱区之间转移，场桥调度需要解决的核心问题是保证其在整个码头堆场转运作业过程中的作业时间延迟最小[2-4]、作业成本最小[5-6]、大车移动距离最小[7-8]等目标，这类问题研究更多偏向粗略作业计划，难以实现自动化集装箱码头箱区ARMG的精准协同作业。实际上绝大部分自动化集装箱码头中，箱区配置两台ARMG，通过两台ARMG相互交接协作完成集装箱进出箱区作业，这种装卸工艺使得自动化集装箱码头作业组织更加复杂，箱区装卸效率低[9]。通常自动化集装箱码头箱区中双ARMG系统分为可穿越和不可穿越两种组合方式，可穿越式双ARMG作业范围覆盖整个箱区，不可穿越式双ARMG相互间不能交叉行走，各自负责岸侧和海侧装卸作业。

在不可穿越双ARMG调度研究方面，Ng等[10-12]研究了给定作业时间约束下双ARMG的调度问题，目标是尽量减少工作等待时间的总和，并提出分支定界算法、基于动态编程的启发式算法求解该类问题，然而模型仅考虑序列优化问题；Gharehgozli等[13-14]考虑场桥间可能存在的干扰、作业时的安全间隔和任务之间的作业顺序等约束，优化两个场桥的作业次序和堆存策略，建立了带优先约束的非对称广义多旅行商问题模型，但是对不可穿越双ARMG同样未考虑任务分配问题；吕家智[15]、韩晓龙等[16]、魏晨等[17]都将作业总完成时间作为最小化优化目标，构建了双场桥调度混合整数规划模型，不同的是问题约束以及模型求解方法；梁承姬等[18-19]在堆场混堆模式下，以最小化作业完成时间和存取箱作业时间延迟量为目标，考虑场桥间的安全距离和作业干扰等约束，建立了混合整数规划模型；裴磊磊等[20]以双ARMG总作业时间最短和行驶距离之差最小为目标建立混合整数规划模型，并采用遗传算法与仿真相结合的方法进行求解。

与不可穿越双ARMG系统区别最大的是，可穿越双ARMG系统的双ARMG工作范围虽然可以覆盖全场，但是ARMG作业仍然存在干涉。在可穿越双ARMG系统调度问题上，Cao等[21]基于可穿越式双ARMG出场箱的操作策略建立了整数规划模型，并设计了贪婪启发式算法、模拟退火算法和组合启发式算法来解决问题；冯媛君[22]以最小化任务完工时间为目标构建了可穿越式双ARMG的调度优化模型，分析了作业过程中可能出现的干涉，实验结果表明模型能有效避免作业过程中场桥间的干涉并平衡两场桥的任务；Vis等[23-25]以完工时间最小为目标建立连续时间模型调度可穿越式双ARMG，设计了基于模拟退火的启发式算法求解该模型，并提出一种单排优化方法计算模型的下界值；Stahlbock等[26]研究了可穿越式双ARMG提高集装箱码头效率的程度，以汉堡的CTA码头为实例，用不同在线算法从多个角度评估了这些算法的表现；Speer等[27]给出一种新的调度方法，以任务的延误时间、双ARMG的完工时间、任务的作业时间三者加权之和为目标，设计了分支定界算法求解该问题；周静娴等[28]考虑到可穿越式双ARMG在同一倍位作业时会发生冲突，构建了多目标混合整数规划模型来最小化完工时间和ARMG空载时间，并与单ARMG调度的效率进行了对比；Briskorn等[29]也考虑ARMG作业时会存在干涉，以最小化完工时间为目标对ARMG调度进行优化，不过假定每台ARMG的作业次序已经确定。

综上所述，在港口自动化、智能化发展趋势下，双ARMG系统调度问题成为当前该领域的研究焦点，由于不可穿越式双ARMG系统存在诸多缺点[9]，可穿越式双ARMG系统、轨道梭车+双ARMG系统、可穿越式高架桁车系统等装卸工艺引发越来越多学者的研究兴趣。在自动化集装箱码头双ARMG系统调度方面，虽然现有研究取得了重要成果，但是大部分研究将箱区任务分配与ARMG作业顺序优化两个问题割裂开，而实际上这两个问题联系紧密，对其分开单独研究不能保证箱区整体作业效率最优。基于此，本文针对可穿越双ARMG系统中作业分配及作业次序联合优化问题建立数学规划模型，并采用改进的双层遗传算法对联合优化问题进行求解。其中外层算法求解箱区作业分配问题，内层算法实现外层分配方案下的ARMG作业顺序优化。最后通过算例实验论证所提改进双层遗传算法在求解可穿越双ARMG系统调度问题的优化效果和算法效率。

1 穿越式双ARMG系统调度问题描述

主流自动化集装箱码头箱区通常垂直于岸线布局，集装箱堆放与岸线呈90o；海侧船舶与箱区之间通过自动导引小车(Automated Guided Vehicle, AGV)或跨运车完成集装箱水平运输；箱区内通过ARMG完成集装箱装卸、堆存、翻捣等作业。典型的配置双穿越式ARMG的自动化集装箱码头箱区平面布局如图1所示(德国汉堡的Altenwerder集装箱码头[26])，图中①为海侧AGV装卸区，②为集装箱堆存箱位，③为外层母ARMG，④为可穿越子ARMG，⑤为外集卡装卸区。进口集装箱通过AGV运送至①后由任意ARMG卸箱至箱区堆存，等待提箱外集卡到达⑤区域后，再由ARMG装车运走(如图1直线⑥)。出口箱作业过程与进口箱相反(如图1直线⑧)，中转箱则由AGV运送至①区并由ARMG卸箱到箱区堆存，等待二程船舶装船时再由ARMG装车至①区AGV转运到岸边装船(如图1曲线⑦)。在所有作业过程中，集装箱在箱区内装卸通常不是一次装卸到位，需要通过ARMG几次翻捣装卸才能完成集装箱进出堆场作业，在该作业过程中，可穿越式ARMG(如图2)最大的特点是相互之间可穿越行驶，但是不能在相同区域同时作业，而且当外层母ARMG装卸作业时，内层子ARMG不能穿越。

可穿越式双ARMG任务分配与作业序列联合优化问题可以描述为：在箱区一个作业批次中有N个任务待执行，这N个任务可同时包括集港(出口箱进场)、装箱(出口箱出场)、卸船(进口箱进场)、提箱(进口箱出场)、捣箱(箱区内移箱)等作业类型，而且每个任务的起始位置和目标位置均已知。现堆场中有2台可穿越ARMG同时作业，需要将N个任务分配给这2台ARMG并规划每台ARMG的作业次序。假设ARMG从初始位置出发执行列表中的作业任务，完成最后一个任务的时刻为工作完成时间，最后一台ARMG的工作完成时间即为整个作业批次的总完成时间。任何一个作业任务执行时间包括ARMG行走时间、等待时间和装卸时间，其中行走时间包括从ARMG当前位置到目标集装箱初始提箱位置的行走时间，以及提取集装箱后载箱行驶至该任务目标卸箱位置时间；装卸时间包括在集装箱初始位置抓取集装箱时间，以及在集装箱目标位置卸下集装箱的操作时间。对于穿越式双ARMG，母ARMG装卸作业时，子ARMG不可穿越，另外在对同一倍位的集装箱进行装卸作业时可能会发生冲突，此时先到达的ARMG先执行任务操作，另一台ARMG停止等待。该问题优化的目标是在满足约束条件的前提下使该批次任务的总完成时间最短。另外，针对该问题还有一些常规的假设，例如集装箱均为20英尺标准箱；ARMG在目标位置的提箱和卸箱操作时间采用平均值，与集装箱所处的位置无关；忽略人为和自然因素的影响等。

2 可穿越双ARMG任务分配与作业序列联合优化模型构建

2.1 符号定义

可穿越双ARMG任务分配与作业序列联合优化数学模型中所涉及的所有符号定义如表1所示。

表1 符号定义

2.2 优化模型的构建

可穿越双ARMG系统任务分配与作业序列优化模型，以任务总完成时间最小化为目标，考虑可穿越双ARMG在作业过程中存在的干涉约束、任务执行过程时序约束等，其数学优化模型如下：

minF=T。

(1)

s.t.

yki=0,1，∀i∈S,∀k∈{A,B}；

(2)

(3)

(4)

(5)

(6)

(7)

∀i,j∈S,i≠j,∀k∈{A,B}；

(8)

∀i,j∈S,i≠j,∀k∈{A,B}；

(9)

∀i,j∈E,i≠j,∀k∈{A,B}；

(10)

∀i,j∈S,i≠j,∀k∈{A,B}；

(11)

∀i,j∈S,i≠j,∀k∈{A,B}；

(12)

(13)

i≠j,∀k,k′∈{A,B},k≠k′；

(14)

i≠j,∀k,k′∈{A,B},k≠k′；

(15)

∀k,k′∈{A,B},k≠k′；

(16)

∀k,k′∈{A,B},k≠k′；

(17)

(18)

3 改进双层遗传算法设计

自动化箱区中双ARMG任务分配与作业序列优化有很强的关联性，每一个任务分配方案对应一种特殊的作业序列要求；同时，受时序约束和作业干涉约束的影响，由双ARMG作业序列细微变化而导致的连锁反应会对目标函数产生深远影响。实际上，每一个任务分配方案对应该方案下的一个作业序列优化问题，简单通过双层编码方式[30-31]难以有效求解该问题，因此本文设计双层遗传算法进行求解。虽然双层遗传算法运算时间较长，但是相对于批次作业时间比例很小，适用于求解该问题。

3.1 算法整体流程

双ARMG任务分配与作业序列联合优化双遗传算法整体流程如图3所示。外层算法用于求解双ARMG任务分配问题，内层算法用于求解该分配方案下的双ARMG作业序列优化问题，内层算法整体上可以认为是外层算法中的目标函数求解过程。算法最主要的改进为，在内层算法中根据本文求解问题的特点设计的基于贪婪策略和随机策略的混合策略(用于种群初始化)，以及求解目标函数值时使用的双ARMG时空状态规划方法。

3.2 内外层算法遗传操作

(1)染色体编码与解码

1)外层算法 求解双ARMG任务分配问题。将双ARMG分别命名YCA(Yard Crane A)和YCB(Yard Crane B)，其中YCA为母ARMG，YCB为子ARMG。染色体编码通过0，1两个数字编码，0表示将任务分配给YCA，1表示将任务分配给YCB，基因顺序号表示任务号。如图4所示，编码011001表示将1，4，5号任务分配给YCA，2，3，6号任务分配给YCB。

2)内层算法 求解双ARMG作业序列优化问题。染色体编码时，基因使用任务号编码，基因顺序大小表示作业的先后顺序。如图5所示，假设365241染色体为对应上述011001外层染色体而生成的内层作业序列染色体，该方案下YCA被分配的任务号为145，各任务分别对应的内层染色体基因顺序号为653，根据基因顺序号从小到大排序，翻译为YCA的实际作业序列5→4→1,5号任务顺序号最小，第一个执行，4号任务次之，1号任务顺序号最大，最后执行。同理，YCB被分配任务236，对应的顺序号为412，根据基因顺序号从小到大排序，翻译为YCB的实际作业序列3→6→2。

(2)遗传算子操作

1)交叉算子 本文采用中间重组的交叉方法，根据事先定义的交叉概率将两条父代染色体中间部位的基因片段交叉互换。由于内层染色体的任务号和任务顺序号之间存在一一对应关系，交叉操作后还需要找出新生成的两条染色体中多余和重复的基因，用缺少的基因依次替换每条染色体上多余的基因，以保证任务号和顺序号之间的对应该系。

2)变异算子 变异算子根据事先设定的变异概率判断是否对该个体进行变异，是则对该个体随机选择变异位进行变异。本文采用交换变异的方法选取待变异染色体任意两个位置上的基因，对调这两个基因的顺序完成变异，该操作适用于内外层染色体。

3.3 基于混合策略种群初始化

由于双层遗传算法同时求解双ARMG任务分配与作业序列优化，需要使用内层算法求解外层的每一个可行解(任务分配方案)，以得到外层可行解的目标函数，因此算法计算量大。为使内层算法加速收敛，提高其求解速度，在种群初始化时使用贪婪策略与随机策略组合的混合策略，贪婪策略能使算法在较高起点开始进化，随机策略可以保证算法的随机性，避免早熟。

内层算法初始化使用贪婪策略时，双ARMG根据最近原则依次确定任务的作业顺序。以3.2节YCA被分配任务号145、YCB被分配任务号236为例，假设各项任务作业的起始位置和目标位置如表2所示，YCA的初始位置在12倍，YCB的初始位置在36倍。使用贪婪策略生成内层算法初始解时，YCA优先选择作业起始位置最近的1号任务，完成1号任务后将其坐标位置变为30倍，因此1号任务结束后选择起始位置离30倍更近的5号任务，最后执行4号任务。同理，使用贪婪策略的YCB任务序列为2→3→6。在使用混合策略生成内层算法初始种群时，可以设定一定比例数量的种群使用贪婪策略，另外一部分种群使用随机策略。

表2 小型算例

3.4 双ARMG时空状态规划

当内层算法生成双ARMG作业序列时，可以通过双ARMG时空状态规划计算可行解目标函数。双ARMG虽然可以相互穿越，但是仍然存在两种干涉约束：①同一时段二者不能在同一倍位进行装卸作业；②当母ARMG装卸作业时，子ARMG不能穿越。由于直接规划双ARMG时空状态比较困难，本文提出两阶段双ARMG时空状态规划方法。第一阶段，不考虑双ARMG作业冲突，直接根据双ARMG作业序列和其他已知条件计算双ARMG时空状态的推进过程，得到松弛条件下(不考虑干涉)双ARMG时空状态表；第二阶段，在松弛条件下时空状态表的基础上检测干涉情况，并调整时空状态表，直到消除所有干涉情况后得到满足所有约束条件的双ARMG时空状态表。

表3 松弛条件下的ARMG时空状态

第二阶段，在松弛条件下的时空状态表中，针对两类潜在干涉情形进行检测和调整。第一类潜在干涉和调整是针对母ARMG和子ARMG不能同时在相同位置进行装卸操作的约束，调整情形如图6所示。如果未调整，则场桥1和场桥2会在位置18处发生同时装卸作业事件，因此后到场桥1需要等待先到场桥2完成该项操作后再进入倍位18进行装卸作业。第二类潜在干涉和调整是针对母ARMG进行作业时子ARMG不能穿越的约束，调整情形如图7所示，若未经调整，则场桥1(母ARMG)在装卸作业时场桥2(子ARMG)将会穿越场桥1，调整后场桥2将等待场桥1完成装卸作业后再穿越。

第二阶段干涉检查和调整算法伪代码如下所示。其中：LastBay表示上次倍位，ThisBay表示本次倍位，STime表示任务开始时刻，RTime表示到达时刻，PTime表示操作时刻，ETime表示操作完成时刻,SafeTime表示走过安全距离所需的时间。

表3按PTime列升序排序

For i=2;i≤最大行;i++:

//第一类干涉检测与调整

If(时段[PTime(i),ETime(i)]与时段[PTime(i-1)-SafeTime,ETime(i-1)+SafeTime]重叠且ThisBay(i)=ThisBay(i-1)):

Δt=ETime(i-1)+SafeTime-PTime(i)；

For j=I;j≤最大行;j++:

If(场桥(j)=场桥(i)):STime(j),RTime(j),PTime(j),ETime(j)都增加Δt。

//第二类干涉检测与调整(场桥A为母ARMG)

If(场桥(i)='A'):

//检测i-1行状态并调整

If(场桥(i-1)='B'且时段[STime(i-1),RTime(i-1)]与时段[PTime(i)-SafeTime,ETime(i)+SafeTime]重叠且i-1行倍位与i行倍位存在穿越关系)：

Δt=ETime(i)+SafeTime-PTime(i-1)；

For j=i-1,j≤最大行，j++:

If(场桥(j)=场桥(i-1))：STime(j),RTime(j),PTime(j),ETime(j)都增加Δt。

//检测i+1行状态并调整

与i-1行检测与调整方法相同

4 实验设计与结果分析

本文实验以自动化集装箱码头常规配置方案进行参数设置，实验中的各项参数如下：倍位间距ds=6.5 m，ARMG抓取集装箱时间po=25 s，ARMG放落集装箱时间pd=30 s，ARMG大车移动速度V=4 m/s。本文所有算例基于Intel Xeon(R)E5520 CPU@2.25 GHz，4 GB内存的Window10系统运行。

4.1 典型算例分析

首先通过一个任务规模为20、箱区长度为48倍的典型算例，分析改进双层遗传算法的收敛过程和计算结果。算例所有任务的起始提箱倍位、目标落箱倍位如表4所示。

表4 典型算例输入任务列表

续表4

该算例中，设置内外层算法选择概率均为0.6，变异概率为0.05，内层算法初始种群生成策略随机生成概率为0.9，贪婪策略生成概率为0.1；外层算法的最大迭代次数为500代，内层算法连续10代最佳目标函数不变为收敛判别条件。经过500代运算后得到的最佳目标函数收敛过程如图8所示。

由图8可见，20项作业任务完成时间从初代934.875 s快速下降，在第14代下降为891.25 s，最终在第108代收敛到888 s，可见算法具有较好的收敛性。最终得到的双ARMG任务分配、作业序列和最终时空状态推进过程如表5所示。

表5 最优解中的ARMG时空状态

续表5

表中外层母ARMG(YCA)被分配10项任务，任务序列为4，3，5，10，15，2，16，8，12，9，完成时间888 s；子ARMG(YCB)被分配10项任务，任务序列为13，11，17，14，1，19，7，6，20，18，完成时间为883.13 s。将表5双ARMG时空状态推进过程转化为图9双ARMG时空状态图。从图9可见，双ARMG作业过程不存在相同位置同时作业的情况，也不存在子ARMG(YCB)在母ARMG(YCA)装卸作业时穿越的情况，但允许外层YCA在YCB装卸作业时穿越。可见，该算例的最优解满足双ARMG作业过程干涉约束，同时双ARMG作业过程也满足时序约束。

4.2 灵敏度分析

改进双层遗传算法对算法性能影响的参数主要有内外层算法选择与变异概率、内外层算法收敛条件、内层算法初始化种群生成中贪婪策略与随机策略的生成比例。由于参数众多，通过逐步确定方式进行参数选择来分析这些参数对算法性能的影响。

(1)实验一——内层算法收敛条件

经过预先算例实验分析发现，内层算法收敛条件对算法运算时间和优化效果影响较大，因此优先确定内层算法收敛条件。先假设内外层算法的选择、变异概率分别为0.6和0.05，外层算法收敛条件为连续30代不变；内层算法种群初始化时的随机策略概率为0.9，收敛条件分别设置为连续10，20，30，40代不变，结合表4算例对内层算法收敛条件进行实验，每组运算10次求得的最终目标函数和CPU消耗时间均值如图10所示。

由图10可见，内层算法收敛条件逐步提高，CPU消耗时间显著增加，但目标函数下降缓慢。因此，从算法效率优先角度考虑内层算法收敛条件选择连续10代不变，此时平均CPU时间为117.97 s，相对于批次任务完成时间在可接受范围内。

(2)实验二——内层算法初始化随机策略比例

在实验一基础上固定内层算法收敛条件为连续10代不变，内层算法种群初始化时的随机策略概率为0.1～0.9，分别设置9组实验，每组实验运行10次，得到最终目标函数和CPU消耗时间均值如图11所示。

由图11可见，内层算法初始化时随机策略概率从0.1～0.9，最佳目标函数先逐渐下降，在0.6时达到最小然后逐渐上升，CPU运算时间无明显变化，因此内层算法初始化时选择随机策略概率为0.6，对应的贪婪策略生成概率为0.4。

(3)实验三——外层算法收敛条件

在实验二基础上，进一步固定内层初始化随机策略概率为0.6，外层算法收敛条件分别设置为连续10，20，30，40，50代不变，每组实验运行10次，得到目标函数和CPU消耗时间均值如图12所示。

由图12可见，外层算法收敛条件逐步提高时，CPU消耗时间显著增加，但目标函数下降缓慢。当外层算法收敛条件为连续30代不变时，CPU消耗时间增速加快，最佳目标函数减速降低，此时CPU时间均值为137 s，相对于批次任务完成时间在可接受范围内，因此选择外层算法收敛条件为连续30代不变。

(4)实验四——交叉、变异概率

在实验三基础上，固定外层算法收敛条件为连续30代不变，内层算法交叉概率设为[0.4,0.5,0.6]，变异概率设为[0.04,0.05,0.06],每组实验运行10次，得到目标函数和CPU消耗时间均值如表6所示。

表6 内层算法交叉率与变异率分析

续表6

由表6可见，内层算法交叉概率不变时，变异概率变化对CPU耗时基本没有影响，但是3组实验中变异概率为0.05时，目标函数值在同组实验中均较小，因此变异概率选择0.05。对相同交叉概率实验结果求均值，发现随着内层算法交叉概率的提高，CPU耗时提升得比较明显，当交叉概率从0.4提升到0.5和0.6时，目标函数值下降明显且较为稳定，因此内层算法选择交叉概率为0.5，变异概率为0.05。

固定内层算法的交叉概率和变异概率，外层算法的交叉概率分别设置为[0.4,0.5,0.6]，变异概率分别设置为[0.04,0.05,0.06],每组实验运行10次，得到目标函数和CPU消耗时间均值如表7所示。

表7 外层算法交叉率与变异率分析

由表7可见，外层算法变异概率对目标函数和CPU耗时均无明显影响，当变异概率为0.04时,总体上目标函数值较小，因此选择外层变异概率为0.04.对相同交叉概率实验结果求均值，发现随着外层算法交叉概率的提高，CPU耗时提升得比较明显，目标函数值略微上升，因此选择交叉概率为0.4。

4.3 算法性能分析

根据4.2节参数灵敏度分析结果，外层算法的交叉概率为0.4，变异概率为0.04，收敛条件连续30代不变；内层算法的交叉概率为0.5，变异概率为0.05，初始化随机策略概率为0.6，贪婪策略概率为0.4，收敛条件连续10代不变，根据不同箱区规模和任务规模设计15组实验，每组实验运行10次求均值，得到不同规模下的单任务平均完成时间，如图13所示。

由图13可见，不同规模下任务的平均完成时间基本在40 s～50 s之间。任务数量增加，任务的平均完成时间没有增加，可见算法优化效果不受任务数量的影响。箱区规模变化时，不同实验表现出不同的变化趋势，主要因为箱区倍位数增加会使任务运输距离增加，但不同算例下任务的起始取箱点和目标卸箱点之间的距离随机性较大，因此不同算例会有不同的表现。

图14所示为不同规模下的CPU平均耗时，可见随着任务规模的增加，CPU平均耗时呈现线性增长，算法CPU运算时间可控，相对于批次任务总体完成时间较小，适用于求解实际问题。

为分析双层遗传算法的优化效果，设计单层遗传算法，将任务分配与作业序列分层编码[30-31]。上层染色体使用“01”编码，0表示对应位置的任务分配给YCA，1表示对应位置的任务分配给YCB；下层染色体使用任务号编码，基因位置表示任务先后顺序，例如01011#53214，表示YCA任务序列为52，YCB任务序列为314。在遗传操作时，上下层染色体分别独立操作。遗传操作中采用轮盘赌选择策略，交叉变异操作同双层遗传算法中的内外层染色体操作，并通过预先实验分析设置单层遗传算法的交叉率为0.8，变异率为0.05。单层遗传算法和双层遗传算法在不同规模实验中的性能表现如表8所示。由表8可见，单层遗传算法运算时间在0.6 s以内，相对于双层遗传算法存在较大优势，但是优化效果明显差于双层遗传算法，平均单任务完成时间比双层遗传算法增加30%左右。可见，双层遗传算法对作业时间敏感的双ARMG任务分配与作业序列联合优化问题具有良好的优化效果。

表8 单、双层遗传算法在不同规模实验中的性能(每组实验运行10次取均值)

5 结束语

本文针对自动化集装箱码头的可穿越式双ARMG任务分配与作业序列联合优化问题建立数学优化模型，以双ARMG完成任务时间最小为目标，考虑了双ARMG作业过程时序约束和相互干涉约束等，设计了改进的双层遗传算法求解该问题，其中外层算法求解任务分配问题，内层算法求解作业序列优化问题。另外，本文在内层算法初始种群生成过程中引入包含随机策略和贪婪策略的混合生成策略，贪婪策略可生成较为合理的初始解集，随机策略用于扩大算搜索空间，以避免算法早熟。

实验分析表明，本文提出的改进双层遗传算法可以有效求解可穿越式双ARMG任务分配分配和序列优化问题，与传统的将两个问题分开求解方法相比有一定的优势。然而双层遗传算法也存在运算量较大的不足，外层算法中计算每个个体目标函数都需要完整运行一次内层遗传算法，当任务规模增加时计算量呈线性增长，影响了算法的效率，未来的研究可考虑在提高算法优化效果同时，一步提高算法效率。另一方面，自动化集装箱码头双ARMG箱区系统作业与水平运输系统协同作业对于提升自动化集装箱码头整体装卸效率具有重要意义，这也将是下一步研究工作的重点。