熊 晔，毛剑琳

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

自动导引车(Automated Guided Vechicle，AGV)在柔性制造系统、自动化集装箱码头、自动化仓储以及物流业中应用广泛[1]。多载AGV是一种水平作业设备，一次搬运一件以上的制件，能大幅度提高了作业效率[2]。在传统的AGV调度研究中，大多数都是假定AGV系统的缓冲区容量无限且以单载AGV研究为主，对多载且缓冲区容量有限得AGV系统研究甚少。

Azimi等[3]用仿真实验提出了单载AGV的最优调度策略；Ho等[4]提出了同时求解多载AGV的负载选择和装载调度问题的多属性方法；Fazlollahtabar等[5]提出了一种自动化集装箱码头最小化多载AGV提前与延迟时间的综合启发算法；谷宝慧[6]针对单载AGV载重和运送货箱体积限定问题简历AGV路径优化模型，利用改进的量子微粒群算法进行实现；杜亚江[7]等建立了复杂约束的单载AGV多参数问题数学模型，采用混合遗传算法优化了调度时间。

以上研究大多以缓冲区容量有限、AGV只能进行单载操作为主。在实际的FMS中，多数AGV系统加工区中缓冲区容量都是有限的，且多载AGV有着节约运输成本、提高整体系统效率的优点。因此，对柔性制造系统(Flexible Manufacturing System，FMS)中的加工区缓冲区容量的多载AGV调度进行研究具有十分重要的理论和应用价值。

本文从提高柔性制造系统AGV作业效率入手，以加工区缓冲区容量、AGV的负载为约束，建立缓冲区容量有限的多载AGV调度模型，使用融合了灰狼优化算法思想的混合灰狼遗传算法求解，并与传统遗传算法进行对比，模拟实验结果验证了新算法的优越性。

1 问题描述

一个典型的柔性制造系统作业车间包括AGV小车、缓冲区有限的加工区、导向网络和仓库，其平面构造图如图1所示。AGV按需求一次可运送一个大制件或者两个小制件进入FMS中，由仓库驶出进入FMS，经过5个加工区的作业后返回仓库，即为完成一个循环。

图1 柔性制造系统作业车间的构造平面图

一个特定FMS中有一个AGV和一个制件集，目的是最小化所有任务时间：计算出每个制件在每台机器的加工时间以及每个输入/输出缓冲区的时间，从而确定每个机器与机器之间所走路程的起始和完成时间。

2 模型建立

在数学模型中，符号定义如下：

M：加工区集；

W：制件集；

A：搬运任务集；

N：任务次序集；

G：系统允许的最大制件量；

m：加工区编号，m∈M，Mo表示仓库；

w：制件编号，w∈W；

A：任务编号，a∈A；

n：任务执行的次序编号，n∈N；

CIm：加工区m的输入缓冲区容量，CIm>0；

COm：加工区m的输出缓冲区容量，COm=CIm；

CImh：加工区m的输入缓冲区的剩余可容纳制件的量；

Im：加工区m的输入缓冲区上的制件个数；

COmh：加工区m的输出缓冲区的剩余可容纳制件的量；

Cm：加工区m的输出缓冲区上的制件数。

Um：表示在加工区m上现有的制件数；

Twm：制件w在加工区m上的加工时间；

Uwm：表示制件w在加工区m上加工；

Tbm：为制件w在加工区m上的开始加工时间；

Tem：为制件w在加工区m上的结束加工时间；

Tq：AGV装载制件的固定时间；

Tf：AGV卸载制件的固定时间；

Tba：AGV的搬运任务a的开始时间；

Tea：AGV的搬运任务a的结束时间；

Tb(m1,m2)：AGV从加工区m1移动到m2的所用时间；

Ta：AGV执行任务a所用的时间；

Cq：任务q完成操作后AGV容量的占用情况；

C：AGV最大负荷能力；

D：AGV在任务q完成后的容量改变情况。

定义决策变量

缓冲区容量有限的多载AGV调度问题，以最小化多载AGV完成调度集内所有任务花费时间最短为目标，建立数学模型，模型的目标函数与约束条件如下

(1)

式(1)表示自动导引小车完成调度集内全部任务所用最短时间。自动导引小车每次完成且只完成一个任务以式(2)表示。

(2)

搬运任务a的结束时间减去开始时间为AGV完成一次搬运任务所耗费的时间

Tea-Tba=xnaTa,∀a∈A,n∈N

(3)

后一个任务开始时间等于前一个任务的结束时间，即

x(n+1)kTbk=xnaTea,∀a,k∈A∩a≠k,n∈N

(4)

加工区输出缓冲区上有多个制件，则存在一个加工区分配多个搬运任务时，在调度时段，相同加工区的任务只能按分配时间的先后执行

n>1,Cm>1,xnaTbm>xlkTem,∀a,k∈A∩a≠k,n,
l∈N∩n≠1

(5)

一个加工区一次只能加工一个制件

bmwj+bmjw=1,∀w,j∈W,m∈M

(6)

系统现有制件数不可超过系统承受的最大制件数

(7)

输入缓冲区的容量不满时，完成一次搬运任务所耗时等价于小车从当前位置空载移动到目标制件所在的加工区、目标制件装载的时间、AGV移动到目标加工区输入缓冲区的时间、目标制件卸载的时间的总和

xnaTa=Tb(Ya,Xwa)+Tq+Ta(XwaUwm)+Tf,CImh≠0,
∀a∈A,w∈W,n∈N

(8)

输入缓冲区的剩余容量为零时，AGV完成一次搬运任务所耗时等价于在目标加工区上的制件的结束加工时间及目标制件卸载的时耗总和

xnaTa=ymwTem+Tf,CImh=0,ymwj=1,∀w,j∈W,
w≠j,a∈A,n∈N

(9)

输入/输出缓冲区的剩余容量为输入/输出缓冲区容量减去输入/输出缓冲区上的制件数

CImh=CIm-Im,∀m∈M

(10)

COmh=COm-Om,∀m∈M

(11)

输入缓冲区的制件数、输出缓存区上的制件、加工区上正在加工的制件数的总和即为加工区现有的制件数

Um=Im+Om+ymwj,∀w,j∈W,w≠j,m∈M

(12)

加工区的输出缓存器剩余容量不为零时，制件的加工结束时间等于制件的加工开始时间加上制件在加工区上的加工时间

Tem=Tbm+Twm,∀m∈M,w∈W,COmh≠0

(13)

加工区的输出缓存器为满时，制件加工完毕之后需等候进入输出缓存区

Tem>Tbm+Twm,∀m∈M,w∈W,COmh=0

(14)

AGV相继完成任务q、p后AGV的负载变化如下

zqp(Cq+dp-Cp)=0

(15)

对AGV负载的约束为

dq≤Cq≤C

(16)

0≤Cp≤C+dp

(17)

3 多载混合灰狼遗传算法(MHGWOGA)

灰狼优化算法(Gery Wolf Optimization，GWO)是由Mirjalili S等[8]在2014年提出的新算法，通过模仿自然界灰狼种群领导层级和以及狼群跟踪、包围猎物的狩猎过程来实现优化。GWO算法能在解空间中快速找出最优解，避免出现局部最优[9]。

本文将GWO算法中灰狼社会等级、狩猎机制引入至标准遗传算法的选择算子中，克服了传统的遗传算法易早熟的缺点，提高了算法全局搜索的效率。

3.1 编码与解码

本文研究的是AGV任务排序问题，选择加工区的序数方式进行编码[10]，将搬运任务集内的任务进行排序，自动导引小车执行的任务的先后顺序从而决定制件去加工区作业的顺序。同一个加工区使用相同的编号，如图2所示。

图2 编码解释

解码按照AGV单载、多载需求开始进行。针对同一加工区的不同任务，AGV会根据任务工件的大小来判断是使用单载AGV还是多载AGV执行任务，执行任务的顺序是根据染色体中出现的同一序号的顺序执行：同一个加工区发出的第一个任务是染色体基因中出现的第一个序号，以此类推，即可得出同一加工区的不同任务的执行顺序。

3.2 适应度函数

适应度函数设计为

(18)

3.3 选择

选择操作是为了避免优良基因的损失，使性能好的个体生存繁殖的概率增大[11]。这里采用轮盘赌和精英选择结合的方法。若不采用精英保留策略，仅是采用轮盘赌选择算子，会造成优良的个体缺失，因此引入灰狼优化算法来化解这个矛盾。

在每一次选择操作的时候保留α、β、δ3种个体，形成如图3所示的灰狼内部社会等级地位，三者适应度关系满足式(19)。剩余的个体即是ω，整个种群在α、β、δ的领导下向全局最优解进化。

图3 灰狼层级金字塔图

(19)

灰狼需先判断猎物位置并进行包围，数学表达式如下

D=|C*Xp(t)-X(t)|

(20)

其中，Xp(t)表示第t代猎物位置向量；X(t)表示第t代时灰狼位置向量；常数C为摆动因子[12]，由式(21)决定

C=2r1

(21)

r1为[0,1]区间的随机值，对灰狼位置更新

X(t+1)=Xp(t)-A*D

(22)

其中收敛因子A由式(23)决定

A=2a*r2-a

(23)

其中，r2亦为[0，1]区间的随机值。a在迭代过程中从2线性下降到0，计算公式如式(24)所示

(24)

在追捕过程中，α带领β、δ狼完成狩猎行为，即由α、β、δ狼距离猎物的位置，判断猎物的大致位置后，对猎物进行追捕。狼群狩猎的原理[13]如图4所示。

图4 灰狼狩猎原理图

(25)

Dβ=C2*Xβ(t)-X(t)

(26)

Dδ=C3*Xδ(t)-X(t)

(27)

X1=Xα-A1*Dα

(28)

X2=Xβ-A2*Dβ

(29)

X3=Xδ-A3*Dδ

(30)

X(t+1)=(X1+X2+X3)/3

(31)

其中，Xα表示α当前位置，Xβ表示β当前位置，Xδ表示δ当前位置，X(t)为第t代灰狼的位置向量[14]。由式(25)～式(30) 计算出个体与α、β、δ之间的距离，然后由式(31)即可定义出猎物的最终方位。

改进后的选择步骤如下：

步骤1初始化随机狼群；

步骤2计算出每头狼对应的适应度值；

步骤3将适应度排列前3的灰狼个体位置分别记为α、β、δ；

步骤4按照式(25)～式(27)计算其它个体与α、β、δ的距离，并根据式(28)～式(30)计算每个灰狼个体的位置；

步骤5更新参数a、A、C等参数的值；

步骤6如不满足结束条件，跳转至步骤2；

步骤7导出α狼的位置；

步骤8按轮盘赌规则选择个体复制到下一代。

3.4 交叉

本文采用了部分映射交叉方式，随机产生两个随机数p，q∈[2，n-1]，交换两个染色体i和j位于p和q之间的基因片段，映射交叉操作如图5所示[15]。

图5 部分映射交叉示意图

3.5 变异

本文中的变异方法采用倒置变异[16]，也就是在染色体上随机选择两个位置，然后颠倒两个基因序列，如图6所示。

图6 倒置变异示意图

4 数学实验

为验证混合灰狼遗传算法的有效性，本文以某柔性制造车间为例，设计一组仿真实验。该FMS中存在5个加工区和1个仓库。每个加工区均配有容量为3的输入缓冲区F1和容量为3的输出缓冲区F2。制件从仓库出发，经过加工区后运回，仓库加工区分别用a、b、c、d、e表示，仓库用0来表示。

AGV的移动路径时间如表1所示，制件在不同加工区的加工时间如表2所示。

表1 AGV的移动路径时间

表2 制件在不同加工区加工时间

通过MATLAB进行实验仿真，使用传统的遗传算法和本文设计的混合灰狼遗传算法对缓冲区容量有限的多载AGV调度模型进行求解，得出AGV配送及加工完成所有制件的总时间。参数设置如下：初始种群规模为50；交叉概率Pc为0.6；变异概率Pm为0.01。在制件数不同的情况下，仿真结果如表3所示。HGWOGA最优解、GA最优解的列表示为分别采用单载AGV模型混合灰狼遗传算法和单载AGV模型遗传算法进行调度后AGV配送及加工完成所有制件的总时间。MHGWOGA最优解、MGA最优解的列表为分别采用多载AGV模型混合灰狼遗传算法和多载AGV模型遗传算法进行调度后，AGV配送及加工完成所有制件的总时间。

表3 制件数不同时4种算法的调度结果

上表可看出，当制件数<15时，4种算法都能得到相同的最优解。但是随着制件数的增加，当制件数>15时，MHGWOGA算法的调度时间要远小于HGWOGA算法的调度时间，且当制件数>20时，单载AGV系统已经发生死锁，而多载AGV系统仍然能运行至22个制件。这说明本文所提出的缓冲区容量有限的混合灰狼遗传算法多载AGV调度模型较单载AGV调度模型的改进策略是有效的。

以1表示小制件，2表示大制件，确定制件从仓库的运出次序。以制件数分别为15、20为例，设定制件运出次序分别为1，2，1，2，1，1，1，1，2，1，2，1，1，2，2和1，2，2，1，1，2，1，2，1，1，2，1，2，1，1，1，1，2，1，1 ，可得出图7、图8两种算法的进化迭代图。

图7 制件数为15两种算法进化过程对比

图8 制件数为20两种算法进化过程对比

从图中可以看出，当制件数为15时，MGA算法约在10代收敛，MHGWOGA算法约在3代就已经达到收敛；当制件数为20时，MGA算法约在90代收敛，而MHGWOGA算法约在10代就已经达到收敛，后者的收敛速度要远快于前者的收敛速度，且能得到更好的最优解。这也说明了MHGWOGA算法的有效性。

5 结束语

本文针对FMS中缓冲区容量有限的多载AGV调度模型，通过将灰狼优化算法中的社会等级、狩猎制度引入传统的遗传算法中，提出了一种全新的多载混合灰狼遗传算法，大幅提升了算法的搜索能力。仿真实验结果表明，相对于传统的遗传算法，MHGWOGA算法能有效求解缓冲区容量有限的多载AGV调度的问题，且具有收敛速度快、得到调度更优解及提升AGV调度效率的优点。但在实际生产中，存在大量有限缓冲区的多载AGV情况，仍亟待深入研究。