基于模擬退火算法的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.