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

華祎明，王凱鵬，陳博翱，崔 晶，何美玲

（江蘇大學 汽車與交通工程學院，江蘇 鎮江 212013）

0 引言

隨著信息技術、物流技術和管理技術的不斷發展，世界經濟的進一步全球化，汽車零部件需求呈現出更高的隨機性，因而使得本就需求量龐大、種類繁雜的零件分配任務更加復雜。傳統的汽車零件運輸模式已經很難適應如今快節奏、個性化的市場需求，因此，很多汽車產業公司為提高綜合效益普遍采用了JIT（Just In Time）物流模式。與此同時，由于汽車存儲系統的繁雜性，如何對倉庫的設備進行合理配置以及倉庫存儲模式的選擇便顯得尤為重要。自動化立體倉庫是倉儲物流中出現的新型系統。自動化立體倉庫大多采用混流生產模式下的信息管理中心來實現整體的自動化控制，在優化儲存功能的同時，也大大降低了企業的人員成本。其倉庫布局合理、操作簡便，能夠有效地增強物流作業的質量，從而大大提高了整個系統的工作效率。很多汽車產業公司正在逐步將JIT模式與自動化立體倉庫相結合進行生產和管理，并將不斷發展成為一種完善的物流供應體系。

貨位優化可以有效提高存儲的系統效能。何李，等將貨位分配與作業調度集成優化，提出兩階段狼群算法，能夠較好地滿足柔性化訂單。張延華，等兼顧算法的全局搜索能力和局部搜索能力，引入模擬退火算法，有效提高了算法的收斂速度。Haiping Ma，等針對自動化立體倉庫的調度問題，提出了一種基于集成學習的集成多目標生物地理學優化（EMBBO）算法。Yu ling Jiao，等則證明了多種群遺傳算法的結果優于簡單加權遺傳算法的結果。

綜上所述，目前國內外學者缺少對優化結果的驗證或者對優化結果的驗證較為簡單。考慮到Flexsim軟件能高效直觀地驗證優化結果的有效性，可以達到一般數字證明無法實現的實際運行效果，因此本文以入庫效率和貨架穩定性為目標函數建立多目標優化數學模型，提出一種非線性規劃的改進遺傳算法，為入庫的貨物分配最佳的貨位，并通過Flexsim建模驗證該算法的有效性。

1 貨位分配模型

1.1 問題描述

以某汽車零部件企業的自動化立體倉庫為例，該企業的貨位分配采用隨機存儲的方式。但由于汽車零部件種類多、數量大，該倉庫出入庫作業效率十分低下，而且貨位分配不合理，貨架穩定性差。首先對上述汽車零部件物流企業的自動化立體倉庫進行分析，以明確貨位優化目標。

為方便研究作出如下假設：（1）出入庫口為（0，0）；（2）每個貨格的基本參數（長度、寬度、重量）相同且適宜，貨格為標準的正方體；存儲貨物后，該貨位的幾何中心即為該貨位的重心（貨物重量對貨架穩定性帶來的影響忽略不計）；每個貨格能且只能存儲一個貨箱；（3）堆垛機在不同方向上的運動是獨立的，堆垛機以最大速度勻速運行（忽略其啟動和制動），且不考慮各種摩擦阻力的影響；（4）堆垛機一次僅能搬運一個貨物；（5）不考慮取、放貨時堆垛機的滯留時間；（6）忽略貨架重量；（7）運行時速度不考慮貨物重量。

1.2 模型符號說明

：貨架列數；

：貨架層數；

：貨架個數；

：貨架的標號；

：堆垛機的總運行時間；

f：一個周期內在第w排貨架第i列第j行的某個貨位的存取貨物頻數；

x：堆垛機在第w排貨架第i列第j行的某個貨位有零件存放時為1，否則為0；

v：堆垛機的水平速度；

v：堆垛機的豎直速度；

v：堆垛機的垂直提升速度；

t：堆垛機從出入庫口到取貨位所用的時間；

m：在第w個貨架第i列第j層的貨品的質量；

：堆垛機水平運動的距離；

：貨位單位長度；

：巷道寬度；

：貨架上各貨位重心與質量之積的和。

1.3 模型的建立

根據上述的模型假設以及參數設定，建立多目標的自動化立體倉庫貨位分配模型：

（1）貨物入庫效率分析。將貨物盡可能存放在離入口更近的地方，可以減少堆垛機的搬運時間，從而減少整體的入庫時間。

堆垛機運行的總時間為：

堆垛機從出入庫口到取貨位所用的時間表達式為：

其中，堆垛機的水平位移為：

（2）貨物貨架穩定性分析。作業安全在入庫作業中尤為重要，在入庫作業時，盡量遵循“上輕下重，均勻分配”的原則，降低貨物貨架重心，以提高貨物貨架的穩定性。

在人行天橋的應用中，根據城市發展需要，可能需要對橋梁結構進行改造，鋼結構拆裝便捷，并且污染比較小，回收利用價值較高。

保障倉庫穩定性的目標函數為：

式（4）計算的是各貨位重心與質量之積的和，當某個貨位上沒有貨物時，m的值為0。

綜上所述，該倉庫的貨位分配模型為：

2 模型求解

2.1 算法的選擇

（1）遺傳算法。遺傳算法在計算多目標優化問題上有較好的表現，它可以在自然環境的前提下提高自身的優越程度。這一過程首先使用染色體表示種群中的個體，通過某個種群中的個體再進行模擬進化，實現達爾文進化論中的“優勝劣汰，適者生存”。遺傳算法的主要特征：它是種群中個體的適應度，當進行適應度評估時，會通過執行交叉、適應度比例再生以及變異操作生成新的種群，每次迭代，都會用新的種群來替代舊的種群。

遺傳算法的優點為：可從多個初始點切入，按照不同的方法進行搜索來實現全局最優；可以高效的處理多目標優化問題，相當于在搜索范圍內對多個解進行結果評估，更快跳出局部最優解，同時該算法本身易于實現并行化；可從問題解的串集開始搜索，而不是從單個解開始，覆蓋面大，利于全局擇優；可以通過概率機制進行迭代，使得多目標的解具有隨機性。

（2）非線性規劃。非線性規劃是求解規劃問題的一種方法，它能夠求出目標函數的最優結果，也能在出現非線性函數的約束條件下求最優解。它是在多種有一定關系的變量下，變量與約束條件相互對應，計算或得出一個問題的線性目標函數最優解。

根據以上兩種算法的特點，本文設計了基于遺傳算法嵌套非線性規劃的求解方法，進行多目標的貨位分配模型求解。

2.2 操作流程

（1）編碼方式。編碼方式為整數編碼，即每條染色體代表一個貨位，貨位信息由整數編碼，貨位信息包含貨位的排數、列數、層數信息，基因的值采用整數，表示貨位在立體倉庫中的具體三維坐標。如本模型中（3,2,1）代表的含義是第1排貨架的第3列第2行。

（3）適應度函數的建立。在上述模型中本文已經建立兩個求解最小值的目標函數，在實際的求解過程中，本文將多目標函數轉化為單目標函數，通過加權算法來平衡兩個目標函數對整體結果的影響。

（4）選擇操作。將種群中適應度高的個體選出，遺傳給下一代種群，以此進行循環操作，進行不斷的迭代，迭代達到一定次數后使得優化后的個體更進一步的靠近目標函數的最優解。用適應比例方法（見式（9）進行選擇操作，選擇概率大的個體。

（5）交叉操作與變異操作。將種群里的任意兩個個體，按照一定的概率交換他們內部的部分基因，以此形成新的個體。本文設置的交叉概率為60%；新基因的產生方式是由變異操作來完成，本文設置的變異概率為1%。

（6）終止條件。將最大的迭代次數設置為100，得到最后一代種群中適應度最高的解，即為算法得出的最優解。

圖1為貨位分配的算法流程圖。

圖1 算法流程圖

3 應用實例

3.1 參數設定

為了研究方便，本文選取該汽車零部件自動化立體倉庫的一部分：3列9層6排作為研究對象。堆垛機的水平移動速度v為2m/s，堆垛機的豎直移動速度v為2m/s，垂直移動速度v為0.5m/s。貨位單位長度L為1.1m，巷道寬度為1.5m。貨物分類及其參數見表1。

表1 貨物分類及其參數

3.2 仿真結果

使用MATLAB對模型進行求解，得到圖2和表2。圖2中虛線為遺傳算法的求解結果，實線為改進遺傳算法的求解結果，可以明顯看出改進遺傳算法的目標函數值更優且迭代次數更少。改進遺傳算法在32次迭代時就已經接近最優解，此時的函數值為7 200左右，而遺傳算法在70次迭代后才接近最優解，函數值在7 800左右。

表2 貨位分配結果

圖2 遺傳算法與改進遺傳算法的各代平均值

優化結果見表3將優化前后的函數目標值進行對比，與隨機入庫相比，優化后的函數值分別降低了34.35%和30.78%，加權后的總目標函數值降低了31.66%。倉庫的貨位分配主要集中在倉庫的入口和貨架的底層，極大地提高了入庫效率和貨架穩定性。

表3 優化前后函數目標值對比

3.3 Flexsim模型驗證

具體實體種類及實現的功能見表4。

表4 模型實體種類及其功能

倉庫模型中所需要的具體機械設備有：單元貨格式貨架10個；傳送帶18條；自動堆垛機5個；機器人6個；貨格2 700個，倉庫布局如圖3所示。

圖3 倉庫仿真布局圖

將Flexsim仿真模型運行8h，輸出運行結果，得到實體的停留時間、阻塞時間、限制時間等數據，匯總見表5。分析表5數據可以看出，通過貨位分配，自動化立體倉庫設備利用率較高，不存在阻塞現象，系統可以有效持續運行。

表5 匯總統計表

4 結語

本文提出一種改進遺傳算法，在JIT背景下對汽車零部件自動化立體倉庫進行貨位分配優化。在提高自動化立體倉庫入庫效率的基礎上，兼顧貨架穩定性構建多目標數學模型。仿真實例表明，優化后的函數值顯著降低，倉庫系統可以有效運行，無阻塞現象，因此該優化方案有較好的應用價值。