孫衛(wèi)明 方彥軍 肖勇 唐猛

(廣東電網(wǎng)公司電力科學(xué)研究院1,廣東 廣州 510000;廣東省智能電網(wǎng)新技術(shù)企業(yè)重點(diǎn)實(shí)驗(yàn)室2,廣東 廣州 510080;武漢大學(xué)動(dòng)力與機(jī)械學(xué)院3,湖北 武漢 430072)

電能計(jì)量設(shè)備檢定中心智能立庫調(diào)度優(yōu)化研究

孫衛(wèi)明1,2方彥軍3肖勇1,2唐猛3

(廣東電網(wǎng)公司電力科學(xué)研究院1,廣東 廣州 510000;廣東省智能電網(wǎng)新技術(shù)企業(yè)重點(diǎn)實(shí)驗(yàn)室2,廣東 廣州 510080;武漢大學(xué)動(dòng)力與機(jī)械學(xué)院3,湖北 武漢 430072)

為有效解決電能計(jì)量設(shè)備檢定中心智能立體倉庫的出入庫作業(yè)調(diào)度優(yōu)化問題,提出了一種改進(jìn)的人工魚群算法(AFSA)。針對(duì)系統(tǒng)出入庫作業(yè)的特點(diǎn),設(shè)計(jì)了一種包含軌道引導(dǎo)小車(RGV)的升降機(jī)在各階段選擇信息的編碼和解碼方法。將記憶行為和個(gè)體交流行為引入算法,并采用自適應(yīng)步長和視野范圍來避免算法陷入局部最優(yōu),加快算法的后期收斂速度。結(jié)果表明,該改進(jìn)算法收斂速度更快、優(yōu)化率更高、得到的解最優(yōu),具有較強(qiáng)的實(shí)用性和魯棒性。

智能立體倉庫 電能計(jì)量 升降機(jī) 人工魚群算法(AFSA) 調(diào)度優(yōu)化

0 引言

智能立體倉庫是存放電能計(jì)量設(shè)備的主要載體,也是檢定中心的重要組成部分,其運(yùn)行效率直接影響檢定中心的整體效率[1-2]。因此,提高智能立體倉庫的運(yùn)行效率是提高檢定效率的關(guān)鍵。

對(duì)于自動(dòng)小車存取系統(tǒng)(autonomous vehicle storage and retrieval system,AVS/RS)的軌道引導(dǎo)小車(rail guided vehicle,RGV)調(diào)度問題,羅鍵等[3]提出了一種基于改進(jìn)量子微粒群的優(yōu)化方法,但未對(duì)升降機(jī)的選取進(jìn)行討論。吳長慶等[4]提出了一種基于Petri網(wǎng)和有向圖的死鎖控制方法,但系統(tǒng)中只含有一臺(tái)升降機(jī)。目前,對(duì)于多RGV多升降機(jī)AVS/RS系統(tǒng)的存取調(diào)度問題鮮有人研究。

本文給出了AVS/RS系統(tǒng)的出入庫作業(yè)調(diào)度數(shù)學(xué)模型,并運(yùn)用改進(jìn)的人工魚群算法(artificial fish swarm algorithm,AFSA)求出該模型的最優(yōu)解,從而得到系統(tǒng)的最優(yōu)調(diào)度策略。

1 AVS/RS系統(tǒng)調(diào)度問題描述與建模

1.1 問題描述

多升降機(jī)AVS/RS系統(tǒng)的調(diào)度優(yōu)化問題,即當(dāng)系統(tǒng)中有任務(wù)觸發(fā)時(shí),為每個(gè)RGV規(guī)劃運(yùn)行路徑。與平面AGV系統(tǒng)不同的是:RGV在執(zhí)行跨層作業(yè)時(shí),系統(tǒng)不僅需要規(guī)劃水平路徑,還要對(duì)其垂直路徑進(jìn)行規(guī)劃,即選擇合適的升降機(jī)來完成垂直方向上的運(yùn)動(dòng),以提高系統(tǒng)整體的運(yùn)行效率。

AVS/RS系統(tǒng)主要包含入庫作業(yè)、出庫作業(yè)兩種作業(yè)類型。入庫作業(yè)是指RGV將單位負(fù)載從其所在貨位運(yùn)至出入庫(I/O)口,出庫作業(yè)是指RGV將單位負(fù)載從出入庫口(I/O)運(yùn)至其分配貨位。對(duì)于上述兩種作業(yè)類型,RGV執(zhí)行一次操作時(shí)需要經(jīng)過兩個(gè)運(yùn)行過程:一是RGV從當(dāng)前位置運(yùn)行至單位負(fù)載所在位置完成裝載;二是RGV從該單位負(fù)載所在位置運(yùn)行至其目標(biāo)位置完成卸載。兩種操作的運(yùn)行過程示意圖如圖1所示。系統(tǒng)在進(jìn)行單位負(fù)載的出入庫作業(yè)調(diào)度時(shí),RGV按照分批作業(yè)的方式進(jìn)行,即將所有任務(wù)按照RGV數(shù)量分為若干批,然后進(jìn)行循環(huán)作業(yè)。

圖1 RGV作業(yè)平面示意圖Fig.1 Schematic diagram of the RGV job plane

對(duì)于大多數(shù)任務(wù)而言,至少有一個(gè)階段需要借助升降機(jī)來實(shí)現(xiàn)垂直方向上的運(yùn)動(dòng)。當(dāng)系統(tǒng)完成任務(wù)分配后,需要對(duì)各RGV各階段的路徑進(jìn)行規(guī)劃。水平路徑是由垂直路徑所決定的。為提高整體存取效率, RGV的路徑規(guī)劃需考慮升降機(jī)的調(diào)度。因此,RGV各階段的水平路徑及升降機(jī)的選擇(垂直路徑)是系統(tǒng)調(diào)度優(yōu)化的關(guān)鍵。

1.2 問題的轉(zhuǎn)化

RGV在執(zhí)行出入庫作業(yè)時(shí),其每一階段都包括水平方向上和垂直方向上兩個(gè)部分的運(yùn)動(dòng)路徑。

水平方向上的運(yùn)動(dòng)路徑包括以下兩方面內(nèi)容。

①水平方向上的運(yùn)動(dòng)路徑

一是RGV從當(dāng)前位置至升降機(jī)所在位置的運(yùn)行距離dhk1;二是RGV出升降機(jī)至到達(dá)目標(biāo)節(jié)點(diǎn)的運(yùn)行距離dhk2。水平方向上的運(yùn)行時(shí)間為Dhk=dhk1+dhk2。

②垂直方向上的運(yùn)動(dòng)路徑

在多RGV多升降機(jī)AVS/RS系統(tǒng)中,從系統(tǒng)的運(yùn)行成本考慮,RGV的垂直運(yùn)行路徑應(yīng)由電梯的空跑距離和RGV實(shí)際搭乘電梯的距離組成。選擇不同的升降電梯,其垂直路徑也不相同。垂直運(yùn)行路徑為Dvk=Wd+Rd。其中,Wd為升降電梯從當(dāng)前位置運(yùn)行至RGV所在層的距離,即升降機(jī)的空跑距離; Rd為RGV從升降機(jī)至目標(biāo)層的運(yùn)行距離,即RGV的實(shí)際搭乘距離。Wd與升降機(jī)的當(dāng)前位置、升降機(jī)的狀態(tài)等因素有關(guān)。

本文將AVS/RS系統(tǒng)中RGV的調(diào)度優(yōu)化問題轉(zhuǎn)化為不相關(guān)并行機(jī)的混合流水線調(diào)度問題(hybrid flow-shop schedulingproblem,HFSP-UPM)[5-9]。各RGV進(jìn)行一次出入庫作業(yè)時(shí),至少有一個(gè)階段需要進(jìn)行電梯的選擇,把各升降電梯看作不相關(guān)并行機(jī)。另外,HFSP要求每一階段各工件均要完成一次機(jī)器的選擇,但作業(yè)過程中會(huì)出現(xiàn)某一RGV在某一階段不需要使用升降電梯(非跨層任務(wù))的情況,為此本文添加一個(gè)虛擬電梯。選擇虛擬電梯,表明在此階段無需搭乘電梯且垂直運(yùn)行距離Dvk為0。AVS/RS系統(tǒng)一次作業(yè)的示意圖如圖2所示。

圖2 AVS/RS系統(tǒng)調(diào)度示意圖Fig.2 Schematic diagram of AVS/RS system scheduling

1.3 數(shù)學(xué)模型

綜上所述,多升降機(jī)AVS/RS系統(tǒng)的出入庫作業(yè)調(diào)度優(yōu)化可視為以路徑長度為優(yōu)化目標(biāo)的HFPS問題[8-9],具體描述如下。

設(shè)系統(tǒng)當(dāng)前入庫(出庫)任務(wù)為T個(gè),由N個(gè)RGV運(yùn)用(F-1)個(gè)升降機(jī)進(jìn)行批組循環(huán)作業(yè),且N≥F,將S個(gè)任務(wù)分為T/N=P(令P為整數(shù))個(gè)批組進(jìn)行循環(huán)作業(yè)。每個(gè)循環(huán)中的作業(yè)組數(shù)量為N,每個(gè)批組需經(jīng)歷兩個(gè)階段。令每階段的并行升降機(jī)個(gè)數(shù)為F,其中有一個(gè)為虛擬升降機(jī),記RGV的編號(hào)為b(b=1,2,…, N)。每一階段RGV可選擇任意升降機(jī)到達(dá)其目標(biāo)層,同一RGV選擇不同的升降機(jī)所經(jīng)歷的路徑不同。因此尋找一個(gè)完成所有任務(wù)距離最短的作業(yè)方案I為優(yōu)化目標(biāo),則目標(biāo)函數(shù)為:

式(1)為調(diào)度優(yōu)化指標(biāo),其中,Ds,b,hk1為該RGV從當(dāng)前位置運(yùn)行至升降機(jī)f所在位置的運(yùn)行距離, Ds,b,hk2為該RGV從升降機(jī)當(dāng)前位置運(yùn)行到目標(biāo)貨位的運(yùn)行距離。式(2)為第b個(gè)RGV在階段s選擇升降機(jī)f的垂直運(yùn)行距離,包括升降機(jī)f從當(dāng)前位置到達(dá)該RGV所在層的運(yùn)行距離Ws,b,f及該RGV實(shí)際搭乘升降機(jī)的運(yùn)行距離Rs,b,f。式(3)為各階段升降機(jī)的使用情況。式(4)表示同一階段每個(gè)RGV只能占用一臺(tái)升降機(jī)。

2 改進(jìn)的人工魚群算法(IAFSA)

2.1 基本人工魚群算法

基本人工魚群算法(AFSA)是首先構(gòu)造簡單的人工魚模型,然后通過模擬魚群覓食、聚群、追尾等食物搜索行為,并將每一代的最優(yōu)解計(jì)入“公告板”,最終實(shí)現(xiàn)問題尋優(yōu)的群智能優(yōu)化算法。人工魚的狀態(tài)定義為X= (x1,x2,...,xn),X為欲尋優(yōu)的變量,n表示向量X的維度。人工魚當(dāng)前所在位置的食物濃度定義為Y=f(X), Y表示適應(yīng)度函數(shù)值。AFSA算法中,dij=||Xi-Xj||表示個(gè)體之間的距離,V為人工魚的視野范圍,S為人工魚的最大可移動(dòng)步長,δ為擁擠度因子[10]。

雖然AFSA算法善于利用全局信息,具有較強(qiáng)的全局搜索能力,但由于擁擠度的作用,使得個(gè)體始終無法集結(jié)到最優(yōu)值附近,從而導(dǎo)致后期的收斂速度較慢且容易陷入局部極值點(diǎn)。

2.2 改進(jìn)算法

目前已經(jīng)出現(xiàn)一些人工魚群的改進(jìn)算法,如運(yùn)用粒子群算法對(duì)人工魚群算法進(jìn)行優(yōu)化[11]、增加魚群的跳躍行為[12]等。本文將記憶、個(gè)體交流兩種行為引入人工魚群算法,同時(shí)采用自適應(yīng)步長和視野范圍,以此來提高算法的后期收斂速度和避免其陷入局部最優(yōu)。

2.2.1 記憶行為和個(gè)體交流行為

①記憶行為

記憶行為指人工魚Xi向自身所經(jīng)歷的最優(yōu)位置Xi|best移動(dòng)一步。該行為使人工魚在決定下一步的移動(dòng)方向時(shí)能夠參考自身所經(jīng)歷過的最優(yōu)位置,增強(qiáng)了魚群行為的方向性。

②個(gè)體交流行為

個(gè)體交流行為指人工魚Xi向魚群公告板上記錄的最優(yōu)位置Hbest移動(dòng)一步。該行為使人工魚在決定下一步移動(dòng)方向時(shí)能夠參考整個(gè)魚群的最優(yōu)位置,增強(qiáng)了魚群搜索過程中個(gè)體間的信息交流與共享。

2.2.2 自適應(yīng)步長和視野范圍

為了增強(qiáng)算法的全局及局部搜索能力和優(yōu)化精度,人工魚在初期采用較大的視野范圍及步長進(jìn)行大范圍搜索。在算法的后期,通過逐步縮小視野范圍及步長在最優(yōu)值附近進(jìn)行局部搜索,以此來提高算法的局部搜索能力和尋優(yōu)精度。

式中:初始視野范圍V=Zm/4,Zm為搜索空間的最大值;S=V/8;t為當(dāng)前的迭代次數(shù);Tmax為最大迭代次數(shù)。

3 AVS/RS系統(tǒng)優(yōu)化調(diào)度

針對(duì)AVS/RS系統(tǒng)調(diào)度的特點(diǎn),本節(jié)對(duì)改進(jìn)人工魚群算法(improved artificial fish swarm algorithm, IAFSA)中的編碼與解碼、適應(yīng)度函數(shù)進(jìn)行說明,最后給出算法流程。

3.1 編碼與解碼

根據(jù)AVS/RS系統(tǒng)調(diào)度模型的特點(diǎn),采用整數(shù)編碼方式表示RGV在各階段所選擇的升降機(jī)編號(hào),每階段的并行升降機(jī)數(shù)量為F。狀態(tài)向量Xi構(gòu)成一條人工魚,人工魚的維度為2N(N為RGV數(shù)量)。它包含了系統(tǒng)中RGV及升降機(jī)的調(diào)度情況,每條人工魚對(duì)應(yīng)一個(gè)可行的調(diào)度方案。如令一條人工魚的狀態(tài)為: Xi={xi1,xi2,…,xiN;xi(N+1),xi(N+2),…,xi(N+N)}={1,4, 3,2,0;3,2,1,4,2},每個(gè)字符元素為[0,F]之間的整數(shù),如第三個(gè)元素“3”表示在第一階段3號(hào)RGV搭乘3號(hào)升降機(jī)來完成垂直運(yùn)動(dòng)。根據(jù)約束條件確定RGV在各階段的升降機(jī)選擇即稱為解碼。

3.2 適應(yīng)度函數(shù)

本文的優(yōu)化目標(biāo)為完成所有任務(wù)組的最大運(yùn)行距離,采用乘冪變換對(duì)目標(biāo)函數(shù)進(jìn)行適度縮小,則適應(yīng)度函數(shù)為:

式中:Lmax為一條人工魚所代表的一個(gè)調(diào)度方案的最大運(yùn)行距離。

3.3 適應(yīng)度函數(shù)

AVS/RS調(diào)度模型的IAFSA算法流程如下。

①基于AVS/RS調(diào)度模型的特點(diǎn),初始化人工魚群信息,包括各人工魚S、V。

②計(jì)算各人工魚適應(yīng)度值,公告板記錄最優(yōu)值,根據(jù)2.2.2節(jié)方法調(diào)整人工魚S、V。

③對(duì)各人工魚的4種行為(聚群、追尾、記憶和個(gè)體交流)進(jìn)行評(píng)價(jià),選擇最優(yōu)的行為。若個(gè)體執(zhí)行該最優(yōu)行為后適應(yīng)度值優(yōu)于當(dāng)前位置,則執(zhí)行該行為;否則重新進(jìn)行行為選擇。

④計(jì)算各人工魚適應(yīng)度值,更新公告板,調(diào)整人工魚S、V,判斷是否達(dá)到最大迭代次數(shù)。若達(dá)到最大迭代次數(shù),則輸出最優(yōu)解;否則轉(zhuǎn)至步驟③。

4 實(shí)例

以某省級(jí)電力公司電能計(jì)量設(shè)備檢定中心智能立體倉庫為例。系統(tǒng)包含RGV數(shù)量N=4臺(tái),升降機(jī)數(shù)量F=4臺(tái),貨架長18 m,高16.5 m;共有6排貨架,單層每面有13個(gè)貨位,每排23層,共10 764個(gè)貨位;單元貨位高度h=0.45 m,寬度w=0.7 m,深度d=0.5 m。RGV的水平速度Vx=2 m/s,升降機(jī)的速度Vy=1.5 m/s。為了驗(yàn)證改進(jìn)的AFSA算法求解該問題的有效性,隨機(jī)生成一個(gè)包含4個(gè)貨位點(diǎn)的作業(yè)組,分別用基本AFSA算法、量子粒子群優(yōu)化算法(quantum particle swarm optimization,QPSO)算法[1]與本文提出的IAFSA算法進(jìn)行實(shí)例仿真比較。其中,設(shè)初始群體規(guī)模A=150,維數(shù)為10,最大迭代次數(shù)為maxk=160,3種算法各獨(dú)立運(yùn)行20次,得到的平均收斂過程曲線如圖3所示。

圖3 3種算法的收斂過程曲線Fig.3 The convergence process curves of three of the algorithms

由圖3可以看出,本文提出的IAFSA算法由于采用自適應(yīng)步長和視野范圍,既能夠避免陷入局部最優(yōu),又加快了后期收斂,大約經(jīng)過100代就能趨于收斂,得到的結(jié)果最優(yōu)。

4個(gè)貨位采用3種算法獨(dú)立運(yùn)行20次后結(jié)果比較如表1所示。

表1 4個(gè)貨位的算法結(jié)果比較Tab.1 Comparison of the results of algorithms in 4 cargo spaces

從表1可以看出,在相同種群規(guī)模和迭代次數(shù)的前提下,本文提出的IAFSA算法具有收斂速度快、最優(yōu)解較好的優(yōu)點(diǎn),適合本模型的尋優(yōu)。

5 結(jié)束語

針對(duì)AVS/RS系統(tǒng)存取作業(yè)調(diào)度問題的特點(diǎn),本文首先對(duì)該系統(tǒng)優(yōu)化調(diào)度問題進(jìn)行詳細(xì)分析并建立相應(yīng)的數(shù)學(xué)模型。針對(duì)該模型的特征,提出了一種改進(jìn)的人工魚群算法來進(jìn)行求解。然后設(shè)計(jì)了一種包含RGV的升降機(jī)在各階段的選擇信息的編碼和解碼方法;分別將記憶行為與個(gè)體交流行為引入人工魚群算法,并采用自適應(yīng)步長和視野范圍來避免算法陷入局部最優(yōu),同時(shí)提高算法的后期收斂速度。最后,以某省級(jí)電能計(jì)量設(shè)備自動(dòng)檢定中心的AVS/RS系統(tǒng)為例,將該算法與另外兩種算法進(jìn)行比較。結(jié)果表明,該改進(jìn)算法收斂速度更快、優(yōu)化率更高,得到的解最優(yōu),有效性和魯棒性較強(qiáng),能夠?yàn)锳VS/RS系統(tǒng)的調(diào)度優(yōu)化提供理論依據(jù)。

[1] 林乃瑜,林岳凌,譚振豪,等.電能表自動(dòng)加封系統(tǒng)在計(jì)量檢定流水線上的應(yīng)用[J].廣東電力,2013,26(11):122-127.

[2] 梁洪浩,丁國茂.面向未來電網(wǎng)的計(jì)量自動(dòng)化系統(tǒng)存儲(chǔ)技術(shù)研究[J].廣東電力,2012,25(4):22-26.

[3] 羅鍵,吳長慶,李波,等.基于改進(jìn)量子微粒群的軌道引導(dǎo)小車系統(tǒng)建模與優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng),2011,17(2):321-328.

[4] 吳長慶,何善君,羅鍵,等.自動(dòng)小車存取系統(tǒng)中軌道引導(dǎo)小車環(huán)路死鎖控制的研究[J].計(jì)算機(jī)集成制造系統(tǒng),2008,14(9): 1767-1773.

[5] 王凌,周剛,許曄.求解不相關(guān)并行混合流水線調(diào)度問題的人工蜂群算法[J].控制理論與應(yīng)用,2012,29(12):1551-1557.

[6] Pan Q K,Tasgetiren M F,Suganthan P N,et al.A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J].Information Sciences,2010,181(12):2455-2468.

[7] 王圣堯,王凌,許曄.求解相同并行機(jī)混合流水線車間調(diào)度問題的分布估計(jì)算法[J].計(jì)算機(jī)集成制造系統(tǒng),2013,12(6):51-15.

[8] Wang X,Tang L.A tabu search heuristic for the hybrid flow-shop scheduling with finite intermediate buffers[J].Computers& Operations Research,2008,36(3):907-918.

[9] Alaykyran K,Engin O,Doyen A.Using ant colony Optimization to solve hybrid flow shop scheduling problem[J].International Journal of Advanced Manufacturing Technology,2007,35(5/6):541-550.

[10] 陳鐵梅,羅家祥.帶擾動(dòng)和變異因子的改進(jìn)禁忌搜索算法求解貼片機(jī)過程優(yōu)化[J].控制與決策,2013,28(3):363-368.

[11] 段其昌,唐若笠.粒子群優(yōu)化魚群算法仿真分析[J].控制與決策,2013,28(9):1436-1440.

[12] Tsai H C,Lin Y H.Modification of the fish swarmalgorithm with particle swarm optimization formulation and communication behavior[J].Applied Soft Computing,2011,11(8):5367-5374.

Research on the Scheduling Optimization of Intelligent 3D Warehouse in Electric Energy Metering Equipment Test Center

In order to effectively solve the problem of scheduling optimization for IN/OUT of storage jobs in intelligent 3D warehouse for electric energy metering equipment test center,the improved artificial fish swarm algorithm(AFSA)is proposed.In accordance with the features of IN/ OUT jobs in the system,the encoding and decoding method is designed,in which the lifter selection information for rail guided vehicle(RGV) at each stage is contained.The memory behavior and individual communication behavior are introduced into the algorithm,and local optimization of the algorithm is avoided by adopting adaptive step and vision field,in addition,the late convergence is speedup.The result shows that this improved algorithm offers faster convergence speed and higher optimized rate and gets optimum solution,possesses stronger practicality and robustness.

Intelligent 3D warehouse Electric energy metering Lifter Artificial fish swarm algorithm(AFSA) Scheduling optimization

TP18

A

國家自然科學(xué)基金資助項(xiàng)目(編號(hào):61170024);

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(編號(hào):121031);

廣東電網(wǎng)公司電力科院研究院基金資助項(xiàng)目(編號(hào):K-GD2013-0470-001);

廣東省智能電網(wǎng)新技術(shù)企業(yè)重點(diǎn)實(shí)驗(yàn)室基金資助項(xiàng)目(編號(hào):2060299)。

修改稿收到日期:2014-03-27。

孫衛(wèi)明(1971-),男,1994年畢業(yè)于華中理工大學(xué)電磁測量及其儀表專業(yè),獲學(xué)士學(xué)位,高級(jí)工程師;主要從事電能計(jì)量及計(jì)量自動(dòng)化的研究。