基于遺傳算法的RGV調(diào)度優(yōu)化模型

宮尚俊?賈慧?吳慧敏

在一個智能加工系統(tǒng)中，輸送系統(tǒng)連接多個計算機數(shù)據(jù)機床和外部物料運送工具，其調(diào)度策略和工作效率對整個的智能加工過程至關(guān)重要。本文針對智能RGV的動態(tài)調(diào)度策略設(shè)計問題，通過分析RGV的工作條件以及作業(yè)流程，建立基于遺傳算法的RGV動態(tài)調(diào)度優(yōu)化模型，最后運用MATLAB軟件編程，結(jié)合數(shù)據(jù)求出結(jié)果證明了模型的可操作性和算法的有效性，給出了具體的RGV的調(diào)度策略和系統(tǒng)的工作效率。

隨著現(xiàn)代工業(yè)的快速發(fā)展，物流的自動化、智能化已是必然趨勢，自動化立體倉庫得到越來越多的應(yīng)用。RGV（Rail Guided Vehicle）軌道式自動引導(dǎo)車能夠結(jié)合各種高新技術(shù)于一身具有多種實用功能，被廣泛地應(yīng)用于物料加工處理系統(tǒng)當中，是實現(xiàn)可以感知、思維、推理、路徑規(guī)劃和決策的智能物流的中堅力量，可以有效的完成物料的運送、清理過程。RGV的動態(tài)調(diào)度問題很大程度決定了輸送系統(tǒng)的運送效率。因此RGV動態(tài)調(diào)度問題一直是研究的熱點，有很多學(xué)者在這方向上做出了自己的努力。劉永強采用遺傳算法對自動化立體倉庫進行建模，得到優(yōu)化的調(diào)度多個RGV運送出入貨任務(wù)方案，并運用仿真方法進行進一步研究；劉燚等針對擾動事件影響下的車間調(diào)度問題，綜合考慮完工時間與交貨期，運用模擬退火遺傳算法，建立了作業(yè)車間動態(tài)調(diào)度模型；潘全科將雙向調(diào)度方法嵌入到遺傳算法中，結(jié)合神經(jīng)網(wǎng)絡(luò)對智能制造系統(tǒng)的多目標車間調(diào)度問題進行了研究；查申森等提出了一種基于RGV、AGV的柔性輸送系統(tǒng)，有效地克服傳統(tǒng)單一RGV輸送系統(tǒng)軌道占用空間大、對場所適應(yīng)性差等缺點?；谝陨涎芯烤C述，結(jié)合直行軌道式自動化立體倉庫智能加工需求，可知實現(xiàn)RGV穿梭車的合理調(diào)度、提高RGV系統(tǒng)的運行效率、研究并設(shè)計智能RGV系統(tǒng)的動態(tài)調(diào)度策略對促進智能加工行業(yè)高速發(fā)展具有深遠的意義。

一、問題的分析

解決這類問題時，我們首先要了解RGV的工作條件以及作業(yè)流程，再設(shè)置一個算法調(diào)度RGV以實現(xiàn)在約束條件下處理最多生料，這個問題等價于設(shè)置一個算法確定一個穩(wěn)定狀態(tài)下的動態(tài)調(diào)度順序使得在考慮一個穩(wěn)定循環(huán)下所有的RGV移動距離的時間、RGV給每個CNC上下料的時間、RGV清洗熟料的時間之和最短。由于約束條件較多、較復(fù)雜而且經(jīng)分析易得在一個穩(wěn)定的循環(huán)周期內(nèi)每個CNC都需要RGV給予上一次料，所以用一般的算法可能不能求出實際解，而遺傳算法正好可以有效解決這個問題，它是從問題潛在的解集開始的，通過按照適者生存原理，將所有解與目標函數(shù)進行對比并排除掉相對遠離目標的，最終會產(chǎn)生出越來越好的近似解。除此之外借助自然遺傳學(xué)的遺傳算子進行組合交叉和變異產(chǎn)生出新的種群，這種方法能夠使種群進行優(yōu)勝劣汰從而后生代種群比以前的更加適應(yīng)環(huán)境。最后將最后一代種群中的最優(yōu)個體經(jīng)過解碼，可以作為問題近似最優(yōu)解即得出RGV的最優(yōu)動態(tài)調(diào)度。

二、模型的假設(shè)

為方便解決具體問題，對文章作出以下假設(shè)：

（一）機械臂前端上方會一直能夠保持生料的供應(yīng)，清洗后的成料都能被傳送帶輸出系統(tǒng)；

（二）CNC只有等待RGV上下料工作完全完成后才開始對生料進行加工處理，即RGV完成上下料作業(yè)后到機械臂將熟料放到清洗槽中的時間中CNC不對生料進行加工；

（三）RGV的初始上料過程與整個流程結(jié)尾回到初始位置時間與整個班次相比相對較少，為方便計算系統(tǒng)工作效率，假設(shè)這些時間為0。

三、模型的建立

遺傳算法（Genetic Algorithms，簡稱GA）是一種基于生物的自然選擇原理和基因遺傳機理的搜索算法，通過模擬生物的遺傳和進化過程，逐步篩選最終得到自己所想要目標的最優(yōu)解。用這種算法建立動態(tài)調(diào)度模型有很多的優(yōu)點，例如遺傳算法能夠從多個可行解開始搜索，比從單一可行解開始搜索的速度更快從而可以減少得到最優(yōu)的結(jié)果的時間；遺傳算法進行遺傳操作時不需要設(shè)置太多的外部條件，只需要找到目標函數(shù)就行，非常適合像計算機數(shù)控機床這種比較復(fù)雜的系統(tǒng)；遺傳算法的理論研究現(xiàn)在已經(jīng)發(fā)展的比較成熟，針對很多的實際問題都有相應(yīng)的理論和方法，因此用這種算法非常的方便，而且算法計算出來的結(jié)果可行性高。

遺傳算法需要涉及五大要素：編碼、初始群體的產(chǎn)生、適應(yīng)度評估、遺傳操作的設(shè)計和控制參數(shù)的設(shè)定。具體步驟如下：

（一）編碼策略

在編碼過程中本文使用十進制編碼，用隨機數(shù)列作為染色體，其中，；隨機序列都與種群中的每一個個體相對應(yīng)。

（二）初始種群

本文利用改良圈算法來獲得一個比較不錯的初始種群，即對于初始圈，，交換u與v之間的順序，此時的新路徑為：記，若，則用新的路徑替代舊的路徑，一直到不能替代為止。

（三）目標函數(shù)

目標函數(shù)為一個穩(wěn)定周期RGV的給各個CNC上下料的時間最短

1.

（四）交叉操作

我們的交叉操作采用單點交叉，因為單點交叉在編輯程序的過程中較簡單且能夠有效的保證解的多樣性。

（五）變異操作

變異能夠?qū)崿F(xiàn)群體的多樣性，能夠擴大尋找最優(yōu)解的范圍。具體操作如下，按照一定的變異率，對選定變異的個體，隨機的選取3個整數(shù)，滿足

（六）選擇

采用確定性的選擇策略，也就是說選擇目標函數(shù)值最小的M個個體進化到下一代，這樣可以保證父代的優(yōu)良特性被保存下來。

為計算出具體結(jié)果定義穩(wěn)定狀態(tài)下的時間間隔矩陣Tij，

2.

為方便理解Tij的具體含義，文中列舉了矩陣部分元素的具體表達形式。其中m1、m2、m3分別表示RGV移動1、2、3個單位所需時間；ti表示RGV為CNCi#一次上下料所需時間；tc表示完成一個物料的清洗作業(yè)所需時間。矩陣元素tij表示從CNCi#到CNCj#完成上下料并清洗過的時間。位置0表明位于初始位置即CNC1#和CNC2#正中間。因為RGV在完成一項作業(yè)任務(wù)后，才會判別執(zhí)行下一個作業(yè)指令。如果沒有接到其他的作業(yè)指令，則RGV就在原地等待直到下一個作業(yè)指令。又因為在初始上料過程中經(jīng)計算經(jīng)過不同的路徑給所有CNC上料的總時長都遠小于CNC加工物料時間，所以RGV還需要等待。因此經(jīng)過分析易得為減少工作時間、提高工作效率，RGV的最終位置為回到原點，達成一個穩(wěn)定的循環(huán)。在這里用位置9表示RGV回到末尾位置即初始位置。

最后將矩陣帶入遺傳算法求解的MATLAB程序中會求得一個穩(wěn)定狀態(tài)下的最優(yōu)順序，并能計算出RGV一個周期下的總調(diào)度時間。算出時間后，再計算RGV的工作效率。由于假設(shè)3，所以在計算系統(tǒng)工作效率時只需計算出一個穩(wěn)定周期下的RGV工作效率就行，計算系統(tǒng)工作效率公式如公式3

3.

其中η為系統(tǒng)的作業(yè)效率，T0為RGV調(diào)度時間，T為系統(tǒng)工作的總時間。

四、模型的求解

將表1：智能加工系統(tǒng)作業(yè)參數(shù)的3組數(shù)據(jù)表中第一組數(shù)據(jù)帶入并結(jié)合時間間隔矩陣的元素含義可得時間間隔矩陣，接著將所得的時間間隔矩陣帶入遺傳算法的MATLAB程序中即可得出RGV給CNC上料的順序：2、4、3、6、5、8、7、1以及RGV一個調(diào)度周期耗時總時間為542秒，即經(jīng)過542秒后RGV回到初始狀態(tài)9開始進行第二次的循環(huán)。因為RGV總調(diào)度時間只需542秒，CNC加工完成一個一道工序的物料所需時間為560秒，最后用公式3計算系統(tǒng)作業(yè)的工作效率，得出結(jié)果為96.79%。

五、結(jié)論與討論

本文討論了RGV動態(tài)調(diào)度策略優(yōu)化問題。根據(jù)分析RGV的工作條件以及作業(yè)流程得出一些基本的約束情況，建立了基于遺傳算法的RGV動態(tài)調(diào)度優(yōu)化模型，在模型的建立過程中構(gòu)造了時間間隔距離矩陣將不可計算的最短時間長度問題轉(zhuǎn)化為最短距離問題使模型顯得更淺顯易懂、RGV調(diào)度順序結(jié)果更易計算出。最后結(jié)合2018高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題第一種情況第1組數(shù)據(jù)求出穩(wěn)定狀態(tài)下RGV的調(diào)度順序并計算出系統(tǒng)的作業(yè)效率來驗證模型的實用性和算法的有效性。結(jié)果表明基于遺傳算法的RGV動態(tài)調(diào)度模型具有實用性，算法能夠求出RGV穩(wěn)定狀態(tài)下的調(diào)度順序且該順序下的系統(tǒng)工作效率為96.79%比較合理，因此該算法也具有有效性。（第一作者單位為安徽財經(jīng)大學(xué)經(jīng)濟學(xué)院，第二作者單位為安徽財經(jīng)大學(xué)國際經(jīng)濟貿(mào)易學(xué)院，第三作者單位為安徽財經(jīng)大學(xué)會計學(xué)院）