AVS/RS系統動態分析及決策模型

Dynamic Analysis and Decision Making Model of AVS/RS System

方彥軍　唐　猛

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

AVS/RS系統動態分析及決策模型

Dynamic Analysis and Decision Making Model of AVS/RS System

方彥軍唐猛

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

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

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

關鍵詞：AVS/RS動態排隊網絡聚合法分析決策

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引言

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

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

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

1AVS/RS系統的描述

1.1　系統的描述

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

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

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

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

② 存取任務的到達時間是均等的，都服從泊松分布；小車進出電梯的時間可忽略不計。

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

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

1.2　任務場景發生概率

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

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

Pc=P1P2P3

(1)

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

2AVS/RS系統的動態排隊網絡模型

2.1　單任務動態排隊網絡模型

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

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

圖1　單任務的動態排隊網絡模型

當一臺自動小車空閑時，則一個將要到達的任務就會立即進入系統的隊列當中，并跟該小車進行綁定；否則該任務就需要在任務隊列中等待，直到有空閑小車出現為止。當任務完成后，小車會回到緩沖區中等待下一個任務的到來。

2.2　多任務場景動態隊列網絡的合并

所有等級的外部任務到達系統的第一個節點為節點j的總概率可表示為：

(2)

(3)

從節點i流向節點j的任務流量為：

(4)

從節點i離開網絡的流量為：

(5)

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

(6)

各節點服務時間的平均值和變異系數值：

(7)

(8)

i,j=1,2,…,n

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

圖2　AVS/RS綜合排隊網絡

2.3　運行時間的計算

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

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

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

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

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

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

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

本文運用改進的聚合法[14]對該系統網絡模型進行求解，需要經歷4個步驟。

① 將DQN模型轉化成CQN模型，將同步站點設為第一個站點，任務在此等待小車。

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

③ 用步驟②計算得到的任務相關指數服務器代替同步站點。

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

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

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

(9)

式中:θj(n)為當節點j中含有n個任務時的服務率；Pj(n)為整個網絡中含有N個任務時n個任務到達節點j的概率。

(10)

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

③ 系統性能指標計算如下。

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

(11)

各節點(站點)中的平均任務數量為：

(12)

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

(13)

整個網絡的吞吐率為：

(14)

式中:ej為單個任務訪問節點j的平均次數。

4實例應用與分析

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

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

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

由第三節可知，本系統的排隊網絡模型轉化成了一個不包含同步站點的CQN模型，因此共含有3個工作站點，表1為仿真得到的3個站點的性能參數。

表1　系統性能參數a

表2　系統性能參數b

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

表3　V=11，L=7時的系統效率

表4　V=11，L=6時的系統效率

表5　V=10，L=7時的系統效率

表6　V=10，L=6時的系統效率

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

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

5結束語

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

參考文獻

[1] 羅鍵，吳長慶，李波，等.基于改進量子微粒群的軌道引導小車系統建模與優化[J].計算機集成制造系統，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] 吳長慶，何善君，羅鍵,等.自動小車存取系統中軌道引導小車環路死鎖控制的研究[J].計算機集成制造系統,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

文獻標志碼：A

DOI:10.16086/j.cnki.issn1000-0380.201501005

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