基于改进克隆选择算法的多AGV路径规划研究

□ 齐 权，张新敏

(沈阳工业大学 机械工程学院，辽宁 沈阳 110870)

1 引言

随着物流技术的广泛应用，自动导引车(AGV)已经被越来越多地应用于柔性制造系统(FMS)中。AGV路径规划是多AGV系统设计的关键问题之一，分配好配送任务之后，规划出一条路径，使AGV从起点无碰撞地到达终点并返回车场，且用时最短，路径规划的好坏直接影响物流系统的效率。自从AGV的路径规划问题由Maxwell和Muekstady提出以来[1]，国内外学者对多AGV系统路径规划问题做了许多研究，Carl Adam Petr提出了Petri网理论，并利用该理论解决AGV路径规划问题，该理论在AGV路径规划问题中被广泛应用[2]；Reza选择遗传算法和禁忌搜索算法解决AGV路径问题；吉林大学的吴晓雨用基于优先级的交通规则法解决冲突问题[3]；广东工业大学的李青欣设计不同类型的遗传算法来解决AGV在不同环境下的路径规划问题[4]；Cai运用遗传算法原理给出了一种基于定长十进编码方法的多个移动机器人路径规划[5]。谢辉辉和钟建琳等人对A*算法的论述中，介绍了A*算法中可以选取的常用启发式函数[7-8]。研究工作对柔性生产环境多AGV路径规划问题进行了深入研究，在建立多AGV路径优化数学模型的基础上，提出了一种改进的克隆选择算法进行求解，并运用离线-在线两阶段式控制策略解决AGV路径空间冲突问题。最后针对具体实例，给出了物料配送路径的优化结果，证明了所提方法的有效性和可行性。

2 问题描述

在某柔性生产车间中，有多个AGV负责物料搬运工作。AGV的任务是接受系统的调度，在不同站点之间以规划好的路径运送物料，以完成对物料的搬运。为更好的探讨AGV作业调度问题的本质，对AGV工作做如下约束：

①AGV的数量、AGV的所要完成的物料搬运任务是固定的；

②AGV运行路径可稳定规划且不冲突；

③AGV的运行速度已知且恒定，AGV在路径中的行驶时间与路径长度成正比；

④AGV完成运输任务后，返回车场；

⑤在同一路径中，两辆AGV不可相向行驶，并且以逆向行驶的方向超越对方。

3 优化模型的建立

对于传统的车辆路径问题，实际应用中可以选择的目标函数主要包括物流配送成本最少、配送车辆行驶总路程最短、使用的车辆数最少、配送的准时性最高等几个目标，大多数车辆路径问题都是单目标问题。

针对执行运输任务的AGV来说，执行配送任务的AGV总行驶路程最低是为了节省车间内宝贵的运输路径资源。减少AGV与AGV在路径中迎面相遇的次数，可以减少AGV与AGV在避障的过程中由于自身性能的缺陷导致死锁现象的出现。此外，由于AGV在转弯过程中行驶较慢，因此要尽量减少AGV在路径中转弯的次数，在规划阶段即需要规划合理路线，以径直的行驶路线代替转弯的规划路线。

综上，所研究问题为多目标优化问题，因此，目标函数的确定需要综合考虑多种因素对配送工作的影响，并将多目标优化问题转化为单目标优化问题，构建目标函数的表达式如下：

(1)

式中，m表示规划的AGV的数量，Si表示编号为i的AGV在路径中行驶的距离，Ri表示编号为i的AGV在路径中转弯的次数，Ta表示AGV在路径中以相反方向行驶并相遇的次数，Cs表示路径长度的时间成本系数，Cr表示由于AGV转弯路程的时间成本系数。

为方便研究工作的进行，设置如下决策变量：

Xijkp表示完成编号为i任务过程中，编号为p的AGV由节点j向节点k行驶的次数。Yij表示任务i由于编号为j的AGV完成，Soijk表示实时状态下，编号为i的AGV从j向k已行驶的路径长度。

模型受到如下条件约束：

①每个运输任务由一台AGV完成，其中m表示模型中AGV的数量。

(2)

②AGV完成运输任务之后返回车场，其中Bp表示，编号为p的AGV车场所在节点编号。

XijBpp>1

(3)

③路径只能容纳一台AGV行驶，AGV在路径中与其他AGV相遇，其中一台改变行驶方向，djk能表示节点j、k之间的空间距离。

Soijk+Soukj

(4)

4 基于改进克隆选择算法的多AGV路径规划

4.1 抗体编码设计

克隆选择算法有很多种编码方式，编码不但决定了抗体内数字的排列形式，还决定了从抗体数字变换到解空间的解码方法，同时也影响到变异算子、克隆算子等操作，合适的编码方法能够让算子运算的操作见到实现和执行。在抗体中，以十进制自然数表达AGV对于路径的选择。以数字串表示AGV从出发点到目的地的一条完整路径，每个数字表达AGV的路径选择决策。例如图1所示，当AGV运行到黑色节点时，编码1、2、3、4分别代表规划路径中的后继节点分别为1、4、7、8。

图1 抗体基因编码解码示意图

4.2 适应度函数设计

基于改进克隆算法求解AGV路径规划的过程中，需要根据抗体解的质量进行排序，选取解质量较优秀的抗体进行克隆，在对克隆抗体执行变异操作的基础上，选取解质量最优的变异抗体替代原抗体。

解的评价方法一般是根据目标函数设计适应度函数，研究工作考虑路径长度、AGV在路径中相遇的可能性、路径的光滑程度3个因素，采取加权的方式先建立目标函数，再转化为适应度函数。其中，路径长度与AGV完成任务的时间有关，长度越短AGV运行时间越少；如果AGV在路径中与其他AGV相遇，可能由于AGV争夺运输空间导致死锁现象的发生，延误物料运输任务的进行；路径的光滑程度也与运输时间有关，AGV转弯时速度需要减小，若优化路径时不考虑AGV的转弯问题，则规划出的最优路径不一定能使AGV以最快最安全的状态到达目标点，且转弯处的加减速能耗随之增加，为此AGV的转弯因素也是研究工作考虑的因素。

设计如式(5)所示的适应度函数，用于迭代过程中评估抗体的优劣，f1、f2和f3越小，表示路径长度越短、AGV在路径中相遇的概率越低和路径越平滑，实际应用中根据f1、f2和f3的重要程度选择合适的α、β和γ。

Fit=N-αf1-βf2-γf3

(5)

式中：N为足够大的正数，Fit为适应度函数，α、β和γ分别是f1、f2和f3的权重系数。

4.3 两阶段式控制策略

两阶段控制策略，又称两阶段交通控制方案[6]，是将多AGV系统的控制系统分为两个模块：离线路径规划模块和在线交通控制模块。两个模块分别对AGV进行离线式任务调度和在线式任务调度。

在离线式任务调度中，所有的运输需求都是已知的。所有AGV的行驶路径在出发之前得以优化。但是一个小的改变例如：任务延迟、道路拥堵、车辆故障或物料不足等可以使整个调度计划难以继续执行。多AGV系统必须能够合理应对各种不确定因素引起的变化，当AGV所在的环境发生变化后，在线交通控制模块根据工作的AGV信息，生成无碰撞的AGV运行路径。

4.4 改进克隆选择算法流程

为解决多AGV系统的路径优化问题，设计了改进克隆选择算法对路径进行规划设计。

4.4.1 种群初始化

对于算法的进化和收敛效果，结构优良的初始种群非常重要，随机生成一组长度为n的整数数组，表达抗体的路径选择策略，整数的取值范围介于1和与图的度(即图中单个节点的最大连接数)之间，数组长度取决于图的复杂程度。初始种群创建的步骤如下：

步骤1，根据系统中需要调度的AGV数量，确定个体支线数目M；根据图中度确定抗体基因取值范围[1，N]。

步骤2，用创建任意离散随机种群的方法对个体每个基因生成一个随机数ri，抗体的基因数n=M×节点数。

步骤3，重复以上步骤p次，产生一个包含p个个体的初始种群。

4.4.2 解码

根据4.1中所述的解码规则，对抗体基因进行解码，转码为AGV的规划运行路线。

4.4.3 抗体适应度评价

抗体适应度评价的目的是选取解的质量较为优秀的抗体进行克隆，并选择解质量优秀的抗体代替原有抗体，增强算法的收敛性，抗体的适应度评价依据4.2设计的抗体适应度函数评价公式进行。

4.4.4 克隆操作

对于适应度较高的抗体，克隆规模越大；反之适应度越低，则克隆出的个体越少。克隆操作能有效扩大搜索范围。实现了个体的高适应度的要求，并且有助于避免种群过早收敛和陷入局部最优。抗体克隆规模为：

(6)

其中，α为克隆系数，f(i)为抗体适应度，ceil()表示向上取整。式(6)表示克隆个数与抗体适应度成正比。

4.4.5 变异操作

变异操作可以实现种群的多样性，搜索到更优秀的抗体。当克隆增殖操作之后，对产生的个体独立地进行变异操作。采用基因突变算子，根据设定好的变异概率Pm，对克隆抗体种群中的一个或几个基因进行变异操作，变异的形式为，抗体基因片段整数的修改。

4.4.6 选择替代操作

从克隆抗体中选出适应度较好的抗体，使它按一定规则保留，替代原抗体，提高收敛速度和计算效率。组成子种群，代替对应的原抗体。在研究工作中，为保留抗体基因多样性，同源克隆抗体只保留一个抗体。为增强算法的收敛性，选择出的抗体将原抗体集合中适应度较低的抗体替代，保留原抗体集合中适应度较好的抗体，为此修改原抗体集合与克隆抗体集合的映射关系，抗体的替代操作依据重新建立的抗体映射关系进行替代操作。

图2 抗体集合映射的修改

4.4.7 终止判断

如果算法迭代一定次数之后，适应度最优i的抗体适应值不发生改变，或者达到最高迭代次数，算法终止运行，否则返回步骤(2)。

5 实例分析

为验证改进克隆选择算法的有效性，以某柔性生产车间为例，以实际应用的场地布局为参照，设计了一组模拟实验。以图3所示的车间为例，车间内有3台AGV，在柔性车间中存在3个加工区，在图中位置分别为结点10、结点22和结点23，还有2个仓库，在图中位置为结点4和结点5，AGV的车场位置为结点9，由AGV将仓库内的物料运送至加工区。模型中AGV穿越路径的时间与长度成正比，在结点处转弯的时间取定值。

图3 车间平面示意图

通过Matlab进行实验仿真，使用传统遗传算法、经典克隆选择算法和所设计的改进克隆选择算法对多AGV路径规划模型进行求解，得出AGV完成配送任务的总时间，参数设置如下：

种群大小：50；

克隆因子：0.3；

抗体变异因子：0.2；

最大迭代次数：90。

解的列表分别表示采用遗传算法和改进克隆选择算法进行任务调度和路径规划后AGV完成配送任务的总时间、AGV在路径中相遇的次数。

由表1可看出，当任务数小于等于19时，两种算法都能得到相同的最优解；但是随着任务数的增加，当任务数等于20时，相对于改进克隆算法，遗传算法的AGV相遇概率更大；当任务数增加到21时，改进克隆选择算法的物料配送时间小于遗传算法的物料配送时间。这说明改进克隆选择算法具有优秀的鲁棒性，可以跳出局部最优。

表1 算法运行结果对比

图4显示了克隆选择算法与改进克隆选择算法的收敛曲线，根据曲线可以看出，克隆选择算法与改进克隆选择算法都可以收敛得到可靠解，而克隆选择算法收敛较慢，改进克隆选择算法鲁棒性较强，收敛速度较快，经典克隆选择算法与改进克隆选择算法都可以得到路径优化问题的最优解。

图4 仿真结果

6 结束语

研究工作以柔性生产车间的多AGV路径优化问题作为研究对象，分析了对AGV运输时间构成影响的因素，并建立了数学模型，提出了两阶段策略，解决AGV在路径中的冲突问题，为解决问题，提出了改进克隆选择算法，为验证算法的有效性和优越性，利用编程软件完成了模拟试验，实验结果证明，改进克隆选择算法相对于经典克隆选择算法的求解质量相同，但求解速度大大加快，可以更少的迭代次数得到最优解，收敛性能大大提高。