Dynamic Analysis and Decision Making Model of AVS/RS System

方彥軍　唐　猛

(武漢大學(xué)動力與機(jī)械學(xué)院，湖北 武漢　430072)

AVS/RS系統(tǒng)動態(tài)分析及決策模型

Dynamic Analysis and Decision Making Model of AVS/RS System

方彥軍唐猛

(武漢大學(xué)動力與機(jī)械學(xué)院，湖北 武漢430072)

摘要：通過模擬自動小車存取系統(tǒng)(AVS/RS)中任務(wù)的動態(tài)排隊過程，建立了一個基于動態(tài)排隊網(wǎng)絡(luò)的系統(tǒng)分析與決策模型。首先，描述了AVS/RS的系統(tǒng)構(gòu)架、運(yùn)行規(guī)則及任務(wù)場景概率。接著，根據(jù)系統(tǒng)任務(wù)特征構(gòu)造了一個動態(tài)排隊網(wǎng)絡(luò)模型(DQNM)。最后，運(yùn)用改進(jìn)的聚合法對該系統(tǒng)模型進(jìn)行求解，并對系統(tǒng)性能進(jìn)行分析。分析表明，該模型能夠找出系統(tǒng)的最佳小車-電梯組合方式，從而為優(yōu)化系統(tǒng)的設(shè)計、提高設(shè)備的利用率、節(jié)約系統(tǒng)運(yùn)行成本提供決策支持。

第一作者方彥軍(1957-)，男，1988年畢業(yè)于武漢大學(xué)電力系統(tǒng)自動化專業(yè)，獲博士學(xué)位，教授；主要從事自動化方面的教學(xué)與研究工作。

關(guān)鍵詞：AVS/RS動態(tài)排隊網(wǎng)絡(luò)聚合法分析決策

Abstract：Through simulating the dynamic queuing process of the tasks in AVS/RS, the system analysis and decision making model based on dynamic queuing network is established. Firstly, the architecture, operation rules and probability of task scenaries of AVS/RS are described. Then the dynamic queuing network model (DQNM) is constructed in accordance with the characteristics of the system tasks. The system model is solved using the improved polymerization method; and the performance of the system is analyzed. The analysis show that this model is able to find out the optimal combination mode of vehicles and lifts, thus it provides decision support for optimizing system design, enhancing the equipment utilization and saving system operating costs.

Keywords：AVS/RSDynamic queuing network(DQNM)PolymerizationAnalysisDecision-making

0引言

自動小車存取系統(tǒng)(autonomous vehicle storage and retrieval systems，AVS/ RS)是一項關(guān)于實現(xiàn)智能立體倉儲中單位負(fù)載自動存取的新技術(shù)[1]。在系統(tǒng)配置參數(shù)固定的情況下，可以通過改變運(yùn)行小車及電梯的數(shù)量來滿足系統(tǒng)不同的吞吐量要求，以提高設(shè)備利用率，節(jié)約運(yùn)行成本。

目前，針對AVS/RS的性能評估,國內(nèi)外學(xué)者進(jìn)行了不同的研究[1-11]。Malmborg[5]提出了運(yùn)用狀態(tài)方程模型來預(yù)測雙命令周期在AVS/RS中交叉使用的比例。Fukunari[7]提出了一個排隊網(wǎng)絡(luò)方法模型來估計預(yù)期資源利用率在AVS/RS中交錯使用的策略。

本文通過模擬自動小車存取系統(tǒng)中任務(wù)的動態(tài)排除過程，建立了AVS/RS系統(tǒng)的動態(tài)分析與決策模型，對系統(tǒng)的所有任務(wù)情景進(jìn)行評估，并找出了小車-電梯的最佳組合方式。該模型為系統(tǒng)的設(shè)計及運(yùn)行提供決策支持。

1AVS/RS系統(tǒng)的描述

1.1　系統(tǒng)的描述

AVS/RS系統(tǒng)主要由自動小車、貨架及軌道和升降電梯3部分組成。由于系統(tǒng)的主要運(yùn)行成本為自動引導(dǎo)小車(RGV)和升降電梯，RGV占總成本的25%，存儲貨架的成本與傳統(tǒng)的AS/RS系統(tǒng)相當(dāng),因此，需要根據(jù)系統(tǒng)的吞吐量需求來對運(yùn)行RGV和升降電梯的數(shù)量進(jìn)行調(diào)整。

由于智能倉儲中貨物的位置都是已知的，尋找貨物位置的時間可忽略,因此，系統(tǒng)采用空間隨機(jī)的存儲策略能夠降低系統(tǒng)的運(yùn)行成本[3]。在這種策略下，特定貨物的位置是一個隨著時間變化的隨機(jī)變量。對于同一個地址，不同的時間允許存放不同的貨物，這樣能夠保證空間利用的最大化[4]。

系統(tǒng)中通常會包含兩種類型的任務(wù)：存任務(wù)和取任務(wù)。存任務(wù)是指將單位負(fù)載從出入庫節(jié)點(I/O)運(yùn)送至可用的空閑貨位節(jié)點；取任務(wù)是指從該負(fù)載所在貨位節(jié)點取貨并運(yùn)送至出入庫節(jié)點(I/O)。系統(tǒng)的運(yùn)行規(guī)則具體如下。

① 小車的停靠位置為其最后一個存或取任務(wù)完成時所在節(jié)點；電梯的停靠位置為其最后一個垂直運(yùn)動完成時所在節(jié)點。

② 存取任務(wù)的到達(dá)時間是均等的，都服從泊松分布；小車進(jìn)出電梯的時間可忽略不計。

③ 每個電梯配備一個出入庫口(I/O)，位于第一層靠近電梯的位置，電梯與I/O口之間的裝卸傳輸時間Tt=14 s。

④ 任務(wù)的響應(yīng)遵循先到先服務(wù)(first come first served,FCFS)的策略，需要使用同一部電梯的小車同樣遵循先到先服務(wù)的策略。

1.2　任務(wù)場景發(fā)生概率

為了得到完成預(yù)期任務(wù)的所需時間，需要對所有可能的任務(wù)場景進(jìn)行考慮。本文根據(jù)任務(wù)類型、小車所在位置、目標(biāo)貨位所在層以及是否使用電梯,將所有任務(wù)共分為6個存任務(wù)場景和7個取任務(wù)場景，一共13個任務(wù)場景[12]。

由于智能倉儲采用隨機(jī)的存儲策略，且小車在各層服從均勻分布，因此各任務(wù)場景的發(fā)生概率Pc的計算公式具體為：

Pc=P1P2P3

(1)

式中:P1=λS|R/(λS+λR)為任務(wù)類型的概率；P2為被占用小車處于所在層的概率，小車在第一層時為1/T，否則為(T-1)/T；P3為目標(biāo)貨位所在層的概率，目標(biāo)在第一層時為P1(1/T)，否則為P1(T-1)/T。

2AVS/RS系統(tǒng)的動態(tài)排隊網(wǎng)絡(luò)模型

2.1　單任務(wù)動態(tài)排隊網(wǎng)絡(luò)模型

對于兩種任務(wù)類型，如果小車需要運(yùn)行至非當(dāng)前位置所在層，則要使用電梯。本文令存取任務(wù)(S/R)為客戶，AVs為二級資源，小車水平方向的移動及搭乘電梯所消耗的時間為服務(wù)器，且每個任務(wù)在進(jìn)入隊列之前需要分配一臺自動小車(RGV)。因此，系統(tǒng)中包含兩種類型的動態(tài)隊列：一種是小車隊列；另一種為電梯隊列。由此可以構(gòu)造一個半封閉的動態(tài)排隊網(wǎng)絡(luò)模型來模擬系統(tǒng)隊列的動態(tài)過程[13]。

圖1為單任務(wù)的動態(tài)排隊網(wǎng)絡(luò)模型。圖1中，VQ1對應(yīng)小車從當(dāng)前位置運(yùn)行至電梯節(jié)點的水平運(yùn)動過程；LQ相當(dāng)于電梯的運(yùn)動過程，當(dāng)電梯完成小車的運(yùn)送后才可釋放，LQ中存在多臺并行的升降電梯；VQ2對應(yīng)小車從電梯位置運(yùn)行至目標(biāo)貨位所在節(jié)點的位置并加上存或取任務(wù)的裝載或卸載過程。被占用的小車直到完成整個存或取任務(wù)后才會被釋放。VQ1和VQ2是用來表示計算小車運(yùn)行時間的虛擬服務(wù)器且存在多臺并行的RGV，因此在VQ1和VQ2前分別存在一個虛擬的小車隊列。即將到達(dá)系統(tǒng)的任務(wù)首先進(jìn)入小車隊列，隨后進(jìn)入電梯隊列。任務(wù)和小車在同步站點中進(jìn)行一一匹配。

圖1　單任務(wù)的動態(tài)排隊網(wǎng)絡(luò)模型

當(dāng)一臺自動小車空閑時，則一個將要到達(dá)的任務(wù)就會立即進(jìn)入系統(tǒng)的隊列當(dāng)中，并跟該小車進(jìn)行綁定；否則該任務(wù)就需要在任務(wù)隊列中等待，直到有空閑小車出現(xiàn)為止。當(dāng)任務(wù)完成后，小車會回到緩沖區(qū)中等待下一個任務(wù)的到來。

2.2　多任務(wù)場景動態(tài)隊列網(wǎng)絡(luò)的合并

所有等級的外部任務(wù)到達(dá)系統(tǒng)的第一個節(jié)點為節(jié)點j的總概率可表示為：

(2)

(3)

從節(jié)點i流向節(jié)點j的任務(wù)流量為：

(4)

從節(jié)點i離開網(wǎng)絡(luò)的流量為：

(5)

由式(3)和式(4)可得到整體路徑矩陣為：

(6)

各節(jié)點服務(wù)時間的平均值和變異系數(shù)值：

(7)

(8)

i,j=1,2,…,n

圖2為合并后的系統(tǒng)多任務(wù)綜合排隊網(wǎng)絡(luò)模型，由圖2可以看出,任務(wù)有兩種離開對列的方式：從LQ離開或從VQ2離開。取任務(wù)可從LQ后離開系統(tǒng)，存任務(wù)可從VQ2后離開系統(tǒng)。

圖2　AVS/RS綜合排隊網(wǎng)絡(luò)

2.3　運(yùn)行時間的計算

每個場景中RGV在每個階段的路徑及所需時間也不同。例如，若某任務(wù)場景中，小車不需要使用升降電梯，則小車將跳過LQ；若小車在I/O節(jié)點，則小車將不會訪問VQ1；若執(zhí)行取任務(wù)的小車與目標(biāo)貨位在同一層，則直接到達(dá)VQ2。VQ1和VQ2的運(yùn)行距離是沿x、y軸兩個方向進(jìn)行計算，小車沿x軸表示在貨架之間運(yùn)動，小車沿y軸表示在貨位之間運(yùn)動。因此，整體運(yùn)行時間可由全部運(yùn)行距離/小車速度得到。同時，也要對小車和電梯的加速、減速和轉(zhuǎn)向遲延時間進(jìn)行考慮。運(yùn)行時間的計算分為4個部分。

① 小車從當(dāng)前位置至電梯所在節(jié)點(VQ1)：由于小車可能在任何一個貨位，因此需要計算AB個場景的運(yùn)行時間。

② 電梯從所在層運(yùn)行至小車所在層(LQ)：電梯的位置可以在任意一層，因此需要計算出T(T-1)種可能的電梯運(yùn)行時間。

③ 電梯搭載裝載貨物的小車運(yùn)行至目標(biāo)層(LQ)：同樣，小車有(T-1)種可能從任一層到達(dá)目標(biāo)層，將裝載貨物的時間計入運(yùn)行時間。

④ 小車出電梯運(yùn)行至目標(biāo)貨位所在節(jié)點并卸載貨物(VQ2)：同樣，需要計算出AB種可能的運(yùn)行時間，同樣將卸載貨物的時間計入運(yùn)行時間。

將②和③中的值相加可得出LQ的值，3種服務(wù)器的訪問順序為VQ1-LQ-VQ2。不同的任務(wù)訪問服務(wù)器的次數(shù)也有差別，因此對于整個系統(tǒng)的分析需要根據(jù)式(7)和式(8)將任務(wù)各環(huán)節(jié)的消耗時間進(jìn)行合并。

3 AVS/RS任務(wù)排隊模型的求解及分析

本文運(yùn)用改進(jìn)的聚合法[14]對該系統(tǒng)網(wǎng)絡(luò)模型進(jìn)行求解，需要經(jīng)歷4個步驟。

① 將DQN模型轉(zhuǎn)化成CQN模型，將同步站點設(shè)為第一個站點，任務(wù)在此等待小車。

② 將同步站以外的所有站點視為一個CQN模型，計算出任務(wù)的相關(guān)吞吐率。

③ 用步驟②計算得到的任務(wù)相關(guān)指數(shù)服務(wù)器代替同步站點。

④ 考慮同步站點的隔離并通過求解M/M/1模型[15]，計算得出外部隊列數(shù)量的平均值。

由于模型中每個節(jié)點存在多個并行的服務(wù)器，因此本文采用基于λ(n)/Ek/m(m為任務(wù)數(shù))的CQN擴(kuò)展模型分析法。

① 任務(wù)的相關(guān)到達(dá)率：假設(shè)任務(wù)到達(dá)每一個節(jié)點的概率等于其離開此節(jié)點的概率，則節(jié)點j的任務(wù)到達(dá)(離開)率λj(n)可根據(jù)式(9)進(jìn)行迭代[13]，得到以下計算公式：

(9)

式中:θj(n)為當(dāng)節(jié)點j中含有n個任務(wù)時的服務(wù)率；Pj(n)為整個網(wǎng)絡(luò)中含有N個任務(wù)時n個任務(wù)到達(dá)節(jié)點j的概率。

(10)

對于Erlang-k階段型分布，任務(wù)從第一階段進(jìn)入到下一階段的概率總是保持不變的。由于每個任務(wù)在每個階段所消耗的時間都服從指數(shù)分布，因此，每個階段的任務(wù)到達(dá)率相同。

③ 系統(tǒng)性能指標(biāo)計算如下。

各節(jié)點(站點)的吞吐率為：

(11)

各節(jié)點(站點)中的平均任務(wù)數(shù)量為：

(12)

則各節(jié)點(站點)中任務(wù)的平均消耗時間為：

(13)

整個網(wǎng)絡(luò)的吞吐率為：

(14)

式中:ej為單個任務(wù)訪問節(jié)點j的平均次數(shù)。

4實例應(yīng)用與分析

本節(jié)以某省級電力公司電能計量設(shè)備檢定中心智能倉庫為實例來驗證本文提出的分析算法。該系統(tǒng)參數(shù)為：RGV數(shù)量V=12臺，升降電梯數(shù)量L=8部，貨架長度Lx=12m，高度Ly=11.5m；貨架數(shù)量A=24排，均為雙排貨架，每排層數(shù)T=23，單層每面貨位數(shù)B=13，共43 056個貨位；單元貨位高度h=0.5m，寬度w=0.8m。RGV的水平速度Vv=2m/s，升降機(jī)的速度VL=2m/s。λS為存任務(wù)的到達(dá)率，λR為取任務(wù)的到達(dá)率。

運(yùn)用軟件ARENA12.0對第三節(jié)提出的SCQN模型求解步驟和系統(tǒng)分析方法進(jìn)行仿真驗證，得到實例系統(tǒng)的性能參數(shù)如表1和表2所示。通過改變存任務(wù)和取任務(wù)的到達(dá)率λS和λR來對不同小車和升降機(jī)數(shù)量的配置組合進(jìn)行分析比較。

表2中，M為每小時任務(wù)數(shù)，n1~n3為各站點的任務(wù)數(shù)。

由第三節(jié)可知，本系統(tǒng)的排隊網(wǎng)絡(luò)模型轉(zhuǎn)化成了一個不包含同步站點的CQN模型，因此共含有3個工作站點，表1為仿真得到的3個站點的性能參數(shù)。

表1　系統(tǒng)性能參數(shù)a

表2　系統(tǒng)性能參數(shù)b

表3~表6為本文滿足存取任務(wù)每小時到達(dá)率相等的前提下，即：λS=λR(λS、λR分別為存任務(wù)和取任務(wù)大到達(dá)率)，在3種不同任務(wù)到達(dá)率的情況下按照本文提出算法得到的4個最佳V-L組合的系統(tǒng)性能分析結(jié)果。其中，Lex為電梯外部對列平均長度，Ln為網(wǎng)絡(luò)中任務(wù)(小車)的平均數(shù)量(包括正在等待服務(wù))，Lv為在小車緩沖區(qū)中的小車平均數(shù)量，Ln/(Ln+Lv)為小車的平均利用率，Wex為電梯外部隊列的平均等待時間，UL為電梯的平均使用效率。

表3　V=11，L=7時的系統(tǒng)效率

表4　V=11，L=6時的系統(tǒng)效率

表5　V=10，L=7時的系統(tǒng)效率

表6　V=10，L=6時的系統(tǒng)效率

由以上表格可以看出，當(dāng)λS+λR=200時，V=10、L=6組合的隊列長度要小于其他3種組合，電梯外部隊列的等待時間最短，且小車與電梯的平均利用率同為最高，說明在此情況下，該種組合為系統(tǒng)的最優(yōu)運(yùn)行方式。同理，當(dāng)λS+λR=250時，系統(tǒng)各項性能指標(biāo)均最優(yōu)，應(yīng)當(dāng)選取V=11、L=6組合作為其運(yùn)行方式。對于組合V=11、L=7，雖然在此任務(wù)到達(dá)率區(qū)間，表面上看小車數(shù)量的增加會加快任務(wù)的進(jìn)度，但是由于等待時間的加長會使任務(wù)的完成時間變得相對更長一些，此時小車與電梯的平均使用率均為最低，從而降低了整個系統(tǒng)的利用率，這就說明在此組合下系統(tǒng)的成本較高且小車與電梯在相當(dāng)長的一段時間處于閑置狀態(tài)。因此，要選擇小車平均利用率較高的組合作為系統(tǒng)的運(yùn)行方式。

綜上所述，本文模型可以根據(jù)系統(tǒng)的預(yù)期吞吐量為系統(tǒng)的前期設(shè)計提供方案，同時在系統(tǒng)實際運(yùn)行時，系統(tǒng)管理者可以根據(jù)不同的任務(wù)量(到達(dá)率)來調(diào)整系統(tǒng)的運(yùn)行方式，即：小車和升降電梯的數(shù)量組合，從而為系統(tǒng)的使用率最大化和成本最小化提供決策支持。

5結(jié)束語

針對AVS/RS系統(tǒng)的特點 ，本文提出了一個基于半封閉動態(tài)排隊網(wǎng)絡(luò)的分析與決策模型。首先，對系統(tǒng)的構(gòu)架及運(yùn)行規(guī)則進(jìn)行描述與定義，并分析各任務(wù)場景的發(fā)生概率。其次，構(gòu)造了一個系統(tǒng)的排隊網(wǎng)絡(luò)模型，將多種任務(wù)排隊模型轉(zhuǎn)化為一個單級的排隊網(wǎng)絡(luò)(DQN)模型。然后，對該模型進(jìn)行求解，并對其性能進(jìn)行分析，得出系統(tǒng)的性能指標(biāo)。最后，以某省電力公司計量檢定中心的智能立庫為例，運(yùn)用本文提出的分析決策模型及算法對不同V-L組合下的系統(tǒng)效率進(jìn)行仿真分析。結(jié)果表明，本文方法能夠準(zhǔn)確地模擬制造過程和實際應(yīng)用當(dāng)中所遇到的問題，為系統(tǒng)的優(yōu)化設(shè)計及提高設(shè)備使用率、節(jié)約運(yùn)行成本提供決策支持。

參考文獻(xiàn)

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

[2] Fuku M,Mborg C J.An network queuing approach for evaluation of performance measures in autonomous vehicle storage and retrieval systems[J].European Journal of Operational Research,2009,193(1):152-167.

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

[4] Banu Y,Sunderesh S.An approximate solution for semi-open queuing network model of an autonomous vehicle storage and retrieval system[J].Transaction on Automation Science and Engineering,2013,10(1):205-215.

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

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

[7] Fuku M,Mborg C J.A network queueing approach for evaluation of performance measures in autonomous vehicle storage and retrieval systems[J].Operational Research,2009,193(13):203-205.

[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] Kuo P H,Krishnamurthy A,Malmborg C J.Performance modelling of autonomous vehicle storage and retrieval systems using class-based storage policies[J].Computer Applications in Technology,2008(31):238-248.

[10]Ekren B Y,Heragu S,Krishnamurthy A,et al.Simulation based experimental design to identify factors affecting performance of AVS/RS[J].Computer Engineering,2010(58):175-185.

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

[12]Ekren B Y,Heragu S S.Simulation based regression analysis for the rack configuration of an autonomous vehicle storage and Retrieval system[J].Production Research,2010(48):6257-6274.

[13]Wang Ling,Zhou Gang,Xu Ye,et al.Advances in the study on hybrid flow-shop scheduling[J].Control and Instrument in Chemical Industry,2011,38(1):1-8.

[14]Avi-Itzhak B,Heyman D P.Approximate queueing models for multiprogramming computer systems[J].Operational Research,2013(21):121-128.

[15]Dallery Y.Approximate analysis of general open queueing networks with restricted capacity[J].Performance Evaluation,2009(11):209-222.

中圖分類號：TP273

文獻(xiàn)標(biāo)志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201501005

修改稿收到日期：2014-06-17。