基于仿真優化的多種類型AGV數量配置優化方法

張遠春 范秀敏,2 駒田邦久

1.上海交通大學,上海,200030 2.上海市網絡化制造與企業信息化重點實驗室,上海,200030 3.大金工業株式會社,大阪,日本,5300054

0 引言

AGV(automatic guided vehicle)在現代企業的車間物料搬運中發揮越來越重要的作用。AGV價格昂貴,且AGV的數量過多反而使其利用率降低,造成資源浪費。如何根據生產計劃配置相應數量的AGV,使其滿足產能需求一直是企業關注的問題。Egbelu[1]考慮AGV路徑、裝卸時間,提出了估算AGV數量的數學模型,但該模型沒有考慮AGV的堵塞時間;王冰等[2]在Egbelu的基礎上研究了不同的調度規則和不同交通管理下的AGV數量估算,但沒有將調度規則與交通管理結合起來研究;Scrinivasan等[3]以KVehicles的方法分析AGV的調度規則為FCFS(先來先服務)時AGV的數量估計,該方法忽視了AGV數量多時交通堵塞的影響,估算誤差大。

實際考慮AGV的數量配置時涉及的因素很多,如AGV的調度規則、AGV的容量、AGV的速度、交通擁堵情況等,很難建立精確的數學模型[4]。有學者將仿真模型和優化算法相結合,用于解決調度規則序列的優化問題[5]。鑒于此思想,本文先建立AGV的仿真模型,通過模型來表達AGV的路徑、調度規則、交通管理等約束;然后利用此仿真模型,并結合遺傳算法的智能搜索功能,得到AGV的最佳數量配置。

1 問題描述

圖1 生產車間布局

圖1所示為一生產車間布局,該生產車間由加工中心、配料區及成品庫存區組成,物料在車間的流動是由n種AGV來完成的。每一種AGV負責一塊區域,區域i對應的AGV數量(第i種AGV的數量)為Ni。如果某一區域的AGV的數量Ni過小,物料來不及運輸,影響零部件的加工;反之,AGV的數量Ni過大,AGV利用率下降,也容易產生交通堵塞。因此AGV的數量配置優化問題描述為:給定工藝布局、AGV的路徑、調度規則、AGV的速度等約束條件,確定每種AGV的最佳數量 Ni-best,使得輸出產品數最大。同時,AGV的利用率不能過低。AGV數量配置優化的數學模型描述如下:

式中,Q為產品輸出;f(*)表示產品輸出與AGV的數量的關系;Ni,min、Ni,max分別為第i種AGV的最小數量和最大數量;Pij為第i種AGV中的第 j輛的利用率;Pi,min為第i種AGV的最小利用率;P(*)表示AGV必須滿足的工藝約束;R(*)表示AGV必須滿足的路徑約束;D(*)表示AGV必須滿足的調度規則約束。

式(1)(目標函數)表示產品輸出最大,式(2)表示每種 AGV數量的邊界;式(3)表示每種AGV的利用率不能低于邊界值;式(4)～式(6)分別表示工藝約束、路徑約束、調度規則約束。由這些約束條件難以建立數學模型,故本文通過仿真模型來表達這些約束條件。

2 仿真優化

2.1 仿真優化原理

仿真優化的基本原理是,利用仿真模型來替代傳統優化模型中的目標函數和約束條件,由優化算法產生一組初始解,將該初始解輸入到仿真模型,仿真一段時間后,得到這組解的性能指標,將這組解及其性能指標輸入到優化算法中搜索迭代得到一組新解,這組新解比迭代前的解性能更優,再將新解導入到仿真模型,如此反復直到性能指標滿足要求,輸出最優解[5-6],如圖2所示。

圖2 仿真優化原理圖

仿真優化不同于傳統的優化,也不同于仿真實驗,具體表現在如下幾方面:

(1)傳統的優化都是先建立解析模型,再利用優化方法來進行求解的。但是由于實際問題的復雜性和隨機性,故很多問題是很難建立精確模型的。而仿真作為一種建模方法,能夠把要素之間的邏輯關系通過建模語言表達出來,真實地反映系統的規律。

(2)仿真優化與仿真實驗不同。仿真實驗通過枚舉方式對可能的組合進行逐一實驗,搜索目標不明確,并且當組合數較多時,這種方法變得復雜、耗時長,甚至無法得到最優解。仿真優化將仿真與各種優化算法結合起來,發揮優化算法的搜索特長,在有限的時間內得到最優解。

根據仿真優化原理,本文提出的AGV數量配置優化方法(圖3)由主控流程、遺傳算法和仿真模型三部分組成。主控流程控制整個優化進程,包括初始種群生成、數據傳遞、種群信息顯示;遺傳算法產生新的AGV數量配置方案;仿真模型負責種群適應值計算。三部分相互協調完成AGV數量配置的優化。

圖3 AGV數量配置優化方法

2.2 遺傳算法

仿真優化下的遺傳算法與傳統優化下的遺傳算法不同,主要表現在以下幾方面:①目標函數值是由仿真獲取的;②仿真優化的時間瓶頸不在算法的迭代過程而在仿真過程。因此在設計遺傳算法時要相應地考慮這些特點。

2.2.1 編碼設計

本文的目的是要確定每一種AGV的數量,使生產線產量達到最大化。因此可以直接以AGV的數量來進行編碼,例如第i基因位上的值代表第i種AGV的數量Ni?？紤]到種群中的每個個體的適應值不是通過函數而是通過仿真來獲取的,因此在編碼時增加基因位代表該個體的適應值即目標值(圖4)。

圖4 基因編碼

編碼時還應考慮到仿真優化大部分時間消耗在仿真過程,減少這部分時間將提高優化速度。在遺傳算法迭代過程中,子代與父代之間有相當一部分個體是相同的,在遺傳算法后期收斂時,子代與父代的差異更小。因此可以考慮在每次迭代完成之后,將子代與父代個體進行比較,如果有相同個體,則它的適應值直接從父代獲取不需要再仿真;相應地在編碼上增加一標志位,如果該個體與父代個體相同,置標志位為1。仿真計算時如果發現這個基因位為1,就不啟動仿真計算。甚至可以考慮將每次進化得到的父代存儲為歷代表,將子代與該歷代表進行比較,優化進程會更快。

2.2.2 初始種群數生成

為了避免遺傳算法過早收斂,采用隨機的方式生成初始種群,具體步驟如下:

(2)對個體的每個基因位產生一個[Ni,min,Ni,max]內的隨機數ri,將該隨機數賦給基因位。

(3)將個體導入到仿真模型中,得到該個體的適應值,將該值賦給該個體的目標值基因位,同時標志位賦值為0,如圖4所示。

(4)重復步驟(2)～(3)N次,產生一個包含N個個體的種群。

2.2.3 適應值函數

由于第1節的數學模型含有邊界約束(式(3)),故可將該邊界約束以懲罰函數的形式合并到目標函數:

2.2.4 選擇操作

采用輪盤賭的選擇方式從父代選取個體生成下一代。編碼中包含了該個體的適應值,執行選擇操作時,適應值直接從編碼中提取。需要注意的是,選擇操作一定要先于交叉和變異操作。一旦執行交叉或變異操作,編碼中的適應值將是無效的。

2.2.5 交叉操作

交叉是將兩個父代的部分基因進行替換、重組而產生新的個體,這里采用兩點交叉(圖5)。不同個體同一位置的基因表示同一種AGV的數量,基因的范圍是相同的,因此通過交叉不會產生非法解。

圖5 交叉算子

2.2.6 變異操作

變異算子能夠提高算法的局部搜索能力,維持群體的多樣性,防止過早收斂[7]。這里采用均勻變異。每次變異時,根據每一種AGV的數量[Ni,min,Ni,max],產生[Ni,min,Ni,max]之間的隨機數(圖6中的基因位)。這樣可以避免非法解,同時又能保證搜索覆蓋整個解空間。

圖6 變異算子

2.2.7 迭代終止條件

本文采用的終止條件:遺傳算法在迭代過程中,如果連續20代目標值沒有變化,停止迭代。

2.2.8 控制參數選擇

控制參數包括群體規模 N、交叉概率Pc、變異概率Pm。群體規模過小,容易收斂到局部最優解;規模過大,會造成計算量過大,群體規模一般根據實際在10～200之間選擇。交叉概率Pc過大,群體中的優良個體破壞的可能性大,使搜索走向隨機化;交叉概率Pc過小,進化速度變慢,甚至停滯。一般Pc取值范圍為0.1～0.99。同樣,當變異概率Pm很小時,易產生未成熟收斂,而增大Pm的值可以使解空間保持多樣性,一般取為0.0001～0.1。

種群的規模選擇20,由于搜索空間比較大,本文根據遺傳算法進程選擇不同的交叉概率和變異概率,在遺傳算法的初期強交叉強變異(Pm=0.01,Pc=0.7),在遺傳算法后期弱交叉弱變異(Pm=0.001,Pc=0.1)。

2.3 AGV仿真模型建立

圖7 AGV的建模

整個仿真模型可以分成兩部分,即加工部分和AGV物料運輸部分(圖7)。加工部分包括工位、輸入輸出緩沖區、配料區和成品倉庫。AGV物料運輸部分可進一步分為AGV控制層和AGV執行層。當加工區有物料運輸需求時,就觸發物料運輸事件,AGV控制層檢測到該事件后,就根據AGV調度策略選擇一輛空閑的AGV并向其發送物料運輸指令。AGV接受到該指令后,根據指令的相關信息執行該指令,在該過程中,AGV如果發生堵塞或碰撞,AGV控制層就會調用交通管理策略來協調AGV的運行。AGV任務完成之后,如果沒有新任務就調用AGV停車策略,使AGV停在指定位置。在整個任務處理過程中,AGV狀態表、物料運輸事件表始終根據AGV狀態及AGV對任務處理情況實時更新。

3 實例

3.1 裝配線布局及其他相關數據

以日本大金工業株式會社空調裝配車間為例,利用仿真優化方法對其車間的AGV的數量配置進行優化。該空調裝配車間有3條裝配線,每條裝配線都能獨立完成空調的裝配,只是產品的型號不同。每條裝配線需要3種物料,這3種物料位于不同的配料區,A1線的a種物料位于A_A1區域,如圖8所示。這樣3條裝配線共9種物料,對應有9塊配料區,物料從配料區到裝配線對應由9種AGV來完成運送。圖8所示為該裝配車間的布局,圖中實線表示的是AGV的路徑,從圖中可以看出,該車間AGV的路徑重疊、交叉比較嚴重,不同種類、不同速度的AGV運行經常出現堵塞、需要避撞的情況。

9種AGV的數量范圍均為[1,10];路徑選擇規則為最短路徑規則;調度規則為先到先服務;交通協調規則為紅綠燈協調法;最低利用率為60%;運送a種物料的AGV速度為500mm/s;運送b種物料的AGV速度為500mm/s;運送c種類物料的AGV速度為450mm/s;3條裝配線的節拍因產品型號而異。

圖8 AGV路徑及裝配線布局

3.2 仿真優化的實現

根據仿真優化的思想,本文提出的優化方法分成三大模塊(圖9):遺傳算法模塊、主控模塊和仿真模塊。主控模塊控制整個優化進程,包括初始種群生成、數據傳遞、種群信息顯示。優化模塊利用MATLAB的遺傳算法包,該算法包含大量與遺傳算法操作相關的函數;同時 MAT LAB Engine提供數據接口,實現與其他模塊的數據交互。仿真模塊采用仿真軟件QUEST,它自帶的仿真語言SCL能夠對復雜的邏輯關系進行建模,同時QUEST提供SOCKET數據通信接口,可以通過主控模塊與優化模塊進行數據交互。圖10所示為建立的仿真模型。

圖9 仿真優化的實現

圖10 AGV仿真模型

3.3 仿真優化結果

AGV數量配置優化進程如圖11所示,遺傳算法在第96代收斂,目標值為361。對應的9種AGV最佳數量配置為[3,3,5,2,3,4,2,3,5]。由此可見,利用仿真優化方法對AGV數量配置的優化的可行性。表1是仿真優化方法和其他估算方法的結果,從目標值可以看出仿真優化方法的結果更優。

圖11 遺傳算法進程

表1 結果比較

4 結語

本文以輸出產品數最大化為目標,以AGV的數量配置為決策變量建立了問題的數學模型;針對該問題的復雜性,提出了仿真優化方法,討論了該方法的實現問題;最后通過對日本大金工業株式會社空調裝配車間AGV數量進行優化來驗證方法的有效性及實用性。

[1]Egbelu P J.The Use of Nnon-simulation Approa-ches in Estimating Vehicle Requirements in an Automated Guided Vehicle Based T ransport System[J].Material Flow,1987,4:17-32.

[2]王冰,張惠僑.自動導向系統的規劃設計[J].上海交通大學學報,2001,35(12):1793-1797.

[3]Srinivasan M M,Bozer Y A,Cho M.Trip-based Material HandlingSystems:Throughput Capacity Analysis[J].IIE Transactions,1994,26(1):70-89.

[4]Iris F A Vis.Survey of Research in the Design and Control of Automatic Guided Vehicle Systems[J].European Journal of Operation Research,2006,170(3):667-709.

[5]王國新,寧汝新,王愛民.基于仿真的生產調度優化技術研究[J].計算機集成制造系統,2007,13(7):1420-1427.

[6]王國新,寧汝新,王愛民,等.仿真優化在制造系統中的應用現狀及發展趨勢[J].系統仿真學報,2008,20(1):1-6.

[7]王小平,曹立明.遺傳算法——理論、應用與軟件實現[M].西安:西安交通大學出版社,2002.