一种考虑冲突规避的多AGV路径规划方法

摘要

本发明公开了一种考虑冲突规避的多AGV路径规划方法，包括：基于柔性工厂布局以及工件加工过程的多AGV任务分配、工序与机床分配问题，构建以最短完工时间为目标的调度模型；采用A*算法分别对各AGV单独的路径进行规划，寻找各AGV规划方案的冲突并进行逐个规避，得到初始路径种群；采用遗传算法并引入增强精英策略，对初始路径种群进行运算，得到最短完工时间下的最优路径方案。本发明添加了对AGV之间占位冲突、边线冲突的判断和规避，机器占用与AGV等待过程的处理以及对算法死锁的预防等过程，可实现对多AGV的路径规划和冲突规避。

权利要求

1.一种考虑冲突规避的多AGV路径规划方法，其特征在于，包括：基于柔性工厂布局以及工件加工过程的多AGV任务分配、工序与机床分配问题，构建以最短完工时间为目标的调度模型；

对各加工工件的工序和机床进行匹配，并对工序和AGV进行编码，按照工序顺序，将工件一一分配给对应的机床和AGV，得到各AGV的任务列表；

基于所述AGV任务列表，采用A*算法分别对各AGV单独的路径进行规划，寻找各AGV规划方案的冲突并进行逐个规避，得到各AGV的初始路径种群；

以调度模型的完工时间作为适应度，采用遗传算法并引入增强精英策略，对初始路径种群进行求解，得到最短完工时间下的最优路径方案；

AGV规划方案的冲突规避包括：

占位冲突规避：若两辆AGV在同一时刻占据了同一位置，此时，A*算法判定为发生占位冲突，对其中一辆发生冲突的AGV设置限制，使其在每一次搜索临近点时都进行冲突检测，排除掉与限制条件时间位置相同的点，得到新路径；

若两个AGV路线发生重叠，冲突在重叠的每一个格栅都发生一次，A*算法只记录第一个位置重叠发生的时间和位置坐标，并解决冲突；

为规避AGV装载或卸货时，在终点位置发生冲突，将接件和送件的目的地区别设置，同时将机床临近不同的两个点规定为接件区和送件区；

边线冲突规避：若两辆AGV在某个时刻发生位置坐标交换，A*算法判定发生边线冲突，此时记录冲突的时刻和两辆AGV冲突前各自的位置坐标(t,L1,L2)，并在检测到冲突后对其中一辆AGV施加限制，防止路线中出现t时刻在位置L1且t+1时刻向L2行驶的情况；

多车、多类型冲突规避：若发生两个及以上冲突同时发生的情况，A*算法任选两辆AGV解决其冲突；

机器占用和AGV等待冲突规避：在每个任务的送件过程结束时，判断上一工件的加工是否结束，如果没有结束，需要让AGV等待至加工结束；AGV等待的时间等于上一工件加工时间减去路上消耗的时间；若等待时间大于零，则要在下一次规划的路径前面插入等待时间。

2.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法，其特征在于，所述调度模型的建立基于以下假设：假设一：AGV在没有分配到任务时停在AGV各自的起始位置；

假设二：地图格栅由正方形小网格组成，机床的形状近似为正方形或者长方形的网格矩阵；

假设三：AGV的车身形状近似为一个半径为r的圆形，其中r小于格栅图网格边长，且大于边长的一半；

假设四：两辆AGV不能同时处在同一格栅内，也不能在处于相邻格栅的时候交换位置，否则都视为AGV发生碰撞；

假设五：AGV装载和卸载工件的时间记为一个单位时间，与AGV驶过一个网格用时相同；

假设六：AGV处在机床的装卸点时，不视为与机床碰撞；

假设七：每辆AGV一次只能装载一个工件；

假设八：AGV的运行速度是匀速的，是作为条件预设的；

假设九：不考虑AGV和机床的故障情况，二者都可持续正常工作；

假设十：AGV将工件运送到下一个机床之前，需要判断上一个工序是否加工完成，以及下一机床是否正在加工工件。

3.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法，其特征在于，所述调度模型的数学模型为：F＝min(MS)    (1)；

MS＝max(Ti‑T0)    (2)；

其中，公式(1)为目标函数；公式(2)定义完工时间为最后一辆AGV停止运行的时刻减去初始时刻；公式(3)‑(4)为限制条件，具体表示位置冲突和边线冲突两种情况都不允许发生；公式(5)表示机床同时只加工一个工件；公式(6)表示AGV一次只承载一个工件；公式(7)表示对AGV装载工件的时间约束；

MS表示完工时间；Ti表示第i辆AGV运行结束时刻；T0表示第一辆AGV起始时刻；Pi,t表示第i辆AGV在t时刻的位置；i,j表示AGV的编号；A表示AGV的编号集合；x,y表示工件的编号；

x x x,dr

Mm表示第m台机床在加工工件x的标志；Vi表示第i辆AGV在运输工件x的标志；ti 表示第ix x,pk辆AGV卸载工件x的时刻；tm表示第m台机床加工工件x花费的时间；tj 表示第j辆AGV装载工件x的时刻。

4.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法，其特征在于，AGV的任务列表的确定过程包括：编码前操作：编码前对机床和各工件的工序进行匹配；

编码：选用两组染色体作为最初种群，分别为工序染色体和AGV染色体；对于工序染色体，生成打乱顺序的公差为1的正整数数列，正整数表示工件编号，每个编号出现的次数与工序数相同，出现第几次则代表第几道工序；对于AGV染色体，正整数编码代表AGV编号；

解码：仿真染色体编码方案，计算完工时间。

5.根据权利要求4所述的一种考虑冲突规避的多AGV路径规划方法，其特征在于，编码前操作，用两个机床的曼哈顿距离除以AGV速度得到的行驶时间近似代表运送时间，将该时间与加工时间的和作为寻找下一个最佳机床的评判标准，寻优过程为：当 时，

若[dmanh(m,n)]min＝dmanh(m,p),p∈J；

则

式中， 表示第m台机床正在加工工件x， 表示此时第m台机床没有对工件X进行加工，dmanh(m,n)表示机床m到机床n的曼哈顿距离，pm,x代表机床m的x轴坐标，J表示机床集合。

6.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法，其特征在于，AGV规划方案的冲突规避还包括：算法死锁的预防：当发生当前AGV路径被其他AGV封死、互相闪避和两AGV目的地相同的情况时，则判定为发生算法死锁，此时，将实际完工时间超过舍弃阈值的方案舍弃；舍弃阈值设置为：MSlim＝3×MSavg，其中，MSlim为舍弃阈值，MSavg为第一代染色体完工时间的算数平均值。

7.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法，其特征在于，采用A*算法对各AGV进行路径规划时，还包括：路径规划时刻的统一：

每次进行路径规划时，将各AGV的起始时间统一，找到路线耗时最短的AGV，记录该路线长度为lmin，在其余AGV路线中找到一点使该点与起点之间的距离等于lmin，将该点命名为切割点并将路线在该点进行切割；此时只有切割前路线最短的AGV抵达终点，需要将任务列表的下一目的地传入；其余AGV的起点更新为切割点；

若有AGV返回仓库后，进入等待状态，在该已返回仓库的AGV路径中添加一段等待时间，随着时间的增加保持该AGV位置不变；等待时间的选取范围为：tw≥1.5×Lmap，其中，Lmap为地图的长。

8.根据权利要求1所述的一种考虑冲突规避的多AGV路径规划方法，其特征在于，采用遗传算法并引入增强精英策略，对初始路径种群进行求解的过程包括：进化：以完工时间为适应度，在经典遗传算法的基础上，增加精英保留的过程，根据适应度从高到低将两代染色体排序，选择适应度相对高的前半部分保留进入下一代；

重复进化过程，直至达到预设的迭代次数，得到最小适应度；

输出最小适应度下的最优方案及最短完工时间。

说明书

一种考虑冲突规避的多AGV路径规划方法

技术领域

[0001] 本发明涉及AGV控制技术领域，更具体的说是涉及一种考虑冲突规避的多AGV路径规划方法。

背景技术

[0002] 柔性制造系统(FMS)依靠高效的自动化运输设备，不仅可以随时调整零件的加工流程和顺序，还允许小批、多种零件并行生产，为企业的生产提供了灵活性。FMS中一个最基本的问题就是物料的运输调度方案，即车间内的物流管理，而在车间物流系统中应用最广泛的就是基于多AGV(自动导引车)的物流系统。

[0003] 多AGV物流运输系统涉及到很多关键技术，包括多AGV的任务调度分配、路径规划、避免冲突的措施等。合理有效的任务调度和规划可以大大提高生产效率，降低运输的成本。

[0004] 目前国内外学者对于多AGV调度问题总体上有两种解决框架：分步解决和整体优化。

[0005] 分步解决就是分别独立的实现任务分配、路径规划和交通管控，可以减少整体的复杂度和计算量，但是会把调度问题割裂开，导致每个过程的最优结果之间存在冲突。因此近年来多AGV调度问题呈现出整体化发展的趋势。

[0006] 整体优化一般是将AGV调度问题的目标和限制抽象成一个数学模型，再通过优化算法解决。这样更符合生产实际，不会割裂各个生产过程，能得到平衡各过程的优化结果。其缺点是研究的问题复杂、计算量大，因为任务调度等过程都是典型的非确定多项式问题，结合起来较为复杂。因此在模型建立时，通常需要做一些理想化的假设来降低模型复杂度，比如忽略路径冲突，在工厂环境下提前预设制造任务(加工零件种类、数量、规定的加工位置)等。

[0007] 目前对多AGV调度问题的研究大都弱化了对路径冲突的处理，采用局部路径规划的方法临时进行躲避或者在模型建立时直接忽略了路径冲突。少数研究借用分步优化常用的基于时间窗的方法，从宏观调度的角度防止冲突的发生，这样在AGV数量较少的情况下可以取得很好的效果，但是多AGV情况下时间窗的排布限制非常多，很难得到兼顾效率和安全的排布方案。

[0008] 因此，如何提供一种考虑冲突规避的多AGV路径规划方法是本领域技术人员亟需解决的问题。

发明内容

[0009] 有鉴于此，本发明提供了一种考虑冲突规避的多AGV路径规划方法，添加了对AGV之间占位冲突、边线冲突的判断和规避，机器占用与AGV等待过程的处理以及对算法死锁的预防等过程，可实现对多AGV的路径规划和冲突规避。

[0010] 为了实现上述目的，本发明采用如下技术方案：

[0011] 一种考虑冲突规避的多AGV路径规划方法，包括：

[0012] 基于柔性工厂布局以及工件加工过程的多AGV任务分配、工序与机床分配问题，构建以最短完工时间为目标的调度模型；

[0013] 对各加工工件的工序和机床进行匹配，并对工序和AGV进行编码，按照工序顺序，将工件一一分配给对应的机床和AGV，得到各AGV的任务列表；

[0014] 基于所述AGV任务列表，采用A*算法分别对各AGV单独的路径进行规划，寻找各AGV规划方案的冲突并进行逐个规避，得到各AGV的初始路径种群；

[0015] 以调度模型的完工时间作为适应度，采用遗传算法并引入增强精英策略，对初始路径种群进行求解，得到最短完工时间下的最优路径方案。

[0016] 进一步的，所述调度模型的建立基于以下假设：

[0017] 假设一：AGV在没有分配到任务时停在AGV各自的起始位置；

[0018] 假设二：地图格栅由正方形小网格组成，机床的形状近似为正方形或者长方形的网格矩阵；

[0019] 假设三：AGV的车身形状近似为一个半径为r的圆形，其中r小于格栅图网格边长，且大于边长的一半；

[0020] 假设四：两辆AGV不能同时处在同一格栅内，也不能在处于相邻格栅的时候交换位置，否则都视为AGV发生碰撞；

[0021] 假设五：AGV装载和卸载工件的时间记为一个单位时间，与AGV驶过一个网格用时相同；

[0022] 假设六：AGV处在机床的装卸点时，不视为与机床碰撞；

[0023] 假设七：每辆AGV一次只能装载一个工件；

[0024] 假设八：AGV的运行速度是匀速的，是作为条件预设的；

[0025] 假设九：不考虑AGV和机床的故障情况，二者都可持续正常工作；

[0026] 假设十：AGV将工件运送到下一个机床之前，需要判断上一个工序是否加工完成，以及下一机床是否正在加工工件。

[0027] 进一步的，所述调度模型的数学模型为：

[0028] F＝min(MS) (1)；

[0029] MS＝max(Ti‑T0) (2)；

[0030]

[0031]

[0032]

[0033]

[0034]

[0035] 其中，公式(1)为目标函数；公式(2)定义完工时间为最后一辆AGV停止运行的时刻减去初始时刻；公式(3)‑(4)为限制条件，具体表示位置冲突和边线冲突两种情况都不允许发生；公式(5)表示机床同时只加工一个工件；公式(6)表示AGV一次只承载一个工件；公式(7)表示对AGV装载工件的时间约束；

[0036] MS表示完工时间；Ti表示第i辆AGV运行结束时刻；T0表示第一辆AGV起始时刻；Pi,t表示第i辆AGV在t时刻的位置；i,j表示AGV的编号；A表示AGV的编号集合；x,y表示工件的编x x x,dr号；Mm表示第m台机床在加工工件x的标志；Vi表示第i辆AGV在运输工件x的标志；ti 表示x x,pk
第i辆AGV卸载工件x的时刻；tm 表示第m台机床加工工件x花费的时间；tj 表示第j辆AGV装载工件x的时刻。

[0037] 进一步的，AGV的任务列表的确定过程包括：

[0038] 编码前操作：编码前对机床和各工件的工序进行匹配；

[0039] 编码：选用两组染色体作为最初种群，分别为工序染色体和AGV染色体；对于工序染色体，生成打乱顺序的公差为1的正整数数列，正整数表示工件编号，每个编号出现的次数与工序数相同，出现第几次则代表第几道工序；对于AGV染色体，正整数编码代表AGV编号；

[0040] 解码：仿真染色体编码方案，计算完工时间。

[0041] 进一步的，编码操作前，用两个机床的曼哈顿距离除以AGV速度得到的行驶时间近似代表运送时间，将该时间与加工时间的和作为寻找下一个最佳机床的评判标准，寻优过程为：

[0042] 当 时，

[0043] 若[dmanh(m,n)]min＝dmanh(m,p),p∈J；

[0044] 则

[0045] 式中， 表示第m台机床正在加工工件x， 表示此时第m台机床没有对工件X进行加工，dmanh(m,n)表示机床m到机床n的曼哈顿距离，pm,x代表机床m的x轴坐标，J表示机床集合。

[0046] 进一步的，AGV规划方案的冲突规避包括：

[0047] 占位冲突规避：若两辆AGV在同一时刻占据了同一位置，此时，A*算法判定为发生占位冲突，对其中一辆发生冲突的AGV设置限制，使其在每一次搜索临近点时都进行冲突检测，排除掉与限制条件时间位置相同的点，得到新路径；

[0048] 若两个AGV路线发生重叠，冲突在重叠的每一个格栅都发生一次，A*算只记录第一个位置重叠发生的时间和位置坐标，并解决冲突；

[0049] 为规避AGV装载或卸货时，在终点位置发生冲突，将接件和送件的目的地区别设置，同时将机床临近不同的两个点规定为接件区和送件区；

[0050] 边线冲突规避：若两辆AGV在某个时刻发生位置坐标交换，A*算法判定发生边线冲突，此时记录冲突的时刻和两辆AGV冲突前各自的位置坐标(t,L1,L2)，并在检测到冲突后对其中一辆AGV施加限制，防止路线中出现t时刻在位置L1且t+1时刻向L2行驶的情况；

[0051] 多车、多类型冲突规避：若发生两个及以上冲突同时发生的情况，A*算法任选两辆AGV解决其冲突。

[0052] 进一步的，AGV规划方案的冲突规避还包括：

[0053] 机器占用和AGV等待冲突规避：在每个任务的送件过程结束时，判断上一工件的加工是否结束，如果没有结束，需要让AGV等待至加工结束；AGV等待的时间等于上一工件加工时间减去路上消耗的时间；若等待时间大于零，则要在下一次规划的路径前面插入等待时间。

[0054] 进一步的，AGV规划方案的冲突规避还包括：

[0055] 算法死锁的预防：当发生当前AGV路径被其他AGV封死、互相闪避和两AGV目的地相同的情况时，则判定为发生算法死锁，此时，将实际完工时间时间超过舍弃阈值的方案舍弃；舍弃阈值设置为：MSlim＝3×MSavg，其中，MSlim为舍弃阈值，MSavg为第一代染色体完工时间的算数平均值。

[0056] 进一步的，采用A*算法对各AGV进行路径规划时，还包括：

[0057] 路径规划时刻的统一：

[0058] 每次进行路径规划时，将各AGV的起始时间统一，找到路线耗时最短的AGV，记录该路线长度为lmin，在其余AGV路线中找到一点使该点与起点之间的距离等于lmin，将该点命名为切割点并将路线在该点进行切割；此时只有切割前路线最短的AGV抵达终点，需要将任务列表的下一目的地传入；其余AGV的起点更新为切割点；

[0059] 若有AGV返回仓库后，进入等待状态，在该已返回仓库的AGV路径中添加一段等待时间，随着时间的增加保持该AGV位置不变；等待时间的选取范围为：tw≥1.5×Lmap，其中，Lmap为地图的长。

[0060] 进一步的，采用遗传算法并引入增强精英策略，对初始路径种群进行求解的过程包括：

[0061] 进化：以完工时间为适应度，在经典遗传算法的基础上，增加精英保留的过程，根据适应度从高到低将两代染色体排序，选择适应度相对高的前半部分保留进入下一代。

[0062] 重复进化过程，直至达到预设的迭代次数，得到最小适应度；

[0063] 输出最小适应度下的最优方案及最短完工时间。

[0064] 经由上述的技术方案可知，与现有技术相比，本发明公开提供了一种考虑冲突规避的多AGV路径规划方法，建立了以最小完工时间为目标的调度模型，通过引入增强精英策略改进遗传算法对该模型进行求解，不仅能大幅节约运算时间，同时还能找到适应度更优的染色体；此外，在单AGV路径规划的A*算法基础上，引入同时规划、路径切割、冲突的判断及规避、死锁的预防等过程，避免多AGV运行过程中发生的各种冲突，保证柔性工厂的加工效率。

附图说明

[0065] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。

[0066] 图1为本发明提供的考虑冲突规避的多AGV路径规划方法的流程图；

[0067] 图2为本发明采用经典遗传算法引入增强精英策略后的寻优过程示意图；

[0068] 图3为采用经典遗传算法的寻优过程示意图；

[0069] 图4为占位冲突示意图；

[0070] 图5为边线冲突示意图；

[0071] 图6为多车冲突示意图；

[0072] 图7为算例1的地图；

[0073] 图8为算例1的寻优过程；

[0074] 图9为算例1的仿真过程示意图；

[0075] 图10为算例2的地图；

[0076] 图11为算例2的寻优过程；

[0077] 图12为算例2的仿真过程示意图。

具体实施方式

[0078] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0079] 如图1所示，本发明实施例公开了一种考虑冲突规避的多AGV路径规划方法，包括：

[0080] S1、基于柔性工厂布局以及工件加工过程的多AGV任务分配、工序与机床分配问题，构建以最短完工时间为目标的调度模型；

[0081] S2、对各加工工件的工序和机床进行匹配，并对工序和AGV进行编码，按照工序顺序，将工件一一分配给对应的机床和AGV，得到各AGV的任务列表；

[0082] S3、基于各AGV的任务列表，采用A*算法分别对各AGV单独的路径进行规划，寻找各AGV规划方案的冲突并进行逐个规避，得到各AGV的初始路径种群；

[0083] S4、以调度模型的完工时间作为适应度，采用遗传算法并引入增强精英策略，对初始路径种群进行求解，得到最短完工时间下的最优路径方案。

[0084] 具体而言，S1中，调度模型的建立基于以下假设：

[0085] 假设一：AGV在没有分配到任务时停在AGV各自的起始位置；

[0086] 假设二：地图格栅由正方形小网格组成，机床的形状近似为正方形或者长方形的网格矩阵；

[0087] 假设三：AGV的车身形状近似为一个半径为r的圆形，其中r小于格栅图网格边长，且大于边长的一半；

[0088] 假设四：两辆AGV不能同时处在同一格栅内，也不能在处于相邻格栅的时候交换位置，否则都视为AGV发生碰撞；

[0089] 假设五：AGV装载和卸载工件的时间记为一个单位时间，与AGV驶过一个网格用时相同；

[0090] 假设六：AGV处在机床的装卸点时，不视为与机床碰撞；

[0091] 假设七：每辆AGV一次只能装载一个工件；

[0092] 假设八：AGV的运行速度是匀速的，是作为条件预设的；

[0093] 假设九：不考虑AGV和机床的故障情况，二者都可持续正常工作；

[0094] 假设十：AGV将工件运送到下一个机床之前，需要判断上一个工序是否加工完成，以及下一机床是否正在加工工件。

[0095] 调度模型的数学模型为：

[0096] F＝min(MS)   (1)；

[0097] MS＝max(Ti‑T0)   (2)；

[0098]

[0099]

[0100]

[0101]

[0102]

[0103] 其中，公式(1)为目标函数；公式(2)定义完工时间为最后一辆AGV停止运行的时刻减去初始时刻；公式(3)‑(4)为限制条件，具体表示位置冲突和边线冲突两种情况都不允许发生；公式(5)表示机床同时只加工一个工件；公式(6)表示AGV一次只承载一个工件；公式(7)表示对AGV装载工件的时间约束；

[0104] MS表示完工时间；Ti表示第i辆AGV运行结束时刻；T0表示第一辆AGV起始时刻；Pi,t表示第i辆AGV在t时刻的位置；i,j表示AGV的编号；A表示AGV的编号集合；x,y表示工件的编x x x,dr号；Mm表示第m台机床在加工工件x的标志；Vi表示第i辆AGV在运输工件x的标志；ti 表示x x,pk
第i辆AGV卸载工件x的时刻；tm 表示第m台机床加工工件x花费的时间；tj 表示第j辆AGV装载工件x的时刻。

[0105] 在一个实施例中，S2中，AGV的任务列表的确定过程包括：

[0106] S21、编码前操作：编码前对机床和各工件的工序进行匹配；

[0107] 后续的编码部分确定了工序和AGV的任务分配，但是没有匹配工序与机床。若将机床也进行编码成为第三条染色体会使算法效率降低，所以本发明选择在编码过程的开始对机床和工序进行匹配。

[0108] 每个种类工件都有各自的加工用时表，例如表1为工件A加工时间表，单位是AGV走过格栅图一个网格消耗的时间。其中，Inf表示该工序不能在此机床加工。

[0109] 表1 工件A的加工时间表

[0110] 工序 机床1 机床2 机床3 机床4 机床5 机床61 Inf Inf Inf 4 3 2
2 Inf 4 2 Inf 3 Inf
3 Inf Inf Inf 5 4 1

[0111] AGV接到任务的位置与机床的距离非常随机，用两个机床的曼哈顿距离除以AGV速度得到的行驶时间近似代表运送时间，将这个时间与加工时间的和作为寻找下一个最佳机床的评判标准，寻优过程见下式：

[0112] 当 时，

[0113] 若[dmanh(m,n)]min＝dmanh(m,p),p∈J；

[0114] 则

[0115] 式中， 表示第m台机床正在加工工件x， 表示此时第m台机床没有对工件X进行加工，dmanh(m,n)表示机床m到机床n的曼哈顿距离，pm,x代表机床m的x轴坐标，J表示机床集合。

[0116] S22、编码：选用两组染色体作为最初种群，分别为工序染色体和AGV染色体；对于工序染色体，生成打乱顺序的公差为1的正整数数列，正整数表示工件编号，每个编号出现的次数与工序数相同，出现第几次则代表第几道工序；对于AGV染色体，正整数编码代表AGV编号；

[0117] 编码过程是将实际调度方案用数值串的方式表达。选用两组染色体，都通过整数排列的方式编码。染色体随机生成，两组染色体的长度均为所有零件工序总数 其中，Gx为工件x的工序数；W为工件编号的集合。

[0118] 如表2所示，第一组染色体为工序染色体，在实际运行过程中，首先生成打乱顺序的公差为1的正整数数列，正整数表示工件编号，每个编号出现的次数与工序数相同，出现第几次代表第几道工序。第二组为AGV染色体，正整数编码代表AGV编号。以表2中第一列为例，负责将工件1运送到承担其第一道工序加工任务机床的是在AGV染色体中与之位置相对应的1号AGV。

[0119] 表2 染色体编码

[0120]工序染色体 1 3 1 3 2 2 1
AGV染色体 1 1 2 1 1 1 2

[0121] 此后，根据工序染色体顺序，将工件一一分配给机床和AGV，形成AGV的任务列表，各AGV按照任务列表逐个完成运送任务。

[0122] S23、解码：仿真染色体编码方案，计算完工时间；

[0123] 解码是遗传算法从染色体生成适应度的过程，本发明以完工时间作为适应度，解码的过程就是仿真染色体编码方案计算完工时间的过程。

[0124] 在一个具体实施例中，S3对采用A*算法分别对各AGV单独的路径进行规划的过程包括：

[0125] 1、冲突的判断和规避，本发明的冲突判断模式是先规划好路径再寻找冲突。检测到冲突后，记录发生冲突的两车编号、时间和位置坐标，输入冲突信息并重新开始路径规划，其中的冲突信息会转换成单AGV路线规划时的限制。具体为：

[0126] ①、占位冲突规避：如图4是一个典型的占位冲突。若两辆AGV在同一时刻占据了同一位置，此时，A*算法判定为发生占位冲突，对其中一辆发生冲突的AGV设置限制，使其在每一次搜索临近点时都进行冲突检测，排除掉与限制条件时间位置相同的点，得到新路径，再进行后续的冲突检测。

[0127] 若两个AGV路线发生重叠，冲突在重叠的每一个格栅都发生一次，A*算只记录第一个位置重叠发生的时间和位置坐标，并解决冲突；具体为：对其中一辆发生冲突的AGV设置限制，使其在每一次搜索临近点时都进行冲突检测，排除掉与第一个位置重叠发生的时间和位置坐标相同的点，得到新路径，再进行后续的冲突检测。

[0128] 为规避AGV装载或卸货时，在终点位置发生冲突，将接件和送件的目的地区别设置，同时将机床临近不同的两个点规定为接件区和送件区。

[0129] 在AGV装载或卸货时，若两个AGV当前目标的位置坐标相同，两辆AGV必然会在终点位置发生占位冲突。这是由于正在执行送件任务的AGV和正在执行接件任务的AGV目标被设定为同一机床的同一点。为了解决这一状况，把接件和送件的目的地区别设置，分别把机床临近不同的两个点规定为接件区和送件区。

[0130] ②、边线冲突规避：如图5所示，为边线冲突的基本情形，若没有碰撞干涉，两辆AGV会在某个时刻发生位置坐标的交换。

[0131] 若两辆AGV在某个时刻发生位置坐标交换，A*算法判定发生边线冲突，此时记录冲突的时刻和两辆AGV冲突前各自的位置坐标(t,L1,L2)，并在检测到冲突后对其中一辆AGV施加限制，防止路线中出现t时刻在位置L1且t+1时刻向L2行驶的情况。

[0132] 在A*算法搜索中，假设已经选定io点，此时AGV运行时间为t，搜索临近点时，若i0的坐标恰好是L1，则排除掉L2。

[0133] 与占位冲突相同，在路径有多处冲突时从第一处冲突开始判断和处理。

[0134] ③、多车、多类型冲突规避：若发生两个及以上冲突同时发生的情况，A*算法任选两辆AGV解决其冲突。

[0135] A*算法实际运行时，在寻找第一个冲突的位置和类型的过程中，由于需要调度的AGV数量较多，模型迭代次数多，一定会发生两个及以上冲突同时发生的情况，如图6所示。本发明采取的方法也是逐个解决，任选两辆AGV解决其冲突，其它冲突可能会随之解决，如果没有解决，则冲突还会被重新检测到，再次处理。

[0136] ③、机器占用和AGV等待冲突规避：AGV把工件送到机床时，可能会出现上个工件的加工没有结束的情况。所以需要在工件送到机床进入加工过程时对机床进行锁定，锁定时间是工件的加工时间。

[0137] 具体为：在每个任务的送件过程结束时，判断上一工件的加工是否结束，如果没有结束，需要让AGV等待至加工结束；AGV等待的时间等于上一工件加工时间减去路上消耗的时间；若等待时间大于零，则要在下一次规划的路径前面插入等待时间。在下一次规划的路径前面插入等待时间的目的是使AGV在等待结束后能够直接执行下一个任务。

[0138] ⑤、算法死锁的预防：在A*算法运行过程中，有小概率会发生AGV死锁导致算法陷入死循环的情况，如路径被其它AGV封死、互相闪避、两AGV同目的地等，对于这些小概率死锁情况，采取舍弃这一组解的措施。

[0139] 具体为：当发生当前AGV路径被其他AGV封死、互相闪避和两AGV目的地相同的情况时，则判定为发生算法死锁，此时，将实际完工时间超过舍弃阈值的方案舍弃，即舍弃当前AGV路径规划的方案，更改其目的地，然后进行下一次规划；舍弃阈值设置为：MSlim＝3×MSavg，其中，MSlim为舍弃阈值，MSavg为第一代染色体完工时间的算数平均值。

[0140] 2、路径规划时刻的统一：

[0141] 本发明A*算法对冲突的判断和解决是根据同一时刻小车位置进行的，因此对AGV同时进行路线规划时，起始时间必须统一。

[0142] 但是由于起点和终点的不同，每辆AGV规划出的路线耗时必然会出现差异。这会导致每辆AGV的时间结点都不同，在下一次进行路线规划时，A*还是会把起点当作起始位置统一计时。

[0143] 因此要对规划出来的路径进行截取，每次进行路径规划时，将各AGV的起始时间统一，找到路线耗时最短的AGV，记录该路线长度为lmin，在其余AGV路线中找到一点使该点与起点之间的距离等于lmin，将该点命名为切割点并将路线在该点进行切割；此时只有切割前路线最短的AGV抵达终点，需要将任务列表的下一目的地传入；其余AGV的起点更新为切割点；

[0144] 如果多辆AGV同时抵达目的地，则随机选取一辆AGV进入下一个任务。其他AGV的目的地暂时保持不变。此时，已抵达目的地但未进入下一个任务的AGV由于目的地没有更新，因此它们在下一步搜索中，规划得到的路径长度为0，并且耗时时间t＝0。之后采用路径截取的方法，再使其中一辆已到达目的地的AGV进入到下一个任务。如此循环，直到使所有已到达目的地的AGV进入到下一个任务。

[0145] 若有AGV返回仓库后，如果通过持续更新目标的方法让AGV保持等待，由于仓库中AGV起点和终点必然重合会造成切割后得到的每一个方案都是t＝0的单状态路径。当AGV返回仓库后，在之后的规划中它的起点和目的地都是仓库，因此规划得到距离为0的路径，AGV耗时也必定是0。因为路径长度为0，对于路径截取算法而言，这条路径必定为最短路径，路径截取会使AGV不停地进入到路径截取算法的执行中，这就是t＝0的单状态路径及它产生的问题。所以，如果判定AGV已经进入等待状态，在该已返回仓库的AGV路径中添加一段等待时间，随着时间的增加保持该AGV位置不变；等待时间的选取范围为：tw≥1.5×Lmap，其中，Lmap为地图的长，这样确保等待过程不会成为最短的路线，以至于打断没进入等待状态的AGV路线。设置等待时间的目的是为了使已到达仓库的AGV在每次规划中路径的耗时不再为0，避免系统陷入路径截取算法无限执行的状态。

[0146] 3、完工时间的记录

[0147] 采用A*算法对各AGV进行路径规划时，在每一次路线规划后，都得到一个包含所有AGV路线的单步解决方案，由于路径截取算法的存在，使所有路线的用时都是一样的，每次运行完均需记录路线，累加每个单步方案消耗的时间得到最终的完工时间。

[0148] 在一个具体实施例中，S4包括：

[0149] S41、进化：以完工时间为适应度，在经典遗传算法的基础上，增加精英保留的过程，将两代染色体排序，选择前半部分保留进入下一代。

[0150] S42、重复进化过程，直至达到预设的迭代次数，得到最小适应度；

[0151] S43、输出最小适应度下的最优方案及最短完工时间。

[0152] 经典的遗传算法包含选择、交叉、变异等过程，本发明中，选择过程选用锦标赛法以提升运算速度；对于交叉过程，通过采用不同交叉方式将一代100个个体迭代100次来研究各种交叉算子对收敛效率的作用，分析实验得到的最小适应度值，最终工序染色体选用部分匹配交叉(PMX)，AGV染色体选用两点交叉；遗传过程，工序染色体选用逆转遗传，AGV染色体选用了均匀遗传。

[0153] 本发明在经典算法之后，增加精英保留的过程：根据适应度从高到低排序，将两代染色体排序，选择前半部分保留进入下一代，即保留适应度高的。之后重复进化过程，直至达到预设的迭代次数。

[0154] 为了研究精英保留对算法收敛效率的影响，将经典算法与引入精英保留的算法进行实验对比，两个算法采用相同的交叉和变异算子。其中采用附加增强精英策略的算法将一代100个个体迭代100次得到最小适应度的过程如图2所示，最小适应度为618，而经典算法采用同样迭代次数得到的最小适应度为682。

[0155] 采用经典算法将一代100个个体迭代1000次和2000次，寻找最小适应度的过程如图3所示。从图3的寻优过程可以看出，经典算法的种群多样性更大，数据一直在震荡。但是两次实验得到的最小适应度分别是642和625，均大于附加增强精英策略的算法。在迭代次数多10倍和20倍的情况下，经典算法仍然没有找到更好的结果。

[0156] 可知，采用增强精英保留的策略不仅能大幅节约运算时间，同时还能找到适应度更优的染色体。

[0157] 为了进一步说明本发明方法的冲突规避效果，本发明还进行了如下仿真实验。

[0158] 1、算例1的仿真实验

[0159] 本发明采用格栅法建立地图，算例1的地图如图7，是5行8列的格栅图。其中最左侧带填充色的格栅代表AGV的仓库，中间部分带填充色的格栅代表机床，装载/卸载位置设置在机床两侧未标出。由3个AGV负责在6个机床之间完成运输任务。待加工零件有四种，每种一个，各种零件在机床的加工时间如表3所示。

[0160] 表3算例1各零件的加工时间

[0161]

[0162] 将表3的数据输入调度模型，设置遗传算法种群个体数为50，经历100次迭代后，得到最短的完工时间为23个单位时间(截止到最后一个件加工完)，并得到各AGV在整个过程中的运行方案。寻优过程如图8所示。

[0163] 调度模型输出得到的最小完工时间接近实际最小值。

[0164] 得到最优结果后，生成环境地图并模拟各AGV的路径运行，通过观测运行状况验证方案是否能够规避冲突。

[0165] 用matplotlib包绘制地图元素。用简单二维图形代表AGV和机床，用颜色区分开机床的不同区域。

[0166] 以图9为例，对算例1的地图环境进行动态仿真。圆形表示AGV，上面的数字代表AGV编号。中间方框填充区域表示机床，中间无填充方框区域表示等待区，分别负责AGV的卸货和装载。左侧小方形表示AGV的仓库。

[0167] 将算例1得到的路径仿真后，验证了没有冲突的发生。

[0168] 2、算例2的仿真实验

[0169] 算例2的地图如图10所示。采用9行14列的大地图，放置了16个机床。工序列表也需要扩大，预设了各工序在16个机床的加工时间，并且将一个工件增加到四个工序。工序加工时间表与算例1的相似，只是将加工任务分配给16个机床。每种工件有三个。

[0170] 输入时间表，同样设置种群个体数50，经历100次迭代，得到最短的完工时间为134个单位时间。

[0171] 寻优过程如图11所示，实验得到的最小完工时间也接近实际的最小值，但比起算例1，算例2得到的最小完工时间与最优解相差的相对较多。

[0172] 用matplotlib包绘制地图元素，图形和颜色代表的含义与算例1相同。如图12所示，对算例2的地图环境进行动态仿真。

[0173] 将算例2得到的路径仿真后，同样验证没有冲突的发生。

[0174] 经过两个算例的仿真实验，调度模型都得到了接近实际最优解的输出，但是较复杂算例的输出结果误差较大一些，原因可能是复杂度更高的问题用遗传算法解决时更可能陷入局部最优。

[0175] 通过动态仿真，观测到两个算例的路径都不存在冲突，验证了多AGV路径规划算法对冲突的判断与解决能力以及改进遗传算法优化结果的有效性。

[0176] 本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

[0177] 对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。