基于蟻群算法和遺傳算法RGV動(dòng)態(tài)調(diào)度研究

周自力,吳福珍,張心怡

(1.浙江水利水電學(xué)院 建筑工程學(xué)院,浙江 杭州 310018;2.浙江水利水電學(xué)院 基礎(chǔ)部，浙江 杭州 310018)

0 引 言

RGV軌制導(dǎo)車輛(rail guided vehicle)是一種無人駕駛、能在固定軌道上自由運(yùn)行的智能車。RGV倉(cāng)庫(kù)導(dǎo)軌式調(diào)度系統(tǒng)的工作效率是當(dāng)前的瓶頸，故解決RGV動(dòng)態(tài)調(diào)度效率是關(guān)鍵。

(1)國(guó)內(nèi)外研究現(xiàn)狀

意大利學(xué)者M(jìn).P. FANTI[1]在文獻(xiàn)中通過著色賦時(shí)Petri網(wǎng)建立了具有環(huán)狀運(yùn)輸系統(tǒng)的標(biāo)準(zhǔn)化自動(dòng)倉(cāng)庫(kù)模型，根據(jù)六種RGV調(diào)度的策略下的貨物運(yùn)輸效率，得出了RGV利用率最高的調(diào)度策略。南洋理工大學(xué)學(xué)者E.K. ONG和S. G. LEE, R. DE SOUZS[2]在發(fā)表的文獻(xiàn)中用先到先服務(wù)(first come, first serve)的策略，研究倉(cāng)庫(kù)環(huán)形運(yùn)輸系統(tǒng)各種情況下的使用效率，得出每種調(diào)度情況下的最佳RGV數(shù)量。廈門大學(xué)羅建教授和博士研究生吳長(zhǎng)慶等[3]在其文獻(xiàn)中，對(duì)于自動(dòng)小車的控制問題，利用雙重著色賦時(shí)Petri網(wǎng)，建立了RGV的動(dòng)態(tài)調(diào)度系統(tǒng)模型。在RGV運(yùn)行最短路徑的條件下，提出了RGV系統(tǒng)效率最高的模型。

(2)現(xiàn)狀的分析和本文研究的問題

在現(xiàn)有的國(guó)內(nèi)外對(duì)于RGV調(diào)度研究中，已經(jīng)對(duì)3種運(yùn)輸系統(tǒng)(直行軌道式、分段式、環(huán)形軌道式)的RGV調(diào)度問題做了一般性的研究，但現(xiàn)有的模型對(duì)運(yùn)輸系統(tǒng)的設(shè)計(jì)和RGV的調(diào)度較為簡(jiǎn)單，但并沒有考慮物料流量對(duì)效率的影響。如果碰到大流量的物品調(diào)度，效率無法滿足實(shí)際需求。本文研究的問題是在物料流量相對(duì)較大的情況下，即在運(yùn)輸系統(tǒng)運(yùn)行的大部分時(shí)間里，RGV處于工作狀態(tài)，且RGV數(shù)量遠(yuǎn)小于所需物料運(yùn)輸量，如何調(diào)度運(yùn)輸系統(tǒng)的RGV，使得效率達(dá)到最高。針對(duì)上述問題，本文運(yùn)用蟻群算法和遺傳算法，很好地優(yōu)化了調(diào)度多個(gè)RGV小車運(yùn)送貨物方案，減少RGV小車的待機(jī)和堵塞，最大限度提高了系統(tǒng)運(yùn)行效率。

1 基于蟻群算法的一道工序加工RGV動(dòng)態(tài)調(diào)度模型

1.1 RGV概述

RGV根據(jù)指令能自動(dòng)控制移動(dòng)方向和距離，完成上下料及清洗物料等作業(yè)任務(wù)。物料在CNC中加工有3種情況：一道工序的物料加工；兩道工序的物料加工；CNC在加工過程中發(fā)生故障(發(fā)生概率約為1%)，每次故障排除時(shí)間介于10～20 min之間，故障排除后即加入作業(yè)序列。

1.2 RGV一道工序加工RGV動(dòng)態(tài)調(diào)度模型

本文關(guān)鍵是分析自動(dòng)引導(dǎo)車在導(dǎo)軌上的移動(dòng)狀態(tài)，根據(jù)蟻群算法，借助自動(dòng)化倉(cāng)庫(kù)[3]的生產(chǎn)管理調(diào)度，以建立RGV動(dòng)態(tài)調(diào)度模型。為使整個(gè)加工過程效率最大化，需對(duì)RGV進(jìn)行合理的動(dòng)態(tài)調(diào)度。

對(duì)于一道工序的RGV加工作業(yè)情況，先將所有加工點(diǎn)需求按泊松分布生成，對(duì)RGV的初始位置和運(yùn)行速度進(jìn)行標(biāo)記，根據(jù)各加工點(diǎn)的位置和產(chǎn)生需求的時(shí)間，進(jìn)行動(dòng)態(tài)標(biāo)記，本文用蟻群算法[4]對(duì)模型進(jìn)行求解。故整個(gè)問題轉(zhuǎn)化為如何調(diào)度RGV，使其在任務(wù)動(dòng)態(tài)變化的情況下，效率達(dá)到最高，該效率可用RGV走過的總路程或花費(fèi)的總時(shí)間來描述。故本文用蟻群算法對(duì)模型進(jìn)行求解。

定義:

(1)

RGV加工的運(yùn)動(dòng)可分為兩部分：①?gòu)淖鳂I(yè)原點(diǎn)移動(dòng)至CNC加工點(diǎn)(或者從加工點(diǎn)返回至原點(diǎn));②從一個(gè)加工點(diǎn)移動(dòng)至另一個(gè)加工點(diǎn)。RGV從作業(yè)的原點(diǎn)到加工點(diǎn)進(jìn)行的是點(diǎn)到點(diǎn)(point to point，PTP)運(yùn)動(dòng)，RGV在各加工點(diǎn)之間的移動(dòng)也是PTP。PTP運(yùn)動(dòng)指的是只考慮起點(diǎn)與目標(biāo)點(diǎn)，不用考慮兩點(diǎn)之間移動(dòng)的過程。

1.3 計(jì)算CNC加工機(jī)距離矩陣

由平面解析幾何中兩點(diǎn)間距離公式，以式(1)中的CNC加工機(jī)坐標(biāo)，很容易計(jì)算出任意兩CNC加工機(jī)間的距離矩陣，因此用RGV移動(dòng)的距離總和作為目標(biāo)函數(shù)，衡量結(jié)果是否為最優(yōu)解。

任意兩CNC加工機(jī)i、j之間的距離可表示為:

(2)

由樣本的移動(dòng)距離長(zhǎng)度得到目標(biāo)函數(shù)，每?jī)蓚€(gè)CNC加工機(jī)之間的組合數(shù)為t-2組，故建立目標(biāo)函數(shù)：

(3)

1.4 迭代尋找最佳路徑

這一步是蟻群算法的核心，首先由螞蟻的轉(zhuǎn)移概率建立解的空間，即所有的螞蟻逐一經(jīng)過CNC加工機(jī)，進(jìn)而計(jì)算每一只螞蟻?zhàn)哌^的距離。并在每次迭代后通過信息素改變公式即時(shí)更新各個(gè)CNC加工機(jī)連接路徑上的信息素濃度。通過循環(huán)迭代，記錄下最優(yōu)的路徑和路徑長(zhǎng)度。

建立了對(duì)于一道工序的RGV加工作業(yè)的數(shù)學(xué)模型：

T=min {T1+T2}

(4)

RGV的移動(dòng)軌跡為：

CNC1→CNC3→CNC5→CNC7→CNC8

→CNC6→CNC4→CNC2→CNC1

2 基于遺傳算法的RGV動(dòng)態(tài)調(diào)度的模型建立與求解

對(duì)于兩道工序的RGV加工作業(yè)情況，此時(shí)物料的處理過程變?yōu)閮刹?，并要在兩臺(tái)不同的CNC上加工完成，第一種情況的加工策略已不再適用，需要考慮的是如何調(diào)度RGV使其能完成兩臺(tái)CNC的協(xié)同工作，最后根據(jù)建立的模型進(jìn)行計(jì)算機(jī)仿真[5]。

不論是幾臺(tái)CNC協(xié)同工作，考慮的調(diào)度策略目標(biāo)仍然是效率最高，路徑最短，時(shí)間最少，故可將該問題理解成將物料從地點(diǎn)A運(yùn)送至地點(diǎn)B，然后根據(jù)各個(gè)個(gè)體在種群中的位置確定適應(yīng)度函數(shù)值，即

(5)

其中:N—個(gè)體數(shù)量；p—選擇壓力；

n—個(gè)體在種群當(dāng)中的位置。

綜上所述，建立了對(duì)于有兩道工序的RGV初始階段狀態(tài)圖(見圖1)，加工作業(yè)的數(shù)學(xué)模型如下：

T=min {T1+T2}

(6)

圖1 初始階段RGV狀態(tài)圖

當(dāng)CNC加工第一道工序所需時(shí)間遠(yuǎn)大于CNC加工第二道工序所需時(shí)間時(shí)，第二道工序所需要分配的CNC數(shù)量為3臺(tái)，第一道工序分配的CNC數(shù)量為5臺(tái)。RGV的調(diào)度策略不變。

本文利用網(wǎng)絡(luò)流原理，綜合考慮了以上3個(gè)不同的階段，根據(jù)混合優(yōu)化、就近原則和先到先服務(wù)的策略，按照?qǐng)D1所示的RGV調(diào)度策略，通過計(jì)算機(jī)仿真建模[6]，利用遺傳優(yōu)化算法[7]，結(jié)合C語(yǔ)言得出最優(yōu)解。

3 基于等概模型的故障RGV動(dòng)態(tài)調(diào)度模型建立與求解

通過計(jì)算機(jī)仿真求解出當(dāng)CNC在加工過程中發(fā)生故障的RGV調(diào)度過程，需對(duì)計(jì)算機(jī)仿真結(jié)果進(jìn)行檢驗(yàn)。相當(dāng)于擲一個(gè)有100面的骰子，因?yàn)橛?%的故障率，故當(dāng)骰子擲出1時(shí)，表示該正在運(yùn)行的CNC加工機(jī)發(fā)生了故障，否則正常運(yùn)行。引入0-1規(guī)劃：

p{x=1}=p=1%

(7)

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

(8)

當(dāng)發(fā)生故障時(shí)，CNC加工機(jī)停止工作，然后需人工排除故障，此后RGV的路線將重新排序，見式(6)。

為檢驗(yàn)算法的實(shí)用性，首先要考慮算法的正確性，其次必須考慮執(zhí)行算法所消耗的時(shí)間和輔助工具間，以及算法的易讀程度，易編碼和易于調(diào)試。

(1)算法的正確性

本文通過枚舉的方法，枚舉出了一道工序無障礙發(fā)生時(shí)除模型外的兩種情況，分別是交錯(cuò)式物料加工順序和波浪式物料加工順序。針對(duì)這兩種順序，本文利用EXCEL以及仿真的方法分別對(duì)表1中的3組作業(yè)參數(shù)進(jìn)行驗(yàn)證。得出結(jié)果后，再通過蟻群算法得出的最短路徑分別對(duì)3組數(shù)據(jù)進(jìn)行檢驗(yàn)。

(2)消耗的時(shí)間及輔助工具

關(guān)于蟻群算法[8]消耗的時(shí)間以及輔助工具的問題，我們只需將八臺(tái)CNC加工機(jī)的位置通過建立直角坐標(biāo)系用X、Y坐標(biāo)來表示，并制成EXCEL表格，將數(shù)據(jù)導(dǎo)入MATLAB，利用已有程序即可運(yùn)行出結(jié)果，該過程僅僅需要幾秒鐘，而我們用到的輔助軟件MATLAB是一個(gè)發(fā)展成熟且廣泛應(yīng)用的軟件[9]。

(3)算法是否易于讀懂，易編碼和易于調(diào)試

該算法的思想源于意大利學(xué)者在對(duì)新型的算法研究過程中，發(fā)現(xiàn)蟻群在尋找食物時(shí)通過分泌一種信息素交流覓食信息從而快速找出目標(biāo)，蟻群算法正是來自于螞蟻覓食的最短路徑原理[10]。我們利用MATLAB軟件真實(shí)的模擬螞蟻覓食的過程，從而得出最短路徑，完全切合題意。

同時(shí)，本文結(jié)合TSP旅行商問題更加容易理解該算法。在本文中，我們?cè)赥SP旅行商問題[11-12]程序的基礎(chǔ)上，只修改了幾點(diǎn)，其他程序基本沒變，然后運(yùn)行程序，很快得出結(jié)果。

針對(duì)發(fā)生故障情況下的兩道工序，本文利用MATLAB軟件進(jìn)行了1 000次的計(jì)算機(jī)仿真模擬(見圖2,圖3)。

圖2 1000次計(jì)算機(jī)仿真分布圖

圖3 1000次計(jì)算機(jī)仿真模擬圖

在比較的過程中，計(jì)算出各個(gè)加工物料情況中3組數(shù)據(jù)的CNC時(shí)間的效率(見表1)。

表1 3組數(shù)據(jù)的CNC時(shí)間的效率 %

結(jié)合遺傳算法和蟻群算法建立出的RGV動(dòng)態(tài)調(diào)度模型的系統(tǒng)作業(yè)效率高以上，因此我們的模型具有很強(qiáng)的實(shí)用性。利用任務(wù)一建立的RGV動(dòng)態(tài)調(diào)度模型，本文對(duì)表1提供的3組數(shù)據(jù)進(jìn)行檢驗(yàn)，得到在連續(xù)8 h內(nèi)4種情況下產(chǎn)出成料的數(shù)量，具體數(shù)據(jù)(見表2)。

表2 模型檢驗(yàn)的3組數(shù)據(jù)結(jié)果表 個(gè)

遺傳算法適合求解類似于本文的離散問題。遺傳算法有較強(qiáng)的全局搜索能力，當(dāng)樣本有較大的交叉概率時(shí)，通過遺傳算法，能夠產(chǎn)生大量的新個(gè)體，進(jìn)而提高了全局搜索的范圍，具備數(shù)學(xué)模型支持，但是存在著漢明懸崖等問題。相比較之下，蟻群算法適合解決路徑最優(yōu)化的問題，一般的迭代方法容易陷入局部極小的陷阱而出現(xiàn)"死循環(huán)"現(xiàn)象，使迭代無法進(jìn)行。遺傳算法很好地克服了這個(gè)缺點(diǎn)，是一種全局優(yōu)化算法。遺傳算法和蟻群算法都是隨機(jī)算法，區(qū)別是遺傳算法是仿生學(xué)的算法而蟻群算法是數(shù)學(xué)算法。針對(duì)不同的研究方向，它所體現(xiàn)出來的優(yōu)缺點(diǎn)是不一樣的，結(jié)合兩種算法的優(yōu)勢(shì)，提高了優(yōu)化性能。

4 結(jié) 論

應(yīng)用RGV調(diào)度模型，結(jié)合遺傳算法和蟻群算法對(duì)模型進(jìn)行研究與分析，對(duì)遺傳算法和蟻群算法的參數(shù)進(jìn)行選擇，賦予一組較優(yōu)參數(shù)，使得最終仿真結(jié)果更合理。按先到先服務(wù)的原則，在一道工序、兩道工序的不同情況下，對(duì)物料產(chǎn)出數(shù)量分析比較，找出了最優(yōu)解。

在分組模型中，根據(jù)每組的調(diào)度任務(wù)不同，則RGV數(shù)量也不同，因此盡量使每個(gè)RGV小車的運(yùn)輸任務(wù)數(shù)量相同，從表1和表2可以看出，隨著RGV數(shù)量增加，物料的產(chǎn)出量也增加，隨著RGV小車數(shù)量減少，RGV小車待機(jī)時(shí)間減少，物料產(chǎn)出也隨之減少。

其次，如果固定RGV小車的數(shù)量，隨著每個(gè)RGV小車所要承擔(dān)的任務(wù)增加，產(chǎn)出量也會(huì)增加，但增加情況沒有上一情況幅度大。故實(shí)際情況下，應(yīng)綜合考慮是增加RGV的數(shù)量還是增加每個(gè)RGV所需承擔(dān)的任務(wù)數(shù)量，或取兩種情況最優(yōu)組合。

仿真結(jié)果表明，有故障的兩道工序的3組數(shù)據(jù)分別為156,180,184。將這些數(shù)據(jù)與1 000次計(jì)算機(jī)仿真模擬圖比較，會(huì)發(fā)現(xiàn)這些數(shù)據(jù)均落在計(jì)算機(jī)仿真模擬圖所模擬的范圍內(nèi)，因此本文建立的故障RGV動(dòng)態(tài)調(diào)度模型靈敏度較高。本文結(jié)合遺傳算法和蟻群算法，很好地解決了物料數(shù)量較大時(shí)RGV調(diào)度問題，通過仿真數(shù)據(jù)，為RGV小車的調(diào)度提供了實(shí)際規(guī)劃作為依據(jù)，以最大程度發(fā)揮生產(chǎn)線的作用。