冯晨钟，宋世创，李慕航

(山西农业大学，山西 太谷 030800)

0 引言

近几年，电子商务在我国高速发展，快递行业发展迅猛，部分派件点经常出现排队现象，派件时间效率等都受到限制。本论文深入研究智能派件，仓储系统中通常有多辆小车并发执行任务，遗传算法、蚁群等算法可以解决单个小车到达目的地的最短路径问题，如果两车即将发生碰撞，通常采用优先级的方式依靠停车进行错车，这样做虽然路程最短，但忽略了停车时间的长短，在智能派件中时间参数是我们考虑的第一要素。

梁肖[1]将遗传算法的路径优化应用到小麦收割机的收割过程；何庆[2]提出一种改进自适应的Metropolis准则,使模拟退火算法部分的染色体跳变更具有自适应性,利于算法寻优解决遗传算法一出现局部最优的问题；申艳光[3]提出了通过聚类分析中K-means算法与改进遗传算法相结合的混合遗传算法，实现优化配送路线；周建国[4]将遗传算法应用到农产品配送的路径优化上，提高其配送效率。

遗传算法在优化路径方面达到很好的效果，论文结合实际把遗传算法应用到仓储机器人的路径优化问题，解决多个机器人在同一仓库工作的冲突问题。

1 图表转化

采用栅格法对仓库实际与计算能识别的矩阵建立对应关系。栅格法实质上是将AGV的工作环境进行单元分割，将其用大小相等的方块表示出来，这样栅格大小的选取是影响规划算法性能的一个很重要的因素。通常边长应该略大于小车的长度，方便小车在格栅中行走。本文考虑小车所在的环境因素，对小车环境进行抽象描述：以边长为a*a的正方形格为单位，将小车所在环境进行分解，建立起形状相似、面积相同的栅格图。

格栅与路径权值：设置速度和格栅的边长(考虑小车的长度)得到每个栅格的权值，论文把该值设为2S，即小车通过一个格栅的权值为2。

在栅格图中定义左上角第一个栅格坐标(0,0)，横向为x轴，纵向为y轴建立直角坐标系。假设仓储长为L米(对应纵坐标)，宽W米(对应横坐标)，以边长为a米的单元栅格为单位，则每行的方格数为h(W/a)，每列的方格数为v(L/a)。

栅格编号：id=y*(W/a)+(x+1)

2 遗传算法

2.1 传统遗传算法

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的操作使用符合适者生存原则，在潜在的解决方案种群中逐次产生一个近似最优的方案，在遗传算法的每一代中，根据个体的问题域中的适应度值和从自然遗传学中借鉴来的改造方法进行个体选择，产生一个新的近似解。使得种群中的个体进化，更适应环境。

2.2 改进的遗传算法

2.2.1 初始种群

传统遗传算法的初始群体固定不变，计算的行走距离只考虑路径的路程，即长度,相当于只考虑静态的路径，没有考虑多辆车同时执行任务避障的时间。

2.2.2 更新种群

每一辆小车的行走路径都要在已经规划好并且还未执行完的路径的基础上进行设计规划。首先判断新路径和已经存在的路径是否存在交叉，交叉包括路径上的交叉和时间上的交叉，在路径交叉的基础上判断是否时间交叉。如果存在时间交叉(获取到达该段的时刻，判断其是否在锁定时间)，即该路段处于上锁状态，如果不存在时间交叉，即处于解锁状态。通过权值的动态变换来更新种群。更新种群流程图如图1所示。

图1 更新种群流程图

3 实验

为了验证算法适应性，分别进行了货架数量为2和货架数量为6的仿真实验。当货架数量为6，仓储部署图如图2所示。

图2 仓储部署图

抽象及权值简化图(本文涉及的仓储简化图中的黑点表示起点和终点)如图3所示，将仓储实际跟遗传算法的用种群矩阵建立联系。

假设此车规划路径时，⑥-⑦与其他车已规划好的路径存在非同向交叉。

图3 抽象及权值简化图

传统遗传算法运行的最优、平均函数值如图4所示，30代左右，最优函数值趋于稳定；从对比及最优函数值变化趋势可知，该算法可以很好地解决仓储的最优路径规划问题。

图4 最优，平均函数值变化趋势图

更新种群后权值简化图如图5所示。图6为染色体最终位置图。从染色体的最终效果可以看出算法能很好地解决冲突问题，实现路径最优化。

图5 更新种群后的权值简化图

图6 染色体的最终位置图

4 结语

本文采用遗传算法实现仓储机器人的路径规划，采用时间同步、上锁与解锁的方法解决多车执行任务中出现的冲突、碰撞等问题，建立了自适应的种群更新机制。该方法对遗传算法的种群进行了更新，实现根据实际情况的自适应种群。仿真和模拟实验表明，该算法可以有效解决两车或多车经过同一点的冲突问题，采用传统的遗传算法实现处理后的种群的最优路径的选择。本文改进的遗传算法达到了仿真及模拟实验的要求，取得了较好的效果。

[1] 梁肖,周湘贞.基于遗传算法的小麦收割机路径智能优化控制研究[J].农机化研究,2018,40(2):56-60.

[2] 何庆,吴意乐,徐同伟.改进遗传模拟退火算法在TSP优化中的应用[J].控制与决策,2018,33(2):219-225.

[3] 申艳光,张玲玉 ,刘永红.基于混合遗传算法的物流路径优化方法研究[J/OL].计算机技术与发展, 2018(3)[2018-04-07] http://kns.cnki.net/kns/brief/default_result.aspx.

[4] 周建国.基于改进遗传算法的农产品配送路径优化研究[J].中国市场,2018(1):136-138.

[5] ChenLin.An Adaptive Genetic Algorithm based on Population Diversity Stratety [A].Junfa Mao.2009 Third International Conference on Genetic and EvolutionaryComputing[C],New York:IEEE,2009:93-96.

[6] 李延梅. 一种改进的遗传算法及应用[D].广州：华南理工大学,2012.

[7] 梁芳. 遗传算法的改进及其应用[D].武汉：武汉理工大学,2008.