一種多巷道立體倉庫貨位分配優化方法

陳港生，謝家翔，付建林，丁國富

（西南交通大學 機械工程學院，成都 610031）

0 引言

隨著計算技術、人工智能等的快速發展，制造業公司的競爭也日益加劇，同時公司內對先進生產技術的需求也越來越迫切。在“德國工業4.0”的驅動下，傳統的生產制造業正不斷地向智慧生產過渡，而發展建設智能倉儲是“工業4.0”的三大主題之一，也是“中國制造2025”的關鍵內涵[1]。立體倉庫作為現代智能物流重要部分，合理優化立體倉庫貨物貨位可以有效縮短堆垛機工作時間、提高工作效率、降低企業生產物流成本。

對于立體倉庫貨位分配問題，許多國內外學者進行了較為深入的研究，遺傳算法、粒子群算法等啟發式算法被大量運用于貨位分配問題求解，優化目標常集中于產品出入庫效率、貨架穩定性、產品之間的聚集程度等。黃鵬等[2]面對大規模立體倉庫貨位分配問題，提出了一種兩階段混合算法，引入貪婪交叉算子，通過實驗證明了算法的優越性；蔡安江[3]等關于雙向式立體倉庫貨位分配問題，給出了一種改進混合蛙跳算法；焦玉玲等[4]以產品出入庫效率、倉庫貨架穩定性和產品集中程度，設計了一種多種群遺傳算法來提高標準遺傳算法提前收斂問題，由于該問題面對的是立體倉庫單一巷道內貨位分配問題，因此本文在此基礎上，把立體倉庫貨位分配問題推廣至多巷道；Xie等[5]針對分組條件下的貨位分配問題，設計了一個雙層分組優化模型，針對該模型提出了一種多階段隨機搜索方法和禁忌搜索算法；Tu等[6]針對考慮補貨時間約束以及工作負載均衡的貨位分配問題，提出了一種具有隨機系數的啟發式多目標遺傳算法；Bessenouci等[7]以作業時間為優化目標，運用模擬退火算法和禁忌搜索算法的混合算法解決了貨位分配的動態調整問題，并對混合算法的實驗參數進行了敏感性實驗；Li等[8]以產品出入庫效率、貨架穩定性為優化目標，提出了一種新型帕累托遺傳算法，得到了比較滿意的結果。

不難看出，在研究貨位分配問題時，大多數研究者都以倉庫貨架穩定性、產品出入庫效率以及產品之間的集中程度為優化目標，研究重心在倉庫某一排貨架上的貨位分配問題，而忽略了貨物分巷道存放導致最終分配的結果使得堆垛機作業量大、巷道擁堵、作業效率低下等問題。為此，本文考慮到多巷道貨位分配問題中的堆垛機負載均衡原則，構建了立體倉庫多排貨架貨位分配多目標優化模型，并根據遺傳算法存在的局部搜尋能力差、提前收斂等缺陷，給出了含進化逆轉的自適應多種群遺傳算法；最后仿真實驗結果表明，相比于標準遺傳算法，該算法尋優速度更快、分配結果更加合理，能夠很好地解決立體倉庫貨位分配問題。

1 模型建立

1.1 問題描述及模型假設

多巷道自動化立體倉庫主要由多排高層貨架、堆垛機械、出入庫臺和周邊運輸設備（如傳送帶、AGV等）組成。為提高倉庫的管理效率，一方面可以優化立體倉庫布局，另一方面可以考慮優化立體倉庫貨位分配，但在企業中立體倉庫的布局往往是已經提前設置好了，想要更改變得較為困難，因此對立體倉庫內貨物的貨位進行優化是一種提高倉庫作業效率、降低堆垛機運行作業成本的有效方法。本文以某企業小型零部件立體倉庫為研究對象，綜合考慮貨物的出入庫效率、貨架整體穩定性、堆垛機負載均衡原則。在此立體倉庫中，每巷道內都有一個堆垛機承擔著巷道內左右兩排貨架上貨物的存放，倉庫布局如圖1所示。

圖1 立體倉庫布局簡圖

針對立體倉庫貨位分配遇到的相關問題和應遵循的原則，為了方便建立數學模型和研究問題，現對立體倉庫做出如下假設：

1）假設某倉庫總共有a排、b層、c列貨架。所有貨位長、寬、高尺寸相等均為L。

2）貨物存放在托盤中，每個貨位只能存放一個托盤。

3）堆垛機的運行速度恒定，用Vy、Vz表示堆垛機在水平和垂直方向上的運行速度。

4）只考慮貨物質量，不考慮貨架質量。

1.2 建立貨位分配多目標優化模型

用（x，y，z）表示貨物在貨架中分配的貨位位置信息，其中，x為貨物所在貨架排數，y為該排貨架所對應的列數，z為該排貨架對應的層數，它們決定著貨位分配的最終結果；用Pk表示入庫訂單中第k個貨物的周轉率，Mk表示入庫訂單中第k個貨物的質量，它們是貨物分配優化的輸入參數；N表示一批入庫訂單中待入庫貨物總數；引入決策變量Skxyz用來判斷第k個貨物是否存放在（x，y，z）貨位中，若是則為1，否則為0。

1）建立以出入庫效率最高為目標的函數F1。

為滿足立體倉庫快速響應出入庫需求，要求將出入庫頻率高的貨物放在靠近出入口位置，從而縮短堆垛機的工作時間，提高系統運行效率，即堆垛機完成某一貨物的作業時間與該貨物的出入庫頻率的乘積最小，則構建目標函數為

2）建立以貨架穩定性為原則的目標函數F2。

為了保證倉庫內貨架的安全性，貨架上貨物的存放因滿足“下重上輕”原則，避免貨架因重心失衡而造成傾倒。大多學者都以貨物的質量與其所在層數的乘積之和最小為優化目標，但針對的是倉庫某一巷道內堆垛機負責的兩排貨架的穩定性，并未考慮當立體倉庫存在多臺堆垛機同時工作時該倉庫內所有貨架的整體穩定性。因此，本文設計了考慮立體倉庫內多臺堆垛機同時工作時所有貨架整體等效重心最小的目標函數式為

3）建立堆垛機負載均衡的目標函數F3。

為了降低堆垛機的負載，同時提升倉庫的作業效率，因此要求均衡各個巷道內貨物的出入庫量，將一批入庫訂單中的貨物分散地放在不同巷道內的貨架上，以防止貨物在某個巷道內大量堆積，而造成整個巷道堵塞，從而降低了堆垛機的作業效率，不利于倉庫運作。建立的函數表達式如式（3）～式（6）所示：

式中：Ox表示第x排貨架上存放的貨物周轉率之和，Qi表示第i個巷道內存放貨物的周轉率之和，表示一批訂單中所有貨物的周轉率的平均值，ni表示每個巷道內分配的貨位數。

可以看出該目標函數式以堆垛機作業的每個巷道為對象，考慮了每個巷道內出入庫頻率均衡和該巷道內貨物的數量均衡，能很好地反映每個巷道內堆垛機的負載情況。

由于此優化問題是多目標優化問題，因此為了方便計算，需要將多目標函數轉化為單目標函數，并根據倉庫的實際情況確定相關系數。

2 算法設計

遺傳算法（Genetic Algorithm,GA）是通過仿造自然科學界中的“物競天擇，適者生存”的發展規則，從隨機得到的一組候選解出發，經過染色體的選擇、交叉、變異，從而產生性能更為優良的下一代群體，通過不斷地循環迭代搜索，最終尋找到最優解[9-10]。遺傳算法全局搜尋能力很強，而局部搜尋能力薄弱。因此，本文提出了一種自適應多種群遺傳算法（Adaptive Multi-population Genetic Algorithm,以下簡稱AMPGA）以改善傳統的遺傳算法，同時，引入進化逆轉算子提高其局部搜尋能力。

2.1 算法流程

AMPGA則是在GA的基礎上，增加了自適應選擇、交叉算子以及進化逆轉算子，并將之推廣到了各個種群群體中，各個群體在進化的過程中不斷地完成個體遷移。為了確保各群體的最優個體不被破壞和損失，通過人工選擇算子篩選出各代種群中的最優個體放入精英種群中加以保存。AMPGA的算法結構示意圖如圖2所示。

圖2 AMPGA算法流程圖

2.2 算法實現

1）編碼。在本文研究問題中采用十進制編碼，每個自然數代表一個貨位。將隨機產生的自然數進行編號，然后用編號的先后順序代表任務訂單所分配的貨位位置。以立體倉庫第一排7×6的貨架為例，如圖3所示，如數字16代表分配貨位坐標為（1，2，3），即分配位置為第一排、第二列、第三層貨架。

圖3 貨位分配示意圖

2）產生初始種群。根據倉庫可用貨位n，隨機生成1～n的自然數序列代表一個個體的貨位分配結果，按照此方法，產生R個種群，每個種群包含P個個體。

3）計算適應度值。根據一批入庫訂單總數N，取每個個體中前N個自然數代表分配的N個貨位，根據分配的貨位計算相應的目標函數值，適應度函數Ffit=1/(1+F)，其中Ffit是每個個體的適應度值，F為多目標優化函數化為單目標函數后的值。

4）選擇。為保證上一代最優個體能順利保存下來，按照個體的適應度值大小來進行優勝劣汰操作，采用輪盤賭選擇和精英保留策略。

5）交叉。Srinvas等[11]提出了一種線性自適應遺傳算法（Adaptive Genetic Algorithm,以下簡稱AGA）,將個體的交叉率和變異率隨個體的適應度值進行線性調整，得到了比較好的收斂效果。但是，該方法在演化初期時存在停滯的缺陷，這不利于算法的迭代優化，容易導致算法陷入局部最優，提前收斂。石山等[12]通過對AGA的調整，將交叉率和變異率以余弦方式進行自適應調整，有效地避免了AGA存在的問題，構造的算子為：

式中：fmax表示種群中最大適應度值，favg表示該種群平均適應度值，Pcmax和Pcmin分別為交叉率的上限和下限，f′表示要交叉的兩個個體中較大的適應度值，Pmmax和Pmmin分別為變異率的上限和下限，f表示要變異個體的適應度值。

本文使用余弦改進型自適應遺傳算子，并將其運用到多個種群中。目前常用的交叉方式有單點交叉、兩點交叉和順序交叉，為了體現種群的多樣性，本文將3種交叉方式同時用于多個種群中，每個種群隨機選擇一種交叉方式進行交叉。交叉的具體過程如圖4所示。

圖4 常見的3種交叉方式

6）變異。為防止非法解的產生，目前普遍采用的變異方法為兩點位置互換變異，即在要變異的個體上隨機產生兩個突變的位點，使其基因位點順序對調。

7）進化逆轉。為繼續提升遺傳算法的局部搜尋能力，在完成變異后引入進化逆轉，即在個體染色體上隨機產生兩個位點，將兩點區間內的順序倒置。與變異不同的是，變異是隨機的，而這里的“進化逆轉”是單方向性的，只有逆轉后個體適應度值有提升才有效被接受，否則逆轉無效不被接受。

8）個體遷移。個體遷移機制具體步驟如下：

Step 1：對種群個體適應度值按照從優到劣進行排序。

Step 2：設i=1。

Step 3：用第i個種群中的最優個體取代第i+1個種群中的最劣個體。

Step 4：令i=i+1。判斷i是否等于種群數，如果是則轉Step 5，否則轉Step 3。

Step 5：將最后一個種群的最優個體取代第一個種群的最劣個體。

9）算法終止條件。將人工選擇的最優個體放入精英種群。算法終止條件采用雙重收斂判據，即達到最大迭代次數或者精英種群中最優個體保持代數時算法終止。

3 仿真實驗

3.1 實驗參數設定

以某企業小型零部件立體倉庫為研究對象，來驗證所建模型的有效性和算法的優越性。該倉庫共有6排貨架，每排貨架有6層、每層10列，共有6×6×10=360個貨位。根據層次分析法以及綜合考慮立體倉庫的實際情況，將目標函數1至目標函數3的權重分別設置為：ω1=0.375、ω2=0.372、ω3=0.253, 堆垛機水平速度Vx=2.5 m/s,垂直速度Vy=1.5 m/s,貨架長L=1m,寬W=1 m，高H=1 m。本文選用SGA和未含進化逆轉算子以及自適應選擇、交叉算子的MPGA和含進化逆轉算子和自適應選擇、交叉算子的AMPGA進行實驗。SGA、MPGA和AMPGA算法的實驗參數設置如表1所示。

表1 3種算法實驗參數設定

3.2 實驗結果及分析

根據該企業入庫訂單中50個待入庫貨物樣本數據，分別采用上述3種算法進行仿真實驗，表2是3種算法的實驗結果，表3是入庫貨物訂單數據及優化后貨位數據，圖5是3種算法目標函數值隨迭代次數的變化曲線，圖6是優化后的貨物分布圖。

表2 3種算法實驗結果比較

表3 入庫貨物訂單信息及優化前后貨物貨位信息

圖5 目標函數隨迭代次數變化圖

圖6 50個訂單優化后貨物分布

從圖5可見，貨位分配的歸一化多目標函數值隨迭代次數的增加而逐漸減小，在迭代0～380次左右時精英種群最優個體的保持代數都小于事先設定的值，迭代次數大于380次時，歸一化的目標函數值曲線趨于水平，直到最后達到精英種群最優個體保持代數時算法收斂。從表3和圖6的結果可以發現，周轉率較大的貨物被分配在離出入庫口近的貨位上，低的被分配在了相應稍遠的位置，符合出入庫效率要求；從整體貨架的穩定性考慮，質量大的貨物被分配到了貨架底層位置，而質量小的被分在了高層；從堆垛機的負載情況來看，每個巷道內貨架上的貨物分配基本均衡，滿足堆垛機負載均衡；上述結果從側面證明了本文所建立優化模型的有效性。從表2可見，采用多種群遺傳算法的優化結果比SGA 提高了6.03%，但使用余弦自適應多種群遺傳后其優化結果提高了9.03%，且由于引入了自適應交叉、變異算子，其收斂速度更快，有效地提高了求解速度和求解精度。

為了更加完全、準確地評價改進后AMPGA的優化性能，在不同規模訂單下進行了50次循環實驗，每個訂單貨物的質量和周轉率都是有差異的，算法的平均實驗結果如表4所示。

表4 3種算法的實驗結果

從表4中的實驗數據可以分析出，在不同規模訂單下，3種算法的優化程度有著不同的區別，MPGA相比于SGA少2%～12%，AMPGA相比于SGA少2%～14%，且AMPG A優化程度比MPGA更顯著。AMPGA在大規模訂單下其優勢相對于SGA更為明顯，同時在收斂耗時方面，AMPGA耗時短、收斂快，能夠更快得到最優解，因此AMPGA更適合大規模立體倉庫貨位分配優化問題。

4 結語

本研究針對多巷道立體倉庫貨位分配優化問題，綜合考慮了出入庫效率、貨架穩定性與堆垛機負載均衡，建立了多巷道立體倉庫貨位分配優化的多目標函數模型，并設計了一種自適應多種群遺傳算法（AMPGA）來優化立體倉庫中貨位分配。通過實驗仿真驗證了所建模型的有效性，比較不同訂單規模下3種算法的貨位分配結果，結果顯示AMPGA算法在大規模訂單下優化效果更佳，收斂更快，能夠很好地解決多巷道立體倉庫貨位分配問題。