雙深度多層穿梭車倉儲系統并行作業及建模分析

占翔南，徐立云+，宓 宏，李愛平

(1.同濟大學 機械與能源工程學院，上海 201804；2.浙江衢州聯州致冷劑有限公司，浙江 衢州 324004)

0 引言

雙深度多層穿梭車系統是近年來出現的一種新型智能立體倉庫，依靠穿梭車完成水平作業，借助提升機完成垂直作業，從而實現貨物的出入庫作業，彌補了多層穿梭車系統中每個巷道只能由獨立的穿梭車進行服務以及存儲能力不足等缺點。然而，該系統也存在倒貨作業和系統響應時間長等現象，如何提高雙深度多層穿梭系統的作業效率是亟待解決的問題。

目前，國內外學者對立體倉庫的研究多以多層穿梭車系統為研究對象，主要研究方法包括確定性模型分析法和排隊模型分析法。確定性模型分析法可以根據作業順序準確計算單次任務的作業時間，MALMBORG[1]首次對多層穿梭車系統展開研究，采用連續Markov鏈的方法來計算系統的水平作業和垂直作業時間，以評估系統的響應時間；WANG等[2]針對自動小車存取系統(Autonomous Vehicle Storage/Retrieval System，AVS/RS)建立了作業時間序列優化模型，并將系統的調度問題轉化為裝配線并行作業問題，通過優化任務隊列減少穿梭車和提升機的等待時間來提高系統運行效率；楊瑋等[3]針對雙載式多層穿梭車倉儲系統復合作業路徑優化問題建立了作業時序數學模型，并采用混合植物繁殖算法進行求解與分析。排隊模型分析法考慮了排隊對系統性能的影響，可以更加準確地分析系統的性能指標，KUO等[4]將穿梭車服務流程和提升機服務流程分別建模為M/G/V隊列和G/G/L隊列，用于研究系統中的隨機存儲策略和結束點停留策略；ROY等[5]通過建立多層排隊網絡模型，并采用基于嵌入式Markov鏈的方法分析系統響應時間和資源利用率；CAI等[6]建立了多級半開環排隊網絡模型，并采用矩陣幾何法分析了AVS/RS系統的利用率和輸出效率，說明虛擬同步策略比物理同步策略更優。

然而，上述文獻在建模過程中均采用了順序作業方式，由于順序作業方式下穿梭車和提升機之間的等待時間會增加系統響應時間，為進一步減小系統響應時間，HU等[7]首次對并行作業方式進行研究，并采用確定性模型對分體式自動存儲系統(Split-Platform Autonomous Storage/Retrieval System, SP-AS/RS)的性能進行了分析，結果表明并行作業方式可以減小垂直平臺和水平平臺之間的等待時間；ZOU等[8]采用并行作業方式對AVS/RS系統進行分析，針對單個巷道建立了fork-join排隊網絡模型，比較了AVS/RS系統在并行作業方式和順序作業方式下的系統性能。以上研究表明，并行作業方式可以減小系統響應時間，提高作業效率。對于雙深度多層穿梭車系統，XU等[9]在順序作業方式下對雙深度多巷道存取系統建立了行程時間模型，分析了貨位占用率對系統輸出的影響，并給出了存在最佳貨位占用率的條件；LERHER[10]在順序作業方式下，對雙深度多層穿梭車系統在單命令周期和雙命令周期下進行了行程時間建模，但迄今為止，對雙深度多層穿梭車系統并行作業及建模分析尚未進行研究。

綜上所述，已有學者從多層穿梭車倉儲系統及其相關問題出發，對倉儲系統進行建模研究，并應用于工程優化問題，如倉儲系統作業效率優化問題、作業任務調度問題等，但仍存在以下不足：①作業效率優化問題中多以順序作業方式為研究基礎，缺乏對并行作業方式的研究和優化，從而影響倉儲系統的柔性；②針對單個巷道進行建模分析，并根據單個巷道的結果對倉儲系統整體進行評估，缺乏對倉儲系統整體的分析，若系統中出現跨巷道取貨作業，該方法則不能準確評估系統性能指標；③缺乏對倒貨作業的考慮，影響評估結果；④作業效率優化問題中，直接根據系統模型建立仿真模型進行驗證，需要的時間較長且缺乏理論基礎。

針對以上問題，本文以雙深度多層穿梭車倉儲系統為對象，考慮并行作業方式對作業效率的影響，先建立分離—聚合排隊網絡模型，然后考慮倒貨作業時間和取貨時間服從一般分布的特點，設計基于Coxian分布的近似分解算法進行求解。與根據單一巷道評估系統整體的方法相比，對倉儲系統整體進行建模分析能夠更準確地評估系統性能指標；另外，與仿真驗證相比，該方法能夠更快地評估系統性能指標且具有理論可行性。

1 問題描述

倉儲系統建模是根據倉儲系統配置和設備運行特點構建倉儲邏輯系統來描述真實倉儲系統[11]。倉儲系統建模問題的關鍵在于：①如何根據系統配置和運行特點準確地描述倉儲系統；②如何確定評價指標以保證模型的準確性和可靠性；③如何高效快速地對模型進行求解。同時，倉儲系統建模是研究作業效率優化問題的基礎，能夠進一步為倉儲系統作業調度和路徑規劃等問題提供指導。

目前，倉儲系統的評價指標主要包括地面面積利用率、系統吞吐能力、系統響應時間和設備利用率等，而雙深度多層穿梭車倉儲系統因具備空間利用率高、系統吞吐能力強、設備利用率高等優點而受到眾多企業的青睞。本文研究并行作業方式對雙深度多層穿梭車倉儲系統作業效率的影響，將系統響應時間、穿梭車和提升機利用率、平均等待時間和平均等待隊長作為性能評價指標。系統響應時間指單個取貨任務的完成時間，能夠評估系統在不同配置和取貨任務到達率下的吞吐量；穿梭車和提升機利用率用于評估系統設備的使用率，并可以據此找出系統瓶頸；平均等待時間和平均等待隊長用來評估取貨任務在系統外部的等待情況，可以據此確定系統的取貨任務到達率。

雙深度多層穿梭車倉儲系統主要由雙深度高密度存儲貨架、提升機、穿梭車、軌道和控制系統構成。其中，每層配置一臺穿梭車，用于貨物的水平運輸；系統配置若干個電梯且位于貨架的同一側，用于貨物的垂直運輸；當穿梭車處于空載狀態時可以在巷道和貨架內任意移動，當穿梭車處于滿裝狀態時只能在巷道內移動；在倉庫中央設置了貨物進出的緩存區，用于暫時存放貨物；穿梭車將貨物放置在緩存區，提升機將貨物從緩存區取走，提升機和穿梭車每次只能運輸一件貨物。雙深度多層穿梭車系統的示意圖如圖1所示。

雙深度多層穿梭車系統的并行作業方式指穿梭車與提升機可以同時朝目標層的緩存區移動，然后進行貨物交接，最后由穿梭車完成存貨任務或由提升機完成取貨任務。

在并行作業方式下，存貨任務操作流程如下：

(1)提升機先從停留點移動至系統的I/O位置，然后將貨物運送到目標層。當提升機到達目標層后，將貨物放至緩存區。在提升機運行的過程中，穿梭車也從其停留點移動至緩存區。

(2)如果提升機和穿梭車都已到達緩存區，則穿梭車裝載貨物；如果一方未到達緩存區，則先到者需要等待另一方。穿梭車裝載貨物后，將其運送至指定貨位，存貨任務結束。

取貨任務的操作流程如下：

(1)穿梭車從停留點移動至取貨貨位，然后運送貨物至緩存區。在穿梭車運行過程中，提升機將從其停留點移動至目標層。

(2)如果穿梭車和提升機均已到達緩存區，則提升機裝載貨物；如果一方未到達緩存區，則先到者需要等待另一方。提升機裝載貨物后，將其運送至系統I/O位置。

在以上描述中，將存取任務的操作(1)中穿梭車的作業稱為水平作業，提升機的作業稱為垂直作業，將操作(2)稱為剩余作業。在并行作業方式下，穿梭車執行水平作業的同時提升機執行垂直作業。最后由穿梭車執行存貨任務的剩余作業，由提升機執行取貨任務的剩余作業。本文假設穿梭車的可用狀態由緩存區的狀態決定，當緩存區被占用時，穿梭車不可執行取貨任務。取貨任務流程如圖2所示。

當系統完成存取作業任務分配后，如何使穿梭車和提升機配合高效完成作業任務，是雙深度多層穿梭車倉儲系統作業效率優化的目的。因此，需要對穿梭車和提升機并行作業方式進行建模和求解，而建立合理的穿梭車和提升機并行作業模型是作業效率優化的關鍵。

2 系統建模

為建立合理正確的穿梭車和提升機并行作業模型，需要對模型的主要假設條件和參數符號進行說明?？紤]單元負載式雙深度多層穿梭車倉儲系統，以托盤為存取單元，貨物從同一出口進出，I/O位置位于貨架的正下方，每個貨位只能單獨存放一種貨物，貨位的尺寸相同。同時，為了研究方便且不失一般性，進行如下假設：

(1)穿梭車和提升機服從先到先服務(First Come First Service, FCFS)原則。

(2)本文只考慮取貨任務，該假設基于如下兩點：①取貨任務是倉儲系統中關鍵的操作，它決定了倉儲系統的服務水平；②存貨任務和取貨任務的操作步驟相同，如果本文模型可以較好地模擬取貨任務，則也適用于存貨任務。

(3)采用隨機存儲策略，在該策略下，每個空貨位對貨物存儲具有相同的概率。

(4)提升機和穿梭車均服從結束點(Point of Service Completion, POSC)停留策略，即它們會停在任務結束的地方。本文以取貨作業為例，提升機總停留在系統的I/O點，穿梭車總停留在緩存區旁。

本文涉及的符號參數如表1所示。

表1 主要符號參數

續表1

2.1 分離—聚合排隊網絡模型

定義位于第t層的取貨任務為第t(t=1,2,…,T)類顧客，根據假設(3)可知，取貨貨物位于第t層的概率P(t)=1/T，第t層的顧客到達率λrt=λr/T。將存儲貨位編號為Mac(a=1,2,…,A，c=1,2,…,C)，例如貨位編號M25表示該貨位位于第2巷道第5列，Mac的概率分布為P(Mac)=1/(A·C)。根據本文假設的POSC停留策略，穿梭車空閑時一直停在緩存區，為獲得Mac處的貨物，穿梭車的行走距離

(1)

式中：x1為穿梭車行走距離；a為巷道編號；c為貨架列編號。

如前所述，雙深度存儲貨架存在倒貨作業現象，如圖3所示，當穿梭車需要取走位于第2列的目標貨物，而第1列貨位被占用時，需要先將第1列貨物取出并放置在倒貨貨位，再將目標貨物取出，在此過程中，穿梭車移動的距離稱為倒貨距離。根據文獻[10]可知，若系統中的貨位占用率為α，則出現倒貨作業的概率為(2α-1)，穿梭車倒貨距離

(2)

根據上述分析可知，水平作業的服務時間

Ts(Mac)=x1/Vs+(2α-1)·x2/Vs+εs。

(3)

因為提升機在空閑狀態時位于系統I/O位置，提升機完成垂直作業需要行走的垂直距離為(t-1)H，所以垂直作業的服務時間

Tl1(t)=(t-1)H/Vl。

(4)

提升機服從POSC停留策略，剩余作業的服務時間

Tl2(t)=Tl1(t)+2εl。

(5)

基于模型假設，并行作業方式下雙深度多層穿梭車倉儲系統的運行過程可以等效為一個分離—聚合排隊網絡模型，如圖4所示。

在該分離—聚合排隊網絡模型中，取貨任務服從泊松分布，取貨任務的到達率為λr。根據目標貨物的所在層將取貨任務分為T類，對應的到達率分別為λr1,λr2,…,λrT，μs1,μs2,…,μsT分別表示各層穿梭車的水平作業服務速率，μl1,μl2分別表示提升機在原始位置和聚合點的垂直作業服務速率。在分離點處，取貨任務同時對提升機和穿梭車發出指令，然后將一個取貨任務分為水平作業和垂直作業。水平作業由第t層穿梭車完成，完成后穿梭車在水平隊列等待；垂直作業由提升機完成，完成后提升機在垂直隊列等待。當水平作業和垂直作業都完成后，它們離開各自的隊列，在聚合點處重新聚合成一個取貨任務，然后移動到μl2服務點，提升機在該點進行剩余作業，即裝載貨物并運送至系統I/O位置。因為完成剩余作業不需要等待提升機，所以可以將μl2模擬為擁有無限服務能力。

穿梭車和提升機的作業時間均服從一般分布[12]，因此該排隊網絡模型屬于非模塊形式(non-product form)排隊網絡，無法直接求解。本文設計了基于Coxian分布的近似分解算法來求解該排隊網絡模型，算法分兩步：

(1)計算分離—聚合點的服務速率 構建一個包含分離—聚合點的閉環排隊網絡模型，將該模型中的服務點用Coxian分布近似替代，計算分離—聚合點的吞吐率，從而得到該點的服務速率。

(2)計算分離—聚合排隊網絡模型的系統運行性能指標 構建一個開環排隊網絡，將分離—聚合點用單個服務點替代，運用最大熵值法(Maximum Entropy Method, MEM)對開環排隊網絡模型求解，最終得到分離—聚合排隊網絡模型的系統響應時間、穿梭車利用率和平均等待隊長等性能指標。

2.2 分離—聚合點的閉環排隊網絡

構建如圖5所示的閉環排隊網絡模型，假設該模型中有Z個取貨任務，每個取貨任務在第t層執行的概率為1/T。令Ls為水平作業中排隊等待的顧客數，Ll為垂直作業中排隊等待的顧客數，則該閉環排隊網絡的狀態變量

sk=(Ls,Ll),k=Ll(m+1)+Ls，

其狀態空間為Ll+Ls

水平作業和垂直作業聚合包括兩種情況：①當Ls>1時，完成一個垂直作業，即提升機到達目標層，該過程的服務速率為μl1；②當Ll>1時，完成一個水平作業，穿梭車到達緩存區，該過程的服務速率為μs?；谝陨蟽煞N情況，分離—聚合點模型閉環排隊網絡的吞吐率

(6)

式中π(sk)表示sk的狀態概率。

(7)

(8)

(9)

在該排隊網絡模型中，用μst表示第t層穿梭車的水平作業服務速率，根據假設(3)可知

根據式(6)計算λf(Z)需要計算閉環排隊網絡的狀態概率π(sk)。首先，將μv服務點和μl1服務點分別用(α,T)和(β,S)的Coxian分布替換，其中α=[1 0 … 0]1×p，β=[1 0 … 0]1×q，p,q分別表示μv和μl1的Coxian分布階數。狀態轉移矩陣T和S與吸收矩陣T0和S0的詳細推導過程參見文獻[11]。將閉環排隊網絡的狀態變量轉化為(sk,i,j)，i,j(i=0,1,…,p,j=0,1,…,q)分別為穿梭車和提升機在服務過程中所處的狀態。

定義穩態概率分布π(t)=[π0,π1,π2,…]，Ql=0的所有狀態概率向量π0=[π(s0),π(s1),…,π(sm)]，Ql=1的所有狀態概率向量π1=[π(sm+1),π(sm+2),…,π(s2m)]，狀態變量sk的轉移矩陣表示為

(10)

式中：B0表示π0狀態轉移至π0狀態的轉移矩陣，

(11)

IT為p×p的單位矩陣，IS為q×q的單位矩陣，⊕表示克羅內克和，?表示克羅內克積，

C0表示π0狀態轉移至π1狀態的轉移矩陣，

C0=

(12)

A0表示π1狀態轉移至π0狀態的轉移矩陣，

A0=

(13)

B表示π1狀態轉移至π1狀態的轉移矩陣，

B=

(14)

C表示π1狀態轉移至π2狀態的轉移矩陣，

C=

(15)

A表示π2狀態轉移至π1狀態的轉移矩陣，

A=

(16)

在穩定狀態下，該排隊網絡滿足

π(t)Q=0，

(17)

由歸一化條件可知

π(t)e=1。

(18)

式中e為單位向量。

根據文獻[6]，狀態概率向量πi滿足

πi+1=πiR,i≥1。

(19)

式中R為速率矩陣。聯立式(17)～式(19)得到狀態轉移概率π(sk)，將π(sk)代入式(6)，得到分離—聚合點的吞吐率λf(Z)。

2.3 基于分離—聚合點的開環排隊網絡模型

通過式(6)求得分離—聚合點的吞吐率，將其用單個服務點代替，并定義μFES=λf(Z)，得到如圖6所示的開環排隊網絡模型。

圖中服務點1的服務速率μFES=λf(Z)。由于μFES與任務數Z相關，且服務點2的服務速率服從一般分布，根據模型判別條件可得該開環排隊網絡模型是一個非模塊形式(non-product-form)，可采用最大熵值法對該開環排隊網絡進行求解[13]。首先狀態概率

π(k1,k2)=π(k1)×π(k2)。

(20)

式中：k1,k2分別表示服務點1和服務點2顧客的數量；π(k1),π(k2)表示服務點1和服務點2的邊際狀態概率。

服務點1的邊際狀態概率為：

(21)

(22)

服務點2的邊際狀態概率為

(23)

(24)

(25)

(26)

(27)

在求得服務點1和服務點2的邊際狀態概率后，由式(20)計算開環排隊網絡的狀態概率。由此可得，服務點1的平均服務速率

(28)

服務點1和服務點2的平均顧客數分別為

(29)

(30)

因此系統響應時間

(31)

取貨任務在外部隊列的平均等待時間

(32)

外部等待隊列長度

Le=λrWr；

(33)

穿梭車利用率和提升機利用率分別為

(34)

ρl=1-π1(0)×π2(0)。

(35)

系統響應時間Tr、外部隊列的平均等待隊長Le、提升機利用率ρl、穿梭車利用率ρs和外部隊列的平均等待時間Wr為表征作業效率的性能指標，用于評價雙深度多層穿梭車倉儲系統的作業效率。

3 案例分析

3.1 案例驗證

為驗證分離—聚合排隊網絡模型的有效性，選取鄭州千味央廚的雙深度多層穿梭車倉儲系統一個月的發貨數據進行分析。統計數據可知，該倉儲系統貨品種類為160種，2017年10月的發貨總量為96 000托，日均發貨量為3 200托，日均訂單數量為173個，日均工作時間為15 h，其余數據如表2所示。鄭州千味央廚倉儲系統在2017年10月份發貨數據如表3所示，發貨周期為30 d，發貨單據號為5 190個，發貨總量為2 054 596件。

表2 千味央廚單月發貨數據信息

表3 千味央廚10月份發貨數據

本文采用4種不同配置的雙深度多層穿梭車倉儲系統進一步驗證分離—聚合排隊網絡模型的合理性。如表4所示，編號分別為1#，2#，3#，4#，其中前兩種代表小型倉儲系統，后兩種代表大型倉儲系統，每層配置1臺穿梭車，巷道數均為6條，提升機均為2臺，其余倉儲系統的主要輸入參數設置如表5所示。對每種不同的系統配置，采用6種不同的輸入，即取貨任務到達率λr(單位：托/h)分別為150，200，250，300，350，400。

表4 4種不同的倉儲系統配置方案

表5 倉儲系統主要輸入參數設置

通過表2和表3的原始數據計算可得，該倉儲系統原來的取貨任務到達率約為214托/h，采用本文方法后該倉儲系統的最大取貨任務到達率約為350托/h，提升系統作業效率約63.5%，證明了該方法的有效性。

為了消除初始偏差，仿真模型從第100以后取值，每個仿真方案重復運行100次，每次仿真時間為1 000 h，以達到在95%的置信水平，仿真結果的分布半長小于其均值的2%，其結果如表6所示。對Tr，Le，ρl，ρs，Wr5個系統評價指標進行分析比較，仿真結果、理論結果和誤差分別用S1，S2，η表示，如表7所示，其中

(36)

表7 仿真結果與理論結果

續表7

表6 仿真結果的分布半長

由表7得到如下結論：

(1)在不同系統配置和不同取貨任務到達率下，系統響應時間的誤差為0.72%～4.47%，平均等待隊長的誤差為4.38%～11.7%，提升機利用率的誤差為1.32%～5.56%，穿梭車利用率的誤差為3.15%～10.01%，平均等待時間的誤差為1.87%～9.65%。結果表明，分離—聚合排隊網絡模型可以準確、有效地計算雙深度多層穿梭車倉儲系統并行作業下的性能指標。

(2)在取貨任務到達率相同的條件下，隨著系統層數的增加，平均等待時間、平均等待隊長、系統響應時間、提升機利用率和穿梭車利用率均增加，這是由于系統層數增加，相應的水平作業和垂直作業時間變長，平均等待時間、平均等待隊長和系統的響應時間隨之變長。

(3)在同種系統配置下，隨著取貨任務到達率的增加，平均等待時間、平均等待隊長、系統響應時間、提升機利用率和穿梭車利用率均增加。

3.2 作業方式對比

為進一步驗證雙深度多層穿梭車倉儲系統并行作業方式的合理性，選取鄭州千味央廚的3#雙深度多層穿梭車倉儲系統進行分析。取貨任務到達率λr從150托/h以步長為20增加至350托/h，系統響應時間的對比結果如圖7所示。

根據圖7結果可知，在不同的取貨任務到達率下，雙深度多層穿梭車倉儲系統并行作業均優于順序作業方式；隨著取貨任務到達率的增加，系統響應時間逐漸增大，并列作業方式的優勢逐漸明顯。當取貨任務到達率λr=150托/h時，并行作業方式相對順序作業方式的系統響應時間提升了9.48%；當取貨任務到達率λr=350托/h時，并行作業方式相對順序作業方式的系統響應時間提升了21.95%，從而證明該系統下采用并行作業方式能夠更好地減小系統響應時間，提升系統作業效率。

并行作業方式下的系統運行總時間是提升機和穿梭車運行時間的最大值，順序作業方式下的系統運行總時間是提升機和穿梭車運行時間的總和。采用并行作業方式雖然增加了提升機的作業負擔，以及作業任務對提升機的等待時間，但是提升機能力充足，所減少的總運行時間大于所增加的等待時間，因此并行作業方式可以減小系統響應時間，提升系統作業效率。

上述研究結果表明，分離—聚合排隊網絡模型能夠快速、有效地分析系統運行性能指標；并行作業方式能夠減小系統響應時間，提高系統柔性。另外，倉儲系統可根據性能指標調整穿梭車和提升機的數量，從而節約系統運行成本，該方法可以為并行作業方式下的作業任務調度和路徑優化提供理論依據。

4 結束語

本文針對雙深度多層穿梭車倉儲系統并行作業流程提出分離—聚合排隊網絡模型，并通過分離—聚合點的閉環排隊網絡模型和基于分離—聚合點的開環排隊網絡模型分別對分離—聚合點的服務速率和系統運行指標進行求解。最后，對4種不同配置的倉儲系統進行分析，結果表明，分離—聚合排隊網絡模型可以準確、有效地反映雙深度多層穿梭車倉儲系統并行作業下的各項性能指標，與傳統順序作業方式相比并行作業可以減小系統響應時間9.48%～21.95%，從而較大幅度地提高系統作業效率。為進一步提高倉儲系統吞吐能力，未來將對貨物分類存儲策略和基于周轉率存儲策略進行研究。