面向集装箱装船排箱优化调度问题的交互感知狼群算法

2021-09-17潘星宇邹雨澄肖人彬林瑞忞董泊远

南昌工程学院学报 2021年4期

潘星宇，邹雨澄，肖人彬，林瑞忞，董泊远

(华中科技大学 1.人工智能与自动化学院，2.生命科学与技术学院，3.计算机科学与技术学院，湖北武汉 430074)

近年来，随着海上运输的不断发展。港口自动化已成为普遍趋势。截至目前，全世界已有 30 多个自动化码头在多个国家实现应用并投入实际生产，取得了良好的运营效果。自动化码头的出现与深入发展已成为今后港口持续发展的重大变革[1]。船舶到港装卸集装箱作业是港口日常生产活动过程中的关键组成部分，集装箱港口的整体经济效益与集装箱船舶在港装卸作业质量紧密相关，而船舶装卸质量和效率又直接影响到船舶在港时间、港口船只停泊安排及海上航行安全等多个方面，进而影响港口声誉地位、收益与运营成本[2]。是否能进一步提高船舶装卸质量和效率来提高港口的竞争力是亟待解决的问题。

长期以来，面向集装箱装船排箱优化调度问题，国内外学者已从多方面已进行了许多研究。Boner和Brinati针对集装箱装船问题，首先以堆场翻箱量最小和岸桥移动距离最短为优化目标建立了0-1规划模型[3]。但由于模型0-1变量较多，使得问题在规模较大时求解困难，实用性不强。针对问题模型求解困难的问题，Avriel和Penn通过忽略船舶重量稳定性约束简化上述规划模型，优化目标同样设为堆场翻箱量最小，变量个数较之前有所减少[4]。Imai则以堆场翻箱量最小和船舶重量稳定性为优化目标，建立了多目标整数规划模型，并利用加权法得到问题模型的非劣解[5]。Kim率先提出了估算堆场翻箱量的一个简单方法，将其定义为基本倒箱量；并分析研究了堆场集装箱在船舶贝位中的分配、排布等问题，提出应兼顾考虑集装箱重量等级、目的港远近等因素[6-8]。

从算法角度，可以应用于排箱优化调度所采用的优化方法可分为两类。一类是精确算法，如动态规划算法[9]，这种类型的算法的的优势在于针对小规模的翻箱问题可以精确地得到全局最优解；但在问题规模逐步增加时，算法的时间复杂度会迅速膨胀，进而极大的影响求解效率。另一类是智能优化算法，如粒子群算法[10]、萤火虫算法[11]、聚类算法[12]、退火算法[13]、遗传算法[14]、基于规则的启发式算法[15]、与深度学习结合的群智能算法[16]等。由于其过程不完全可控，可能出现针对同一状态有不同结果，表现较为不稳定。

实践方面，由于多数研究并未考虑集装箱堆场作业中个体对象的差异性(分类、重量等因素)，而是将所有集装箱视为同一属性的单位，仅保留集装箱相对坐标及次序两个变量，如此虽然降低了建模难度，但也导致研究成果无法得到实际应用。

1 装船排箱优化调度模型构建

在集装箱码头的操作中，自动化龙门吊装卸工艺系统被广泛用作操作主体，并辅以码头内部运输系统和整体调度与指挥系统，该系统包括一系列相互关联的操作过程。为了优化集装箱码头的整体运营效率，不仅要考虑各个环节的各自优化，同时还需考虑船上作业和堆场作业等环节之间的相互制约。

本文讨论的船舶靠港集装箱码头装船作业主要可分为装载流程及卸载流程，该模式码头集装箱的装卸流程如图1所示。由于海路运输的特殊性，于起始港口装载的一批货物(装载流程)往往存在多个目的地港口(卸载流程)。装载流程包括：集装箱堆场作业、AGV自动引导车运输作业、岸桥装卸作业等。卸载流程则需要将以当前港口为目的地的货物卸载，其过程涉及到船舶内的翻箱。同时，在所有船上作业过程中，还需要考虑船体的重量平衡。

图1 流程示意图

参考文献[17-19]中的建模内容，在整个操作流程中，集装箱在堆场中的摆放形式和在船舱中的堆放形式如图2～3所示，集装箱沿船舶近岸一侧依次层层装载。如图2所示，堆场中集装箱按箱区规则码放，任一堆场中集装箱均可由唯一的8位编码表示其位置、重量及目标港信息。依照箱区、贝位、栈位、层位、重量、目标港信息组合而成。(例：10532144分为1/05/3/2/14/4表示为1箱区第5贝第3栈第2层的集装箱，其重量为14，目标港为4号港)一个编号唯一确定一个集装箱的位置等信息，这称为集装箱堆场的位置属性。如图3所示，集装箱按照装载顺序形成序列，序列编号唯一确定该集装箱在船舱中的贝位、列位及层位。综合利用集装箱在船坞上的位置属性和集装箱装载顺序的序列，可以得知任一集装箱装载后在船舱中的具体位置。同时，预设集装箱船中已预先装载了6层的集装箱，这些集装箱并未包含在此装运计划中。

图2 堆场示意图图3 船舱示意图

minT=∑i(Ri×(∑i′μii′+βij′×α))，

(1)

s.t.μii′+max(0，xi-xi′)>0，

(2)

(3)

为了减少在随后的港口装卸作业中额外的集装箱操作，提高船舶在港口装卸的效率以及减少船舶在港口停留的时间，集装箱在船中应尽量满足目标港口较远的在下，目标港较近的在上。如式(4)所示：

(4)

(5)

(6)

(7)

(8)

(9)

2 交互感知狼群算法求解装船排箱调度模型

2.1 基本狼群算法

狼群算法(Wolf Pack Algorithm，WPA)是一种由吴虎胜等提出的群智能算法[20]。受到狼群捕猎方式的启发，WPA的主要特征是以一头狼领导一众探狼在解空间内搜寻最优解，一旦探狼所处位置更优，则成为新任头狼，此后进行种群更新，其余探狼继续围绕当前头狼的位置进行新一次寻找，不停迭代直至狼群汇合，即搜索范围收敛至最优解后停止。与其他的群智能算法例如粒子群算法、萤火虫算法[21]不同，WPA是一种有分工的随机概率搜索算法，本质上是利用角色分工与交互更好的探索解空间，使其能够以较大的概率快速找到最优解；算法本身有着优秀的收敛性和良好的鲁棒性，其交互特点使得其尤其适合高维、多峰的复杂函数问题的求解。

由于其较好的全局搜索能力，WPA被广泛应用于智能电网[22]；血管阻塞水平评估[23]；与差分进化算法(Differential Evolution Algorithm，DEA)融合应用于卫星导航欺骗干扰识别[24]，相比单独使用具有更高的识别精度；在战斗火力规避计算上比传统算法更加精确[25]。同时也有对于算法本身结构进行调整的例子，如等级划分狼群算法(Hierarchic Wolf Algorithm，HWA)，采用双重编码形式，克服了只能用于求解连续问题的局限[26]；应用神经网络动态优化初始权值和阈值，能够明显提升收敛速度及精度[27-28]；改进步长因子[29-30]也有一定的增益；分布式狼群算法(Distributed Wolf Algorithm，DWA)可以解决三维传感器优化布置问题等[31]。

狼群算法主要包括初始狼群生成、探狼游走、头狼召唤、奔袭、围攻等行为、胜者为王的头狼角逐规则以及优胜劣汰的狼群更新规则[20]。

以求解函数最小值为例，简要叙述狼群算法的求解过程：

(1)种群初始化：在构建的解空间中随机或依照设定的规则生成狼群在解空间中的位置分布，依据每只狼所在位置对应的适应度函数的值选取出最优的一匹头狼。

(2)游走：狼群开始在解空间中进行设定步长的随机移动，若发现某可行解的适应度函数值小于移动前位置，则更新位置为当前位置，若此位置值也优于头狼，则也更新头狼。否则将继续进行随机移动直到达到设定的最大次数。之后由头狼发起召唤。

(3)奔袭：头狼召唤后每只探狼响应头狼召唤以较大步长向头狼奔袭(在解空间中向头狼位移)，若奔袭途中某探狼表现优于头狼，则更新头狼位置，奔袭过程停止。否则将继续。

(4)围攻：当探狼和头狼距离满足围攻要求后，进入围攻范围的探狼对进行较小步长的搜索，若过程中某探狼表现优于头狼，则更新头狼位置。然后进行下一步种群更新。

(5)狼群更新：按照预先设定的比例淘汰部分数值最差的人工狼(表现差的狼被自然选择淘汰)，之后在解空间中随机或按照规则生成新的人工狼补齐狼群数量，从而实现狼群的更新。

(6)终止判断：若没有达到预先设置的目标函数精度范围——数据在阈值范围内波动(或完全收敛至一特定值)，则从探狼游走开始重复迭代直到达到最大迭代次数为止。否则终止迭代，输出结果。

2.2 改进的交互感知狼群算法

狼群算法是一种较新的启发式算法，其特点在于狼群算法对于小步长的搜索非常准确。考虑在问题中解空间分布及其离散且不均匀的复杂性，且针对排箱问题中一两个箱子移动的次序的变化可能会影响后面许多箱子的位置的特点，小步长的搜索方式十分有效。再加上狼群算法的“猛狼奔袭”策略，赋予了WPA搜索精细度很高，但又不会轻易陷入局部最优解的特点。相对地，遗传算法、贪婪算法等非群智能算法的细节搜索能力远不如WPA。

然而，算法仍存在一些不足，需要进一步改进：

(1)探狼的游走行为的部分本质上是贪婪算法，所以会比较容易陷入到局部最优解之中，对整体空间探索不够充分。

(2)狼群算法前期收敛速度放缓较快，这是因为在搜索后期时搜索步长过大且判定执行围攻的判定距离过大，会反复越过最优解。

(3)在目标求解函数纬度较高时，狼群算法收敛缓慢，且计算时间大幅上升，这是因为计算维度过高会导致随机更新狼群和选取围攻方向时效率变低。

因此，提出以下一些基本狼群算法的改进方式。

2.2.1 改进奔袭环节

在基础狼群算法中，头狼召唤其他狼以较大的步长快速向头狼移动。在移动过程中所有狼的轨迹是线性的。仅有一头头狼作为目标会局限奔袭过程中探索的空间，因此容易陷入局部最优情况中。所以本算法提出由多头引领狼取代唯一头狼进行召唤。

此环节中，每头探狼会选择设置的多头引领狼中最有吸引力的一匹为奔袭的目标。吸引力定义如下：在自然界中狼群的交流依靠声音的传播，而其强度与传播距离的平方成反比。仿照声音传播规律，第i匹引领狼对某探狼WDj产生的吸引力attractij可表示为

(10)

其中f(Xi)为引领狼坐标对应的适应度值，di，j则代表引领狼到该探狼的欧式距离。

在基本狼群算法中，游走及奔袭步长固定，在一般情况的求解中会导致收敛速度较慢；为了加快求解过程的收敛速度，本文提出利用交互感知反馈的自适应步长方式。因为在奔袭过程中各个探狼WD会趋向不同引领狼WL进行分群奔袭，分别向其选定的目标引领狼WDi，j集中，其中i=arg(max(attractij))；此时将所有探狼标记为WDi，j，且有：

(11)

(12)

奔袭过后，每只探狼WDi，j会更多地带有其所选定引领狼WLi的特征；所以某引领狼WLi的信息可以在一定程度上表征一系列探狼WDi的状态。进而言之，所有引领狼的信息可以表征当前狼群的总体状态。

2.2.2 面向装船排箱问题的改进

在装船排箱问题中，依照上文提到的生成方式所生成的探狼序列与解空间搜索时初始化的随机位置有所不同，不能简单的依照搜索解空间时的交互方式。所以针对装船排箱问题中狼群的迭代提出以下几点调整。

设在m×n的解空间中n为狼群规模，m为变量数对应装船问题中的待装船集装箱数量。探狼wolfi定义为wolfi={xi1，xi2，…，xim}；wolfi对应问题中一个集装箱装船编码序列，其中xij为第i条可行装箱顺序编码的第j个编码位置的集装箱，另有xip≠xiq，p≠q，p，q，j∈{1，2，…，m}。

为了体现距离概念，本文定义了一种编码间的距离概念以便进行奔袭环节的距离判断。wolfi与wolfj的距离disij为每个箱子在两个编码序列中所在位置下标之差的绝对值之和。具体的，对于两只狼所代表的装箱编码序列wolfi与wolfj：

(13)

(1)狼群生成与更新环节

依次读取堆场建模yard中待装船箱的位置生成箱子编码序列box={box1，box2，…，boxm}，初始狼群生成与更新时wolfi是box的一个随机排序排列。

wolfi=random.permutation(box).

(14)

引领狼的选择与原始狼群算法中相同，根据每头狼的编码序列计算出适应度后选出最优的k头作为引领狼。

(2)游走环节

与在连续的解空间中可以进行的随机游走有所差别的是，装箱探狼编码中的每个值存在唯一性。故本文采用一种在随机栈中调换装船顺序的方法进行探狼的游走。

图4 IPWPA算法流程图

具体的，本游走方式是在探狼i的编码wolfi={xi1，xi2，…，xim}中随机挑选并交换一对编码xij与xik的位置并保证装船后两编码所在位置位于同一栈中。

(3)奔袭环节

wolfi根据式(10)以及上文定义的距离关系在引领狼中选定wolfj并判定disij>threshold_s后进行奔袭环节。

奔袭定义为对于wolfi及其目标奔袭头狼wolfj，交换k段编码序列装船后对应船上栈中序列。

(4)围攻环节

对于wolfi，通过距离判断disij

进行围攻时随机交换k次wolfi={xi1，xi2，…，xim}中一对编码xij与xik的位置，并保证xij与xik不在同一船上栈中。

利用IPWPA算法对集装箱装船排箱问题求解具体流程如下：

①模型初始化：根据预设的工况的具体情况初始化堆场yard，初始化船只状况ship；导入集装箱的重量、位置、目标港等参数及船舶舱内已装载的集装箱的信息。

②算法初始化：设定IPWPA算法的控制参数，包括狼群数量m，距离判定标准step等。随机初始化m个装船排序序列即探狼编码pwolf。然后，依照探狼位置pwolf和适应度计算公式计算适应度pfitness即总翻箱代价(见式(1))。全部探狼计算完毕后，选出k匹最优的狼作为引领狼。

③可行域约束：在迭代过程中，每次对狼所代表的序列进行操作变换与更新时，都需通过重量稳定性约束修正狼即装船排箱顺序序列，将每头狼所代表的序列限制在可行解区域内(见式(5)～(9))。

④迭代搜索：依照图4所示流程与上文中针对排箱问题的狼群交互方式进行迭代搜索。

3 结果及分析

模仿实际情况按照模型设计3种堆场翻箱工作情况S1～S3，各个情况下堆场集装箱堆存情况如表1所示。按照设计，堆场总有3个一样大小和堆叠形式的箱区，各个箱区贝位数量一致。每个贝位含有6个栈，每栈高度为4层，共24个空位但最多只堆放21个集装箱，即每贝最顶层有3个空位用于翻箱，如图2所示。堆场集装箱质量划分为20个等级，在1～20范围内随机取整数值；目的港在1～5范围内随机取整数值，且1代表最近的目的港，5代表最远的目的港。同时，各箱区内随机分布一些不在装船计划中的集装箱。

使用IPWPA与PSO[19]WPA[20]算法进行求解与比较，设置3种算法的种群数量均为100，迭代上限次数500进行实验。表2为IPWPA在3种堆场情况的5次实验中的最优结果。选用在每种工况下3算法的最优结果进行对比。结果如图5～7所示。

表1 堆场中集装箱堆存情况

表2 IPWPA实验结果

在最简单的情况S1种，如图5所示，在迭代开始时PSO算法与WPA算法均收敛速度显著快于IPWPA算法，但随着迭代增加，两对算法的算法收敛速度都有所放缓，未达到最优解，而IPWPA尽管起初收敛速度较慢但最终达到了最优解224。如图6所示，在S2情况中IPWPA也达到了最优解497，而PSO和WPA的结果都劣于IPWPA。

在最复杂的情况S3中，由图7可以看出WPA无论在收敛速度还是最终结果上均劣于IPWPA，PSO在开始迭代时下降速度略快于IPWPA，而在大约100次迭代之后PSO陷入局部最优解并最终停滞。IPWPA在约110次迭代后优于了PSO算法并在最终到达该工作情况下的最优值1 224.

综合来看，在较简单的工作情况下，尽管在迭代开始时，PSO与WPA在收敛性优于IPWPA算法，然而两种算法收敛会迅速放缓，PSO效果好于WPA但最终值均差于IPWPA算法。随着问题的复杂度不断增加，PSO算法在收敛速率上丧失了优势。WPA无论是在结果还是收敛速度上均差于改进算法。从最终结果来看，IPWPA在3个堆场工作情况下都优于PSO和WPA算法。表现了IPWPA算法在问题上的优越性。

在排箱问题中，存在大量的相似相近的局部最优点。IPWPA在交互策略上的改良使得其更好的避免了陷入局部最优解的情况。其优势在于通过自适应的步长调整可以更好的搜索解空间，而PSO多次陷了局部最优解中。