基于蚁群算法和遗传算法RGV动态调度研究

周自力,吴福珍,张心怡

(1.浙江水利水电学院 建筑工程学院,浙江 杭州 310018;2.浙江水利水电学院 基础部，浙江 杭州 310018)

0 引 言

RGV轨制导车辆(rail guided vehicle)是一种无人驾驶、能在固定轨道上自由运行的智能车。RGV仓库导轨式调度系统的工作效率是当前的瓶颈，故解决RGV动态调度效率是关键。

(1)国内外研究现状

意大利学者M.P. FANTI[1]在文献中通过着色赋时Petri网建立了具有环状运输系统的标准化自动仓库模型，根据六种RGV调度的策略下的货物运输效率，得出了RGV利用率最高的调度策略。南洋理工大学学者E.K. ONG和S. G. LEE, R. DE SOUZS[2]在发表的文献中用先到先服务(first come, first serve)的策略，研究仓库环形运输系统各种情况下的使用效率，得出每种调度情况下的最佳RGV数量。厦门大学罗建教授和博士研究生吴长庆等[3]在其文献中，对于自动小车的控制问题，利用双重着色赋时Petri网，建立了RGV的动态调度系统模型。在RGV运行最短路径的条件下，提出了RGV系统效率最高的模型。

(2)现状的分析和本文研究的问题

在现有的国内外对于RGV调度研究中，已经对3种运输系统(直行轨道式、分段式、环形轨道式)的RGV调度问题做了一般性的研究，但现有的模型对运输系统的设计和RGV的调度较为简单，但并没有考虑物料流量对效率的影响。如果碰到大流量的物品调度，效率无法满足实际需求。本文研究的问题是在物料流量相对较大的情况下，即在运输系统运行的大部分时间里，RGV处于工作状态，且RGV数量远小于所需物料运输量，如何调度运输系统的RGV，使得效率达到最高。针对上述问题，本文运用蚁群算法和遗传算法，很好地优化了调度多个RGV小车运送货物方案，减少RGV小车的待机和堵塞，最大限度提高了系统运行效率。

1 基于蚁群算法的一道工序加工RGV动态调度模型

1.1 RGV概述

RGV根据指令能自动控制移动方向和距离，完成上下料及清洗物料等作业任务。物料在CNC中加工有3种情况：一道工序的物料加工；两道工序的物料加工；CNC在加工过程中发生故障(发生概率约为1%)，每次故障排除时间介于10～20 min之间，故障排除后即加入作业序列。

1.2 RGV一道工序加工RGV动态调度模型

本文关键是分析自动引导车在导轨上的移动状态，根据蚁群算法，借助自动化仓库[3]的生产管理调度，以建立RGV动态调度模型。为使整个加工过程效率最大化，需对RGV进行合理的动态调度。

对于一道工序的RGV加工作业情况，先将所有加工点需求按泊松分布生成，对RGV的初始位置和运行速度进行标记，根据各加工点的位置和产生需求的时间，进行动态标记，本文用蚁群算法[4]对模型进行求解。故整个问题转化为如何调度RGV，使其在任务动态变化的情况下，效率达到最高，该效率可用RGV走过的总路程或花费的总时间来描述。故本文用蚁群算法对模型进行求解。

定义:

(1)

RGV加工的运动可分为两部分：①从作业原点移动至CNC加工点(或者从加工点返回至原点);②从一个加工点移动至另一个加工点。RGV从作业的原点到加工点进行的是点到点(point to point，PTP)运动，RGV在各加工点之间的移动也是PTP。PTP运动指的是只考虑起点与目标点，不用考虑两点之间移动的过程。

1.3 计算CNC加工机距离矩阵

由平面解析几何中两点间距离公式，以式(1)中的CNC加工机坐标，很容易计算出任意两CNC加工机间的距离矩阵，因此用RGV移动的距离总和作为目标函数，衡量结果是否为最优解。

任意两CNC加工机i、j之间的距离可表示为:

(2)

由样本的移动距离长度得到目标函数，每两个CNC加工机之间的组合数为t-2组，故建立目标函数：

(3)

1.4 迭代寻找最佳路径

这一步是蚁群算法的核心，首先由蚂蚁的转移概率建立解的空间，即所有的蚂蚁逐一经过CNC加工机，进而计算每一只蚂蚁走过的距离。并在每次迭代后通过信息素改变公式即时更新各个CNC加工机连接路径上的信息素浓度。通过循环迭代，记录下最优的路径和路径长度。

建立了对于一道工序的RGV加工作业的数学模型：

T=min {T1+T2}

(4)

RGV的移动轨迹为：

CNC1→CNC3→CNC5→CNC7→CNC8

→CNC6→CNC4→CNC2→CNC1

2 基于遗传算法的RGV动态调度的模型建立与求解

对于两道工序的RGV加工作业情况，此时物料的处理过程变为两步，并要在两台不同的CNC上加工完成，第一种情况的加工策略已不再适用，需要考虑的是如何调度RGV使其能完成两台CNC的协同工作，最后根据建立的模型进行计算机仿真[5]。

不论是几台CNC协同工作，考虑的调度策略目标仍然是效率最高，路径最短，时间最少，故可将该问题理解成将物料从地点A运送至地点B，然后根据各个个体在种群中的位置确定适应度函数值，即

(5)

其中:N—个体数量；p—选择压力；

n—个体在种群当中的位置。

综上所述，建立了对于有两道工序的RGV初始阶段状态图(见图1)，加工作业的数学模型如下：

T=min {T1+T2}

(6)

图1 初始阶段RGV状态图

当CNC加工第一道工序所需时间远大于CNC加工第二道工序所需时间时，第二道工序所需要分配的CNC数量为3台，第一道工序分配的CNC数量为5台。RGV的调度策略不变。

本文利用网络流原理，综合考虑了以上3个不同的阶段，根据混合优化、就近原则和先到先服务的策略，按照图1所示的RGV调度策略，通过计算机仿真建模[6]，利用遗传优化算法[7]，结合C语言得出最优解。

3 基于等概模型的故障RGV动态调度模型建立与求解

通过计算机仿真求解出当CNC在加工过程中发生故障的RGV调度过程，需对计算机仿真结果进行检验。相当于掷一个有100面的骰子，因为有1%的故障率，故当骰子掷出1时，表示该正在运行的CNC加工机发生了故障，否则正常运行。引入0-1规划：

p{x=1}=p=1%

(7)

p{x=0}=1-p=99%

(8)

当发生故障时，CNC加工机停止工作，然后需人工排除故障，此后RGV的路线将重新排序，见式(6)。

为检验算法的实用性，首先要考虑算法的正确性，其次必须考虑执行算法所消耗的时间和辅助工具间，以及算法的易读程度，易编码和易于调试。

(1)算法的正确性

本文通过枚举的方法，枚举出了一道工序无障碍发生时除模型外的两种情况，分别是交错式物料加工顺序和波浪式物料加工顺序。针对这两种顺序，本文利用EXCEL以及仿真的方法分别对表1中的3组作业参数进行验证。得出结果后，再通过蚁群算法得出的最短路径分别对3组数据进行检验。

(2)消耗的时间及辅助工具

关于蚁群算法[8]消耗的时间以及辅助工具的问题，我们只需将八台CNC加工机的位置通过建立直角坐标系用X、Y坐标来表示，并制成EXCEL表格，将数据导入MATLAB，利用已有程序即可运行出结果，该过程仅仅需要几秒钟，而我们用到的辅助软件MATLAB是一个发展成熟且广泛应用的软件[9]。

(3)算法是否易于读懂，易编码和易于调试

该算法的思想源于意大利学者在对新型的算法研究过程中，发现蚁群在寻找食物时通过分泌一种信息素交流觅食信息从而快速找出目标，蚁群算法正是来自于蚂蚁觅食的最短路径原理[10]。我们利用MATLAB软件真实的模拟蚂蚁觅食的过程，从而得出最短路径，完全切合题意。

同时，本文结合TSP旅行商问题更加容易理解该算法。在本文中，我们在TSP旅行商问题[11-12]程序的基础上，只修改了几点，其他程序基本没变，然后运行程序，很快得出结果。

针对发生故障情况下的两道工序，本文利用MATLAB软件进行了1 000次的计算机仿真模拟(见图2,图3)。

图2 1000次计算机仿真分布图

图3 1000次计算机仿真模拟图

在比较的过程中，计算出各个加工物料情况中3组数据的CNC时间的效率(见表1)。

表1 3组数据的CNC时间的效率 %

结合遗传算法和蚁群算法建立出的RGV动态调度模型的系统作业效率高以上，因此我们的模型具有很强的实用性。利用任务一建立的RGV动态调度模型，本文对表1提供的3组数据进行检验，得到在连续8 h内4种情况下产出成料的数量，具体数据(见表2)。

表2 模型检验的3组数据结果表 个

遗传算法适合求解类似于本文的离散问题。遗传算法有较强的全局搜索能力，当样本有较大的交叉概率时，通过遗传算法，能够产生大量的新个体，进而提高了全局搜索的范围，具备数学模型支持，但是存在着汉明悬崖等问题。相比较之下，蚁群算法适合解决路径最优化的问题，一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。遗传算法和蚁群算法都是随机算法，区别是遗传算法是仿生学的算法而蚁群算法是数学算法。针对不同的研究方向，它所体现出来的优缺点是不一样的，结合两种算法的优势，提高了优化性能。

4 结 论

应用RGV调度模型，结合遗传算法和蚁群算法对模型进行研究与分析，对遗传算法和蚁群算法的参数进行选择，赋予一组较优参数，使得最终仿真结果更合理。按先到先服务的原则，在一道工序、两道工序的不同情况下，对物料产出数量分析比较，找出了最优解。

在分组模型中，根据每组的调度任务不同，则RGV数量也不同，因此尽量使每个RGV小车的运输任务数量相同，从表1和表2可以看出，随着RGV数量增加，物料的产出量也增加，随着RGV小车数量减少，RGV小车待机时间减少，物料产出也随之减少。

其次，如果固定RGV小车的数量，随着每个RGV小车所要承担的任务增加，产出量也会增加，但增加情况没有上一情况幅度大。故实际情况下，应综合考虑是增加RGV的数量还是增加每个RGV所需承担的任务数量，或取两种情况最优组合。

仿真结果表明，有故障的两道工序的3组数据分别为156,180,184。将这些数据与1 000次计算机仿真模拟图比较，会发现这些数据均落在计算机仿真模拟图所模拟的范围内，因此本文建立的故障RGV动态调度模型灵敏度较高。本文结合遗传算法和蚁群算法，很好地解决了物料数量较大时RGV调度问题，通过仿真数据，为RGV小车的调度提供了实际规划作为依据，以最大程度发挥生产线的作用。