密集倉(cāng)儲(chǔ)規(guī)劃的實(shí)用算法研究

臧冀原，贠 超，張志強(qiáng)

（北京航空航天大學(xué) 機(jī)器人研究所，北京 100029）

0 引言

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

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

1 問(wèn)題分析

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

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

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

目標(biāo)函數(shù)：求倉(cāng)儲(chǔ)額定藥盒的最小貨架高度

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

整個(gè)貨架的寬度不能超過(guò)立體倉(cāng)庫(kù)的總體寬度

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

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

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

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

每種藥盒的存儲(chǔ)量不得低于額定存儲(chǔ)量

每種藥盒存放在相應(yīng)的貨位上。

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

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

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

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

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

2 求解過(guò)程

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

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

li為第i種藥盒的實(shí)際長(zhǎng)度尺寸；

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

hi為第i種藥盒的實(shí)際高度尺寸；

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

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

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

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

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

ηi'為第種藥盒額定存儲(chǔ)占用的通道。存在如下關(guān)系：

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

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

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

2.3 規(guī)劃算法流程

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

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

圖1 預(yù)排布流程圖

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

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

2.4 規(guī)劃結(jié)果

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

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

圖 3 層高分布圖

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

以上尺寸單位皆為mm。

3 結(jié)論

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