共享适应度粒子群在双机ETV中的应用

，

(中国民航大学 电子信息与自动化学院，天津 300300)

0 引言

升降式转运车(Elevating Transfer Vehicle，ETV)是机场货运区运输集装货物的转运工具。许多大型机场在立体仓库内配置了两台甚至更多的ETV同时作业。这些ETV运行在同一巷道内，不可避免的会出现碰撞。另外每个ETV通常拥有两个货位，立体仓库内有两排货架，每个货架有两个货位，这些情况都显著提升了调度过程的复杂度。所以研究双机双货位ETV控制系统对提高机场货运区转运效率和减少ETV磨损有着重要的意义。

近年来一些学者对双机ETV调度算法进行了研究。宋宇博[1]等分析航空货站AS/RS多端口出入库的作业方式具有并发性和分布性特点,调度过程具有高密度和高柔性的特点，提出了一种两阶段禁忌搜索算法，并研究了ETV防冲突避让算法，结果表明,此算法取得了良好的效果。季琼[2]等使用分配法对专家系统进行改进，建立了双ETV任务分配调度专家系统的知识库，提升了机场货运站的作业效率。YB[3]等使用带约束的优化模型分析双机ETV调度问题。以上方法均是基于任务集并结合ETV载物台的状态生成任务链，该过程建模复杂且不易实现。论文针对这个问题提出一种基于ETV载物台状态，结合下一任务属性生成任务链的算法。该算法较基于任务的模型结构更加清晰，编程简单易行。

标准粒子群算法易陷入局部最优，常见的优化算法采用调节权重、增加变异项等[4-6]。实验仿真发现，这些优化算法在处理双机ETV调度问题时虽然有一定的效果，但是跳出局部最优的能力依然较差且出现早熟现象。为了解决这个问题，引入共享适应度函数，改进了粒子群算法。

1 双机ETV复合调度建模和粒子群算法

ETV所在的立体仓库结构如图1所示。

图1 机场立体仓库结构示意图

图中看出立体仓库分为两排，每排有n层m列货位，ETV载物台有A、B两个货位。每个货位可装载一个10号集装器(Unit Load Device,ULD)，两个货位合并可装载一个20号集装器。为了描述方便，约定称10号集装器为小箱，称20号集装器为大箱，并且约定2、3号货位所在排为内侧货位，1、4号货位所在排为外侧货位。

机场货运区立体货架地址采用排-层-列的顺序编码。例如国内某机场拥有4排5层45列货架。为了计算方便，将三维编码按照公式(1)映射为一维编码。

s=5(x-1)+y+20(z-1)

(1)

式中，s为地址，x为排，y为层，z为列。例如第1排第一层第一列的地址编码为1，以此类推。

1.1 任务集和任务链分析

任务的合集称之为任务集，任务的属性包括出、入、倒、盘库等。每个出/入库任务选择最近的出/入口作为其目的/源地址，每个倒/盘库任务将下一个节点的地址作为其目的地址。每个任务映射为一个向量即C(i)=(srcadd(i),dstadd(i),size(i))，向量内元素依次为：源地址、目的地址、货物大小。

任务集内的任务按照一定的先后顺序组成一个任务序列，这些任务序列的源地址、目的地址首尾相连组成一个任务链。任务链节点是一个向量即L(i)=(add(i),dis(i))，向量内元素依次为：地址、x轴位移，其中任务链节点地址仅包含y、z两个方向，x轴位移根据每个任务的源/目的地址和货物大小综合计算。任务链描述的是ETV载物台在立体仓库内运动的轨迹。例如任务链两个相邻节点(add1,-1)、(add2,1)，描述的是ETV载物台在地址add1处获取第三排货位的ULD，然后运动到add2地址处向第三排卸载此ULD。

许多研究人员从任务的角度出发研究ETV的调度问题，分析复杂且易出错。从任务链的角度出发将调度问题简化为一个具有马尔科夫性的过程，即：任务链的下一个节点状态仅和当前任务状态及下一个任务有关，而和任务链之前的节点无关。另外基于任务链的模型仅计算每个节点x轴方向运行时间和相邻两节点运行时间即可计算出总的运行时间，较基于任务的模型结构更加清晰。任务链生成步骤如图2所示。

图2 生成任务链步骤

1.2 按照任务序列生成任务链

ETV载物台有两个货位，理论上可以同时载入两个小箱，但是如果两个小箱目的地址有竞争，ETV会产生死锁。解除死锁的方法主要有4种：①撤销全部有关任务；②依次撤销最后加入的任务，直到死锁消失；③强制剥夺陷入死锁进程的资源，直到死锁消失；④调用更多的资源分配给死锁进程。具体到ETV调度问题有两种策略避免死锁：①撤销最后一个任务；②寻找中转货位。文献[7]证明多数情况下采用中转货位策略花费时间长于撤销最后一个任务策略，为了减少ETV的磨损且减少运行时间,论文采用第二种ETV死锁避免策略生成任务链。

按照任务序列顺序，以ETV的两个载物台货位状态为条件并加入死锁避免策略，生成任务链。假设ETV载物台的两个货位用m1、m2表示，分以下几种情况：

1)m1、m2均为空。载入下一个任务。

①如果下一任务货物类型为内侧小箱，将任务信息赋值给离此地址最近的载物台。然后将任务链的下一节点赋值为载入任务的源地址和货物类型。此时载物台有一个小箱，任务链增加了一个节点。

②如果下一任务为外侧小箱且目的地址为同侧，将任务信息赋值给与任务货位最近的载物台货位，将远离任务货位的载物台货位的源、目的地址均赋值为与任务货物相邻的内侧货位的地址。然后将任务链的下一节点赋值为载入任务的源地址和货物类型。此时载物台有两个小箱，任务链增加了两个节点。

③如果下一任务为外侧小箱且目的地址为对侧，按照距离下一任务的目的地址最节省时间且在对侧的空闲货位为中转货位；任务完成后，载物台上只剩中转货物，源地址为中转货位地址，目的地址为中转货位的原始地址。任务链增加了3个节点。第一个节点的地址为中转货位地址，货物类型为1；第二个节点的地址为任务的目的地址，货物类型为1；第三个节点的地址为中转货位地址，货位类型为1。

③如果下一任务链货物类型为大箱，将任务信息赋值给载物台所有货位。将任务链的下一节点地址赋值为载入任务的源地址，货物类型为2。

最后更新立体货架存货信息。

2)m1、m2有一个为空。

如果是下一任务货物类型为大箱，按照死锁避免策略应当首先清空载物台再进行装载，装载完成时，载物台上只有一个大箱，载物台两货位信息为大箱的源地址、目的地址和货物类型。按顺序增加两个任务链节点：1、当前任务的目的地址，货物类型为1；2、下一任务的源地址，货物类型为2。最后更新立体货架存货信息。

如果不是大箱，分几种情况分析：

①m1有货，目的地址为同侧，直接载入下一任务。当下一任务源地址和m1同侧时，将m1赋值给m2，将下一任务的信息赋值给m1。此时载物台上有两个货物。当下一任务源地址和m1异侧时，将下一任务信息赋值给m2。

任务链增加一个：节点为下一任务的源地址，货物类型为1。

②m1有货，目的地址为异侧。如果下一任务源地址为m1同侧，将m1赋值给m2，下一任务信息赋值给m1，此时载物台上有两个货物。如果下一任务源地址为m1异侧目的地址m1异侧，将下一任务信息赋值给m2。

任务链增加一个：节点为下一任务的源地址，货物类型为1。

如果下一任务源地址为m1异侧目的地址m1同侧，此时产生死锁。使用撤销策略避免死锁，首先完成当前任务，然后装载下一任务，完成时载物台有一个m2货物，m2属性为下一任务属性，

任务链增加两个：第1节点为当前任务的目的地址，货物类型为1；第二节点为下一任务的源地址。

③m2有货，分析方法和第二类m1有货相似。

3)m1、m2均有货。

如果ETV载物台两货物均为小箱，选择离m1、m2目的地址耗时最短的货位为下一任务链节点。①下一任务是卸载m1，将m2赋值给m1，清空m2，增加一个任务链节点：m1目的地址。②下一任务是卸载m2，将m1赋值给m2，清空m1，增加一个任务链节点：m2目的地址。完成后m1、m2有一个为空。

如果ETV载物台为一个大箱，下一任务是卸载m1和m2，任务完成后清空m1和m2，任务链增加一个节点：地址为m1或m2的目的地址，货物类型为2。

1.3 使用粒子群算法求任务序列

国内某机场某立体仓库内拥有一个巷道两个ETV，双机ETV调度问题属于并行调度问题(ParallelMachineShopSchedulingProblem,PMSP)，PMSP是NP完全问题[8]。随着启发算法的深入研究，NP完全问题得到了很好的解决。其中粒子群算法结构简单易行得到了广泛的应用。

双机ETV调度问题是带有约束条件的优化问题，它的适应度函数为式(2)：

pi=max(T1i,T2i)

(2)

式中，T1i、T2i分别表示1号ETV和2号ETV执行任务链所用时间。

约束条件如式(3)所示：

(3)

式(3)中，第一行约束条件保证一号ETV运行的区间在第1～40列，第二行约束条件保证二号ETV运行的区间在第5～45列，第三行约束条件保证相同时刻两ETV之间的距离大于等于4列，第四行和第五行保证两个任务链均属于任务集，第六行保证两个子任务集内任意元素不属于对方任务集。

1.4 双ETV调度问题粒子编码

双机ETV调度要解决的是任务分配问题，将任务、ETV序号映射为粒子的位置，这个过程叫做编码。相对应的，将粒子位置映射为任务、ETV序号的过程称之为解码。

设有40个出入库任务，则一个粒子需要40个维数，将粒子的每个维数和每个任务一一对应，根据粒子每个维度的坐标确定任务的序列。首先将粒子每个维度的坐标值按照从大到小的顺序排列。将坐标值大于0的维度对应的任务分配给1号ETV，将坐标值小于0的维度对应的任务分配给2号ETV。并且每个ETV分配的任务执行顺序为粒子坐标值的顺序。例如10个粒子分配情况如表1所示。

表1 粒子编码示例

表中，1号ETV执行的任务序列为8、1、5、7、4；2号ETV执行的任务序列为6、3、2、10、9。

1.5 标准粒子群算法

在一个N维空间中有M个粒子，每个粒子的位置记为xi=(x1,x2,…,xn)，速度记为vi=(v1,v2,…,vn)。在基本粒子群算法中，计算每个粒子的适应度，如果第i个粒子在某次迭代中适应度比以前更优，则更新第i个粒子的最优值并记做pid；选出这些粒子的最优值记做全局最优值并记做pig。按照公式(4)进行位置的迭代。

(4)

式中，w为惯性系数，w等于0.9；c1、c2分别为认知系数和社会系数，c1、c2均等于2；Pid为单粒子最优值；Pig为所有粒子的最优值；r1和r2属于U(0,1)均匀分布；

继续迭代，直至满足停止条件，全局最优解Pig即为模型最优解，对应的粒子位置xig即为最优位置。

1.6 混沌粒子群算法

许多改进的粒子群算法利用复杂的函数调节速度迭代算式，但是仿真结果发现在求解本文问题时容易陷入局部最优。Khare[9]等提出一种混沌迭代粒子群算法，王[10]等增加了一种变异因子。这些算法均提高了跳出局部最优的能力。受此启发对认知系数和全局系数进行非线性优化。为了提高迭代后期样本的多样性，利用混沌算子可以不重复的遍历吸引域内的所有点的特性，引入Tent混沌算子进行变异。

混沌优化粒子群算法中，位置更新算式如式5所示。

(5)

(6)

2 共享适应度改进粒子群算法

改进的粒子群算法虽然加快了收敛速度，而且在一定程度上提高了收敛效果，但是仍然易出现早熟现象。为了解决这个问题，论文在混沌粒子群算法的基础上，采用共享函数改进粒子群算法，提高算法的收敛效果。共享适应度算法来源于多峰函数的遗传算法求解，其思想是将某个小生境内的所有个体的适应度值除以一个和个体数目相关的函数值，用来鼓励较少个体物种的繁殖。论文借用这个思想在混沌粒子群算法的基础上，划定了一个共享半径，通过共享适应度的方式驱离重新初始化的粒子。

共享函数描述的是两个粒子之间的相互关系，它的值由此粒子和其他粒子之间的关系决定。增加了共享函数的粒子适应度为式(7)：

(7)

两个粒子位置向量差值的1范数记做两个粒子之间的距离，即公式(8)：

(8)

当粒子群陷入到局部最优时随机选择一部分粒子重新初始化，新旧两个粒子群相对独立。为了防止新粒子群回到原粒子群的局部最优附近，选取早熟区范围是距离全局最优解最近的20%的粒子，这些粒子中离全局最优解最远的粒子距离设为共享半径ds，当新粒子进入到共享半径时，它的适应度函数应当急剧增加，以促使其远离这个区域。基于以上思想设计共享适应度函数为公式9：

(9)

式中，ds为共享半径，di为粒子到原全局最优解的距离，M是惩罚系数，为定值100。

改进算法流程如下。

Step1：初始化粒子群。

Step2：在满足约束条件的基础上计算各个粒子的适应度，判断是否到达迭代次数的最大值，如果是则跳转到Step6，如果否继续。

Step3：判断收敛条件，如果收敛说明陷入局部最优，跳转至步骤5，如果否继续。

Step4：按照公式(2)更新位置和速度，然后跳转到Step2。

Step5：按照1.5章所述算法确定共享半径，选出部分粒子重新初始化，并且计算这部分粒子的共享适应度并排序，判断所有粒子是否均在共享半径外。如果有粒子在共享半径内，继续初始化这些共享半径内的粒子，直到所有新粒子均在共享半径外，然后跳转到Step2。

Setp6：迭代停止，得到最优解。

3 实验和结果

国内某机场ETV仓库拥有7个路侧I/O口和6个空侧I/O口，设路侧为入口、空侧为出口，则出入口分布如表2所示。

表2 出入口位置

实验样本选用20个入库任务和20个出库任务，如表3所示。

表中，任务号格式为X-X-X，以此表示为任务类型、任务号、大小箱类型。其中大小箱类型分别表示‘1’为小箱和‘2’为大箱。

表3 任务库

3.1 算法步骤

算法步骤如Step1～5所示。

Step1：选择距离最近的出/入口作为出/入库任务的目的/起始坐标生成只含有源/目的地址的任务集。

Step2：判断是否达到停止条件。如果是，跳转到Setp5；如果否，继续。

Step3：按照标准PSO算法、混沌优化粒子群算法、共享适应度粒子群算法分别迭代生成新的编码顺序

Setp4：根据粒子群算法生成的编码顺序生成任务链，并按照公式(2)计算粒子群的适应度。然后跳转到Step2。

Step5：迭代停止，得到最优解。

3.2 仿真结果和分析

3种粒子群算法的最大迭代次数均为200次。粒子群规模均为20个。为了测试算法的有效性，分别运行10次并记录。10次迭代结果分别如图3～5所示。

图3 标准PSO迭代结果

图4 混沌优化PSO迭代结果

图5 共享适应度PSO迭代结果

从图3～5可以看出，该样本有3个局部最优解区域，分别在1 500 s、1 650 s、1 800 s左右。标准粒子群算法易出现早熟现象。混沌粒子群算法虽然加快了运行速度而且在一定程度上提高了跳出局部最优的能力。从图5可以看出，在迭代后期有一些粒子到达了1 500 s左右区域，共享适应度粒子群算法在增加少量迭代次数的情况下有较强的跳出局部最优的能力，全局寻优能力更强。

计算10次任务链的平均时间如图6所示。

图6 平均任务链时间对比

图中可以看出，共享适应度粒子群算法所得任务链时间最短。

使用公式(10)计算第i次迭代中10次结果的标准差，如图7所示。

(10)

图7 标准差对比

图中可以看出迭代初期标准PSO的标准差最低，共享适应度粒子群算法标准差波动最大。迭代后期混沌优化粒子群算法标准差最大，共享适应度粒子群算法标准差最小。结果说明迭代初期共享适应度粒子群算法频繁的执行粒子重初始化程序，使粒子跳出局部最优；迭代后期共享适应度粒子群算法所得结果更稳定。

图8是共享函数改进粒子群算法获得的最优序列的位置-时刻图。

图8 最优位置时刻图

图中可以看出，最优序列下两个ETV大部分时间在各自的半区运行，且运行轨迹较平滑，进一步验证了算法的有效性。

4 结束语

针对从任务的角度出发生成双机ETV任务序列较困难的问题，提出一种基于ETV载物台货位生成任务链的算法。和文献[7]所述算法相比，不仅降低了模型的复杂程度，而且可以方便的计算每个时刻载物台货位的状态和任务序列的执行时间。针对双机ETV求解最优序列过程中极易陷入局部最优的问题，将共享适应度概念应用到了模型的求解。仿真结果表明，和标准PSO、混沌优化粒子群算法相比，改进的共享适应度粒子群算法所得结果更优，稳定性更好。