一种考虑强连通性的AGV导向路径网络设计优化方法

本发明涉及物流自动化技术，特别是一种考虑强连通性的agv导向路径网络设计优化方法。

背景技术：

1、如图2所示,为依托agv储运系统实现物料流转的智能车间。车间智能化物料流转系统结合了agv储运系统和生产制造系统，以实现高效物料运输和加工流程。生产制造系统由多个加工区域组成，每个区域负责不同工序的物料加工。agv储运系统则由多台单向行驶的agv组成，在车间内的物流通道上铺设单向轨道，形成agv的轨道运输网络。agv沿着轨道单向行驶，连接车间各加工区域，实现物料在不同工序之间的流转。这种系统的设计不仅有助于降低能量消耗和减少时间成本，还可以提升整体系统的稳定性和可靠性。通过有效的路径规划和行驶方向的确定，agv在工作站之间的运输变得更加高效和可靠，为生产流程的顺利进行提供有力支持。

2、agv单向导引路径网络设计问题的目标是，在已知每个单元装卸点位置和单元间物流量的情况下，确保导向路径能够满足强连通约束条件下，对每条agv车道的行驶方向进行确定。

3、路径网络设计问题属于np难问题，虽然采用0-1整数规划方法能够得到精确解，但是计算的复杂度比较高，将使模型构建难度随着约束增加而增加，在求解较大规模问题时，求解时间会比较长；采用其他现有的方法也会存在一些不足；为了解决路径网络设计问题，需要开发一种有利于提高路径规划效率的方法。

技术实现思路

1、针对上述缺陷，本发明的目的在于提出一种考虑强连通性的agv导向路径网络设计优化方法，该方法能提高路径规划的效率。

2、为达此目的，本发明采用以下技术方案：

3、一种考虑强连通性的agv导向路径网络设计优化方法，包括以下步骤：

4、s0、在已知每个单元装卸点位置和单元间物流量的情况下，确保导向路径能够满足强连通约束条件下，对每条agv车道的行驶方向进行确定；以agv负载距离和空载距离所形成的总运输距离最小化为目标，构建导向路径网络数学模型；

5、s1、使用通用变量邻域搜索算法求得导向路径网络数学模型的导向路径；通过图的深度搜索方法，理解和识别图的强连通结构；

6、s2、根据强连通图的耳朵分解序列生成的算法，可以在线性时间内得到强连通图的耳朵分解序列的初始解；

7、s3、降邻域搜索，在满足强连通约束的前提下设置包括反转圈、反转路和子图重定向的邻域动作，探索其中一个或者多个邻域；同时带入局部搜索算法，寻找更好的解；如果找到更好的解，更新当前解并根据需要调整搜索策略；达到预设终止条件后，输出整个过程中最优的解；

8、s4、将降邻域搜索步骤中最优的解结合到通用变量邻域搜索算法中，增强搜索能力。

9、较佳地，步骤s0中数学模型如下所示：

10、为了描述问题和准确建立相应的数学模型，做出如下定义：

11、agv运输容量无上限；

12、每个单元有唯一上料口和下料口，且位置已知；

13、agv的运输路径均为最短路径；

14、不考虑agv是否会出现堵塞的情况；

15、其中，n为单元数量；s为顶点集；pn为上料口,n∈[1,n]；dn为下料口,n∈[1,n]；e(i,j)为从顶点i到顶点j的车道；tij为车道方向；hij为车道长度；fbd为从下料口db到上料口pd的搬运次数；gdb为从上料口pd到下料口db的空载次数；lij为从顶点i到顶点j的最短路径；为车道e(i,j)是否位于下料口db到上料口pd的搬运路线上；为车道e(i,j)是否位于上料口pd到下料口db的空载路线上；qbd为单元b与单元d之间的负载流量矩阵；为单元b与单元d之间的空载流量矩阵；

16、

17、tij+tji＝1                                          式(2.12)

18、σi∈stij≥1                                           式(2.13)

19、σj∈stij≥1                                         式(2.14)

20、σd∈nfbd＝σd∈ngdb                                   式(2.15)

21、

22、该数学规划模型的式(2.1)为目标函数，优化目标是使agv的运行总路程最短，而agv的运行总路程包括空载行程和负载行程两部分；约束式(2.2)-式(2.3)确保计算选择的路线长度等于空载距离，即从上料口pb到下料口dd、从下料口dd到上料口pb的空载路线距离等于所选择的车道长度和；

23、约束式(2.4)-式(2.5)是为了确保只有一条进出上料口pb的车道；

24、约束式(2.6)-式(2.7)是为了保证进出下料口dd的车道数量也都分别只有一条；

25、约束式(2.8)-式(2.9)是为了保证agv进入所有非装卸点顶点的次数与离开该顶点的次数一致；

26、约束式(2.10)-式(2.11)是为了确保每条空载的搬运路线中的车道不会重复出现；

27、约束式(2.12)是为了确保每条车道是单向的；

28、约束式(2.13)-式(2.14)是为了确保导向路径网络是强连通的，需要保证对于顶点集中的任意顶点，都存在一条起始于该顶点并终止于该顶点的导向路径；

29、约束式(2.15)-式(2.16)的作用是确保物流平衡，即确保agv的负载次数与空载次数相等；

30、此外，约束式(2.17)是变量约束，确保其中的每个变量都属于0-1变量；从该数学模型来看，它包含了大量的0-1变量和约束，这将导致解空间随着决策变量规模的增加呈指数级增长。

31、较佳地，步骤s2中：

32、有向图的耳朵分解是将其分解成一个由路和圈所组成的集合，且所有路和圈之间都不存在公共边，其具体定义如下：对于有向多重图d，它的耳朵分解是一个序列ε＝{p0,p1,…pt}，其中p0表示圈，每一个pi(1≤i≤t)为一条路，或是具有下列性质的圈[66]：

33、(1)当i≠j时，pi和pj是弧不交的；

34、(2)对于每一个i＝1，2，…，t，若pi是圈，则pi与v(di-1)之间仅有一个共同顶点；不然，pi的端点是v(di-1)中不相同的顶点，且pi的其余顶点也不属于v(di-1)；此处，di表示拥有顶点集和弧集所构成的有向图；

35、(3)

36、每一个pi称为ε的一个耳朵，ε中耳朵的数量为t+1，若一个耳朵|a(pj)|＝1，则称其为平凡的；否则称为不平凡的耳朵；

37、定理1：一个有向图d＝(v,a)是强连通图的充分必要条件是它至少存在一个耳朵分解序列；此外，在d是强连通图的情况下，对于每个顶点v，可以将包含v的每个圈c用作d的耳朵分解序列的初始圈p0；

38、由定理1可知，每一个强连通有向图d都存在耳朵分解序列，选择不同的顶点v可得到d的不同的耳朵分解序列，显然，每一个强连通有向图d具有多个耳朵分解序列，但两个不同的强连通有向图，其耳朵分解序列一定不相同；

39、推论1：对于具有n个顶点和m条弧的强有向图，它的每一个耳朵分解序列包含m-n+1个耳朵，而且存在一个能够寻找出强连通有向图d的耳朵分解的线性时间算法；

40、通过定理1的证明过程容易证明每一个耳朵分解序列包含m-n+1个耳朵；我们可以基于求得有向图d的一个深度优先搜索算法，每一次回溯过程可构造一个耳朵；由于整个回溯只遍历每个顶点和弧各一次，因此该算法为线性时间算法。

41、较佳地，步骤s2中：

42、通过使用图的深度搜索方法，可以确定无向图g的强连通有向图d，再根据耳朵分解序列生成的算法，我们能够在线性时间内找到强连通有向图d的耳朵分解序列ε；

43、先将待定向的车间agv运输轨道网络建模为无向图g，然后再确定出g的强连通有向图d，最后将其转化为耳朵分解序列ε。这样就能在线性时间范围内生成初始解方案。

44、进一步地，步骤s3中：

45、针对强连通的约束，从图论的角度设计出满足这个约束的邻域动作；

46、反转圈：

47、定理2：如果d'和d”是无向图g＝(v,e)的两种k强连通定向，那么存在一系列k强连通定向d'＝d0,d1,…,dk＝d”，使得每一个di(i＝1,2,…,k)都可以通过反转一个定向圈或路径得到di-1；

48、若d＝(v,a)是强连通有向图，c是d中一个圈，通过定理2可知，对c圈上的每一条弧的方向进行反转，所得到的新的有向图d'仍然属于强连通有向图；令序列ε＝{p0,p1,p2,…,pt}为强连通有向图d的一个耳朵序列，反转耳朵p0中弧方向，用表示，则新序列对应的有向图d'为强连通有向图；因此，随机选取一个圈并且反转圈上面每一条弧的方向所得到的反方向圈得到的仍然是强连通有向图；因此，可以设置随机反转强连通有向图的一个圈上所有弧的方向作为一个邻域动作；

49、反转路：

50、定理3：假设d＝(v,a∪p)为强连通有向图，其中p为从顶点a到顶点b的一条路，令为反转p后所得到的有向图，则为强连通有向图的充分必要条件是在有向图d中至少存在两条从顶点a到顶点b的路径且这些路径不相交；

51、对于强连通有向图d中的一条路径，反转路径上的所有弧仍然可以保持有向图的强连通性；因此，只需要确定是否存在两个顶点之间至少存在两条不相交的路径，就可以确定反转路径的操作所形成的邻域结构，并且确保其邻域结构满足强连通性；

52、子图重定向：

53、定理4：假设有向图d＝(v,a)为强连通有向图；我们将这个图二分解为d1＝(v1,a1)和d2＝(v2,a2)两部分；其中，d1的底图是无向连通图；现在，如果我们重新定向d1得到强连通图d1'＝(v1,a1')，那么由d2和d1'联合构成的并集(d1'∪d2)新图将是一个强连通有向图；所以根据定理4，首先将一个强连通的有向图通过二分解为两个子图，随机选择其中一个子图，并将该子图内的所有弧的方向进行翻转，进而得到一个新的强连通有向子图，然后再与原来的另外一个子图合并得到一个新的强连通有向图。

54、进一步地，步骤s3中带入的局部搜索算法为最佳改进搜索策略的局部搜索算法或首次改进搜索策略的局部搜索算法

55、上述技术方案中的一个技术方案包括以下有益效果：本方案为最小化物料搬运成本，针对agv导向路径网络进行优化，将此问题归结为解决图的最优强连通定向问题。因此，先以最小化由agv的运载成本和空载成本组成的总运输成本作为优化目标，建立相应的数学模型。然后，为提高局部搜索能力，以有向图强连通性中反转路、反转圈、子图重定向保持强连通性的特性为基础，提出三种生成邻域结构的方法，以确保邻域解搜索过程中生成的解的有效性，提高求解效率和质量。

技术特征：

1.一种考虑强连通性的agv导向路径网络设计优化方法，其特征在于，包括以下步骤：

2.根据权利要求1所述的考虑强连通性的agv导向路径网络设计优化方法，其特征在于，步骤s0中数学模型如下所示：

3.根据权利要求1所述的考虑强连通性的agv导向路径网络设计优化方法，其特征在于，步骤s2中：

4.根据权利要求3所述的考虑强连通性的agv导向路径网络设计优化方法，其特征在于，步骤s2中：

5.根据权利要求1所述的考虑强连通性的agv导向路径网络设计优化方法，其特征在于，步骤s3中：

6.根据权利要求1所述的考虑强连通性的agv导向路径网络设计优化方法，其特征在于，步骤s3中带入的局部搜索算法为最佳改进搜索策略的局部搜索算法或首次改进搜索策略的局部搜索算法。

技术总结
一种考虑强连通性的AGV导向路径网络设计优化方法，包括以下步骤：S0、在已知每个单元装卸点位置和单元间物流量的情况下，确保导向路径能够满足强连通约束条件下，对每条AGV车道的行驶方向进行确定；以AGV负载距离和空载距离所形成的总运输距离最小化为目标，构建导向路径网络数学模型；S1、使用通用变量邻域搜索算法求得导向路径网络数学模型的导向路径；通过图的深度搜索方法，理解和识别图的强连通结构；S2、根据强连通图的耳朵分解序列生成的算法，得到强连通图的耳朵分解序列的初始解；S3、降邻域搜索，输出整个过程中最优的解；S4、将降邻域搜索步骤中最优的解结合到通用变量邻域搜索算法中，增强搜索能力。该方法能提高路径规划的效率。

技术研发人员：廖勇,廖芳芳,彭乘风,李翔,林安平,邓健,谢敬廷,徐嘉豪
受保护的技术使用者：湘南学院
技术研发日：
技术公布日：2024/12/5