基于模擬退火算法的RGV智能車(chē)動(dòng)態(tài)調(diào)度

吳靈媛 曹家賡 曹言

摘要：基于CNC在加工過(guò)程中可能發(fā)生故障的情況，構(gòu)建了刀具出現(xiàn)問(wèn)題的情況下新的動(dòng)態(tài)約束模型，利用模擬退火算法，采用MATLAB軟件編程求解，得出了在最大成本與加入新的約束條件下的最大成本新解之間的差值為-650，正好滿(mǎn)足新退火解的要求。

關(guān)鍵詞：模擬退火算法;動(dòng)態(tài)調(diào)度;RGV智能車(chē)

0 引言

1.問(wèn)題背景

RGV是一種無(wú)人駕駛、能在固定軌道上自由運(yùn)行的智能車(chē)。目前已經(jīng)廣泛運(yùn)用到柔性生產(chǎn)制造流程中，其調(diào)度規(guī)劃問(wèn)題成為生產(chǎn)決策的重點(diǎn)。研究的智能加工系統(tǒng)由8臺(tái)計(jì)算機(jī)數(shù)控機(jī)床（CNC）、1輛軌道式自動(dòng)引導(dǎo)車(chē)（RGV）、1條RGV直線(xiàn)軌道、1條上料傳送帶、1條下料傳送帶等附屬設(shè)備組成。

CNC在加工過(guò)程中可能發(fā)生故障的情況，每次故障排除時(shí)間介于10～20分鐘之間，故障排除后即刻加入作業(yè)序列，建立動(dòng)態(tài)調(diào)度模型并提供相應(yīng)的求解算法，以解決整個(gè)車(chē)床加工零件變化情況。

1.算法引用

模擬退火遺傳算法在尋找全局優(yōu)化解方面融合了模擬退火算法和遺傳算法的特點(diǎn)，能夠使優(yōu)化過(guò)程的搜索行為更加完善，在發(fā)生意外情況時(shí)全局的搜索能力和效率都得到加強(qiáng)，而且能有效控制遺傳算法避開(kāi)所有最大值導(dǎo)致的效率分配問(wèn)題，理論上能較好解決車(chē)間故障下的車(chē)輛合理調(diào)度問(wèn)題。

2.算法原理

模擬退火算法來(lái)源于固體退火原理，用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是一種啟發(fā)式隨機(jī)搜索過(guò)程，包括影響的參數(shù)有初值t及其衰減因子Δt、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。

3.算法在本問(wèn)題中的擴(kuò)展

將每一次物料加工的過(guò)程看做一個(gè)完整的退火過(guò)程，而RGV運(yùn)輸過(guò)程中CNC出現(xiàn)的故障是調(diào)度優(yōu)化的干擾項(xiàng)。對(duì)于單個(gè)的工件加工時(shí)間Tj一定有隨機(jī)干擾項(xiàng)θj影響遺傳算法調(diào)度RGV，其中θj是為第j個(gè)工件加工的CNC出現(xiàn)故障而浪費(fèi)的時(shí)間，它的出現(xiàn)與CNC故障的概率pj有正相關(guān)的關(guān)系，pj越大，CNC出現(xiàn)故障的時(shí)間越長(zhǎng)。則文中物料等待時(shí)間模型

中必須要加入隨機(jī)概率下的故障時(shí)間θj。那么重新建立約束的模型如下：

（9）

其中θj= f （ pj），則根據(jù)模擬退火算法的思想，Wj在不斷產(chǎn)生由于 f （ pj）的新解過(guò)程中，需要得到一個(gè)Cj*，使ε=（Cj-Cj*）中的ε得到一個(gè)比較大的值，那么這個(gè)Cj*就是融合了CNC故障之后RGV運(yùn)輸工件的等待時(shí)間模型的合理數(shù)值。

4.運(yùn)行步驟

模擬退火算法新解的產(chǎn)生和接受可以用四個(gè)步驟求解：

（1）在最大成本最小化的目標(biāo)函數(shù)規(guī)劃下，可以得到如下動(dòng)態(tài)規(guī)劃模型：

（10）

（11）

此時(shí)Wj*為目標(biāo)函數(shù)一個(gè)新的約束條件，且其對(duì)目標(biāo)函數(shù)會(huì)產(chǎn)生新的影響，用matlab模擬出隨著pj變化Cj*變化的值。（代碼詳見(jiàn)附件）

（2）在新解的情況下計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差，即ε=（Cj-Cj*），這里記為ΔC。設(shè)定一個(gè)概率：

（2）

當(dāng)在新的約束條件下有最優(yōu)解，即ΔC≤0時(shí)，φ=0，能夠

取得這個(gè)Cj*新解;而若ΔC >0，則，這個(gè)概率非常小，即Cj*=Cj。

（3）在進(jìn)行新解的迭代過(guò)程中，設(shè)置迭代次數(shù)的記錄與最終的停止條件。對(duì)于題目的問(wèn)題可以設(shè)置的停止條件為，則整體的求解優(yōu)化模型建立如下：

5.仿真模擬分析

基于以上方法，采用任務(wù)二的第一組數(shù)據(jù)為例，針對(duì)CNC對(duì)上下料時(shí)間影響的特殊性，對(duì)所提出的動(dòng)態(tài)調(diào)度優(yōu)化模型進(jìn)行仿真驗(yàn)證。

由對(duì)比可知，模擬退火算法調(diào)節(jié)干擾項(xiàng)的遺傳算法是有效果的。在只有6臺(tái)機(jī)器工作的情況下，模型在考慮到局部時(shí)間可能增加的情況下，利用pj存在的區(qū)間（0，1）上隨機(jī)分布對(duì)ΔC的變動(dòng)影響，合理估計(jì)了φ出現(xiàn)的情況，從而跳過(guò)局部最優(yōu)解，得到了和無(wú)故障情況下時(shí)間相差較少的新解，CNC故障下最優(yōu)的調(diào)度路徑為：CNC1↑CNC2↑CNC3↑CNC4↑CNC5↑CNC6↑ CNC7↑CNC8。在最大成本與加入新的約束條件下的最大成本新解之間的差值為-650，正好滿(mǎn)足新退火解的要求。

參考文獻(xiàn)：

[1]喬彥平，張駿.基于一種改進(jìn)遺傳模擬退火算法的TSP求解[J].計(jì)算機(jī)仿真，2009，26 （05）：205-208.

[2]吳焱明，劉永強(qiáng)，張棟，趙韓.基于遺傳算法的RGV動(dòng)態(tài)調(diào)度研究[J].起重運(yùn)輸機(jī)械，2012 （06）：20-23.