基于改进的粒子群算法的多目标点路径规划 [PDF全文]
(浙江科技学院 机械与能源工程学院,杭州 310023)
针对无人仓储系统中自动导航车(automated guided vehicle,AGV)遍历多个目标点路径非最优的问题,结合Three.js三维仿真技术构建的孪生仓储系统,提出一种改进的粒子群(particle swarm optimization,PSO)算法求解虚拟场景内多目标点路径方法。首先利用栅格法构建场景的栅格地图,同时采用A-Star算法对地图中两两目标点进行规划,得到多目标点的完全图模型; 然后将育种学中远缘杂交策略引入PSO算法中,通过亲缘关系较远种群间的杂交,避免了种群多样性下降的问题,提高对模型的求解能力; 最后以系统内实例进行试验验证。结果表明,我们所提方法能实现多目标点的路径求解,与传统算法相比,改进算法在规模较大的问题上更具优势,在规划性能方面提高3%以上。本文算法更易获得多个目标点运送的较短路径,这可为后续同类问题的研究提供参考。
Multi-objective point path planning based on improved PSO algorithm
YUAN Bin, WANG Weibo, WANG Hui
(School of Mechanical and Energy Engineering, Zhejiang University of Science and Technology, Hangzhou 310023, Zhejiang, China)
In response to the problem of the non-optimal path of multi-objective point traversed by the automated guided vehicle(AGV)in the unmanned storage system, an improved particle swarm optimization(PSO)algorithm was proposed to solve the multi-objective point path in the virtual scene in combination with the twin storage system based on Three. js 3D simulation technology. Firstly, the grid map of the scene was constructed by virtue of the grid method. Meanwhile, the A-Star algorithm was used to plan the pairwise target points in the map, obtaining a multi-objective complete graph model. Then, the distant hybridization strategy in breeding science was introduced to the PSO algorithm. Through the hybridization between distant phylogenetic populations, the problem of population diversity decline was avoided, improving the solving ability of the model. Finally, several groups of examples in the system were used to test and verify. Results reveal that the proposed method can achieve multi-objective point path solving. Compared with the traditional counterparts, the improved algorithm has more advantages in large-scale problems, boosting the planning performance by more than 3%. The proposed method is easier to obtain a shorter transportation path between multi-objective points, which provides reference value for the follow-up research on similar problems.
引言

当今电子商务、物流市场的巨大规模和爆发式增长,推动着物流体系向更加高效、智能的方向发展。以无人仓储、无人搬运车等为代表的物流无人化技术成为推进物流产业进一步发展的新动力[1]。在无人仓储系统中,自动导航车对物品进行运送作业的时间占整个系统作业时间的50%~60%,而拣选作业的时间由自动导航车运送时间和存/取货时间两部分组成,其中对单个商品存取时间基本上不变[2]。因此,优化运送路径,对促进无人物流行业的进一步发展具有重要意义。

常用的路径规划方法按其环境是否已知,分为全局路径规划和局部路径规划。对于环境已知的全局路径规划,方法有栅格法[3]、神经网络法[4]及可视图法[5]等; 对于环境未全知的局部路径规划,方法有模糊逻辑算法[6]、人工势场算法[7]及人工蜂群算法[8]等。以上方法在实际路径规划中存在规划结果不佳或规划效率较低的问题,因此在这些方法的基础上涌现了很多改进的路径规划方法。胡立华等[9]提出一种基于蚁群算法的动态路径规划方法,对初始信息使用不均匀分配方式,并在转移概率中引入邻域安全因子,提高了路径规划效率。周驰等[10]在粒子群(particle swarm optimization,PSO)算法基础上结合动态惯性权重、变邻域搜索等策略设计了一种混合PSO算法对窄巷道仓储内拣选路径求解,缩短了拣选作业的路径时间。蔺一帅等[11]将路径规划和货架优化归为一个整体,提出了一种协调优化的算法,提高了仓储内的运输效率。以上算法和模型仅解决了点对点的最优路径规划,然而无人仓储系统内自动导航车(automated guided vehicle,AGV)实际运送过程中的目标点往往并非单一点,对多个目标点的访问路径进行规划才能更贴近实际情况。

针对无人仓储内多目标点路径规划的问题,本研究以基于数字孪生思想构建出的虚拟仓储系统为研究对象,由A-Star算法建立仅保留多目标点间节点关系的完全图模型,并提出了一种改进的PSO算法对模型求解,通过结合作物育种学中远缘杂交思想,提高了对模型的求解能力,更易得到孪生仓储系统内多目标点的最优路径。

1 基于数字孪生的仓储场景设计

本文所述多目标点路径规划问题的研究场景为基于数字孪生思想构建的仓储系统,系统主要包括AGV运动实际场景、AGV运动的虚拟场景及作为孪生数据的多目标点路径,基于数字孪生的仓储系统如图1所示。

图1 基于数字孪生的仓储系统<br/>Fig.1 Storage system based on digital twin

图1 基于数字孪生的仓储系统
Fig.1 Storage system based on digital twin

实际场景运行所用AGV为笔者自主设计的基于视觉和射频识别(radio frequency identification,RFID)的复合式导航AGV,在运行环境内的地面上嵌入存有位置信息的无源射频卡,AGV在运行过程中通过前端的摄像头及底部的RFID传感器识别和读取当前位置信息,实现对AGV的导航和定位功能。虚拟场景是基于Three.js3D引擎和超文本5.0构建的数字孪生仓储系统,其尺寸按照实际比例的场景进行设计。场景由位置固定的货架及运动的AGV模型构成,其中AGV模型由实际AGV的装配体文件转换为模型文件和材质文件后导入场景中。虚、实场景内的AGV沿孪生数据中的多目标点轨迹行驶,并通过WebSocket通信协议实时通信完成虚、实场景内的位置同步,以达到对无人仓储环境中AGV运行的监控目的。

2 基于远缘杂交策略的多目标点路径规划2.1 构建栅格化地图

本研究采用栅格法对孪生仓储环境地图进行建模,虚拟场景俯视图和栅格地图如图2所示。虚拟场景栅格化后对应的栅格地图用像素为350×312的图像表示,其中黑色的区域代表障碍区域,白色区域代表非障碍区域,货架的每个货位在栅格地图中都对应一个驻停点且坐标已知。

图2 虚拟场景俯视图和栅格地图<br/>Fig.2 Top view and grid map of virtual scene

图2 虚拟场景俯视图和栅格地图
Fig.2 Top view and grid map of virtual scene

2.2 A-Star算法构建图模型

A-Star算法是一种在静态网格地图中求解点对点最优路径的启发式算法,相比其他启发式算法具有准确度高、速度快的优点[12]。由于虚拟仓储对应栅格地图中两两目标点间可任意连通,因而可将A-Star算法规划所得多目标点间路径简化为图论中的完全图,完全图中节点表示场景内AGV需访问的目标节点,边表示由规划路径仅保留两端节点关系抽象出的线段,且用该路径的长度作为边的权值。

A-Star算法搜寻路径节点过程中估价函数为

f(n)=g(n)+h(n) (1)

式(1)中:f(n)为起点到目标点的总代价; g(n)为起点到当前节点n的实际代价; h(n)为当前节点n到目标点的估计代价。

AGV在场景中的运动方式偏向于欧氏距离[13],因此本研究采用欧氏距离作为启发式函数:

式(2)中:xi和yi分别为当前节点在栅格化地图中的横、纵坐标; xn和yn为目标节点在栅格化地图中的横、纵坐标。

图3 构建5个目标点的完全图模型<br/>Fig.3 Complete graph model by constructing five target points

图3 构建5个目标点的完全图模型
Fig.3 Complete graph model by constructing five target points

假设目标点的个数为N,即形成一个含有N个节点的完全图Kn=(V,E),V和E表示2个集合,其中元素分别为完全图Kn中的节点和边,每对不同节点间有且只有一条边相连接,所以E中元素是V的2元子集,即集合E中包含N(N-1)/2个元素。以场景内4个目标点为例,则包括AGV初始位置需构建完全图K5,K5中包含5个顶点和10条边。构建出5个目标点的完全图模型如图3所示。

2.3 改进的PSO算法的全局规划

多目标点完全图的构建是将多目标点路径规划转化为旅行商的组合优化问题,即在完全图中求解一组编号顺序,使得两两相邻编号对应边的权重和最小。

本研究采用离散的PSO算法[14]对完全图求解,并在传统PSO算法基础上引入基于远缘杂交的更新策略。该策略将初始种群进行划分,多个种群相互独立进化,迭代过程中将亲缘关系差异较大的种群进行杂交操作,并用杂交后代对种群更新,以提高种群的多样性,从而优化求解效果。

2.3.1 离散的PSO算法

当搜索空间为N维时,粒子群中第i个粒子的位置可用向量xi=(xi1,xi2,…,xin)表示,该粒子的速度可用向量vi=(vi1,vi2…vin)表示,其中下角标i1,i2…in表示向量xi和向量vi在N维空间内不同维度的分量; 每个粒子所经历过的最优位置称为个体历史最优位置,记为p; 整个粒子群所经历的最优位置称为全局历史最优位置,记为g。各粒子迭代过程中,通过对p和g进行学习来更新自身的位置xi和速度vi,逐渐向最优解靠近。根据PSO算法处理离散域中交换子和交换序的定义,粒子的速度和位置更新公式[15]可描述为

式(3)~(4)中:ω为非负的惯性权重; α(p-xti)为以概率α保留从p到第t次迭代第i个粒子对应的交换子,α∈[0,1]; 运算符为交换子合并运算; β(g-xti)为以概率β保留从g到第t次迭代第i个粒子对应的交换子,β∈[0,1]。

迭代过程中,由适应度函数得到粒子更新后的适应度值,并与粒子的p及粒子所处粒子群的g进行比较,从而更新p和g。单个粒子的p更新公式如下:

式(5)中:上角标k为粒子所处迭代次数; 下角标i为粒子群中的第i个粒子; f(xk+1i)为迭代至第(k+1)次第i个粒子对应的适应度函数值。

单个粒子群内g更新公式如下:

2.3.2 粒子个体编码

基于多目标点路径规划模型和完全图的特点,采用整数排列方式编码。单个粒子的编码序列代表一个完整的运送方案,起始位置始终从0开始,如粒子信息为(4,1,3,2,0)代表的拣选路径为:起始位置(0)—货物4—货物1—货物3—货物2—起始位置(0),不同粒子对应不同的目标点访问顺序。

2.3.3 适应度函数

根据多目标点路径规划的优化目标和完全图,得到的适应度公式和距离矩阵为

式(7)~(8)中:x为单个粒子; m为粒子的长度; i为粒子的位置; xi为粒子中第i个位置对应的编号; D(xi,xj)为编号xi到编号xj的距离dxi,xj; D为带权完全图得到的距离矩阵,满足D=DT,dm,n=dn,m; dm,n为(m-1)与(n-1)对应边的权重。

2.3.4 基于远缘杂交的更新策略

本研究受作物育种学中远缘杂交思想[16]的启迪,在PSO算法中引入远缘杂交的策略,分为3个步骤:对种群进行划分; 计算不同种群间亲缘关系的远近程度; 获取杂交后代并更新粒子群。基于远缘杂交的更新策略具体步骤如下:

1)对种群进行划分。将种群规模为n的粒子群划分为规模为m的k个种群,其中k满足m×k=n。在迭代进化中k个粒子群相互独立进化,每个粒子群内单独使用式(5)和式(6)对p和g进行更新,并将单个粒子群内的g作为该粒子群的特征代表粒子参与后续杂交过程。

2)多粒子群间亲缘关系的计算。在迭代陷入局部最优解后,将多个粒子群的特征代表粒子g组成最优解集gs。以窗口长度为2、步长为1的滑动窗口法对最优解集内的两两特征代表进行计算,得到表示亲缘关系远近的S,S初始值为0,取值范围为[0,L]内整数,L表示粒子的维度即目标个数。假设取出2个特征代表A、B,A中以窗口截取相邻编号片段(Pi,Pi+1),在B中滑动窗口从起始位置起依次滑动一个步长寻找是否存在Pi和Pi+1相连片段,若存在则将S的值加1。B中对片段(Pi,Pi+1)搜寻结束后,A中滑动窗口后移得到片段(Pi+1,Pi+2),并在B中重复寻找过程和对S更新。重复上述过程,直至A中的所有相连片段完成寻找过程,得到2个特征代表间的S。图4为表示相同方案的2个粒子,即S=15,图5为亲缘关系为3的2个粒子。

图4 相同方案的2个粒子<br/>Fig.4 Two particles of the same scheme

图4 相同方案的2个粒子
Fig.4 Two particles of the same scheme

图5 亲缘关系为3的2个粒子<br/>Fig.5 Two particles with affinities being three

图5 亲缘关系为3的2个粒子
Fig.5 Two particles with affinities being three

3)更新粒子群。选取亲缘关系较远的g,即S值较小的一对特征代表作为父代双亲,以部分匹配交叉[17](partially matched crossover,PMX)交换双亲粒子内的片段获得杂交后代,并从多个粒子群中选取表现较差的种群,将该粒子群内粒子用杂交后代进行替换,替换比例记为δ。

2.4 多目标点路径规划实现步骤

图6 多目标点路径规划流程图<br/>Fig.6 Flowchart of multi-objective point path planning

图6 多目标点路径规划流程图
Fig.6 Flowchart of multi-objective point path planning

多目标点路径规划流程图如图6所示,步骤可总结如下:

1)使用A-Star算法对多个目标点两两进行路径规划,计算得出两两目标点之间的最短路径及对应长度;

2)以路径长度为权重构建多目标点的完全图,并得到式(8)形式的距离矩阵D;

3)初始化改进粒子群算法参数,将粒子群分为种群规模为m的k个小粒子群,随机初始化各粒子群的粒子,得到各粒子的初始位置xi;

4)使用式(7)和式(8)计算各粒子群中各个粒子的适应度值,记录每个粒子群中每个粒子的p和每个粒子群的g;

5)使用式(3)和式(4)对粒子速度及位置进行更新,并计算更新后的各粒子适应度;

6)每个粒子群内独立使用式(5)和式(6),更新粒子的p及每个粒子群内的g,并将多个粒子群的g放入多粒子群最优解集gs中,其中的最优粒子作为最优值A;

7)是否满足终止条件,是则将点对点路径与A结合得到多点路径,否则转步骤8);

8)是否满足杂交条件,是则从gs中的选取亲缘关系较远的双亲粒子对进行PMX杂交操作,并将gs中适应度值最低粒子对应粒子群以δ的比例用杂交后代进行替换,否则转步骤5)。

3 实例验证与分析

为了验证本文算法的有效性和可行性,以场景内实例进行试验,对改进算法中的相关参数进行分析,并用引入远缘杂交策略的改进的PSO算法与PSO算法、禁忌搜索(tabu search,TS)算法分别对多目标点的完全图进行求解,对试验结果进行比较。试验中最大迭代次数设为100,其中PSO算法中粒子数目设为40,p到粒子交换子的保留概率α设为0.7,g到粒子交换子的保留概率β设为0.8; 改进的PSO算法中上述参数与PSO算法相同; TS算法中禁忌表长度设为20。试验运行环境:操作系统为Windows10,处理器为AMD5800H,CPU为3.20 GHz,内存为16 GB,试验平台为PyCharm2020。

3.1 替换比例δ的试验分析

为验证杂交后代替换粒子群比例δ对路径寻优效果的影响,以场景内20个点作为访问目标点构建完全图,并对δ∈{0,0.2,0.4,0.6,0.8,1}的每个取值分别进行10次试验,记录每次试验的最优路径长度。δ取不同值时本文算法的试验结果、10次结果的平均值分别如图7图8所示,从图中可知,起初随着δ取值的增大,路径寻优的总长度逐渐减小,达到某一阈值后,替换比例的增加会导致寻优效果下降。从结果可知,本试验中当δ=0.6时算法的寻优性能更好。

图7 δ取不同值时本文算法的试验结果<br/>Fig.7 Test results of the proposed algorithm with different values of δ

图7 δ取不同值时本文算法的试验结果
Fig.7 Test results of the proposed algorithm with different values of δ

图8 10次结果的平均值<br/>Fig.8 Average of 10 results

图8 10次结果的平均值
Fig.8 Average of 10 results

3.2 种群划分的试验分析

表1 不同划分方式的10次试验结果
Table 1 Results of 10 trials of different ways of division

表1 不同划分方式的10次试验结果<br/>Table 1 Results of 10 trials of different ways of division

远缘杂交策略中对种群的划分参数直接影响算法的搜索效果,为选取远缘杂交策略中种群的划分个数k和单个种群规模m的最佳值,分别在(m,k)取值为(10,4)、(8,5)、(5,8)和(4,10)且其他参数相同的条件下进行10次试验,结果见表1。由表1可知,在粒子群总规模为40时,将粒子群划分为4个规模为10的小种群,搜索到的路径长度在最短路径和平均值上都更优。

3.3 算法对比试验

为了检验本文算法的优越性,采用场景内目标点个数为15、30、50三种规模的实例进行验证,由A-Star算法构建出实例的完全图后,分别使用改进的PSO算法、PSO算法和TS算法进行10次试验,不同规模下的路径长度迭代收敛对比结果如图9所示。

图9 本文算法与PSO算法、TS算法不同规模下的路径长度迭代收敛对比<br/>Fig.9 Comparison of iterative convergence of path length between the proposed algorithm and PSO, TS algorithms at different scales

图9 本文算法与PSO算法、TS算法不同规模下的路径长度迭代收敛对比
Fig.9 Comparison of iterative convergence of path length between the proposed algorithm and PSO, TS algorithms at different scales

根据图9(a),在目标点规模为15时改进的PSO算法与PSO算法和TS算法相比,搜索到的最短路径略优,但由于搜索空间的复杂度较低,改进的PSO算法的优势不明显。改进的PSO算法、PSO算法和TS算法10次路径长度的平均值分别为683.0、699.7、685.7。

图9(b)和(c)可知,目标点规模增大至30、50时,改进的PSO算法搜寻到的最短路径与PSO算法和TS算法相比表现出更明显的优势。通过观察图9(b)和(c),可以发现在迭代过程中改进的PSO算法的阶梯下降次数最多,TS算法的下降次数最少,即改进的PSO算法在跳出局部最优解的性能更强; 而对下降区域进行观察,可知在迭代前期3种算法的收敛过程差异并不大,主要是因为迭代前期双亲粒子优良特性的片段较少,进行远缘杂交的后代获取到优良特性概率较小。随着迭代过程的进行,粒子群内的优良片段不断汇聚,远缘杂交策略使得不同粒子群长期积累的优良特性得以交换。因此在迭代后期,改进的PSO算法在下降次数上明显多于PSO算法和TS算法,且最终的收敛值更小。改进的PSO算法、PSO算法和TS算法在目标点规模为30时,3种算法所得路径长度的平均值分别为1 037.3、1 120.9、1 078.9,比PSO算法和TS算法规划性能分别提升了7.4%、3.8%; 在目标点为50时,路径长度的平均值为1 782.0、1 988.5、1 841.0,比PSO算法和TS算法规划性能分别提升了10.3%、3.2%。

3.4 虚拟场景内运行测试

采用δ=0.6、m=10、k=4的参数设置,对目标点个数为15的实例进行规划(图 10),实例在栅格地图中规划结果如图 10(a)所示,其中实线表示最优路径,路径的总长度为683,路径1和路径2为多次迭代中出现的较为接近最优解的路径,路径长度分别为708和758。最优路径坐标经过处理后得到AGV在虚拟场景内的运动路径,虚拟场景内AGV的运动过程如图 10(b)所示。

图 10 目标点为15的实例<br/>Fig.10 Example with a target point of 15

图 10 目标点为15的实例
Fig.10 Example with a target point of 15

4 结 语

本研究针对无人仓储系统内AGV多目标点运送路径问题,以基于数字孪生思想构建出的AGV运动虚拟仓储场景为研究对象,结合A-Star算法和改进的PSO算法在虚拟仓储内规划出多个目标点的最短路径。针对PSO算法迭代过程中多样性下降,易陷入局部最优解的问题,利用作物育种学中远缘杂交思想设计了一种改进的PSO算法,提高了种群多样性,更易搜寻到较优解。试验结果表明,该方法在仓库多目标点路径优化尤其是较大规模的问题上具有更好的寻优性能。然而,本文方法仅适用于多目标点间两两互通的仓储场景,今后的研究会考虑更为复杂的场景。此外,将远缘杂交策略应用于其他智能算法之中也可能作为下一阶段的研究目标。

参考文献