面向存儲空間受限的分揀系統(tǒng)內(nèi)多類型存儲單元數(shù)量配置

李 靖，陳慶新，毛 寧

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

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

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

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

1 模型構建

1.1 問題描述

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

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

模型假設如下。

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

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

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

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

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

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

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

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

1.2 模型分析

1.2.1 變量與符號

變量與符號如表1所示。

1.2.2 基于正態(tài)分布的數(shù)量配置

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

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

當分揀系統(tǒng)內(nèi)最多不允許超過b個完整批次時，給定任一數(shù)字c，則

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

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

1.2.3 考慮緩存下的數(shù)量配置減少

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

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

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

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

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

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

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

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

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

1.3 模型建立

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

目標函數(shù)為

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

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

2 基于整數(shù)規(guī)劃的多類存儲單元數(shù)量配置

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

圖3 算法流程圖Figure 3 Algorithm flowchart

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

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

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

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

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

3 算例

3.1 算例設計

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

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

3.2 數(shù)量配置計算結果

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

表3 各類存儲單元數(shù)量配置結果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 實驗結果

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

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

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

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

4 結論

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

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

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

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