0.引言

智能工厂是实现智能制造的关键环节。在智能工厂中，智能设备得到了广泛的应用，AGV、智能机械手等智能搬运设备组成了智能生产物料系统。多搬运载体间的协同作业对智能工厂的正常运转具有十分重要的意义。近年来，多搬运载体间的协同作业研宄成为物流领域的关注热点，国内外学者针对协同问题开展了大量研究。
在搬运载体协同研宄方面，陈敏等[1]针对智能车间中多AGV的调度问题进行研宄，提出7个调度运行机制，通过运用PlantSimulation对进行仿真，验证调度方案的合理性。贺长征等[2]针对柔性制造车间中AGV和加工设各的协同调度问题，建立双资源优化数学模型，设计了“时间窗+Dijkstra+遗传算法的混合算法进行求解，并采用了3种规则解决最优路径规划中的冲突问题。刘旭等[3]建立以AGV工作过程中行驶时间最短的数学优化模型，对遗传算法的交叉变异算子改进，求解获取多AGV协同调度的最佳方案。岳笑凸等研宄面向柔性制造系统中多自动牵引小车的协同调度问题，考虑小车的续航能力因素，以任务的最小完成时间和车辆数最少使用量为调度目标，采用混合遗传一粒子群算法进行求解，并通过仿真验证模型和算法有效性。AbdelmaguidTF等[5]研究加工设备和多AGV双资源间的协同优化，以最大任务结束时间为优化目标，提出一种新的混合遗传算法编码方案进行求解，通过82组实验算例，验证模型和编码方案的性能优劣性。

在路口避碰研究方面，胡杰杰[6]针对智能车间柔性物理，设计了集中式的AGV群控协调算法，赋予AGV任务优先级，解决节点处的冲突问题。肖萌[7]针对多AGV冲突问题以高优先级优先通过为原则，提出冲突判据方法和主轨道双向并行避碰策略，通过仿真验证和实现该方法。肖海宁等[8]研宄单向引导路的AGV系统，建立基于有向图的AGV系统模型，基于此提出路径锁死的破解规则，通过PIantSimuIation仿真验证其有效性。乔岩等[9]研宄在动态变动环境下，针对AGV临时改变行进路线的清况，在交叉节点对AGV的优先级进行动态调整AGV通过路口顺序，并以此更新AGV路线，以改进时间窗算法进行仿真实验，证明方法的具备更好的鲁棒性和高效率性。
目前的研究多为考虑单资源和双资源的协同问题，在三资源协同作业方面研宄较少，在协同研宄中考虑搬运载体路口避碰的研宄也较少。本文考虑仓库存取货的堆垛机、工位间搬运物料的AGV和线边装卸物料的机械手三资源的协同作业中，同时设计多AGV在交叉路凵的可同时通行的避碰规则，优化整个作业车间的物流作业效率。

1.多载体协同作业优化模型

1.1问题描述及假设条件

1.1.1问题描述

针对智能工厂中多搬运载体的协同作业问题，以仓库存取货的堆垛机、工位间搬运物料的AGV和线边装卸物料的机械手为研究对象，研究堆垛机．AGV．线边机械
手三个资源协同执行运输任务的同时，考虑多AGV在交叉路口的避碰问题，建立以最大完工时间最小化的数学规划模型，并建立成本惩罚函数作为辅助优化模型。车间物流作业流程如图1所示，AGV n ，在仓库前的物料交接点等待堆垛机将物料从立体仓库搬运到AGV m 上，由AGV。选择最优路径（红色路径）将物料运输到需求工位旁的交接点，由机械手进行卸载。

图1 车间多搬运载体协作流程图

1.1.2模型假设

根据智能车间的实际情况，为了便于模型求解分析以及考虑AGV交叉路口的碰撞情形，对问题进行合理的假设与简化：
1）AGV在空载和负载的情况下均为匀速行驶；
2）不考虑AGV加速和减速过程；
3）搬运载体车况良好且均有额定容量；
4）AGV的任务执行过程为连续的，不存在中断的情况；
5）AGV可同时接受多个任务，依次执行；
6）考虑AGV在路口的碰撞和堵塞情况；
7）堆垛机和机械手的操作时间和装卸顺序为己知；
8）各搬运载体间相互独立，不存在约束情形；
9）小车在容量充足的情况下，可搬运多个物料或工件；
10）同类型搬运载体的工作能力指标相同。

1.2参变量定义

1.2.1参数设定

H：表示路径节点的集合，h=1，2，···，H;I：表示任务的合集，i=1，2，···，L：表示堆垛机的集合，i=1，2，···，L；M：表示AGV的集合，m=1，2，•••,M;N：表示机械手的集合，n=1，2，···，N;S：表示路径的集合．s=1，2，···，S:K：表示路口的合集，k=1，2，···，K:Ti：表示任务i的完工时间；T1：表示堆垛机执行完单个任务所需的平均时间；Tn：表示机械手执行完单个任务所需的平均时间；TLi：表示堆垛机I开始执行任务i的时刻；Eni：表示机械手n执行完任务i的时刻；Ti：表示机械手n开始执行任务i的时刻：Tilm：表示AGVm开始执行堆垛机1执行完的任务i的时刻；qms：表示AGV。行驶的距离；Vm：表示AGV。的行驶速度；t1mn：表示AGVm从堆垛机行驶至机械手n所需的时间；qms表示AGVm在交叉路口所处的相位；Qqms：表示AGm在交叉路口所处相位的集合。

1.2.2决策变量

tim：AGVm执行完任务i时刻；

1.3目标函数

为实现车间工作效率最大化和物料送达时间误差最小，本文提出智能车间多搬运载体协同作业的两个优化目标，构建完工时间和惩罚成本均最低的多目标优化函数。

1.3.1最短完工时间

minZ=max{Ti}     (1)
其中

式中，Ti表示任务i的完工时间，T1i表示堆垛机1开始执行任务i的时刻，Eni表示机械手n执行完任务i的时刻，整体优化目标为最大完工时间最小化。

1.3.2 最低惩罚成本

针对物料送达过程可能出现的提前送达、准时送达和延迟送达三种情况，本文对三种送达情况建立相应的成本惩罚函数，并作为第二个优化目标，如式(5)所示。
minC=min{f(tim)}     (5)
其中，考虑到物料运输延迟送达对项目进度的影响损失比物料运输提前送达对项目进度的影响损失更为严重，同时为增强资源配置过程中的柔性[10,11]，建立如图2所示的曲线型软时间窗成本惩罚函数。
假设最佳到达的时间窗为[ta,tb]，在此基础上，可偏离得到可接受服务时间窗[t'a,t'b]，其中，t'a=ta-Δ1，t'b=tb+Δ2。若AGVm在[ta,tb]内将物料送达指定工位，惩罚成本为0；若AGVm在[t'a,t'b]或[tb,t'b]内将物料送达指定工位，只需承担较少的惩罚成本；若AGVm在（0，t'a)或（t'b，∞ )内将物料送达指定工位，则需要承担较多的惩罚成本。基于曲线型软时间窗的成本惩罚函数如式（6）所示。

图2 基于曲线型软时间窗的惩罚成本函数

式（6）表示在曲线型软时间窗的约束下，AGVm执行完任务i的时刻tim所对应的惩罚成本。如图2所示，若AGVm在t'a时刻之前送达，单位时间所需承担的惩罚成本为cp1，同时还需要承担[t'a,ta]时间段所产生的惩罚成本；若AGVm在[t'a,ta]时间段内送达，单位时间所需承担的惩罚成本为cp2；若AGVm在[ta,tb]时间段内送达，惩罚成本为0；若AGVm在[tb,t'b]时间段内送达，单位时间所需承担的惩罚成本为cp3；若AGVm在t'b时刻以后送达，对应的单位时间所需承担的惩罚成本为cp4，同时还需承担[tb,t'b]时间段所产生的惩罚成本。
式中，α和β为提前送达和延迟送达的成本惩罚权重，分别取值为0.1和0.8[12]。

1.4约束条件

其中，式（7）表示任何时刻一台堆垛机只能被分配一个任务；式（8）表示任意时刻同一任务只能被分配给一个加工工位；式（9）表示两台相位相冲突的AGV不能同时通过路口；式（10）表示每个任务在同一时刻只能由一台AGV执行；式（(1)表示每个任务在任意时刻只能分配给一个堆垛机；式（12）表示机械手开始处理的时刻不得早于AGV将物料送达机械手所在交接点的时刻：式（13）表示任务被完成的时刻；式（14）表示只有在堆垛机将物料卸载在交接点后，AGV才能开始执行任务；式（巧）表示每台AGV待执行的任务需依次排序执行：式（16）表示参数的非负限制。

2.AGV路口避碰规则

路口碰撞可分为相向冲突、路口冲突和节点占用冲突三种[13]。传统路口避碰为题大多赋予AGV不同级别的优先级，按优先级高低依次通过，单次只能通过一辆AGV[13]。本文研宄中，为使AGV避碰环节更贴近实际，AGV在行驶过程中经过某交叉路口时，根据传感器和RFID采集的数据，分析当前路口的通行情况和路口AGV行驶信息，通过检测每辆AGV的行驶方向，判断多辆AGV的是否可同时通行，并对相冲突的AGV进行优先级调整，使路口可同时通行多辆AGV，有效减少等待时间和碰撞情况的产生。

2.1 AGV冲突类型检测

AGV行驶临近交叉路口时，根据传感器和RFID采集的数据，控制系统对AGV位置和时间状态进行更新，检测并分析在即将驶入的路口是否会发生冲突及其冲突类型。
检测中参数定义如下：
1)λbm为表示AGVm到达节点h的时间；
2）εhm为表示AGVm在节点h的停留时间；
3）θ为表示冲突检测时的安全时间间隔阈值；
4）Kmh为节点h的识别码，且该节点在AGVm的规划行驶路径中；
5）Kmh-1<Kmh<Kmh+1为AGVm通过的节点顺序。
冲突检测模型如下：
1）相向冲突
若检测过程中满足以下关系式(17)、式(18)、式(19)，则AGV在路口将发生相向冲突。

2）路口冲突
若检测过程中满足以下关系式（20）和式（21），则AGV在下一路凵将发生路口冲突。

3）节点占用
若检测过程中满足以下关系式（22）和式（23），则AGV在下一路口将发生节点冲突。

2.2 路口冲突AGV的优先级动态调整

如图3所示，AGVm行驶至交叉路口时，每辆AGVm均有gs、tl、tr三种行驶方向的可能性，分别代表直行、左转、直行，在路口设置互容和不容两种通行相位，处于互容相位的多辆AGV可在不碰撞的情况下同时通过，处于不容相位的多辆AGV不能同时通过路口，（假设路口的转弯半径可同时容纳两辆互容相位的AGV同时通过）。比如AGVtrm1则表示AGVm1在路口右转，则与AGVtlm2、AGVtrm2、AGVtrm3、AGVgsm2、AGVtrm4、AGVgsm4是互容相位，可同时通过路口，与AGVgsm2、AGVtlm3、AGVtlm4是不容相位，不可同时通过路口，其通过路口顺序需根据优先级调整确定。

图3 AGV在路口的冲突相位图

在交叉路口处于不容相位的AGV，为保证各AGV之间有明确的优先关系，通过赋予AGV优先级来确定通路口的先后顺序，其依据是根据理论上AGV完成正在执行任务的剩余时间，值越小，则AGV优先级越大，不同的优先级以增幅A来确定，若是空载车辆，优先级则设为最低。
其中：

式中，rest（Ti)表示任务i的剩余完工时间；Number(k)表示当前路口排队不容相位排队通行的车辆数。

2.3 双路囗路径容量检测

为减少双路口之间路径的堵塞现象，当AGV即将抵达双路口路径时，在检测交叉路口冲突情况的同时，检测双路口之间路径堵塞情况，评估当前是否可以进入该路径而不造成堵塞，如图4所示，评估标准为路径剩余可容纳的车辆数：
N(s)=F[ s ]-Y(s)       (25)

图4 双路口路径容量检测示意图

式中，N（s）为路径s的剩余可容纳的车辆数；F（s）为路径可容纳车辆的额定容量，取值向下取整；Y(s)为路径s中己进入的车辆数；ls为路径s的长度；
lAGVm为AGVm的长度，θ为行车过程中的最小安全距离。
当N（s）＜1时，将禁止AGV通过交叉路口，等待直至有AGV从路径驶出。

3 粒子群算法

PSO是Kennedy和Eberhart受鸟群群体运动的启发于1995年提出的一种新的群智能优化算法[14]，通过粒子间的信息共享，协作完成寻优任务，具有记忆性强、效率
高和搜索速度快等特点，但易陷入局部最优，即局部寻优能力强，全局寻优能力弱[15]。本文对粒子群算法进行优化，采用动态惯性权重和引入遗传算法中的自适应变异概率，避免算法后期陷入局部最优，提升算法的收敛能力和收敛精度，算法流程如图5所示。

图5优化自适应粒子群算法流程图

3.1 PSO算式

设求解模型的维度为D维，有1个粒子，粒子群为L={p1,p2,…,pi,…,pl}速度表示为V={v1,v2,…,vi,…,vD}，位置表示为X={x1,x2,…,xi,…,xD}，pbesti表示粒子i经过的最佳位置，gbesti表示所有粒子经历过的最佳位置。PSO算法的粒子i的第D维速度更新公式为式(27)，粒子i的第D维位置公式为式(28)：

式中，vkid表示粒子i进行第k次迭代时速度矢量的第D维分量；vkid表示粒子i进行第k次迭代时位置矢量的第D维分量；c1，c2表示学习因子加速度，其值为常数；r1，r2为取值范围为[0,1]的两个随机参数；w表示惯性权重，取值非负，用来调节对解空间的搜素范围。
惯性权重表示粒子i的先前速度对当前速度的影响。全局寻优能力与其值成正比，局部寻优能力与其值成反比；反之，粒子局部寻优能力强，全局寻优能力弱。即，值过大，则容易错过最优解；值过小，则算法收敛速度慢或是容易陷入局部最优解。当问题空间较大时，为了在搜素速度和搜索精度之间达到平衡，故本文采用动态惯性权重式(29)，使算法在迭代初期有较高的全局搜索能力以得到合适的种子，而在后期有较高的局部搜索能力以提高收敛精度，随着迭代次数地增加，w不断减小，进而使算法在初期有较强的全局收敛能力，而后期有较强的局部收敛能力。

式中，wmax表示最大惯性权重；wmin表示最小惯性权重；t表示当前迭代次数；tmax表示算法最大迭代次数。

3.2 自适应变异

在算法迭代初期，种群个体的差异性较大，为避免产生不良解，同时为使算法快速收敛，应以较小的概率进行变异。在迭代后期，种群个体多样性逐渐降低，为避免算法陷入局部最优[14]，应以增大个体的变异率。

式中，Pmmin表示最小的变异概率，取值为0.01；Pmmax表示最大的变异概率，取值为0.1。t表示当前的迭代次数；tmax表示最大的迭代次数；Di表示粒子i到当前最优解的欧氏距离；Dmax表示种群中离当前最优解最远的粒子i的最大欧氏距离。

4 算例分析

以电气配件制造车间为例进行本文的实例验证。该车间的电气配件制造工序包括铆接、压线、点焊、攻牙、喷印、移印、预装配、总装配等。该厂装配车间有一个原料仓库，其中包括4个立体仓库，3个堆垛机，车间有15个加工工位，编号1-15，车间呈S型分布，分布步长为5米，每个加工工位前有1台线边机械手，6台激光引导式AGV。AGV负责原料和在制品的配送。该车间个搬运设备参数如表1所示，各工作站点间的车辆行驶时间如表2所示，0表示原料仓库，各加工工位间的距离如表2所示。
本文以固定的搬运任务数和固定使用的AGV数分别进行实验，并分别考虑在交叉路口避碰和不考虑避碰的两种情况进行对照。算例1搬运任务为40，堆垛机数3，AGV数为3；算例2搬运任务为40，堆垛机数3，AGV数为6；算例3搬运任务为70，堆垛机数3，AGV数为3；算例4搬运任务为70，堆垛机数3，AGV数为6。

表1车门搬运设备实际参数表

表2 各工作站点间距离表

实验结果如表3所示，搬运任务数相同时，AGV在交叉路口的耗时与AGV数量成正比，总完工时间与AGV数量成反比。AGV数量相同时，AGV在交叉路口的耗时和总完工时间均与搬运任务数成正比，即固定AGV的使用数量，搬运任务越多，AGV在交叉路口的耗时和总完工时间都随之增加。
1）交叉路口考虑避碰
实验结果如表4所示，考虑AGV在交叉路口的避碰情况，每个算例中AGV在路口的等待耗时均有不同程度的减少，随着AGV数量或者搬运任务数量的增加，

表3 交叉路口不考虑避碰的实验结果表

AGV在路口的碰撞可能性增加，使得AGV在路口的等待耗时减少效果较为明显。
将在交叉路口不考虑避碰规则和考虑避碰规则两种情况进行对比，如图6和图7所示，算例1-4在考虑避碰规则下，路口等待时间和总完工时间都有一定程度的减少，即在考虑交叉路口避碰的情况下，多设备协同作业的总完工时间、路口等待时间和作业效率都有所提高。

表4 交叉路口考虑避碰的实验结果表

2）结果对比

图6 两种情况的交叉路口等待耗时图

图7 两种情况的总完工时间图

3）算法性能比较
通过算例2将本文的优化自适应PSO与传统PSO进行比较，由图8和表5可知，在迭代初期，算法趋于快速收敛，在25代左右寻得次优解。在迭代后期，基于自适应变异概率，其概率值增大，算法的搜索空间得以增大，在35代左右找到全局最优解。优化自适应PSO在解的变化和种群均值的变化都更为稳定且收敛速度更快。

表5 算法运算结果比较表

图8 目标函数变化曲线图

5 结语

本文针对智能工厂中多搬运载体的协同作业问题，建立以总任务完工时间最少为主决策目标和以惩罚成本最低为辅助决策目标的协同作业优化模型。考虑AGV在交叉路口的避碰规则，AGV在检测以互容和不容两种相位判断多辆AGV是否可以同时在交叉路口通行，针对处于不容相位的AGV，通过动态调整行车优先级规则，以最大程度上保证任务执行的准时性。协同作业模型采用优化PSO算法求解，为避免在迭代后期陷入局部最优，引入遗传算法中的自适应变异，增强算法搜索解的维度空间。以电气配件制造装配车间为实例，以控制变量法对在交叉路口考虑避碰规则和不考虑避碰进行对比，结果表明在路口等待时间和总完工时间上，考虑避碰规则的结果都优于不考虑避碰的情况。将优化PSO算法和传统PSO进行同模型同算例对比，结果表明在最优解、种群最优解均值和收敛次数上优化自适应PSO算法呈较为明显优势。

参考文献：

[1] 陈敏,黎展滔,陈庆新,等.考虑有限物流运输能力的智能车间AGV调度算法研究[J].工业工程,2019,22(4):49-57.
[2] 贺长征,宋豫川,雷琦,等.柔性作业车间多自动导引小车和机器的集成调度[J].中国机械工程,2019,30(4):438-447.
[3] 刘旭,楼佩煌,钱晓明,等.基于改进遗传算法的物料配送多AGV调度优化[J].机械设计与制造工程,2015,44(3):16-21.
[4] 岳笑含,许晓健,王溪波.面向FMS基于改进的混合PSO-GA的多AGV调度算法研究[J].计算机科学,2018,45(S2):167-171.
[5] Abdelmaguid T F, Nassef A O, Kamal B A, et al. A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles[J].International journal of production research,2014,42(2):267-281.
[6] 胡杰杰.面向制造车间柔性物流的AGV群控系统研制[D].北京邮电大学,2019.
[7] 肖萌.基于混合遗传算法的电力设备检测柔性调度研究[D].武汉理工大学,2018.
[8] 肖海宁,楼佩煌.自动导引车系统避碰及环路死锁控制方法[J].计算机集成制造系统,2015,21(05):1244-1252.
[9] 乔岩,钱晓明,楼佩煌.基于改进时间窗的AGVs避碰路径规划[J].计算机集成制造系统,2012,18(12):2683-2688.
[10] Belhaiza S, Hansen P, Laporte G. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows[J].Computers & Operations Research,2014,52:269-281.
[11] Belhaiza S. A game theoretic approach for the real-life multiplecriterion vehicle routing problem with multiple time windows[J]. IEEE Systems Journal, 2016,12(2):1251-1262.
[12] Lau H Y K, Zhao Y. Integrated scheduling of handling equipment at automated container terminals[J].International journal of production economics, 2008,112(2):665-682.
[13] 李珍惜.基于激光导航AGV路径规划与避障算法的研究[D].西安科技大学,2019.
[14] Mousavi M, Yap H J, Musa S N, et al. Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization[J]. PloS one,2017,12(3):e0169817.
[15] Ma Y, Xu J. A cloud theory-based particle swarm optimization for multiple decision maker vehicle routing problems with fuzzy random time windows[J].Engineering Optimization,2015,47(6): 825-842文章来源于AGV吧