基于改进遗传算法的物料配送多AGV调度优化

刘旭,楼佩煌,钱晓明,武星

(南京航空航天大学 机电学院，江苏 南京210016)

    为解决混流作业车间中物料配送多自动导引车（AGV）的调度优化问题，以AGV配送物料行驶时间最短为目标建立数学优化模型，提出了一种改进的遗传算法进行AGV的任务分配和配送路径优化。在算法设计过程中，采用直接反映AGV配送路径和任务分配的整数编码方式，为避免常规交叉变异过程中产生不可行解的情况，改进了交叉变异算子，采用最好-最坏交叉模式和基因段随机交换的变异模式，获得了优化的调度方案。最后，以某重型机械公司装配车间内物料输送AGV调度优化为实例，并与遗传算法和分支定界法进行对比，验证了所提方法的可行性和有效性。

    随着自动化技术和计算机技术不断发展，自动导引车（Automated Guided Vehicle，AGV）作为一种灵活高效的输送设备在制造系统、码头以及仓储系统等领域得到广泛的推广和应用。据相关资料统计，在制造业中不足5%时间用于加工装配，而超过95%时间用于物流配送，因此物料的及时准确供应直接关系到生产线的流畅性［1-2］。AGV作为物流配送的关键设备，如何合理地进行调度，以提高物料搬运效率和降低生产成本，一直是企业关注的焦点。目前国内外对AGV调度的研究也比较多，主要集中于AGV路径和生产效率优化方面［3］。王国新［4］等针对制造系统中单AGV任务调度优化问题，提出离散仿真和分支定界（Branch and Bound Algorithm，BBA）相结合的方法，但是该方法迭代次数较多；罗建［5］等针对自动仓储系统调度优化问题，建立单 AGV调度数学模型，运用一种改进量子微粒群算法(Quantum Particle Swarm Optimization， QPSO)来求解模型，但是没有考虑多任务调度问题；Nishi［6］等针对制造系统中多AGV路径规划问题，建立多AGV调度模型，提出一种分解算法进行求解。

    以上研究多集中在单AGV或单任务调度优化问题上，本文对车间物料输送多AGV调度优化问题进行了深入的研究，在建立多AGV调度优化数学模型的基础上，提出了一种改进的遗传算法(Improved Genetic Algorithm, IGA)进行求解，最后针对具体实例，给出了物料配送路径和AGV任务分配优化结果，证明了所提方法的有效性和可行性。

1问题的描述和建模

    混流作业车间物料输送是根据各工作站的物料配送需求，合理调度AGV将物料准确及时地运送到各需求点。混流作业车间物料配送AGV调度优化问题比较复杂，在建模过程中必须考虑AGV任务分配原则、物料需求情况、AGV路径冲突、车载容量等因素。如果AGV调度不合理，可能使物料配送时间过长，导致生产成本增加。鉴于混流作业车间中物料配送多AGV调度比较复杂，故作如下假设：

    a.系统生产节拍、系统布局、系统AGV数量和导引路径均是已知，AGV启动、停止时间和运行故障问题（系统瘫痪、脱线等）忽略不计，AGV在工作站中的服务时间是固定的。

    b.所有缺料的工作站只需配送一次，同一个工作站不允许配送两次。

    c.AGV初始位置均在物料配送中心，沿着最短路径，以固定速率运行。

    d.AGV可以同时接收多个任务，依次执行，并......

作者简介：刘旭(1988—)，男，山东威海人，南京航空航天大学硕士研究生，主要研究方向为自动导引车调度与控制。
（文章来源《机械设计与制造工程》如需详细资料请联系江苏机械门户网025-83726289）