基于模拟退火算法的RGV智能车动态调度

吴灵媛 曹家赓 曹言

摘要：基于CNC在加工过程中可能发生故障的情况，构建了刀具出现问题的情况下新的动态约束模型，利用模拟退火算法，采用MATLAB软件编程求解，得出了在最大成本与加入新的约束条件下的最大成本新解之间的差值为-650，正好满足新退火解的要求。

关键词：模拟退火算法;动态调度;RGV智能车

0 引言

1.问题背景

RGV是一种无人驾驶、能在固定轨道上自由运行的智能车。目前已经广泛运用到柔性生产制造流程中，其调度规划问题成为生产决策的重点。研究的智能加工系统由8台计算机数控机床（CNC）、1辆轨道式自动引导车（RGV）、1条RGV直线轨道、1条上料传送带、1条下料传送带等附属设备组成。

CNC在加工过程中可能发生故障的情况，每次故障排除时间介于10～20分钟之间，故障排除后即刻加入作业序列，建立动态调度模型并提供相应的求解算法，以解决整个车床加工零件变化情况。

1.算法引用

模拟退火遗传算法在寻找全局优化解方面融合了模拟退火算法和遗传算法的特点，能够使优化过程的搜索行为更加完善，在发生意外情况时全局的搜索能力和效率都得到加强，而且能有效控制遗传算法避开所有最大值导致的效率分配问题，理论上能较好解决车间故障下的车辆合理调度问题。

2.算法原理

模拟退火算法来源于固体退火原理，用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是一种启发式随机搜索过程，包括影响的参数有初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

3.算法在本问题中的扩展

将每一次物料加工的过程看做一个完整的退火过程，而RGV运输过程中CNC出现的故障是调度优化的干扰项。对于单个的工件加工时间Tj一定有随机干扰项θj影响遗传算法调度RGV，其中θj是为第j個工件加工的CNC出现故障而浪费的时间，它的出现与CNC故障的概率pj有正相关的关系，pj越大，CNC出现故障的时间越长。则文中物料等待时间模型

中必须要加入随机概率下的故障时间θj。那么重新建立约束的模型如下：

（9）

其中θj= f （ pj），则根据模拟退火算法的思想，Wj在不断产生由于 f （ pj）的新解过程中，需要得到一个Cj*，使ε=（Cj-Cj*）中的ε得到一个比较大的值，那么这个Cj*就是融合了CNC故障之后RGV运输工件的等待时间模型的合理数值。

4.运行步骤

模拟退火算法新解的产生和接受可以用四个步骤求解：

（1）在最大成本最小化的目标函数规划下，可以得到如下动态规划模型：

（10）

（11）

此时Wj*为目标函数一个新的约束条件，且其对目标函数会产生新的影响，用matlab模拟出随着pj变化Cj*变化的值。（代码详见附件）

（2）在新解的情况下计算与新解所对应的目标函数差，即ε=（Cj-Cj*），这里记为ΔC。设定一个概率：

（2）

当在新的约束条件下有最优解，即ΔC≤0时，φ=0，能够

取得这个Cj*新解;而若ΔC >0，则，这个概率非常小，即Cj*=Cj。

（3）在进行新解的迭代过程中，设置迭代次数的记录与最终的停止条件。对于题目的问题可以设置的停止条件为，则整体的求解优化模型建立如下：

5.仿真模拟分析

基于以上方法，采用任务二的第一组数据为例，针对CNC对上下料时间影响的特殊性，对所提出的动态调度优化模型进行仿真验证。

由对比可知，模拟退火算法调节干扰项的遗传算法是有效果的。在只有6台机器工作的情况下，模型在考虑到局部时间可能增加的情况下，利用pj存在的区间（0，1）上随机分布对ΔC的变动影响，合理估计了φ出现的情况，从而跳过局部最优解，得到了和无故障情况下时间相差较少的新解，CNC故障下最优的调度路径为：CNC1↑CNC2↑CNC3↑CNC4↑CNC5↑CNC6↑ CNC7↑CNC8。在最大成本与加入新的约束条件下的最大成本新解之间的差值为-650，正好满足新退火解的要求。

参考文献：

[1]乔彦平，张骏.基于一种改进遗传模拟退火算法的TSP求解[J].计算机仿真，2009，26 （05）：205-208.

[2]吴焱明，刘永强，张栋，赵韩.基于遗传算法的RGV动态调度研究[J].起重运输机械，2012 （06）：20-23.