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

1.上海交通大學(xué),上海,200030 2.上海市網(wǎng)絡(luò)化制造與企業(yè)信息化重點實驗室,上海,200030 3.大金工業(yè)株式會社,大阪,日本,5300054

0 引言

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

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

1 問題描述

圖1 生產(chǎn)車間布局

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

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

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

2 仿真優(yōu)化

2.1 仿真優(yōu)化原理

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

圖2 仿真優(yōu)化原理圖

仿真優(yōu)化不同于傳統(tǒng)的優(yōu)化,也不同于仿真實驗,具體表現(xiàn)在如下幾方面:

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

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

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

圖3 AGV數(shù)量配置優(yōu)化方法

2.2 遺傳算法

仿真優(yōu)化下的遺傳算法與傳統(tǒng)優(yōu)化下的遺傳算法不同,主要表現(xiàn)在以下幾方面:①目標(biāo)函數(shù)值是由仿真獲取的;②仿真優(yōu)化的時間瓶頸不在算法的迭代過程而在仿真過程。因此在設(shè)計遺傳算法時要相應(yīng)地考慮這些特點。

2.2.1 編碼設(shè)計

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

圖4 基因編碼

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

2.2.2 初始種群數(shù)生成

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

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

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

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

2.2.3 適應(yīng)值函數(shù)

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

2.2.4 選擇操作

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

2.2.5 交叉操作

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

圖5 交叉算子

2.2.6 變異操作

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

圖6 變異算子

2.2.7 迭代終止條件

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

2.2.8 控制參數(shù)選擇

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

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

2.3 AGV仿真模型建立

圖7 AGV的建模

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

3 實例

3.1 裝配線布局及其他相關(guān)數(shù)據(jù)

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

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

圖8 AGV路徑及裝配線布局

3.2 仿真優(yōu)化的實現(xiàn)

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

圖9 仿真優(yōu)化的實現(xiàn)

圖10 AGV仿真模型

3.3 仿真優(yōu)化結(jié)果

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

圖11 遺傳算法進程

表1 結(jié)果比較

4 結(jié)語

本文以輸出產(chǎn)品數(shù)最大化為目標(biāo),以AGV的數(shù)量配置為決策變量建立了問題的數(shù)學(xué)模型;針對該問題的復(fù)雜性,提出了仿真優(yōu)化方法,討論了該方法的實現(xiàn)問題;最后通過對日本大金工業(yè)株式會社空調(diào)裝配車間AGV數(shù)量進行優(yōu)化來驗證方法的有效性及實用性。

[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]王冰,張惠僑.自動導(dǎo)向系統(tǒng)的規(guī)劃設(shè)計[J].上海交通大學(xué)學(xué)報,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]王國新,寧汝新,王愛民.基于仿真的生產(chǎn)調(diào)度優(yōu)化技術(shù)研究[J].計算機集成制造系統(tǒng),2007,13(7):1420-1427.

[6]王國新,寧汝新,王愛民,等.仿真優(yōu)化在制造系統(tǒng)中的應(yīng)用現(xiàn)狀及發(fā)展趨勢[J].系統(tǒng)仿真學(xué)報,2008,20(1):1-6.

[7]王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.