密集倉儲規(guī)劃的實用算法研究

臧冀原，贠 超，張志強

（北京航空航天大學 機器人研究所，北京 100029）

0 引言

隨著世界經濟一體化和現(xiàn)代科技的迅猛發(fā)展,現(xiàn)代物流被認為是除降低資源消耗、提高勞動生產率以外的“第三方利潤源泉”[1]。在這一大環(huán)境下,作為物流的重要組成部分的倉儲,也越來越多的被人們關注。如何提高倉儲管理效率和密度,成為一個熱點研究問題。倉儲是通過倉庫對物資進行儲存和保管。倉儲作業(yè)是以保管活動為中心,從倉庫接收物品入庫開始,到按需要把物品全部完好地發(fā)送出去為止的全部過程[2,3]。現(xiàn)代物流配送中心規(guī)模日益增大，品種復雜和存儲量大與存儲空間緊張產生矛盾，如何解決在有限空間內存儲盡可能多的貨物成為一個值得研究的題目。提高倉儲密度在縮短出入庫周期，降低設備及其維護成本，減少占地開支等方面都有這積極的意義。

在不考慮貨架和出庫入庫操作方式的情況下，該問題屬于平面或者三維布局問題，布局問題屬于組合優(yōu)化問題，求解的難點在于迭代次數(shù)隨布局對象數(shù)量呈階乘增加。對于倉儲對象復雜、貨位數(shù)量多的倉儲規(guī)劃，如果采用經典布局求解算法，勢必費力費時，甚至在規(guī)定的時間內得不到最優(yōu)解。如果增加實際倉儲過程中的機構和工藝等約束條件，單次迭代計算時間增加，求解更加緩慢，如何利用這些約束條件，簡化求解過程，降低迭代計算次數(shù)是本文的主要目的。

1 問題分析

對于一個給定的倉儲實體，比如物流配送中心、自動化立體倉庫等，面臨的問題是已知貨物的包裝尺寸和額定存儲量，如果貨位確定的情況下，需要求解占用最少貨位并且冗余空間最少的布局；如果貨位是可調節(jié)或者采用先設計規(guī)劃后加工的方式，需要求解最優(yōu)的貨位布局，使得占據(jù)的存儲空間最小。兩種表述的數(shù)學本質是相同，就是求解滿足額定存儲量的最小存儲空間。

實際的倉儲實體多數(shù)采用縱橫交錯的金屬框架結構，在三維尺寸方向均要求滿足機械結構的約束，使得最小倉儲空間的求解不同于下料問題（partition problem）[4,5]或者布局問題（placement problem）。如果采用模擬退火、蟻群算法等都將會導致巨大計算量，收斂緩慢，甚至得不出全局最優(yōu)解[6,7]。

下面以實際的快速發(fā)藥系統(tǒng)項目為例，對問題做更進一步的描述和求解。對于醫(yī)院門診藥房，需要存儲一定數(shù)量的藥品以備一個補藥周期內的藥品發(fā)放，其中的盒裝片劑的存儲，通常采用金屬貨架擺放，造成空間的巨大浪費，取藥路徑長，藥房工作人員勞動強度大，發(fā)藥效率低下[8]。快速發(fā)藥系統(tǒng)是針對解決醫(yī)院門診藥房盒裝藥品的自動補給、密集倉儲和自動發(fā)放整條流通渠道設計的一套自動立體倉庫系統(tǒng)。密集倉儲為快速發(fā)藥系統(tǒng)的關鍵技術之一，其具體描述如下：

目標函數(shù)：求倉儲額定藥盒的最小貨架高度

其中m為排布的層數(shù)。

整個貨架的寬度不能超過立體倉庫的總體寬度

貨架的某列的寬度取為該列中最寬的貨架寬度

考慮工藝和成本約束，貨架每列的寬度滿足系列約束

｛W'｝s為貨架寬度系列值。

貨架的某行的高度取為該行存放的最高藥盒的高度

每種藥盒的存儲量不得低于額定存儲量

每種藥盒存放在相應的貨位上。

f : (i, j)→r, i=0,...,m; j=0,...,n;r=0,..., p定義為第r種藥盒放置在第i行第j列貨位，滿足Wij≥wr；Hij≥ hr。

(W)m×n為貨位寬度在出貨口截面上形成的矩陣。

(H)m×n為貨位高度在出貨口截面上形成的矩陣。

(w)p為藥盒寬度列陣。

(h)p為藥盒高度列陣；p為藥品的品種數(shù)。

2 求解過程

2.1 數(shù)據(jù)采集

數(shù)據(jù)采集部分包括兩個方面的內容：藥盒最小包裝尺寸的測量和藥品一個周期的發(fā)藥量統(tǒng)計，最終獲得{li,wi',hi,ηi'}T,i=0,...p，其中

li為第i種藥盒的實際長度尺寸；

wi'為第i種藥盒的實際寬度尺寸；

hi為第i種藥盒的實際高度尺寸；

ηi'為統(tǒng)計周期內第i種藥盒的用量，以醫(yī)院最小用藥單位計量。

2.2 數(shù)據(jù)預處理

對于密集倉儲規(guī)劃求解來講，數(shù)據(jù)預處理的目標之一是用轉換系數(shù)解決醫(yī)院藥房最小用藥單位和最小倉儲單位不一致問題。轉化系數(shù)定義為一個最小包裝內包含的最小用藥量的數(shù)量，是一個比值關系，比如藥品A，醫(yī)院使用時是以粒為單位的，而倉儲時，是以盒為單位的，如果一盒包含N粒藥片，那么轉換系數(shù)為N。從而獲得{li,wi',hi,ηi'}T,i=0,...p，其中 ηi'為藥品額定存儲量，以醫(yī)院最小倉儲單位計量。

數(shù)據(jù)預處理的另一個目標是在第一步的基礎上， 把 {li,wi',hi,ηi'}T,i=0,...p， 轉 化 為 {wi',hi,ηi'}T,i=0,...p，其中

wi' 為第種藥盒占據(jù)貨位的寬度；

ηi'為第種藥盒額定存儲占用的通道。存在如下關系：

wi=Wi，如果 Wi-1≤ wi'＜ Wi，則

ni=ηi/([L/li])+1)，其中L為一個貨位存儲的有效長度。

至此三維布局降為二維問題，問題轉換為在平面內分行按列布局若干貨位，使得所占矩形存儲區(qū)域高度最小。

2.3 規(guī)劃算法流程

為了節(jié)省迭代次數(shù)，提高求解效率，整個規(guī)劃算法為兩步：第一步，按行按列的排列規(guī)則，計算機模擬人工排布的方式，在整個寬度方向布局所有貨位，獲得占據(jù)全部寬度的一個較優(yōu)解；第二步，采用平移貨位的方法，將本層最高的藥盒貨位平移到較高一層的空白貨位處，以此降低該層占據(jù)的層高，迭代尋優(yōu)，獲得各層的最小擺布層高，從而獲得整個布局的高度。

對于倉儲的整體布局而言，貨位的調整不支持鏡像、旋轉和置換。貨位繞本身軸線的鏡像視為同一貨位，若繞其它軸線的鏡像會發(fā)生貨位之間的干涉，違背約束條件。同時旋轉是不能使得層高優(yōu)化，也違背約束條件。如果兩個貨位置換可以帶來層高的縮小，那么可以得出這兩個貨位的寬度必然一致，如果寬度不一樣的貨位交換，寬度較小的貨位肯定放不下寬度較大的貨位。而同一寬度的幾列中，層高按升序的方式排列在各層中，故兩個貨位的調換只能導致層高增加（或保持不變）而不會減少。同一層之間貨位的互換或者平移是不影響層高的，故優(yōu)化層高只能通過不同層之間移動貨位到空白貨位處來實現(xiàn)。概率較大情況下，藥盒寬度跟高度成比例關系，故寬度較大的貨位通常高度也較大。為獲得最優(yōu)解，被平移的貨位高度為該層中最高的，寬度必須最接近至空白貨位寬度。

圖1 預排布流程圖

預排布的流程圖如圖1所示，預排布的目的是通過簡單迭代獲得一個滿足約束條件的較優(yōu)解，充分占滿倉儲的寬度方向，每種列寬的貨位按其數(shù)量分成若干行若干列，依次按貨位高度升序排布，作為優(yōu)化迭代的初始值，減少了不必要的計算量。

層高規(guī)劃流程圖如圖2所示，從最頂層到最底層搜索預排布后留下的空白貨位，在空白貨位層以下的層中逐個搜索比較高度在該層中最高寬度最適合空白貨位的貨位，并將該貨位平移至空白貨位處，修改其貨位編碼。

2.4 規(guī)劃結果

在額定儲藥總量20000盒，各藥盒的存儲比例關系通過統(tǒng)計藥房兩周內的發(fā)藥量獲得，貨位總數(shù)1354，貨位寬度系列{38，48，58，68，78，88，98}，立體倉庫存儲寬度限制為3300，儲存有效空間長度1650，藥品品種數(shù)224的情況下，預處理總存儲高度為926，迭代優(yōu)化后的總存儲高度為709，迭代優(yōu)化前后各層層高分布如圖3所示。

圖2 優(yōu)化迭代排布流程圖

圖 3 層高分布圖

虛線為預排布層高值，實線為優(yōu)化迭代后的層高值。

以上尺寸單位皆為mm。

3 結論

該倉儲規(guī)劃算法以快速發(fā)藥系統(tǒng)藥盒存儲為實例，獲得了迭代的最優(yōu)存儲高度，輸出了獲得最優(yōu)存儲高度的貨位排布，解決了實際密集存儲優(yōu)化的最小存儲空間問題。算法的數(shù)據(jù)預處理部分將額定倉儲量轉化為額定貨位數(shù)量，是整個算法實現(xiàn)的基礎。密集存儲規(guī)劃算法避開了經典布局問題求解算法帶來的迭代次數(shù)過多的缺陷，把由于工藝和成本方面導致的倉儲約束作為布局規(guī)則引入問題求解，算法在第一步采用模擬人工排布的試湊法，獲得一個在可行域上的較優(yōu)解。在算法第二步，平移高度較高的貨位到層高更高的空白貨位處，使得高度接近的貨位盡可能的放置在一層中，從而使得每層的占據(jù)的存儲高度盡可能下，達到整體存儲高度最小，獲得最優(yōu)解。

[1] Dyckhoff H., A typology of cutting and packing problems[J].European Journal of Operational Research, 1990,44(1): 145～159.

[2] Dowsland K.A, Dowsland W.B., Packing problems [J].European Journal of Operational Research, 1992, 56(1): 2～14.

[3] Scheithauer G., Terno J.Modeling of packing problems [J].Optimization, 1993, 28: 63～84.

[5] Peter Bradley.The Post-Y2K Frontier.International Journal Of Physical Distribution & Logistics Management.1999, 5: 180

[6] Robert L.Lieb, Rbert A.millen.Third-party Logistics Services.A Compassion Of Experienced American And European Manufactures.International Journal Of Physical Distribution & Logistics Management.1997, (6): 12～13

[7] Robert C.lieb, Hugh L.Randall.1997 CEO Perspectives On The Current Status And Future Prospects Of The Third Party Logistics Industry In The United States.Transportation Journal.