基于遺傳算法的立體倉庫貨位動態(tài)分配優(yōu)化

張曉蘭，蔣麗娜，于洪濤

(哈爾濱商業(yè)大學，計算機與信息工程學院，哈爾濱150028)

隨著計算機技術、現代通信技術和自動控制技術的迅猛發(fā)展，倉儲管理水平也已經向著信息化、自動化、智能化方向發(fā)展[1].而在倉儲管理中貨位的分配及優(yōu)化問題一直是一個非常棘手的問題.高效的貨位動態(tài)分配優(yōu)化算法將提升各企業(yè)在倉儲管理方面的競爭實力.實時分配的優(yōu)化貨位對降低倉庫中貨品搬運的成本，提高倉庫的空間利用率及貨品出入庫的效率具有非常重要的現實意義.

貨位的分配及優(yōu)化問題是一個多目標的優(yōu)化問題.遺傳算法具有魯棒性好，全局搜索能力強的特點，它是解決多目標優(yōu)化問題強有力的工具[2].本文采用基于遺傳算法的權重系數變換法對貨位動態(tài)分配優(yōu)化問題進行研究.

1 立體倉庫貨位動態(tài)分配優(yōu)化問題

1.1 問題的提出

在對企業(yè)倉儲管理實際情況的調研中發(fā)現，一些倉庫的貨位分配策略不盡合理，管理人員僅憑直觀經驗進行藥品貨位分配，缺乏先進的科學依據，不利于貨品的快速出/入庫;且貨品存放隨意，庫存面積利用率不高，庫存周轉效率較低，嚴重影響了企業(yè)的生產組織和經濟效益.經研究發(fā)現，同一貨品存放在倉庫中的不同貨位，所消耗的能量是不同的，例如貨品放在離出/入庫工作臺近的貨位比離出/入庫工作臺遠的貨位要節(jié)省出/入庫時間，同時也節(jié)約了能量消耗，降低運行成本，放存在高貨位比存放在低貨位消耗的能量要多[3].因此，對立體倉庫的貨位進行動態(tài)分配優(yōu)化，可以很好地解決上述問題.

1.2 貨位分配策略的選擇

1.2.1 常用的貨位分配策略

常用的貨位分配策略有:1)定位存儲:每一種貨品都依據其周轉率安排固定的貨位，貨品之間不能互用貨位，其優(yōu)點是管理方便，縮短出入庫運行距離，缺點是降低庫區(qū)空間的平均使用效率.2)隨機存儲:每一種貨品的貨位隨機指派，而且可以經常改變，其優(yōu)點是可以共享貨位，提高貨位使用效率，缺點是出入庫管理和盤點困難.3)分類存儲:所有的貨品按照其特性進行分類，然后采用固定貨位存儲固定種類的貨品，其優(yōu)點是有利于暢銷品的存放，缺點是庫區(qū)儲位必須設計為貨品的最大在庫量，降低了使用效率.4)分類隨機存儲:每一種貨品有固定的存放區(qū)域，但在存放區(qū)域內貨位的分配是隨機的，其優(yōu)點是提高貨位使用效率，缺點是出入庫管理和盤點困難.5)共享存儲:不同的貨品的貨位不但可以隨機指派，而且貨品之間可以共享貨位空間，其優(yōu)點是節(jié)省空間和搬運時間，缺點是管理非常復雜.

1.2.2 貨位存儲策略的選擇

采用RFID對貨品的各種相關信息進行記錄，使倉庫管理系統(tǒng)具備了可實時查詢和定位貨品的功能，克服了出入庫管理和盤點困難的缺點，因此采用隨機存儲的貨位分配策略.

1.3 多目標優(yōu)化問題

1.3.1 優(yōu)化模型的建立

假設立體倉庫有K排I層J列，貨架的寬度與貨架間的距離之和為H、貨位的寬度為L，并且離出/入庫工作臺最近的列記為第1列、最近的排記為第1排.處于第x列y排z層的貨位記為(x，y，z)(x=1，2，……J;y=1，2……K;z=1，2，……I).貨位上貨品的質量為Mxyz.

1)根據“就近存取”的原則，將貨品放在離庫門最近的地方.則貨位分配優(yōu)化模型可以描述為:

2)考慮貨架的承重能力，將貨品質量Mxyz較小的貨品盡可能地存放在貨架的高處.則貨位優(yōu)化模型可以描述為:

3)考慮貨架的穩(wěn)定性，取貨時應該盡可能的先從高處取貨.此優(yōu)化模型可以描述為:

將其轉化為求最小值問題:

1.3.2 優(yōu)化模型的約束條件

當有貨品要進行存儲時，要保證所分配的貨位為空，即:P(x，y，z)=0式中:P(x，y，z)代表貨位(x，y，z)是否為空的標志位.

2 遺傳算法求解約束多目標的貨位動態(tài)分配優(yōu)化問題

從建立的優(yōu)化模型可以看出儲位優(yōu)化是一個多目標優(yōu)化問題.多目標優(yōu)化問題的各目標函數之間往往相互沖突，通常不存在對所有目標都是最優(yōu)的解，只存在一組均衡解，即所謂的Pareto最優(yōu)解，難以得出一個滿足所有目標函數的最優(yōu)解[4].針對這種情況本文采用基于遺傳算法的權重系數變換法求解此多目標優(yōu)化問題，即給每個目標優(yōu)化函數f(i)(i=1，2，……n)賦予權重系數Wi(i=1，2，……n)，則多目標優(yōu)化問題就轉化為單目標優(yōu)化問題，即可以利用單目標優(yōu)化的遺傳算法求解多目標優(yōu)化問題[4].因此優(yōu)化模型可以轉化為:

對于不同的公司，他們注重的優(yōu)化點不同，有的公司注重貨位出入庫的效率，有的注重貨架的承重能力，而有的注重貨架的穩(wěn)定性問題，因而采取權重系數變換法可以給用戶更多的選擇余地，可以根據自己的實際情況進行權重系數的設置，這樣更有利于實際問題的解決，提高工作效益，達到事半功倍的效果.針對本文的實例情況，該制藥企業(yè)對出入庫的效率更加的重視一些，因此采用2∶1∶1的比例分配權重系數.

其遺傳算法求解步驟

1)獲取立體倉庫的當前庫存狀態(tài)信息(空貨位位置、各貨位上貨品重量等).

2)確定種群數目Pop、最大遺傳代數Gmax、編碼長度、代溝GGAP、交叉概率Pc、變異概率Pm等參數.

3)采用二進制編碼方法對貨位進行編碼，并增加貨位標志位P(x，y，z)(其值為0時代表該貨位為空)，隨機生成初始種群.

4)適應度函數的確定.由目標函數可得適應的函數為

其中:Cmax為f(x，y，z)的最大值估計.

5)分別計算每個個體的適應度值，對于違反約束條件的個體進行懲罰.即對個體的適應度調整:

其中:Fit(f(x，y，z))為原始適應度;Fit(f(x，y，z))為調整后的新適應度;P(x，y，z)為懲罰函數.

6)根據適應度和代溝GGAP從種群中選擇優(yōu)良個體.

7)完成種群的重組，按照交叉概率Pc進行交叉、按照變異概率Pm進行變異，形成新的種群.

8)算法終止條件.當遺傳代數達到最大遺傳代數Gmax，結束算法，并輸出最優(yōu)解.

9)更新庫存信息.

應用上述算法以某制藥企業(yè)藥品倉庫為例進行仿真實驗，該倉庫共有10排立體貨架，每排貨架包括4層25列共1 000個貨位.實驗中，取貨架的寬度與貨架間的距離之和H=1、貨為的寬度L=0.8、種群規(guī)模N=100、交叉概率Pc=0.8，變異概率Pm=0.1，最大迭代次數為100.實驗結果驗證了算法的有效性.

3 結語

基于遺傳算法的立體倉庫貨位動態(tài)分配優(yōu)化的算法，以存取路徑距離及貨架承重能力和穩(wěn)定性為優(yōu)化目標.通過權重系數變換法較好的解決了多目標之間相互沖突的問題，并加入懲罰函數，淘汰不滿足約束條件的解.仿真實驗結果表明該算法能夠提高貨位分配效率，降低貨位管理成本.

[1]蔡增玉，甘 勇，金保華，等.基于RFID的物流管理系統(tǒng)設計[J].鄭州輕工業(yè)學院學報:自然科學版，2009，24(6):23－28.

[2]鄒暉華，胡吉全，楊艷芳.自動化立體倉庫貨位分配策略優(yōu)化研究[J].湖北工業(yè)大學學報，2008，23(3):43－45.

[3]QUW J，XU F，LIU ZH，etal.Regional Higher Education Resource Allocation Pareto Equilibrium Analysis[C]//International Conference on Intellectual Technology in Industrial Practice，Chang Sha，China，2010(1):354－348.

[4]李敏強，林 丹，李書全，等.遺傳算法的基本理論與應用[M].北京:科學出版社，2004.