基于遗传算法的工厂AGV路径优化研究

党宏社 孙心妍

摘要：针对工厂AGV行驶路径复杂、应用局限性等问题，vRAGV配送物料行驶路径最短为目标，采用遗传算法进行AGV路径规划，并加入物料类型选择的循环套，通过多次实验确定最合理的控制参数，从而产生AGV运输多种类型物料的最优路径结果。使用Maflab软件对算法进行仿真，结果表明：该算法是有效的，能够直接实现ACV在输多种类型物料时所产生的不同种路径的优化。

关键词：自动导引车;路径规划;遗传算法

0引言

随着社会生产技术的发展和自动化程度的提高，很多工厂为了提升运输工作效率，引入了自动导引小车AGV（Automatic Guided Vehicle）进行物流运输。据相关资料统计，在制造业中不足5%的时间用于加工装配，而超过95%的时间用于物流配送，因此物料的及时准确供应直接关系到生产线的流畅性。节约车间生产成本，减少物料运输时间，提升单台AGV搬运效率，一直以来AGV的路径规划问题，即寻找AGV的最优路径是工厂所关注的焦点。

目前国内外很多学者都对于AGV的路径规划问题做了相应的研究。遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索优化方法，具有算法效率高、鲁棒性强、可实现并行搜索等特点，被广泛用于解决路径规划等领域的问题。G.Jeon和William等人用混合遗传算法求解车辆路径规划问题：李青欣进行了AGV路径规划的遗传算法研究，根据运行环境信息复杂度和数量的不同分别分析了几种不同类型的路径规划。

当前国内外学者在AGV的路径规划问题上取得了诸多成果，但是实际的工厂生产情况多变，机器所需的物料并不相同，因而AGV的运输路径也有差异。多类型物料的运输与AGV路径的优化相结合的研究目前并不多见也不够完善。

针对遗传算法解决路径规划问题时只能完成单任务、实现单次运输路径规划的不足，为提升规划效率，扩大应用面，本文在路径规划以前，加入对于物料的选择情况，构建路径规划数学模型，设计遗传算法并进行数据仿真，一次得到AGV运输多种物料的行驶路径。仿真结果表明本文提出的基于遗传算法的AGV路径规划方案对于解决此类运输问题是有效的。

1工厂AGV路径规划的模型

1.1问题描述

某工厂的AGV运输物料模型一般可以描述为：工厂的生产车间共有20台工作机器，需要5种物料，当AGV运输不同物料时，途经的机器坐标和数量不同，行驶路径有很多种。本文将研究如何运用遗传算法高效直接的产生AGV运输多种物料时的不同路径优化结果。鉴于AGV运输物料的过程比较复杂，且为了便于本文的模型建立及研究，现做如下规定和假设：

1）单台AGV只可运输一种物料：

2）AGV初始位置均在物料配送中心：

3）AGV行驶路径是指从物料配送中心坐标为起点，途经所有需要此种类型物料的机器，最后回到起点;

2遗传算法的流程

本文采用遗传算法进行路径的优化。算法的具体流程图如下图1所示：

采用1-N的数字随机排列的方式进行编码，可以省去解码环节，提高了算法的运行效率，其中一条染色体就代表AGV在车间内运输物料的一种行驶路径。

3.2初始群体的设定

本文中考虑一般情况下，在编码空间内均匀采样，对于Ⅳ台工作机器，随机生成一定数目的个体（一般为机器数量的2倍，即2N），每个个体代表AGV运输特定类型物料的路线。传统的算法解决路径规划问题时，初始群体都是固定值，算法只产生适用一种情况的最优路径，本文在算法的前端加入了物料类型选择的循环套。当AGV运输A、B、C、D、E这5种不同类型的物料时，初始群体的规模也不相同，具体数值如下表所示：

选择过程体现了自然界生物进化过程中“适者生存”的思想，并且能够确保适应度强的优良基因遗传到下一代的个体。

3.4.2交叉操作

本文中，假设随机选择两个已经被复制的个体分别为：A=35749，B=46285，确定交叉点，A=35I 749，B=46I 285，在对应位置交换基因片段，同时保证每个个体依然是1-N的随机排列，防止进入局部收敛，交叉过程后则产生=46749，=35285两个新个体。

3.4.3变异操作

本文中，在已经被选择的个体中，随机选取1个个体，同时随机选取个体的两个基因进行交换，实现变异操作。假设随机选取個体A=3576289，选取该个体上的“3”“7“两个基因进行位置互换，可以得到新的个体=7536289。通过变异操作，可增加种群的多样性，有效地防止了遗传算法过早的收敛，出现“早熟”现象。

3.5控制参数的设定以及循环终止条件

遗传算法中关键的参数为：交叉概率、变异概率和迭代次数C。交叉概率控制着交叉算子的应用频率，变异操作是保持群体多样性的最有效手段，迭代次数决定了遗传操作的执行次数。为了确保参数设置的有效性和合理性，做了如下实验。

3.5.1交叉概率

选择将AGV运输C类物料的路径作为研究对象，遍历机器数目为N=13，AGV行驶路径个数也即群体规模为2N=26，迭代次数C为50次，设定变异概率，改变交叉概率的数值，每种情况实验15次，求出不同数值下的平均路径长度，发现当交叉概率时，平均路径长度最短。因此，本文中遗传算法的交叉概率取值为0.6为宜。

3.5.2变异概率

遍历机器数目、AGV行驶路径个数、迭代次数保持不变，设定交叉概率，改变交叉概率的数值，每种情况实验15次，求出不同数值下的平均路径长度。发现当变异概率时，平均路径长度最短。因此，本文中遗传算法的变异概率取值为0.08为宜。

3.5.3迭代次数

本文将AGV运输不同类型的物料时算法迭代次数设为不同的值，当遍历机器数目为N时，迭代次数C为4N，从而提高了算法的运行效率。

3.5.4循环终止条件

本文迭代终止条件连续4代最优解不发生变化则迭代停止，输出最优解。

4实验仿真与结果分析

在Matlab2016环境下运用改进后的遗传算法进行路径的优化，可以一次性得到AGV分别运输车间要求的5种物料时的优化路径，仿真结果如下图3所示：