基于遺傳算法的自動化立體倉庫的貨位優化分配

摘要：文章針對自動化立體倉庫的庫區和貨位的分配策略問題進行了討論，提出立體倉庫的庫區優化數學模型；在庫區優化基礎上，進一步提出貨位優化數學模型，將Pareto最優解的概念與遺傳算法相結合，提出了一種改進的解決多目標優化問題的Pareto遺傳算法解決貨位優化問題，給出了仿真實驗及分析，結果表明采用改進遺傳算法優化策略可以有效地解決自動化立體倉庫的貨位優化分配問題。

關鍵詞：立體倉庫；貨位優化；遺傳算法；Pareto

中圖分類號：TP301.6文獻標識碼：A

文章編號：1002-3100(2008)01-0038-04

Abstract: In this paper， the controling strategies of section assignment and location assignment of an automated warehouse are discussed. The mathematic model of the section assignment optimization is built. Based on optimization of section assignment， the mathematic model of the location assignment optimization is built further. Combining the concept of Pareto optimal sets with genetic algorithm， the improved Pareto genetic algorithm for resolving the problems of multi-objective optimization is proposed， which is used to deal with the location assignment. The simulation experiment is given， and the result is analyzed. The problem of location assignment optimization could be effectively resolved via the improved genetic algorithm proposed by this paper. The research result of this paper is valuable for improving on the efficiency of automatic warehouse.

Key words: warehouse; location assignment; genetic algorithm; Pareto

在物流控制系統中自動化立體倉庫的出現不僅徹底改變了倉儲行業勞動密集、效率低下的落后面貌，并且大大拓展了倉庫功能，使之從單純的保管型向綜合的流通型方向發展。目前隨著電子數據交換技術的發展及應用，自動化立體倉庫系統逐步向3I（Intelligent， Integrated， Information）倉庫系統過渡。而一個自動化立體倉庫效率的高低主要取決于庫區和貨位的分配策略，使用好的優化策略能大大提高出入庫頻率、方便盤庫和移庫操作。對巷道兩側貨架上的貨物進行存取操作，一般有單元出/入庫和揀選出/入庫兩種作業方式[1]。本文主要討論單元出/入庫作業方式的貨位優化問題。

通過對立體倉庫的庫區和貨位采用合理的分配控制策略，提高自動化立體倉庫的工作效率，一直是一個熱點問題，對自動化立體倉庫貨位分配控制策略的優化算法的研究也在不斷深入。解決這類問題的優化算法包括迭代計算法、枚舉法、隨機算法、遺傳算法等。本文提出了一種改進的解決多目標優化問題的Pareto遺傳算法解決貨位優化問題，可以有效地解決自動化立體倉庫的貨位優化分配問題。

1自動化立體倉庫貨位分配控制策略

為提高自動化立體倉庫的效率和方便貨位管理，自動化立體倉庫貨位分配控制策略常用的有如下幾個：

（1）改進的先進先出。采用改進的先進先出原則，若檢驗合格的有效期為12個月，那么將庫存時間在1~12個月的貨物嚴格按照入庫時間的先后進行出庫操作，不足一個月的貨物忽略先進先出原則，按照距離就近的原則進行操作，提高出庫效率。

（2）上輕下重。進行入庫操作時，重物應放在倉庫的下部貨架，輕的放在上部的貨架，使貨架受力穩定。

（3）分巷道存放。當倉庫有多個巷道時同種貨物要分散存放在不同巷道。

（4）貨物相關性。相關性大的貨物往往同時出庫，所以應該盡可能放在相鄰位置。

（5）貨位分區。根據貨物出入庫頻率和特性，將立體倉庫劃區分段。

（6）最短路線。對于出入庫操作，找到貨物所在的貨位分區后，按照距離出入庫臺最近的貨位作為出入庫的貨位[2-3]。

本文在總結了當前貨位分配優化策略的基礎上，提出了一種新的貨位優化的方法。該方法首先將貨架進行扇形分區，即將存儲貨物進行分類；然后在每一庫區中按照貨位分配策略，采用改進遺傳算法進行貨位優化，這樣更加有利于立體倉庫的貨物管理。

2庫區優化分配問題

2.1庫區分配優化問題的數學模型

庫區分配優化問題是一個典型的指派問題。這是一類特殊的線性規劃問題。在進行貨位分區時，我們作如下假設：貨物的存放種類已知；每種貨物單位時間內存放的數量已知；每一種貨物的存取頻率已知。

由此本文提出以下的控制策略。

Step1：將貨物按照出入庫頻率和質量分類，其數目等于倉庫分區的數目。

Step2：根據貨物的分類數，將貨架進行扇形分區。其中表1描述了一個8列4層的貨架分為4個庫區的扇形分區情況。綜合考慮貨物的需求頻度和質量，可以將貨物表述為n種類型，用p表示質量和需求頻度，p=0，1，2，…，n，分別表示質量和需求頻度依次變小。按由大到小進行排序，進行劃分形成優先級不同的庫區。在此表中p值相同的貨位合成為一個庫區，p越大代表庫區的優先級越低，距離出入庫臺最遠。

Step3：根據堆垛機取放某種貨物的工作量建立權值矩陣，單位時間內堆垛機取放某種貨物的工作量與該貨物的出入庫頻率、貨物的質量和該貨物存放的位置有關，將該貨物的出入庫頻率乘以質量再乘以堆垛機運行至貨物存放位置所在庫區的單位能量消耗因子作為權值因子[4]，即：

Step4：經過Step3得到的分區可能部分小區的貨位數不能滿足實際的需要。則要進行修正，修正的原則是“就近取多補少”，也就是說如果某個區的貨位數較少，則從相鄰的庫區取貨。

2.2遺傳算法求解庫區分配的優化問題

遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法，目前遺傳算法在解決組合優化問題時，操作簡便、魯棒性強，因此在解決指派問題中得到了廣泛應用[5]。本文構造了求解該問題的遺傳算法。

（1）編碼。在本文中編碼采用順序表達法。其意義舉例如下：設某倉庫分為6個區存放6類貨物，用順序表達法時某個個體為[135246]，該個體表示第1個庫區放第1類貨物，第2個庫區放第3類貨物。依次類推。

（2）構造適應度函數。

（3）初始種群的產生。隨機建立有n個元素的數組（n為庫區的個數），其中該數組中的元素互不相同。

（4）選擇操作。在選擇操作中采用輪盤賭機制。

（5）交叉操作。首先是任何在雙親中指派到相同位置的貨物在后代中仍占據這個位置，然后對于剩下的位置從雙親中指派到該位置的兩類貨物中隨機選一類貨物，要按照從左到右的順序進行。最后將剩下的未指派的貨物分派給尚空閑的位置。

（6）變異操作。采用逆變異，即隨機選擇某個體兩個位置，并將兩點間的順序交換。

3貨位分配優化策略

貨位分配的主要目標是處理任意調度貨物時，最大限度地縮短行走時間。首先對貨架進行扇形分區，通過遺傳算法實現庫區進行優化分配。然后在貨物找到相應的庫區后按照貨位優化策略尋找最優貨位。

3.1貨位分配優化問題的數學模型

上述模型中，式（6）依據貨位分配策略中上輕下重的原則。即進行入庫操作時，重物應放在倉庫中的下部貨架，輕的放在上部的貨架，使貨架受力穩定。式（7）依據貨位分配策略中的最短路線原則。即對于出/入庫操作，找到貨物所在的貨位分區后，將離出入庫臺最近的貨位作為出庫貨位。式（8）為在不考慮堆垛機啟動和制動的情況下，將第i列第j層貨位上的貨物搬運到出入庫臺所用的時間。

3.2Pareto遺傳算法求解貨位配置優化問題

貨位的分配需要同時考慮貨架穩定性和出入庫效率，這是一個多個目標函數的優化問題。本文將Pareto最優解的概念與遺傳算法相結合， 提出了一種改進的解決多目標優化問題的Pareto遺傳算法[6]。通常的多目標優化問題大多都有很多個Pareto最優解。傳統的GA在遺傳操作中包括三個算子：選擇、交叉、 變異[7]。Pareto GA在此基礎上還有小生境技術、Pareto解集過濾器和精英保存三個算子。其主要運算過程如下：

（1）編碼。根據貨位的特點，采用p×q矩陣對解進行編碼，如果矩陣的第i行j列位置的元素為m，則表示編號為m的貨物放在貨架的第q+1-i層j列上。

（2）計算適應度值。適應度值為當代中兩個目標函數的最大值減去該個體的目標函數值。

（3）選擇算子。選擇算子之前要對群體進行并列選擇過程和群體分級操作。并列選擇過程：將整個群體均等地劃分為兩個子群體，分別在兩個目標函數的相應子群體中產生數量相同的兩個子種群。群體分級：為了得到最優解，在進行選擇運算之前，需要根據個體的非劣解水平將種群分級。具體實現方法為：將種群中的所有非劣解個體劃分為同一級，并賦予等級為1。重復上述過程，直到種群中所有個體都被賦予相應的級別為止。在選擇過程中，第i級的點的選擇概率可以由下式確定：

（4）交叉操作。在遺傳算法中，通常隨機選擇兩個個體進行交叉操作。針對論文提出的多目標優化問題，引入了交配限制策略[1]。只有當兩個個體不在同一群體時，才能進行交叉操作。按照這種方式，不同目標函數下的優良基因可以進行充分組合，能以較大的概率找到各個目標性能均較好的折衷解。根據貨位優化配置問題的目標函數值直接取決于貨物在貨架上的位置，交叉操作中采用了部分匹配交叉算法。

（5）變異操作。變異算子依概率選擇一部分個體實施變異，隨機選擇兩個貨位，把這兩個貨位上的貨物進行對換。

（6）小生境技術。為了保證尋優過程不收斂于可行域的某一局部，使種群向均勻分布于Pareto前沿面的方向進化，需要通過共享函數定義一小生境加以實現。然后對種群中聚集成小塊的個體施加懲罰，使其適應度值減小。

（7）精英保存策略。為保留種群進化過程中出現的最優個體，將父代種群和子代種群合并為一個種群，對該種群中的個體進行群體排序和共享函數懲罰。然后根據非劣點級別的高低、共享后個體適應度的高低，將種群中靠前的50%個體作為新的種群進行下一輪進化。采用上述技術和策略的遺傳算法不僅可以收斂于多目標優化問題的Pareto解，而且可以保證其分布較為均勻[8]。

（8）Pareto解集過濾器。其作用是將每一代中的非劣點保留下來，同時去掉解集中的劣點。每一代中級別定為1的點都放入Pareto過濾器。Pareto解集的規模可以任意設定。當新點的數量超過規定的Pareto解集的規模時，再進行一次排序，剔除掉其中的劣點。如果剩下的非劣點的數量仍超過Pareto解集的規模，再刪除那些與其它點距離最近的點。

3.3改進的解決多目標優化問題的Pareto遺傳算法步驟

Step2：構造適應度函數并計算各點的適應度；

Step3：利用非劣點的定義對群體分級；

Step4：進行遺傳操作：選擇、交叉、變異、小生境，生成新群體；

Step5：依據這2M個個體的新適應度對各個個體進行降序排序，記憶前M個個體；

Step6：取出級別為1的點，放進Pareto解集過濾器；

4仿真實驗及分析

在表2中，第二列表示貨物編號為1的1類貨物所需要的貨位數為95個，其作業概率為30%，貨物質量為60kg/個。依次類推，已知每種貨物所需要的貨位數、作業概率和貨物的質量，通過用C語言編寫庫區分配的優化程序，可以得到該類貨物存放的庫區號。仿真結果為3類貨物存放在A區，1類貨物存放在B區，5類貨物存放在C區，2類貨物存放在D區，4類貨物存放在E區。貨物質量越大、出入庫頻率越高表示貨物存放在貨架低層、離出入口越近的貨位上的可能性越大。剩余的貨位填充到每個小區末尾，作為備用貨位，以防臨時增加該區物料或方便以后盤庫。按照出庫頻率高的庫區對應優先級高的貨位區的原則，用遺傳算法找到某類貨物的庫區，然后在對應的庫區用Pareto最優解集進行計算，使貨位得以合理分配。

按照貨物的出入庫頻率做以下假設：共有100個貨物要進行出入庫操作，其中1類貨物和3類貨物各30個，2類和4類貨物各10個，5類貨物20個。若按照傳統的順次排放策略，S=23 180kg，T

=1 133s。采用上述算法分配貨位，可以為用戶提供多個Pareto最優解，用戶可根據貨架的承重能力和倉庫的實際運行情況確定最終解。我們選擇其中一組解進行實驗驗證得到S=20 950kg，T=987.2s。由此結果看出在降低貨架重心的同時，總體出入庫效率有較大幅度的提高，提高了自動化立體倉庫的存取效率。優化后的貨位的分布圖如圖1所示。該圖中顏色最深的小方框表示在此位置存放了貨物。顏色的深淺代表了不同的庫區。

5結論

本文重點討論研究了立體倉庫庫區和貨位的分配優化策略，提出立體倉庫的庫區優化數學模型。在庫區優化基礎上，提出貨位優化數學模型，對采用改進遺傳算法Pareto GA解決貨位優化問題進行了分析。其中在庫區優化控制策略中，我們在建立數學模型時綜合考慮了貨物的質量和出入庫頻率，將貨物按照出入庫頻率和質量分類，根據貨物的分類編號，將貨架進行扇形分區。貨物按質量和需求頻度由大到小進行排序形成不同的優先級對應于優先級不同的庫區，部分小區的貨位數不能滿足實際的需要的，按照 “就近取多補少”原則進行修正；在貨位優化控制策略中，我們同時考慮了貨架穩定性和出入庫頻率，這是一個多個目標函數的優化問題，在本文提出的方案中采用Pareto最優解的概念與遺傳算法相結合的改進算法，其涉及群體分級、小生境技術、Pareto解集過濾器和精英保存技術。

通過仿真實驗及分析可以看出本文提出的采用改進遺傳算法優化策略可以有效地解決自動化立體倉庫的貨位分配問題，提高了出入庫操作的執行效率。

參考文獻：

[1] 商允偉，裘聿皇，劉長有. 自動化倉庫貨位分配優化問題研究[J]. 計算機工程與應用，2004(26):16-18.

[2] 柳賽男，柯映林，李江雄，等. 基于調度策略的自動化倉庫系統優化問題研究[J]. 計算機集成制造系統，2006，12(9):1438

-1443.

[3] E Zitzler， L Thiele. Multiobjective evolutionary algorithm a comparative case study and the strength Pareto approach[J]. IEEE Trans on Evolutionary Computation， 1999，3(4):257-271.

[4] 銀光球，何福英. 自動化立體倉庫中庫位優化模型研究[J]. 福建工程學院學報，2006，4(3):347-351.

[5] 周明，孫樹棟. 遺傳算法原理及應用[M]. 北京：國防工業出版社，1999.

[6]Carlos F M， Peter F J. An overview of evolutionary algorithms in multiobjective optimization[J]. Evolutionary Computation， 1995，3(1):1-16.

[7] 趙振華，王杰，婁春元. 基于遺傳算法的帶時間窗約束車輛路徑問題研究[J]. 物流科技，2007(2):92-95.

[8] 費燁，李楠楠，韓澤光. 基于Pareto解集的多目標優化方法及其應用[J]. 起重運輸機械，2006(9):13-15.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。