面向存儲空間受限的分揀系統內多類型存儲單元數量配置

李 靖，陳慶新，毛 寧

(廣東工業大學 廣東省計算機集成制造重點實驗室，廣東 廣州 510006)

為提高大規模板式家具的生產加工效率，往往將多個訂單組批生產，即一個生產批次中包含若干個訂單，每個訂單又包含了不同尺寸類型不同數量的板材。在訂單組批生產加工完成后，需要按訂單分揀板材，再打包交付客戶[1-2]。這就意味著，需要分揀系統來改變板材的生產順序和打包順序，為此需要在分揀系統中設置一定數量的板材存儲單元。由于存儲單元是圍繞著定點機械手設置的，因機械手的活動范圍有限，導致總體存儲空間受到限制。如果這些存儲單元的尺寸相同，會浪費存儲空間(小尺寸的板材占用大尺寸的存儲空間)，使得有限空間內存儲單元的數量較少，無法滿足生產需求。另一方面，鑒于生產批次中訂單情況的不確定性，設置不同數量不同尺寸的存儲單元，雖然能夠有效地利用存儲空間，但卻存在著較大尺寸的板材偶爾會出現無法存放的風險。針對這一問題，本文考慮生產批次訂單情況的不確定性，研究在一定風險(大尺寸板材無法存儲的概率) 約束條件下，優化多種尺寸存儲單元的數量配置，提高分揀系統有限存儲空間的利用率。

國內外關于分揀系統內存儲單元尺寸和數量配置的研究中，鮮有關于多尺寸種類存儲單元的文獻。關于單一類型存儲單元的數量配置問題，文獻[3-8]研究單一類型貨位區域分類對需求存儲空間的影響，認為更多的貨位區域分類降低貨位共享性，導致總的存儲單元數量增加，所需的總的存儲空間增加。賴明勇等[9]研究高層貨架最佳貨格的整數規劃模型，使得建設費用與運行費用之和最低。關于單一類型存儲單元的尺寸和貨架布局問題，馬文凱等[10]采用優化算法得到最優的系統配置(層、排、列) 使得系統成本最少。張歡歡[11]探討自動化倉庫規劃設計中貨架最佳高度和長度，給出了貨位尺寸計算模型和倉庫的布局方法。Lee等[12]提出可以根據貨物的體積對貨架標準貨位尺寸進行相應改變的方法，以提高貨架的空間使用效率。

上述文獻針對立體倉庫的存儲單元數量配置問題作了一定研究，但均基于單一尺寸類型貨位，而單一類型貨位對于多尺寸貨物會造成存儲空間較大的浪費，導致貨位數量不足，無法滿足實際需求。為此，本文構建一種多尺寸類型存儲單元的數量配置模型，為有限存儲空間下貨位數量配置提供決策指導。

1 模型構建

1.1 問題描述

版式家具分揀系統由多個機械手分揀單元構成。如圖1所示，多個訂單多種尺寸的板材經傳送帶無序到達分揀單元，機械手從傳送帶上抓取板材，放入貨架。當貨架內某類訂單板材完整時，則將這個訂單內板材從貨架中取出，實現貨物按訂單的有序出庫。但因機械手的活動范圍有限，導致總體存儲空間受到限制。因此，為了提高存儲空間的利用率，貨架內多尺寸類存儲單元的數量配置成為值得研究的問題。

圖1 單批次貨物進出分揀系統示意圖Figure 1 Schematic diagram of a single batch of goods in and out of the sorting system

模型假設如下。

1) 貨物的幾何形狀為長方體，總的貨物類數服從隨機分布，各類貨物的長、寬、高服從隨機分布，單個貨位存放一個貨物。貨架內貨位的幾何形狀也為長方體。

2) 單個批次有隨機數量的訂單，單個訂單內某類尺寸貨物的數量服從隨機整數分布。

3) 同類貨物在不同訂單的數量服從獨立同分布，單個訂單內不同類貨物的數量相互獨立。

4) 貨物入庫順序：批次內貨物按隨機順序逐個入庫，入庫時間間隔服從指數分布x～E(λ)，上一個批次未開始出庫之前，下一個批次不入庫(即貨架內最多不超過兩個批次) 。

5) 貨物出庫順序與觸發機制：貨架內某個訂單到齊后，訂單內貨物按隨機順序逐個出庫。出庫時間間隔服從同一指數分布x～E(λ)。

6) 入庫貨位分配策略：在貨架當前可供存放且其中體積最小的空余貨位中隨機分配。

7) 貨物在出入庫過程中，認為線體傳輸能力與機械手搬運能力不是瓶頸，足夠滿足以上假設的貨物出入庫的時間間隔。

8) 本文不考慮多尺寸類貨位構成的貨架布局問題。

1.2 模型分析

1.2.1 變量與符號

變量與符號如表1所示。

1.2.2 基于正態分布的數量配置

本文基于正態分布給出了各類存儲單元數量配置的初步計算結果，并引入“出現較大尺寸貨物無法存儲的概率不超過5%的風險”(存儲單元數量配置滿足不爆倉率95%～100%之間) 的概念。入庫貨位分配策略為：在當前可供存放且其中體積最小的空余貨位中隨機分配。假設各類貨位數量無限大，即不考慮貨位類之間借用的情況下，各類存儲單元總是會優先存儲某幾類貨物。所以計算任意幾類尺寸類型貨物數量之和分布是配置各類存儲單元數量的先決條件。因為第i類尺寸類型貨物在第k個訂單的數量Xik服從獨立同分布，由中心極限定理，則一定數量訂單組成的單個批次內任意幾類尺寸類型貨物數量和近似服從正態分布，期望和方差的理論值分別為

以上計算得到靜止狀態下單個批次內任意幾類貨物數量之和分布。然而，并不適用于出入庫時任意幾類貨物數量之和分布。若分揀系統內最多不允許超過b個 完整批次，當批次數大于b時，暫停貨物入庫過程(如果對入庫過程不加控制，由于出入庫相鄰貨物時間服從同一指數分布，即出入庫速度相等，而入庫過程是連續的，出庫過程是非連續的，必然會造成分揀系統內貨物數量隨著時間持續增長) 。因有單個批次貨物數量95%概率小于E(X)+1.96D(X)，則在所有批次貨物數量均為E(X)+1.96D(X)的連續出入庫時，任意幾類貨物數量之和近似實際過程中的上限。在相鄰兩個批次的連續出入庫過程中，后一個批次的入庫完成時間段內，前一個批次的出庫數量服從u=E(X)+1.96D(X)的泊松分布(相鄰貨物時間間隔服從指數分布，則單位時間貨物數量服從泊松分布) 。當u達到一定值時，即近似服從N(u,u)正態分布，前一個批次貨物出庫數量大于任意數字a的單次概率計算如下。

當分揀系統內最多不允許超過b個完整批次時，給定任一數字c，則

由式(4) 可計算出入庫過程中任意幾類貨物峰值的概率分布。當b=2時，c=u2+1.96u20.5，即在貨物出入庫過程中，當貨架內最多不超過兩個批次時，

即各類存儲單元數量配置為E(X)+1.96D(X)+1.96(E(X)+1.96D(X))0.5時，各類貨位的數量配置大于所存儲某幾類貨物峰值的概率介于95%到100%之間，確保出現較大尺寸貨物無法存儲的風險低于5%。

1.2.3 考慮緩存下的數量配置減少

以上計算得到各類貨位的數量配置在95%的概率上大于所存儲某幾類貨物的峰值。然而由于不同存儲單元類內的貨物峰值出現時間不一，不同存儲單元類之間在入庫過程中可以彼此借用、緩存，以減少數量配置。當一類貨位的長、寬、高均小于另一類貨位的長、寬、高時，稱這兩類貨位之間存在包容關系。在貨物出入庫過程中，當小貨位數量不足時，大貨位可以借用給小貨位存放貨物，大貨位可稱為小貨位的緩存貨位。依據緩存貨位的體積大小比較可得到各類貨位的各級緩存貨位，某類貨位的各級緩存貨位兩兩之間并不一定具有包容關系。假設配置了10類貨位，各類貨位的緩存關系如圖2所示，第10類貨位是所有貨位類的最高級緩存貨位類?？紤]緩存后，對只出不進的存儲單元類的集合，有數量配置的減少，對只進不出的存儲單元類的集合，有數量配置的最低要求。實現步驟如下。

圖2 各類存儲單元緩存關系圖Figure 2 Buffer relationship diagram of various storage units

步驟1得到矩陣HWJS。當第i類貨物可被第j類存儲單元存儲時，xij=1，否則xij=0。jmax=imax。

步驟2得到矩陣HWJS′。當HWJS的 行數不變，取部分列數。

步驟3得到矩陣HWJS′′。保留HWJS′矩陣各行等于1的列中體積最小存儲單元的值，此行對應的其余列的值全部為0。

步驟4得到矩陣HWJS′′′。對HWJS′矩陣各行等于1的列中，按存儲單元體積從小到大排序。

步驟5得到只出不進存儲單元類的集合。若任意幾類在HWJS′′中可接受的貨物類的集合等于在HWJS′中可接受的貨物類的集合，則將這組存儲單元稱為只出不進存儲單元類的集合，如圖2所示，對只出不進存儲單元類的集合，即便考慮存儲單元類之間的緩存，就整體而言，也不再接受額外的貨物類的放置，形成只出不進閉環。故考慮緩存后的數量減少。

步驟6得到只進不出存儲單元類的集合。若任意幾組尺寸類型存儲單元在HWJS′′中所接受的貨物類的集合等于在HWJS′′′中可以接受的貨物類的集合，則將這任意n種組合存儲單元稱為只進不出存儲單元類的集合。對這組存儲單元，有最低的數量配置要求，使得爆倉率低于5%的風險。

式(6) 為考慮緩存后的數量配置減少；式(7) 為滿足爆倉率低于5%的約束，即考慮緩存后的各類存儲單元數量配置減少，各類貨位的數量配置大于所存儲某幾類貨物峰值的概率低于95%，但出現較大尺寸貨物無法存儲的風險仍低于5%。

1.3 模型建立

在爆倉率低于5%的約束下，構建所需存儲空間最小為目標的各類存儲單元尺寸和數量配置的非線性整數規劃模型。

目標函數為

約束條件為式(6)～(7)。

其中，式(8) 為非線性規劃目標函數，求解最佳存儲單元數量和尺寸配置。式(9) 表明貨物類和存儲單元類配置范圍約束。

2 基于整數規劃的多類存儲單元數量配置

本文所創建的多類貨位數量配置模型是一種線性整數規劃模型，可求得存儲單元從最少1類到類似全周轉率存儲策略的最多類范圍內，任意幾種尺寸類型存儲單元設定下，各類數量配置結果。模型求解過程并不復雜，可采用Matlab數學規劃工具包直接求解，如圖3所示。

圖3 算法流程圖Figure 3 Algorithm flowchart

步驟1排列出所有不同存儲單元類組。貨位類為i，在最大尺寸存儲單元配置必不可少時，存儲單元最多有組。各組存儲單元尺寸分別為Ln,Wn,Hn=ln,wn,hn。

步驟2計算各組基于正態分布的數量配置。由訂單數量分布信息Xik～U(ai1,ai2)，基于式(1)、(2)、(5) 計算得出。

步驟3計算各組內的緩存關系，得到只出不進類的集合和只進不出類的集合。列出各組約束條件式(6)、(7) 。

步驟4列出各組線性整數規劃模型，求解得出考慮緩存后的數量配置。

步驟5比較各組的需求存儲空間，取最小值。

3 算例

3.1 算例設計

仿真軟件為Matlab R2016b。貨物尺寸類型設置為20類，各類貨物尺寸與貨位類之間緩存關系如表2所示。第20號為貨位類中最大尺寸，當以20號尺寸作為單一貨位尺寸時，貨位類最少1種；當各類尺寸貨物均配置同種尺寸貨位時，貨位類最多20種；當貨位類介于1～ 20之間時，20號尺寸貨位總是必不可少?？偟拇鎯卧渲霉灿?。單次實驗設為10個批次，每個批次包含10個數量的訂單，不同訂單內同一類貨物的數量服從[0,4]，[0,4]，[0,3]，[0,2]，[0,2]，[0,5]，[0,4]，[0,2]，[0,2]，[0,4]，[0,5]，[0,2]，[0,2]，[0,4]，[0,3]，[0,3]，[0,3]，[0,4]，[0,4]，[0,3]的隨機均勻整數分布。出入庫相鄰貨物時間間隔服從λ=0.1 s的指數分布。理論上每個批次貨位數量范圍在0～ 650之間。對每組不同類的存儲單元配置進行10 000組實驗，統計10 000次實驗中的不爆倉率。

表2 各類貨物與貨位之間存儲關系示意圖Table 2 Schematic diagram of the storage relationship between various goods and storage units

3.2 數量配置計算結果

圖4為一組配置為10類存儲單元的算例。該算例給出了各類存儲單元數量配置計算過程。依次對524 288組貨位計算數量配置，結果如表3所示?？紤]不同類貨位之間緩存后，數量配置明顯減少。

表3 各類存儲單元數量配置結果Table 3 Configuration results of the number of various storage units

圖4 一組配置為10類存儲單元的算例Figure 4 A set of examples configured as 10 classes of storage units

3.3 實驗結果

貨物數量隨時間變化與峰值分布如圖5所示。在單次實驗中，任意幾類貨物數量峰值具有不確性。在入庫階段，貨架內貨物數量逐漸增加。當貨架內訂單到齊開始出庫時，由于出入庫貨物平均速度一致，倉庫內貨物數量維持相對平衡。在貨物全部完成入庫過程后，因倉庫內貨物尚未完全出庫，此時倉庫內貨物數量逐漸減少。在總的10 000次實驗中，任意幾類貨物峰值分布近似服從正態分布。設定5%的爆倉率約束既能很好地滿足存儲需求，又避免了較大的數量配置增加。

圖5 出入庫過程中貨物數量變化與峰值分布圖Figure 5 Schematic diagram of quantity change and peak distribution of goods in and out process

實驗結果顯示，兩組數量配置方法均能保證較大尺寸貨物無法存儲的風險低于5%。圖6為兩組配置方法的需求存儲空間比較圖，表明考慮緩存后能有效減少貨位的數量配置，降低需求存儲空間。且隨著存儲單元類的增加，存儲單元總數量配置增加，但需求存儲空間減少。當存儲單元類數等于貨物類數時，需求存儲空間最小。

圖6 兩組配置方法的需求存儲空間比較圖Figure 6 Comparison of the storage space requirements of the two configuration methods

4 結論

本文以板式家具機械手環繞式分揀系統為背景，考慮生產批次訂單情況的不確定性，在一定風險(大尺寸板材無法存儲的概率) 約束條件下，優化多種尺寸存儲單元的數量配置，提高分揀系統有限存儲空間的利用率。所得主要結論如下。

1) 較單一尺寸類型存儲單元配置而言，本文的方法提高了存儲單元空間的利用率，在有限的存儲空間內能夠配置更多的存儲單元數量。

2) 隨著存儲單元種類的增加，存儲單元共享性下降，存儲單元數量必定增加，但總的需求存儲空間減少。這與單一尺寸存儲單元的“更多貨位區域分類必定增加需求存儲空間”的結論相悖。

3) 需求存儲空間減少的原因為其空間利用率的提高帶來的空間減少，優于存儲單元數量增加而導致的空間增加。