基于ISSA和IA*的AGV集成作业调度及其路径规划*

基于ISSA和IA的AGV集成作业调度及其路径规划

2024-03-01张天瑞

组合机床与自动化加工技术 2024年2期

张天瑞,刘悦

(沈阳大学机械工程学院,沈阳 110044)

0 引言

随着科学技术的飞速发展,制造业作为高耗能、高排放的产业,据不完全统计全球每年约产生7亿吨有害废物和55亿吨无害废物。同时,碳排放量的增加会与碳达峰、碳中和的目标形成矛盾。因此,推动制造业低碳、绿色发展具有良好的研究意义。目前在工业4.0背景下,自动导引运输车(automatic guided vehicle,AGV)在工业领域代替人工完成运输作业,随着现代化工厂的发展,越来越多的工厂对AGV的需求量也不断扩大,提高AGV的效率将加快现代化工厂建设[1]。

由于实际生产车间问题的高度复杂性,大多学者使用智能优化算法来解决问题,如蚁群优化算法[2]、洗牌蛙跳算法[3]、果蝇算法[4]、粒子群优化算法[5]等。这些优化算法已被应用于低碳调度,如文笑雨等[6]通过高维低碳调度模型弥补了多目标空间选择压力不足的不足,ZHANG等[7]将果蝇优化算法用于优化最小化完工时间的双资源约束的柔性作业车间调度问题等。

根据AGV路径搜索策略的不同,路径搜索算法可以分为仿生算法、几何模型搜索算法和基于插值的算法。RIAZI等[8]提出一种全新的启发式算法用于解决自动引导车辆无冲突调度和路由问题。邹裕吉[9]提出一种基于Dijkstra和时间窗的多目标聚类遗传算法对AGV无冲突路径进行研究。杨周等[10]提出了一种将蚁群算法和动态窗口相结合的全局动态路径规划算法。潘纹等[11]考虑了配送成本和生产效率提出了一种动态步长果蝇算法。SMOLIC等[12]提出利用向量形式的时间窗口动态求解最短路径问题的路由方法。HU等[13]针对静态路径规划中的低优先级任务的时间窗进行更新,从而避免了车辆之间的冲突和碰撞。LINA[14]基于粒子滤波来混合布谷鸟遗传算法进行聚类分析,可以更有效地处理带时间窗的车辆路径规划任务。

目前,针对贪婪算法的优化能力已被多次证实其在优化其他算法方面的有效性。高珊等[15]利用贪婪随机自适应搜索算法的构造阶段来生成初始解。王迪等[16]将贪婪交换技术应用到鲸鱼优化算法中,提高了算法的收敛速度。李霄鹏、王凌等[17-19]均将贪婪算法与其他算法进行融合后得到了更好的仿真结果。PETKE[20]通过约束CIT测试集生成的遗传算法,得出贪婪算法比模拟退火算法在计算时间方面具有更好的结果。

综上所述,前人对AGV调度和路径规划问题的优化研究虽然取得了较好的进展,但同时考虑能耗的相关研究尚有不足。基于此,本文提出了基于改进飞鼠搜索算法(improved squirrel search algorithm,ISSA)和优化A*融合算法的AGV调度和路径规划双层优化模型,通过测试函数与仿真实验,验证其可行性、有效性和优越性,为提高AGV集成作业调度效率和路径规划安全避障研究提供新的思路和方法。

1 问题描述及数学模型要求

1.1 问题描述

本文针对AGV集成作业调度问题建立双层规划模型,上层为考虑最小化成本和最小化能耗碳排放的集成作业调度模型,下层为基于时间窗的AGV最优路径规划模型。由于AGV系统中通常有多辆车辆,因此需要通过作业调度和路径规划来解决车辆之间的运动冲突。特别是应防止车辆碰撞和死锁,以避免运行中断。本模型与传统AGV路径规划模型区别在于:将作业调度和路径规划分别作为上下双层模型进行建模;同时加入绿色碳排放因素,将现实性和易处理性作为原则进行建模,简化问题存在以下假设:

(1)AGV的初始位置为仓库边缘起点,并以一定的间隔时间随机出发。

(2)AGV完成运输任务后停靠在机器旁边。

(3)使用最短路径算法,生成每个车辆的路径。

(4)各AGV运输能力相同,每次只能完成一个工件的运输任务。

(5)每条路径在同一时刻只允许一台AGV通过,且任意路径可容纳AGV的车身。

(6)调度周期内AGV与加工设备不会发生故障,AGV电量充足。

(7)AGV运行过程中保持匀速,行驶时车轮不打滑。

(8)不考虑AGV的装载和卸载时间,即AGV的装载和卸载时间均为0。

(9)不考虑设备故障、设备停电等不确定因素的影响。

1.2 数学模型

为了更好地理解本文所建立的模型和目标函数,首先将涉及到的主要参数进行定义,如表1所示。

表1 相关参数和定义

(1)上层模型。AGV能耗计算:AGV车辆的二氧化碳排放量是由BEKTA等[21]提出的瞬时燃料消耗模型计算出来的。车辆燃料消耗模型不仅是距离函数,而且是由车辆的行驶距离、载货量和弧线速度组成的函数。本文问题定义在一个完整的有向图G=(X,A)上,其中节点为X={0,1,2,…,x},同时也包括目标位置{1,2,…,x}和一个点0共同组成。弧A表示节点之间所有可能的连接,定义为{(m,n):m,n∈X,i≠j}。AGV在孤(m,n)上每辆AGV的所需要消耗的总机械功率计算如式(1)所示。

(1)

需要通过式(2)来计算电弧中的电弧比常数(m,n);其中,g表示为重力常数(m/s2)为9.81,Cr为滚动阻力系数0.01。

αmn=α+gsinθmn+gCrcosθmn

(2)

为计算运行中每辆AGV车辆碳排放量,如式(3)所示。

Cbmn≈～207.68×Emn·r

(3)

EPmn为本研究使用的效率值;其中effm=1.2,effd=1.1,effp=0.75,Efftotal估计为1.00。

EPmn≈effm·effd·effp·Pmn

(4)

式(5)为最小化AGV最大允许行驶时间:

(5)

(2)下层模型。为了在最大程度上减少AGV车辆的冲突和死锁,采用单向导引路径网络(unidirectional guide path network,UNG)来降低对路径的管理难度,使得AGV车辆只允许单向行驶且两条相邻路径的方向保持反向行驶,即wij≠wji。i,j为路径网络节点编号,i,j=1,2,…,k为AGV行驶路径编号,k=1,2,…,k,其中Vk为路径k中所有节点的集合。v(k1,k2)为路径k1和k2中相同节点的集合。对AGV进行路径规划,在AGV车辆运行过程中,停车等待和重新路径规划是解决路径冲突的最常见的策略。w为路径网络中路段的集合,其中wij={i→j,i,j∈V},表示节点i到节点j之间的距离;w(k1,k2)为路径k1和k2中重叠路段的集合,wij≠wji表示AGV车辆保持单向行驶状态。

采用二维空间有限地图栅格图对AGV运行路径进行模拟仿真,以20×20为例,划分后的栅格图如图1所示,栅格图建模流程如图2所示。

图1 栅格地图示例

由多个规则矩形组成(障碍物空间和自由空间),障碍物空间为车间设备等物品无法进行行驶,自由空间是AGV车辆可行进的路径。障碍物由黑色区域表示,自由行进空间由白色区域表示,为了保证AGV车辆可以在车间内正常同行,实际生产车间中会存在一些不规则的障碍物,将其补偿为矩形。

1.3 飞鼠搜索算法

飞鼠搜索算法(squirrel search algorithm,SSA)是一种性能良好的群智能算法[23],旨在描述南方飞鼠觅食和躲捕食者的过程中进行滑翔的行为,是一种有效的节省觅食成本的方式,通过建立解决全局最优问题的模型,完成对复杂问题的求解。图3为飞鼠搜索算法的基本搜索过程。

图3 飞鼠搜索算法流程图

(1)随机初始化:假设森林中存在N只飞鼠,通过矢量来确定森林中每一个飞鼠的位置。通过式(6)随机确定飞鼠初始位置。

FSij=FSi,L+U(0,1)×(FSi,U-FSi,L)

(6)

式中:FSij是第i只飞鼠在第j维上值,U、L是第j维的上界和下界,U(0,1)是处于0和1间的均匀分布值。

(2)适应值排序和随机选择:飞鼠的适应值由食物源等级进行排序,包括3种类型:最佳食物源、正常食物源和无食物来源,分别代表的是山核桃树、橡树和普通树。将适应度值最小的飞鼠将留在山核桃树上,接下来的3只飞鼠将停留在橡树上或是选择是否向山核桃树移动,其余飞鼠则留在普通树上。

采用随机选择的方法来选择出已满足日常能量的飞鼠并向山核桃树飞行,其余则往橡树进行移动。同时飞鼠觅食过程中会遇到天敌,根据天敌出现的概率来决定飞鼠的移动策略。在飞鼠搜索觅食过程中存在以下3种情况,分别如式(7)～式(9)所示。

①停留在橡树上的飞鼠向山核桃移动。

(7)

②停留在普通树上的飞鼠向橡树移动。

(8)

③部分吃了橡果的飞鼠停留在普通树上,但它们也可能会向山核桃树移动来储存食物。

(9)

(10)

式中:hg=8 m是飞鼠滑行后发生的高度差量,需计算dg所有参数值,5～25 m是普通飞鼠正常一次滑行的水平距离,在该算法中,dg控制在9～20 m的范围里。

(11)

(12)

式中:t是当前迭代次数,mt为最大迭代值,算法的全局和局部搜索能力Smin值的影响,滑动常数Gc用于平衡搜索能力,也可以在迭代中自适应地改变Smin值来实现。若满足季节变化条件,则随机选择变换普通树上飞鼠的位置,得到位置如式(13)所示。

(13)

1.4 A*算法

A*算法是由Dijkstra进化而来的,本质上两者是相同的,由于Dijkstra算法缺少启发式,导致其需要对每个方向上同时按照均匀的速度进行搜索拓展。这使得其搜索效率极大降低,增加了许多无效的搜索区域,相对于A*算法搜索速率较慢。

传统A*算法是在静态环境下对路径搜索的启发式算法,对路径进行全局搜索,在一定程度上避免了无效路径,提高了搜索效率。根据目标位置和全局地图进行全局路径规划,将搜索区域划分成正方形格,简化搜索区域,节点作为方格的中心点。A*算法的核心就是对方格移动的节点数量的计算,其函数如式(14)所示。

F(x,y)=G(x,y)+H(x,y)

(14)

A*算法可以通过对H值的预先估计有效地降低寻路走弯路的可能性,相对于其他算法更高效寻找到距离最小路径。由于其他寻路方法缺少启发性算法,只是针对路径进行一一列举再依次寻找最短路径,这使得A*算法相对于其他算法具有更强的鲁棒性。

原始A*算法针对起始点到单个节点的路线进行搜索,其全局规划的路径会存在拐点,转弯次数过多会影响AGV运行时间。因此,本文引入时间因子和安全距离因子,提出一种优化A*算法,在剔除多余拐点同时增加路径安全性达到优化AGV运动路径的目的。

2 算法设计

2.1 优化飞鼠搜索算法

2.1.1 贪婪策略优化初始种群

初始种群的质量对算法的求解质量和收敛速度有非常大的影响,根据柔性作业车间特点,提出了基于贪婪策略优化飞鼠搜索过程的算法,对飞鼠搜索算法初始种群进行贪婪处理,生成局部最优的初始种群来提高搜索能力,针对具体执行飞鼠位置随机初始化过程为:

针对森林中M个飞鼠,采用均匀分布对每个飞鼠位置进行初始化,针对初始种群进行依次迭代采用贪婪策略,建立上一次迭代的飞鼠位置与当前迭代的飞鼠位置的排序映射,求得上下两代优秀飞鼠个体并记录当前最优解。将第N次迭代和N-1次迭代的优秀个体均进行保留处理,并依次代入位置进行更新迭代直至结束,具体流程如图4所示。

图4 贪婪初始化飞鼠搜索算法流程

通过贪婪策略来对飞鼠搜索算法的种群初始化由于原有飞鼠搜索算法初始解是随机方式生成,该方式生成初始种群对求解结果影响较小。大部分研究表明,随机生成的可以有效地保证种群的多样性,但非随机生成的方法有可能会产生高质量的解。部分策略初始化伪码为:

fitness=zeros(1,pop);
for i=1:pop
fitness(i)=fob j(FS(i,:));
end
[～,index]=sort(fitness);
GBestF=fitness(index(1));
GBestX=FS(index(1),:);
curve=zeros(Max_iter,1);
curve(1)=GBestF;

FS0=x_ini;
FS1=Tent Initialization(pop,dim,ub,lb);
FS=[FS0;FS1]

2.1.2 编码和解码操作

本文采用的编码方式为机器工序双层编码方式,编码方式示例如图5所示,每个工序编码对应一个数字从左到右,表示其工序加工顺序。工序层编码为“13213231”,其中第1个位置上的数字“1”表示工序O1,1,第2次出现的数字“1”表示工序O1,2,第3个位置上的数字“2”表示工序O2,1,第5个位置上的数字“3”表示工序O3,2,以此类推。

图5 工序机器编码图

机器编码中每台机器对应一个的数字,机器编码的每个整数对应其数字下工序所选择的机器序号,机器加工依次顺序从左至右进行。机器层编码为“13211323”,第1个位置上的数字“1”表示为工序O1,1在机器M1上加工,第3个位置上的数字“2”表示工序O2,1在机器M2上进行加工。

本文解码方式采用全主动解码,为了更清楚的展示给出了一组实例的解码过程,其初始工序序列为[3,1,3,2,1,3,2]。图6为半主动调度解,在机床M1上,工序O1,1前存在可允许O2,2插入的空闲时间;在前存在可允许O3,3插入的空闲时间;在机床M3上,工序O1,2前存在可允许O2,1插入的空闲时间。半主动调度解可获得Cmax为8的半主动调度解,全主动解码可获得Cmax为8的全主动调度解,全主动调度解码后的工序序列更新为[1,2,3,2,3,3,1]。

图6 半主动调度解

解码具体过程为:首先依次读取工序编码串,在机器编码部分找到与其工序Oij对应的机器Mn信息并提取;在机器Mn上选择空闲时间段[Tp,Tq],分别为空闲时间的开始时间和结束时间。判断[Tp,Tq]是否大于Tij的加工时间,若满足Tij的加工时间则选择Oij插入到[Tp,Tq]空闲时间段内,否则将工序Oij移动到机器Mn上进行加工,当Mn完成全部工序加工时再对工序Oij进行加工,具体如图7所示。

2.2 优化A*算法

2.2.1 安全距离因子

传统A*算法在计算节点估价函数时,节点周围并无惩罚值产生,AGV无法延时转弯这必将会增加转弯操作从而增加AGV行驶时间。同时,全局路径规划中无法保证其安全性,也存在过多的冗余节点、运动轨迹转弯过多的情况。通过对AGV机器人和障碍物之间的最大距离进行比较,在保证运输路径安全的同时优化AGV运输路径。本文基于以上问题提出了基于安全距离因子的优化A*算法,目的为AGV减少转弯次数和提高路径安全性。安全距离因子如式(15)所示。

(15)

式中:lmax为机器人与障碍物间的最大距离,lmin为机器人与障碍物间的最小距离,lxy为机器人当前位置与障碍物之间的距离。

引入安全距离因子后的传统A*算法的估价函数如式(21)所示,更新后A*算法流程如图8所示。

(16)

图8 引入安全因子A*算法流程

2.2.2 路径平滑

由于AGV的能耗受到运行时间和运行路径的影响,AGV移动路径的节点越多从而会增加路径运行的时间,导致多余能耗的浪费。对A*算法路径规划中的冗余节点进行处理,减少多余的节点平滑路径,缩短AGV最短移动路径。因此,本文基于梯度下降法对所有路径点进行迭代优化,以减少路径中的非必要的转弯节点,节约运行时间和能耗。

具体操作过程为:从起点开始进行,依次选择起点后相邻的5个路径中的节点来定义平滑度与路径节点的关系,并将第3个节点进行位置移动,若相邻两个节点2和节点4之间没有障碍物且连接后路径可移动的范围内则保留新路径。将原先节点3剔除,直接从节点2移动至节点4,直线缩短AGV移动距离,梯度方向保留原先节点3的移动方向,使得5个路径节点的平滑度达到最小值。若移动节点3位置后移动范围之间有障碍物且无法达到安全距离因子,则保留原先节点路径。依次历遍全部节点直至选取目标节点结束操作。

定义节点的最优位移为ΔP,ΔP的大小为移动距离且移动方向为梯度方向。通过平滑度对ΔP的一阶导等于0可求得梯度方向如式(17)所示。

(17)

3 实验仿真与结果分析

3.1 标准函数和基本算例验证

为保证测试实验的客观性和公平性,不同的算法均使用相同的硬件和软件平台,硬件环境为Intel(R)Core(TM)i5-7200UCPU@2.50 GHz,软件环境为Win10操作系统上的MATLAB 2018b仿真软件,所有算法的种群规模设为40,最大迭代次数设为1000。依次采用SSA、ISSA和PSO对Sphere、Rosenbrock、Rastrigrin、Geriwank、Schafferf6和Ackley六个函数进行20次理论极值的搜索。针对优化算法分别采用3个多峰函数和3个单峰函数进行测试,测试函数如表2所示。测试函数实验结果的迭代曲线图如图9～图14所示。

图9 f1(x)函数的收敛曲线

图11 f3(x)函数的收敛曲线

图13 f5(x)函数的收敛曲线

表2 6个测试函数信息

由表2和图9～图14的测试结果可知,本文提出的ISSA算法针对单峰测试函数与多峰测试函数的寻优效果都是最优的,并且对于函数f1(x)、f2(x)、f3(x)、f5(x)、f6(x)中都可以搜索得到理论的全局最优值,此外ISSA在这5个函数结果得出的标准差都是极小的,说明ISSA具有良好的鲁棒性。在测试函数f4(x)中,SSA算法与PSO算法的寻优表现均相对较差,而利用ISSA算法对测试函数f3(x)进行寻优时,ISSA在迭代125次时即可快速收敛达到最优值,说明该算法的寻优能力更强。对于6个测试函数而言,ISAA算法在实验结果中的数据均优于SSA算法与PSO算法,得出结论ISSA算法的寻优精度和寻优能力更强。

为了保证优化飞鼠搜索算法在FJSP问题中的有效性,采用文献[24]中的8×8和10×10经典问题实例进行测试,在经典实例中,均给出了工件数量、并行机数量、加工时间等详细加工数据。其中SSA和ISSA的种群规模设为40,最大迭代次数设为50。Cmax表示最大完成时间,Aver表示算法50次求得最优值的均值,比较结果如表3所示。

表3 8×8和10×10案例结果对比

从表3可看出SSA和ISSA算法在8×8和10×10算例中均能找到最优解,且ISSA寻优结果优于SSA,说明ISSA算法具有较好的寻优能力。10×10算例的最优解甘特图如图15b所示,横坐标为抽象作业单位的加工时间,纵坐标为机器序号,同一种颜色代表同一个工件。SSA和ISSA最大完成时间分别为8和7,ISSA算法找到该算例的最优解。

(a) 优化前 (b) 优化后

3.2 优化A*算法验证

为验证优化A*算法可行性,本文利用栅栏图建模进行环境模拟,采用MATLAB 2018b进行仿真验证。首先为了保证优化A*可以在障碍物分布复杂且环境空间大的情况下的性能,环境模型的搭建基础,分别设置了30 m×30 m和40 m×40 m的栅格地图。为了验证论文所提出方法的有效性,进行了多组仿真对比实验,仿真结果如图16所示,灰色优化前的路线,黑色为优化后的路线。每辆AGV的最短路径长度、拐点数量和运行时间如表4所示。