技术领域
本发明涉及自动化物流仓储技术，尤其指仓储物流自动导引车(AutomatedGuided Vehicle，AGV)路线规划和轨迹优化技术，具体涉及一种基于蚁群算法、遗传算法相结合的仓储AGV路线规划技术。
背景技术
仓储物流AGV的路径规划问题需要更先进的算法加以解决，尤其是基于遗传算法和蚁群算法类别的智能规划技术正在持续受到研究人员关注。越来越多的学者专家寄希望于改进传统的遗传算法和蚁群算法，并将其应用到仓储AGV路径规划算法里，以提高仓储物流的运行效率。本发明同样基于这个技术背景，对AGV路径规划算法做出一定程度的创新。
仓储AGV在现代物流系统中扮演至关重要的角色，是物流仓库中主要的搬运机器。随着人工智能和机器人技术的不断发展，智能工业时代逐渐到来，越来越多的工业场合开始引进工业互联网技术和机器人自动化技术，比较典型的代表就是现代物流仓储系统。相比传统物流系统较多依赖人力搬运，现代物流仓储系统已经大量采用堆垛机以及仓储AGV进行货物运输、搬运以及装卸，大大提高了物流系统运行效率，既减少了人力成本，又提高了企业利润，方便人们生活。AGV是一种具有较强灵活性和一定自主性的自动化搬运设备，涉及机械、材料、电气工程、电子信息、计算机、人工智能和自动控制等相关技术。AGV上装备有自动导向系统，可以保障系统在不需要人工引航的情况下就能够沿规划的路线自动行驶，以可充电的蓄电池为其动力来源，将货物或物料自动从起始点运送到目的地，一般可通过电脑来控制其行进路径以及行为，具有自动化程度高、充电自动化、减少占地面积等诸多优点。
针对AGV路径规划问题已经有很多传统算法和一些新型算法被提出。其中，蚁群算法和遗传算法对于解决仓储AGV路径规划问题具有一定的优越性。路径规划一直以来都是AGV研究领域的关键问题，其目的是在有障碍物的环境中，寻找一条最优或次优路径，该路径连接着起点和终点，安全且无碰撞。随着更多路径规划问题解决算法出现，路径规划算法大体可分为局部路径规划和全局路径规划。局部路径规划包括人工势场法、神经网络法、蚁群算法等几种经典算法；全局路径规划算法包括栅格法、拓扑法、遗传算法等几种比较常用的经典算法，已经可以通过数学理论进行方法证明和完善。其中，蚁群算法由于具有自我组织能力、正反馈机制、易于与其他算法结合、具有并行搜索能力等优点，适合对路径规划问题进行优化提升，因而得到广泛应用。然而由于概率传递的随机性和信息素强度更新的不适当性，传统蚁群算法容易陷入局部最优。而遗传算法由于具有较好的并行性和鲁棒性，被广泛应用于AGV路径规划中，但算法本身却有早熟收敛和局部搜索能力较弱等缺点。针对这些缺点，已经有不少改进方案被提出，比如一种将障碍物凸化处理的地图模型建立法，方便遗传算法的初始种群生成；或对自适应算子进行新的修改，提高了算法初期进化的能力；或者一种结合禁忌搜索算法的初始种群生成方法；亦或用一种多次随机交叉法来维持种群多样性。虽然上面的改进操作提升了遗传算法的部分性能，但是算法仍然存在一些缺点，比如算法的选择策略并没有实质改进，另外，算法的设计没有结合AGV实际运行环境。
单独使用蚁群算法解决AGV路径规划问题效果不够理想，具体体现在几个方面。比如，单独使用蚁群算法收敛速度慢的原因在于计算开销大，尤其当问题规模较大时需要迭代较多次数才能得到路径最优解，而过多的迭代次数往往会耗时巨大，失去的算法本身的意义；而蚁群算法易陷入局部最优的原因是蚂蚁搜寻路径是根据不同路线上信息素浓度的差别进行选择的，且随着蚂蚁数量增多，正反馈机制会更明确地指导蚂蚁选择特定路线前进，因此一旦局部路径的信息素浓度达到较高的水平，蚂蚁就极易陷入局部最优路径，从而无法挣脱，因此求得的路径解也将无法向全局最优路径解迭代；另外，蚁群算法需要初始化的参数较多，比如起始迭代次数N
单独使用传统遗传算法也因为算法本身的一些内在原因使得应用受限。单独使用传统遗传算法容易早熟收敛的原因是杂交算子在搜索过程中的成熟化效应，杂交算子既可强迫算法收敛，使之达到全局最优解，也有可能在搜索过程中过早成熟而使算法终止于非最优状态，所以有必要合理修正遗传算法；由于种群的多样性有限，而对于遗传计算过程来讲，群体的多样性保证了遗传算子正常发挥进化和重组效应。因此，群体的多样性，尤其是初始种群的多样性在防止程序陷入局部最优是有重要作用的；遗传算法需要设定的参数有很多，比如种群数量、变异概率、适应度函数内部参数、迭代选择策略以及变异方式所用到的参数等等，这些参数对于最终结果具有极大影响，并且在迭代过程中并不会更新，因此参数的设置取决于工程经验，这对遗传算法的应用造成了一定障碍。
为了解决此问题，本专利将对遗传算法分为三阶段进行选择策略改进。另外，对变异操作不再采用随机变异法而是采用有向变异法，最后再对优化结果进行轨迹圆滑操作，具有更高的工程实用性，同时应用蚁群算法产生初始路径，优化效果相较传统方法更佳。算法程序编制调试完毕后，将可执行文件上传至装有完整主控复位指令运行时库的工控服务器并按管控系统收集的任务输入开展算法运行，通过与仓储管理系统的预设兼容性接口将运行结果下放至AGV，完成相应取送货动作。
发明内容
日益复杂的厂房环境对AGV路径规划和避障等算法提出更高的要求，包括路径规划耗时短、算法收敛速度快、尽量达到或者接近全局最优解、运动轨迹足够圆滑等。单独使用蚁群算法应用在仓储AGV路径规划上往往存在收敛速度慢、易陷入局部最优的问题；而单独使用传统遗传算法同样有自身的缺陷，主要表现为容易早熟收敛(规划的路径远未达到全局最优路径时就满足算法设定的迭代终止条件，导致路径规划效果不理想)、参数设定过于依赖经验等问题。
本发明针对现有技术问题，提出一种基于蚁群算法的初始AGV路径迭代生成以及基于改进型遗传算法的仓储AGV路径规划方法，所述方法采用蚁群算法产生初始AGV路径，其特征在于设置较少的迭代次数产生几组良好个体，并以此作为遗传算法的初始AGV路径，相比传统方法随机产生的初始种群更加优良，有效降低了遗传算法早熟收敛的可能性。同时改进遗传算法选择策略，引入适应度函数作为路径是否足够优质的判定标准，以AGV路径适应度数量作为判断迭代是否终止的条件，有效地选择出优质路径，减少迭代次数，缩短算法收敛的时间。另外，根据AGV局部路径情况和避障特点，对遗传算法的变异阶段进行改进，使AGV路径只向有利方向变异，快速向全局最优解靠拢。算法参数的设定结合了AGV路径具体问题给出了比较合理的设定范围。最后，所述方法对迭代结束的AGV路径进行轨迹圆滑处理，避免折线转弯因减速、制动、转向而耗时。
本发明的目的是通过以下技术方案实现的：首先对厂房环境网格化划分并给每个网格编码，AGV运行路径即由带顺序的网格序号组成，其次进一步用蚁群算法经少量次数迭代产生初始AGV运行路径，用基于障碍物信息的改进蚁群算法生成用于遗传进化的初始AGV路径，再用三阶段改进型遗传算法对AGV路径进行选择优化、交叉变异，反复迭代直至AGV路径满足迭代终止条件，最后对迭代产生的最优路径进行轨迹圆滑处理，生成圆滑的全局最优路径。
本发明的流程图如图1所示，具体步骤如下：
步骤一：对厂房场地环境网格化划分与编码。
首先需要对厂房场地环境建立网格划分图，标清障碍物的位置，有障碍物的网格标为黑色，无障碍物且可以让AGV通行的网格标为白色，AGV运输车运行路径即由带顺序的网格序号组成，代表AGV逐个经过相应网格。设ms为单位长度与实际长度(米为单位)的比例尺，则一个网格边长的实际长度即为1/ms米。编码方式简洁明确，无需解码、译码操作，可有效加速程序运行。具体划分步骤如下：
1)把AGV运输车看作一个质点，对AGV运输车所处的厂房内环境进行二维网格化处理，并置于平面直角坐标系中，横向为X轴，纵向为Y轴；
2)参考设备摆放、厂房结构等实际情况，标灰位置为障碍物，即车辆不可达的区域。同时，障碍物按等比例的EnlargeNum倍扩大处理，以保留足够的运行安全包络范围余量，其余位置为运输车的安全行驶范围；
3)将环境按n×n的网格划分，每一个网格的边长为1个单位。图中0位置中心处代表立体库出入库口位置，n
4)对模拟网格进行坐标化、数字化，其相互对应关系为：“网格序号GridNum＝横坐标+10×纵坐标”。
步骤二：用基于障碍物信息的改进蚁群算法生成用于遗传进化的初始AGV路径。
由蚁群算法经过少量次数的搜索迭代产生AGV运行的初始路径，用来作为遗传算法的初始种群进行后续的迭代优化。具体步骤如下：
1)设定蚁群算法的参数。设起始迭代次数N
τ
其中L为路径长度；
2)在起点投放一只蚂蚁，记录蚂蚁下步经过的位置j并添加到存储着蚂蚁走过位置的禁忌表，蚂蚁将被禁止再次通过禁忌表中的位置，进而避免路径陷入死循环；p
其中η
其中
其中C
3)确认蚂蚁是否到达目的地，若未完成则继续以p
4)采取赌盘方法选择何处为下一位置，即以p
5)如蚂蚁到达目的地，则继续投放下一只蚂蚁，直至m只投放完毕，每一只蚂蚁到达目的地为止，输出最短路径；
6)全盘更新信息素，迭代次数加1，重回第二步骤继续循环，直至迭代总次数循环完毕；
7)最后得到m组最短路径，将其作为步骤三遗传算法的初始种群。
步骤三：用基于三阶段遗传算法迭代选择AGV最优路径。
本专利提出的三阶段遗传算法具体将种群进化阶段按迭代次数划分为三个阶段，每阶段按指定方式进行选择，设算法迭代次数上限为N
1)弱者扶持阶段——该阶段保护低适应度个体中携带的优秀基因片段(此处的个体是指具体的一条AGV路径，下文提到的个体均是此含义)，采取弱化适应度大小与选择概率的影响关系，提升弱者的生存几率，保持种群多样性，选择策略如下：
设种群数量为m，先计算种群中每一个AGV路径个体适应度Fit(x
设从厂房起点到达终点的路径D＝(D
则路径D的实际总长度为：
令运输车在任意可达区域内均速直线运动，速度为V
再更新每一条AGV路径的适应度值Fit(x
Fit(x
其中a为均衡因子，即通过对全部个体适应度值增加定量，来缩小原始适应度间的比例差距。
结合理论研究并考虑实际工况，设置将最差个体与最优个体间的竞争力差距缩小至约σ×100％，σ建议取0.25～0.35，通过对该阶段AGV轨迹优化情况统计测算，最差最优个体适应度水平比值一般不低于1/GapNum
a＝[(GapNum
最后计算得到第i条路径的新适应度值在总适应度中占比
其中Fit(x)
Fit(x)
2)公平竞争阶段——该阶段按轮盘赌选法执行，赌选策略为计算每个个体适应度值在种群总适应度中所占比重，以此作为个体被选中的概率：
先计算种群中每一条AGV路径的适应度Fit(x
再计算第i条路径的适应度值在总适应度中占比P
其中Fit(x)
Fit(x)
3)强者加持阶段——优秀个体必然携带稀有优秀基因片段，是大自然进化的财富，该阶段为避免优秀个体在优良个体群中被埋没而误杀，采取强化适应度大小与选择概率的影响关系，进一步提升强者的生存几率，选择策略如下：
先计算种群中每一条AGV路径的适应度Fit(x
进一步更新每一条AGV路径的适应度值Fit(x
Fit(x
其中b为突出因子。即通过对全部个体适应度值减少定量，来放大原始高适应度的比例优势；同样，结合理论研究并考虑实际工况，设置将此阶段最差个体与最优个体间的竞争力差距提升至约GapNum
b＝[(GapNum
最后计算得到第i条路径的新适应度值在总适应度中占比
其中Fit(x)
Fit(x)
步骤四：对具有重合点的不同AGV路径进行末端交叉。
为了提高AGV路径的种群多样性以及促使AGV路径跳出可能存在的局部最优，交叉策略采取单点交叉方式，保持优秀个体的基本基因序列及后代的延续性，末端交叉方式如下：
1)交叉点选择两条AGV运行路径中相同的网格序号处，将两条路径交叉点后面的末端路径相互对调，从而产生新的路径，交叉后的路径替代原先的路径作为下一代种群；
2)若存在多个公共网格，则随机选取一个公共网格作为交叉点，若无公共网格则将此两条路径序列直接作为下一代，且公共网格不包含起始、终点，交叉概率设为恒定概率P
步骤五：对AGV路径进行有利变异，根据不同路径情况采取不同变异操作策略，具体指基于路径最短的目标，使路径序列总长往变短趋势发生变异，即减少拐弯次数或优化转弯方式。
本专利设计了根据不同路径情况采取不同操作的策略，具体有利变异规则如下：
1)AGV遇到障碍物时如出现直角折线式转弯避障的情况，则触发相应有利变异，变异不区分方向，规则为确认路线中每一个拐点相邻前后两个位置点的连线是否触碰到障碍物，如未触碰到则以连线作为路径的一部分，以此类推，直至拐点相邻位置点不可连接为止，即遇到障碍物；
2)判断路径连线是否遇到障碍物的方法为构造连线数学表达式并与障碍物边框所在线段计算相交位置，如交点个数为2个及以上，则判断为遇到障碍物，即终止有利变异；
3)当避障时，局部路径中出现小于90°的拐角时触发有利变异，变异规则为拐点向靠近拐角增大的方向移动一个单位，即向拐点相邻两位置点连线的靠近方向。变异后拐角如仍小于90°，则继续执行变异直至拐角大于或等于90°。判断路径拐角大小的方法为构造两条拐边所在直线，并计算两直线间夹角；
4)设定变异概率P
步骤六：重新计算AGV路径适应度，判定迭代是否终止，对终止后的AGV路径进行轨迹圆滑处理。
重新计算变异后的AGV路径种群的适应度Fit(x
进而判断是否符合迭代终止条件，符合则终止迭代，不符合则返回步骤三第1)步，继续迭代直至产生足够高适应度的AGV路径，迭代结束后的AGV路径是直线型路径，转弯处不够圆滑；
再对迭代终止后得到的AGV路径做最后的轨迹圆滑处理。需要找到AGV转弯触发点、转弯半径、以及转弯终止点，最终将得到较为圆滑的AGV路径。
由于迭代后的AGV路径均是直线型路径，当遇到障碍物或者需要转向的时候就需要经过减速、制动、转向、再启动、加速、匀速直线运动的过程，该过程不仅耗时，而且对电机、机械结构均有损耗，因此对AGV路径转折点进行圆滑操作十分必要。
本发明与现有技术相比具有如下优点：
本发明将蚁群算法引入AGV路径规划的具体问题当中，利用蚁群算法经过少量次数的迭代产生了AGV初始运行路径，相比传统的随机产生AGV初始路径的方法，所述方法可以得到更加优良的初始路径，可以作为优质的初始变异种群，给后续的改进型遗传算法迭代优化。少量的迭代次数不仅缓解了蚁群算法计算耗时的弊端，而且初始迭代产生的优质种群可以有效改善遗传算法早熟收敛的缺陷，有助于快速求出全局最优解。
同时，本发明采用遗传算法对初始路径不断迭代优化，针对AGV路径规划具体问题，将遗传算法分为三阶段做出选择策略的改进，既保留了初始劣质种群含有的少量优质基因，维持了种群多样性，又对后期优势种群进行了加持，使得更加优良的AGV优化路径得以保留下来，有助于快速迭代筛选出最优路径解，减少算法的迭代次数，节省计算时间。
另外，本发明抛弃传统遗传算法中随机变异的方法，而是结合AGV实际运行时拐弯和避障的具体情况，调整AGV运行轨迹的变异方式，使AGV局部运行路径向路线总长减少的方向发生变异。相比随机变异可能产生劣质基因的缺陷，本发明可以根据AGV局部路径情况，实现高概率的有利变异，使得AGV路径种群向更优方向迭代，从而有效避免AGV路径陷入局部最优解，促进其向全局最优方向快速收敛。
最后，本发明还根据AGV转向时局部轨迹的实际情况，进一步对进行轨迹圆滑处理，使转弯轨迹以圆弧的形式圆滑过渡，可有效避免在传统算法下AGV折线转弯时制动、转向、再启动的时间，使得AGV路径全局最优解得到进一步优化，既节省了时间，又减小了机械结构和电气设备的损耗。本发明针对实际厂房环境下仓储AGV轨迹规划具体问题，具有更强的工程实用性，大大提升了AGV的运行流畅性，进一步加快了仓储物流的运行效率。
附图说明
图1为本发明的工作流程图。
图2为厂房环境网格划分图。
图3为90°拐角变异过程示意图。
图4为遇到障碍物终止变异示意图。
图5为小拐角变异示意图。
图6为小转角情况下轨迹圆滑处理示意图。
图7为大转角情况下轨迹圆滑处理示意图。
图8为AGV高峰任务分布图。
具体实施方式
现结合附图和实施例说明本发明的具体实施方式。
本实验例的应用场景为一个物流仓库，仓库场地包含授货台、堆垛机、几十台AGV、货架，同时厂房内一些基础设施可能成为AGV行进路径上的障碍物，所提算法程序编制调试完毕后，将可执行文件上传至装有完整主控复位指令运行时库的工控服务器并按管控系统收集的任务输入开展算法运行，通过与仓储管理系统的预设兼容性接口将运行结果下放至AGV，完成相应取送货动作。
如图1所示的蚁群算法-遗传算法混合路径规划方法，包括对厂房环境进行编码建模，用蚁群算法进行少量次数的迭代产生AGV路线初始种群，计算适应度，进一步再按照遗传算法三阶段策略进行种群选择，经过单点交叉、有利变异，产生较为为优质的种群，并通过适应度计算进行判断种群是否足够优良作为终止迭代的条件，不断迭代直至筛选出满足要求的AGV路径规划结果，最后对轨迹进行圆滑处理，输出最优解。所述算法整体的具体步骤与实施细节如下：
执行步骤一：对厂房场地环境网格化划分与编码。
首先对厂房场地环境建立网格划分图，标清障碍物的位置，有障碍物的网格标为黑色，无障碍物且可以让AGV通行的网格标为白色，如图2所示。AGV运输车运行路径即由带顺序的网格序号组成，代表AGV逐个经过相应网格，设ms为单位长度与实际长度(米为单位)的比例尺，则一个网格边长的实际长度即为1/ms米。具体划分步骤如下：
1)把AGV运输车看作一个质点，对AGV运输车所处的厂房内环境进行二维网格化处理，并置于平面直角坐标系中，横向为X轴，纵向为Y轴。
2)参考设备摆放、厂房结构等实际情况，标灰位置为障碍物，即车辆不可达的区域。同时，障碍物按等比例的EnlargeNum倍扩大处理，EnlargeNum建议设置为[1.1,1.5]范围内的数值，此处取1.2，以保留足够的运行安全包络范围余量，其余位置为运输车的安全行驶范围。
3)将环境按n×n的网格划分，每一个网格的边长为1个单位。图中0位置中心处代表立体库出入库口位置，n
4)对模拟网格进行坐标化、数字化，其相互对应关系为：网格序号GridNum＝横坐标+10×纵坐标。如网格85＝(5，8)坐标点，(4，6)坐标点＝网格64。
执行步骤二：用基于障碍物信息的改进蚁群算法生成用于遗传进化的初始AGV路径。
由蚁群算法经过少量次数的搜索迭代产生AGV运行的初始路径，用来作为遗传算法的初始种群进行后续的迭代优化。具体步骤如下：
1)设定蚁群算法的参数。设起始迭代次数N
τ
L为路径长度，如起始位置为0，终点位置为99，某条路径长度可取0→1→71→72→82→88→98→99，即L＝1+7+1+1+6+1+1＝18，τ
2)在起点投放一只蚂蚁，记录蚂蚁下步经过的位置j并添加到禁忌表，禁忌表存储着蚂蚁走过的位置，蚂蚁将被禁止再次通过禁忌表中的位置，避免路径陷入死循环；计算第k只蚂蚁选择从位置i转移到j的概率
3)确认蚂蚁是否到达目的地，若未完成则继续以p
4)采取赌盘方法选择何处为下一位置，即以p
5)如蚂蚁到达目的地，则继续投放下一只蚂蚁，直至m只投放完毕，每一只蚂蚁到达目的地为止，输出最短路径。
6)全盘更新信息素，迭代次数加1，重回第二步骤继续循环，直至迭代总次数循环完毕。
7)最后得到m组最短路径，将它们作为步骤三遗传算法的初始种群。
执行步骤三：用三阶段改进型遗传算法迭代选择AGV最优路径。
将种群进化阶段按迭代次数划分为三个阶段，每阶段按指定方式进行选择，设算法迭代次数上限为N
1)弱者扶持阶段：
该阶段保护低适应度个体中携带的优秀基因片段(此处的个体是指具体的一条AGV路径，下文提到的个体均是此含义)，采取弱化适应度大小与选择概率的影响关系，提升弱者的生存几率，保持种群多样性，选择策略如下：
设种群数量为m，计算种群中每一个AGV路径适应度Fit(x
进而更新每一条AGV路径适应度值Fit(x
Fit(x
其中a为均衡因子。即通过对全部个体适应度值增加定量，来缩小原始适应度间的比例差距。结合理论研究并考虑实际工况，设置将最差个体与最优个体间的竞争力差距缩小至约25％，通过对该阶段AGV轨迹优化情况统计测算，最差最优个体适应度水平比值一般不低于1:1.6，由此取a＝[(1.6-1)/0.25]-1＝1.40。
最后计算得到第i条路径的新适应度值在总适应度中占比
其中Fit(x)
Fit(x)
2)公平竞争阶段：
该阶段按轮盘赌选法执行，赌选策略为计算每个个体适应度值在种群总适应度中所占比重，以此作为个体被选中的概率。
首先计算种群中每一个AGV路径个体适应度Fit(x
进而计算得到第i条路径的适应度值在总适应度中占比P
其中Fit(x)
Fit(x)
3)强者加持阶段：
优秀个体必然携带稀有优秀基因片段，是大自然进化的财富，该阶段为避免优秀个体在优良个体群中被埋没而误杀，采取强化适应度大小与选择概率的影响关系，进一步提升强者的生存几率，选择策略如下：
先计算种群中每一个AGV路径适应度Fit(x
进而更新每一条AGV路径适应度值Fit(x
Fit(x
其中b为突出因子。即通过对全部个体适应度值减少定量，来放大原始高适应度的比例优势。结合理论研究并考虑实际工况，设置将此阶段最差个体与最优个体间的竞争力差距提升至约15％，通过对该阶段AGV轨迹优化情况统计测算，最差最优个体适应度水平比值一般不低于1:1.05，由此取b＝1-[(1-1.05)/0.15]≈0.67。
最后计算得到第i条路径的新适应度值在总适应度中占比
其中Fit(x)
Fit(x)
执行步骤四：对具有重合点的不同AGV路径进行末端交叉。
交叉策略采取单点交叉方式，保持优秀个体的基本基因序列及后代的延续性，交叉方式如下：
1)交叉点选择两条AGV运行路径中相同的网格序号处，将两条路径交叉点后面的路径相互对调，从而产生新的路径，交叉后的路径替代原先的路径作为下一代种群。
2)若存在多个公共网格，则随机选取一个公共网格作为交叉点，若无公共网格则将此两条路径序列直接作为下一代，且公共网格不包含起始、终点，交叉概率设为恒定概率P
执行步骤五：对AGV路径进行有利变异，根据不同路径情况采取不同变异操作策略。
具体指基于路径最短的目标，使路径序列总长往变短趋势发生变异，即减少拐弯次数或优化转弯方式，本专利设计了根据不同路径情况采取如下不同的操作：
1)AGV遇到障碍物时如出现直角折线式转弯避障的情况，则触发相应有利变异，变异不区分方向，规则为确认路线中每一个拐点相邻前后两个位置点的连线是否触碰到障碍物，如未触碰到则以连线作为路径的一部分，以此类推，直至拐点相邻位置点不可连接为止，即遇到障碍物，如图3所示。
2)判断路径连线是否遇到障碍物的方法为构造连线数学表达式并与障碍物边框所在线段计算相交位置，如交点个数为2个及以上，则判断为遇到障碍物，即终止有利变异，如图4所示。
3)当避障时，局部路径中出现小于90°的拐角时触发有利变异，变异规则为拐点向靠近拐角增大的方向移动一个单位，即向拐点相邻两位置点连线的靠近方向。变异后拐角如仍小于90°，则继续执行变异直至拐角大于或等于90°。判断路径拐角大小的方法为构造两条拐边所在直线，并计算两直线间夹角，如图5所示。
4)设定变异概率P
执行步骤六：重新计算AGV路径适应度，判定迭代是否终止，对终止后的AGV路径进行轨迹圆滑处理。
重新计算变异后的AGV路径种群的适应度Fit(x
进而判断是否符合迭代终止条件。符合则终止迭代，不符合则返回步骤三，继续迭代直至产生足够高适应度的AGV路径。对迭代终止后得到的AGV路径做最后的轨迹圆滑处理。需要找到AGV转弯触发点以及转弯半径，以及转弯终止点。圆滑的具体操作如下：
1)首先以90°拐角状态计算出转弯半径R。经计算
继续执行下一步操作。
2)车辆遇到拐弯点，在距理论拐弯点q位置时，以当前位置为切点，执行半径为R的圆弧程序转弯，直到转弯至理论拐点对侧q位置时，以当前位置方向切换为直线运行，至此本次圆滑处理结束，后续路径如有圆滑处理仍需继续执行步骤六直至完成所有任务，小转角和大转角情况下轨迹圆滑前后的路线示意图分别如图6和图7所示。
应用本发明的具体实验例及实验结果如下：
本实验例在班后时间开展，系统空载跑合，为对标实际工作状态，AGV均在额定安全速度下运转，平均运行速度V
以周一早高峰AGV运输车的任务队列为研究对象，将共12个出库任务及8个入库任务配对后的目标位置作为输入条件，如图8所示。
任务的起点均为出入库交接点网格0处，如第一组出入库任务[83,45]的执行过程为AGV携带产品从网格0出发前往网格45送货，完毕后从网格45前往网格83取货，拾取后携带货物回到网格0处，完成一组任务，以此类推，当入库目标点为0位置时，则任务组为仅出库任务。通过采用不同算法进行对比实验，验证混合算法及变异算子改进的效果。
关于算法程序计算耗时，AGV不同于仓储堆垛机需要先计算出全盘最优规划，再按时序从第一项任务开始执行。AGV任务时序已伴随仓储堆垛机规划方案确定，而AGV路径轨迹规划算法程序可采取边工作边运算的方式，即计算出第一组出入库任务的具体路线后，AGV车启动工作，同时算法程序继续运算后续路线，以此类推。当AGV阶段工作完毕，而算法程序还未计算出下条任务路线时，则将出现等待时间。
经过大量实验跑和发现，迭代次数取30～100的最终优化结果均很好，采用本专利的用户可以根据具体情况，适当调整参数以取得最好的效果，本实验例根据具体场合取迭代次数为50，观察不同算法的路径规划效果。
经记录，对比实验的结果如下：
以起点0位置，终点99位置的配送任务为输入，有利变异概率P
表1 AGV调度优化实验结果
由上述结果可知，随着混合算法和变异算子的施加，AGV行进路径、运行时间不断缩短，说明两种算法优化方法均有一定正面效果，同时由此带来了程序计算量的增加，最终导致总耗时偏高。但是AGV任务时序已伴随仓储堆垛机规划方案确定，AGV路径轨迹规划算法程序可采取边工作边运算的方式，即计算出第一组出入库任务的具体路线后，AGV车启动工作，同时算法程序继续运算后续路线，以此类推。采用这种方式，可有效减少计算耗时带来的影响。
以周一早高峰12组AGV出入库实际任务队列为输入，有利变异概率P
观察以上实验结果，可以看出迭代次数为30、50和80时算法的路径规划效果均较好，AGV均能以较短路径到达目的地，且耗时较短。同时可以看出，当迭代次数为50时，迭代效果更好。以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的专业技术人员来说，在不脱离本发明原理的前提下还可以做出一定的改进，这些改进也应当视为本发明的保护范围。
表2迭代次数为30时AGV调度优化结果
表3迭代次数为50时AGV调度优化结果
表4迭代次数为80时AGV调度优化结果
机译： 基于改进蚁群算法的停车AGV路线规划方法
机译： 基于改进蚁群算法的停车AGV路线规划方法
机译： 基于改进的蚁群算法的路径规划方法，装置，终端和介质
