基于分枝定界法的旋轉(zhuǎn)貨架存取路徑優(yōu)化

摘要：隨著城市物流需求向著小批量，多品種和時效性方向發(fā)展，儲存作業(yè)中貨物流動頻率、貨物品種和數(shù)量迅速增加，同時，用戶對貨物到達及服務質(zhì)量也更加嚴格，這大大增加了貨物在倉儲中心存取的復雜性。論文采用分支定界法對旋轉(zhuǎn)貨架的存取路徑優(yōu)化，有效解決了旋轉(zhuǎn)貨架在面對多品種多儲位存取時的存取路徑優(yōu)化問題，可大大提高存取效率，節(jié)約勞動力和存取時間。

關(guān)鍵詞：分支定界法；旋轉(zhuǎn)貨架；存取路徑

中圖分類號：F224文獻標識碼：A文章編號：1002-3100(2007)12-0023-03

Abstract: With the development of urban logistics， the frequency， the varieties and quantity of freight quickly increase， furthermore， customers requests better service， which adds the complexity of distribution center operation. The paper optimizes the route of automated warehouse with branch and bound method. It solves effectively the question of route optimization when lots of freights need to be deposited and fetched， so the effect increases， work force and time are reduced.

Key words: ranch and bound method; automated warehouse; the route of depositing and fetching

0引言

物流倉儲中心的作業(yè)是一連串的“存”和“取”的動作組合。隨著需求向著小批量，多品種和時效性方向發(fā)展，使得儲存作業(yè)中貨物流動頻率、貨物品種和數(shù)量迅速增加。據(jù)統(tǒng)計，倉庫中的卸貨、取貨、分揀和裝車環(huán)節(jié)的作業(yè)一般大約占整個配送中心總作業(yè)時間的40％，而其余約60％的作業(yè)時間卻是作業(yè)人員的行走耗時?？紤]到勞動力成本在倉庫的成本比例比較高以及許多行走耗時是因為儲位規(guī)劃不合理的緣故，那么如何使“存”和“取”的動作快速而有效，做到“好存好取”，對儲位及存取路徑進行有效的管理非常必要?，F(xiàn)代物流倉儲中心除了保管之外，揀貨、發(fā)貨和配送也是很重要的工作之一，要及時掌握和控制貨物在庫狀況，動態(tài)調(diào)整和改善儲位安排以盡量減少行走耗時，從而提高倉儲中心的運作效率與降低勞動力成本。

減少工作人員的無效走動，最重要的一個方面就是要對儲位的優(yōu)化以及貨架存取路徑的優(yōu)化。在貨架中，旋轉(zhuǎn)貨架是一種特殊貨架，相對固定貨架，其存取路徑問題更為復雜，可節(jié)約空間更大，其也是自動化倉庫的重要組成部分，特別適于大型倉儲中心儲存的多種小件及微小件物品的儲存，它以其靈活性、高效性以及準確性成為自動化倉庫的重要儲存設備。旋轉(zhuǎn)貨架為提高小件物品儲存系統(tǒng)的存取效率、縮短出入庫時間、提高儲存作業(yè)的準確性，實現(xiàn)自動化倉庫的集成管理帶來了十分廣闊的應用前景。然而由于目前關(guān)于旋轉(zhuǎn)貨架的優(yōu)化管理、調(diào)度與運行的研究成果較少，使旋轉(zhuǎn)貨架的高效性未能得到充分的發(fā)揮和體現(xiàn)。

1旋轉(zhuǎn)貨架存取路徑優(yōu)化問題

旋轉(zhuǎn)貨架揀選路徑優(yōu)化問題是旋轉(zhuǎn)貨架優(yōu)化運行諸問題中一個非常重要的問題，對旋轉(zhuǎn)貨架揀選作業(yè)問題的優(yōu)化將極大提高旋轉(zhuǎn)貨架以及整個自動化倉庫的作業(yè)效率。另外，旋轉(zhuǎn)貨架揀選作業(yè)問題與實際中許多其它的組合優(yōu)化問題具有一定的相似性，是一個具有代表性的數(shù)學問題。因此，對該問題的研究不僅具有重大的實際意義，而且具有很高的理論價值。

對旋轉(zhuǎn)貨架來講，路線的變化就是正反轉(zhuǎn)問題。當單一正轉(zhuǎn)或反轉(zhuǎn)不理想時，先按某一方向存取幾個貨位，然后反方向運轉(zhuǎn)，存取其他貨位。對某一最優(yōu)路線，如果有正反轉(zhuǎn)問題，它一定符合下列兩點：一是正反轉(zhuǎn)次數(shù)為一，二是通過重復一段路徑來避開另一段路徑，并且前者比后者小。這樣，求最優(yōu)路線問題就歸為以下問題：

（1）是否存在正反轉(zhuǎn)問題；

（2）存在正反轉(zhuǎn)問題，重復哪一段路徑。

假設有N個需存取的貨位，當面前升降臺所在位置為X0，從X0開始，按順時針方向N個貨位依次為：X1，X2，X3，…，XN。

問題：在沒有貨物存取先后的約束條件下，采取何種存取路徑使得這N個貨位被存取后旋轉(zhuǎn)貨架旋轉(zhuǎn)路徑最短。

2分支定界法在旋轉(zhuǎn)貨架存取路徑優(yōu)化中應用

對有約束條件的最優(yōu)問題（其可行解為有限數(shù)），把全部可行解空間反復地分割為越來越小的子集（稱為分支），并且為每個子集內(nèi)的解值計算下一個界（求最小值問題）稱為定界。在每次分支之后，凡是界限超過已知可行解的那些子集不再做進一步分支。這樣，解的許多子集（不去檢查這些子集中的每個解）就可以不予考慮了。繼續(xù)進行直到找出可行解為止，該可行解的值不大于任何子集的界限，將問題分支為子問題集以及對子問題定界的步驟稱為分支與定界的算法。

在分支與定界算法的任何一點必須做分支決策，凡是界限小于迄今為止所有可行解最小上界的任何子集都有可能做為分支的選擇對象（求最小值）。分支決策有兩種：一種是從最下界分支，從可能解的子集進行下一個分支，該子集在最優(yōu)解上有最下界；另外一種是從最新的活動界限分支，從各自解中選擇最新產(chǎn)生的，具有最下界的子集，以做出下一個分支。

根據(jù)上面論述的問題，采用分支定界法對該問題求解步驟可以如下求解：

把解集分為N個子集：對應每一個貨位點的解為一集。但不是檢查每一集的解值。具體步驟如下：

第1步：計算相鄰貨位點間的距離：D0=X1-X0，D1=X2-X1，…，DN-1=XN-XN-1，

DN=X0-XN，若DI<0，則DI=DI=200，其中200為一層的周長，I=0，1，…，N。

第2步：令J=K=0。的DI=DM，則XN點的順解SN即是最優(yōu)解，J=N， K=0。轉(zhuǎn)第12步。（因為從X0出發(fā)按順時方向存取N個貨位的路線，未發(fā)生正反轉(zhuǎn)問題，同時避開了最大的一段）。否則轉(zhuǎn)下步。

第12步：J與K決定了最優(yōu)路線，總路程為MIN。其中K=0表示先順時針存取到貨點J，再返回，逆時針存取其它的貨位（如果有的話）；K=1表示先逆時針存取到貨點J再返回，順時針存取其它的貨位（如果有的話）結(jié)束。

3實例分析

某倉儲中心有一種旋轉(zhuǎn)貨架，200列的一層，當前升降臺所在位置為第0（200）列，需要存取第30列、40列、70列、80列、180列，共五個貨位點。

下面采用分支定界法來對其存取進行優(yōu)化：

（1）求相鄰貨位間的距離。

D0=X1-X0=30-0=30，D1=X2-X1=40-30=10， D2=70-40=30，D3=80-70=10，D4

=180-80=100，D5=200-180=20。

（2）令J=K=0；比較可知D4=100最大，比較D5=D4嗎？不，比較D0=D4嗎？不。

（3）求X4點的順解S4，即按路線0—（順時針）1—2—3—4（返回）—5存取，S4=2*D0+D1+D2+D3

+D5=180。

求X5點的逆解S5，即按路線0—（逆時針）5（返回）—1—2—3—4存取，S5=2*D5

+D0+D1+D2+D3+D5=120。

所以MIN=S5=120，J=5，K=1。

（4）順分枝，D0，D1，D2，D3中D2=30最大，求X2的順解。即按路線0—（順時針）1—2（反方向）—5—4—3存取，S2=2*D0+D1+D5+D4+D3=210。

而對于避開D2的另一解—X3的逆解，出于它重復了D4，一定不是最優(yōu)解，故不加計算。要避開

D3，就必需重復D2和D4，而兩都比它大，故X3的順解和X4的逆解都不加計算（剪枝）。

4結(jié)論

由上面的實例可知，對于對旋轉(zhuǎn)貨架的實際存取中，優(yōu)化的結(jié)果是最優(yōu)路線為0—（逆時針）5—（返回）1—2—3—4最小路程為120。在實際中，往往很多操作人員的實際操作，并沒有考慮旋轉(zhuǎn)貨架的可旋轉(zhuǎn)的優(yōu)勢，一般是根據(jù)經(jīng)驗而定，如上述問題，容易產(chǎn)生采取固定路線0—（順時針）1—2—3—4（返回）—5，路程為180。比較可知，該方法采用的比最優(yōu)的要多60個單位。一般而言，當存取的貨位比較少時，實際經(jīng)驗往往比較接近于優(yōu)化算法結(jié)果。但是，當面對一些較大，存取貨物較多時候，對旋轉(zhuǎn)貨架的存取路徑優(yōu)化就顯得十分必要，一方面可以節(jié)約勞動力，另外也大大節(jié)約了存取時間。在城市物流配送中，對時間的要求越來越嚴格，效率問題與服務質(zhì)量問題也越來越被用戶所關(guān)注。采用一定的優(yōu)化方法，對較大的物流配送中心、在貨物品種多，儲位復雜情況下，對每次存取都采用優(yōu)化后的路線，效率將大幅度提高。

參考文獻：

[1] 運籌學編寫組. 運籌學[M]. 北京：青華大學出版社，1990.

[2] 李永生，鄭文嶺. 倉儲與配送管理[M]. 北京：機械工業(yè)出版社，2003.

[3] 愛德華·弗雷茲（美）. 當代倉儲及物料管理[M]. 劉慶林，譯. 北京：人民郵電出版社，2004.

[4] 楊傳杰. 倉儲與物流[M]. 天津：天津科學技術(shù)出版社，2003.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文?！?/p>