基于遺傳算法的自動(dòng)化立體倉(cāng)庫(kù)貨位優(yōu)化

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

（江蘇大學(xué) 汽車與交通工程學(xué)院，江蘇 鎮(zhèn)江 212013）

0 引言

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

貨位優(yōu)化可以有效提高存儲(chǔ)的系統(tǒng)效能。何李，等將貨位分配與作業(yè)調(diào)度集成優(yōu)化，提出兩階段狼群算法，能夠較好地滿足柔性化訂單。張延華，等兼顧算法的全局搜索能力和局部搜索能力，引入模擬退火算法，有效提高了算法的收斂速度。Haiping Ma，等針對(duì)自動(dòng)化立體倉(cāng)庫(kù)的調(diào)度問(wèn)題，提出了一種基于集成學(xué)習(xí)的集成多目標(biāo)生物地理學(xué)優(yōu)化（EMBBO）算法。Yu ling Jiao，等則證明了多種群遺傳算法的結(jié)果優(yōu)于簡(jiǎn)單加權(quán)遺傳算法的結(jié)果。

綜上所述，目前國(guó)內(nèi)外學(xué)者缺少對(duì)優(yōu)化結(jié)果的驗(yàn)證或者對(duì)優(yōu)化結(jié)果的驗(yàn)證較為簡(jiǎn)單?？紤]到Flexsim軟件能高效直觀地驗(yàn)證優(yōu)化結(jié)果的有效性，可以達(dá)到一般數(shù)字證明無(wú)法實(shí)現(xiàn)的實(shí)際運(yùn)行效果，因此本文以入庫(kù)效率和貨架穩(wěn)定性為目標(biāo)函數(shù)建立多目標(biāo)優(yōu)化數(shù)學(xué)模型，提出一種非線性規(guī)劃的改進(jìn)遺傳算法，為入庫(kù)的貨物分配最佳的貨位，并通過(guò)Flexsim建模驗(yàn)證該算法的有效性。

1 貨位分配模型

1.1 問(wèn)題描述

以某汽車零部件企業(yè)的自動(dòng)化立體倉(cāng)庫(kù)為例，該企業(yè)的貨位分配采用隨機(jī)存儲(chǔ)的方式。但由于汽車零部件種類多、數(shù)量大，該倉(cāng)庫(kù)出入庫(kù)作業(yè)效率十分低下，而且貨位分配不合理，貨架穩(wěn)定性差。首先對(duì)上述汽車零部件物流企業(yè)的自動(dòng)化立體倉(cāng)庫(kù)進(jìn)行分析，以明確貨位優(yōu)化目標(biāo)。

為方便研究作出如下假設(shè)：（1）出入庫(kù)口為（0，0）；（2）每個(gè)貨格的基本參數(shù)（長(zhǎng)度、寬度、重量）相同且適宜，貨格為標(biāo)準(zhǔn)的正方體；存儲(chǔ)貨物后，該貨位的幾何中心即為該貨位的重心（貨物重量對(duì)貨架穩(wěn)定性帶來(lái)的影響忽略不計(jì)）；每個(gè)貨格能且只能存儲(chǔ)一個(gè)貨箱；（3）堆垛機(jī)在不同方向上的運(yùn)動(dòng)是獨(dú)立的，堆垛機(jī)以最大速度勻速運(yùn)行（忽略其啟動(dòng)和制動(dòng)），且不考慮各種摩擦阻力的影響；（4）堆垛機(jī)一次僅能搬運(yùn)一個(gè)貨物；（5）不考慮取、放貨時(shí)堆垛機(jī)的滯留時(shí)間；（6）忽略貨架重量；（7）運(yùn)行時(shí)速度不考慮貨物重量。

1.2 模型符號(hào)說(shuō)明

：貨架列數(shù)；

：貨架層數(shù)；

：貨架個(gè)數(shù)；

：貨架的標(biāo)號(hào)；

：堆垛機(jī)的總運(yùn)行時(shí)間；

f：一個(gè)周期內(nèi)在第w排貨架第i列第j行的某個(gè)貨位的存取貨物頻數(shù)；

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

v：堆垛機(jī)的水平速度；

v：堆垛機(jī)的豎直速度；

v：堆垛機(jī)的垂直提升速度；

t：堆垛機(jī)從出入庫(kù)口到取貨位所用的時(shí)間；

m：在第w個(gè)貨架第i列第j層的貨品的質(zhì)量；

：堆垛機(jī)水平運(yùn)動(dòng)的距離；

：貨位單位長(zhǎng)度；

：巷道寬度；

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

1.3 模型的建立

根據(jù)上述的模型假設(shè)以及參數(shù)設(shè)定，建立多目標(biāo)的自動(dòng)化立體倉(cāng)庫(kù)貨位分配模型：

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

堆垛機(jī)運(yùn)行的總時(shí)間為：

堆垛機(jī)從出入庫(kù)口到取貨位所用的時(shí)間表達(dá)式為：

其中，堆垛機(jī)的水平位移為：

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

在人行天橋的應(yīng)用中，根據(jù)城市發(fā)展需要，可能需要對(duì)橋梁結(jié)構(gòu)進(jìn)行改造，鋼結(jié)構(gòu)拆裝便捷，并且污染比較小，回收利用價(jià)值較高。

保障倉(cāng)庫(kù)穩(wěn)定性的目標(biāo)函數(shù)為：

式（4）計(jì)算的是各貨位重心與質(zhì)量之積的和，當(dāng)某個(gè)貨位上沒(méi)有貨物時(shí)，m的值為0。

綜上所述，該倉(cāng)庫(kù)的貨位分配模型為：

2 模型求解

2.1 算法的選擇

（1）遺傳算法。遺傳算法在計(jì)算多目標(biāo)優(yōu)化問(wèn)題上有較好的表現(xiàn)，它可以在自然環(huán)境的前提下提高自身的優(yōu)越程度。這一過(guò)程首先使用染色體表示種群中的個(gè)體，通過(guò)某個(gè)種群中的個(gè)體再進(jìn)行模擬進(jìn)化，實(shí)現(xiàn)達(dá)爾文進(jìn)化論中的“優(yōu)勝劣汰，適者生存”。遺傳算法的主要特征：它是種群中個(gè)體的適應(yīng)度，當(dāng)進(jìn)行適應(yīng)度評(píng)估時(shí)，會(huì)通過(guò)執(zhí)行交叉、適應(yīng)度比例再生以及變異操作生成新的種群，每次迭代，都會(huì)用新的種群來(lái)替代舊的種群。

遺傳算法的優(yōu)點(diǎn)為：可從多個(gè)初始點(diǎn)切入，按照不同的方法進(jìn)行搜索來(lái)實(shí)現(xiàn)全局最優(yōu)；可以高效的處理多目標(biāo)優(yōu)化問(wèn)題，相當(dāng)于在搜索范圍內(nèi)對(duì)多個(gè)解進(jìn)行結(jié)果評(píng)估，更快跳出局部最優(yōu)解，同時(shí)該算法本身易于實(shí)現(xiàn)并行化；可從問(wèn)題解的串集開(kāi)始搜索，而不是從單個(gè)解開(kāi)始，覆蓋面大，利于全局擇優(yōu)；可以通過(guò)概率機(jī)制進(jìn)行迭代，使得多目標(biāo)的解具有隨機(jī)性。

（2）非線性規(guī)劃。非線性規(guī)劃是求解規(guī)劃問(wèn)題的一種方法，它能夠求出目標(biāo)函數(shù)的最優(yōu)結(jié)果，也能在出現(xiàn)非線性函數(shù)的約束條件下求最優(yōu)解。它是在多種有一定關(guān)系的變量下，變量與約束條件相互對(duì)應(yīng)，計(jì)算或得出一個(gè)問(wèn)題的線性目標(biāo)函數(shù)最優(yōu)解。

根據(jù)以上兩種算法的特點(diǎn)，本文設(shè)計(jì)了基于遺傳算法嵌套非線性規(guī)劃的求解方法，進(jìn)行多目標(biāo)的貨位分配模型求解。

2.2 操作流程

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

（3）適應(yīng)度函數(shù)的建立。在上述模型中本文已經(jīng)建立兩個(gè)求解最小值的目標(biāo)函數(shù)，在實(shí)際的求解過(guò)程中，本文將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)，通過(guò)加權(quán)算法來(lái)平衡兩個(gè)目標(biāo)函數(shù)對(duì)整體結(jié)果的影響。

（4）選擇操作。將種群中適應(yīng)度高的個(gè)體選出，遺傳給下一代種群，以此進(jìn)行循環(huán)操作，進(jìn)行不斷的迭代，迭代達(dá)到一定次數(shù)后使得優(yōu)化后的個(gè)體更進(jìn)一步的靠近目標(biāo)函數(shù)的最優(yōu)解。用適應(yīng)比例方法（見(jiàn)式（9）進(jìn)行選擇操作，選擇概率大的個(gè)體。

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

（6）終止條件。將最大的迭代次數(shù)設(shè)置為100，得到最后一代種群中適應(yīng)度最高的解，即為算法得出的最優(yōu)解。

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

圖1 算法流程圖

3 應(yīng)用實(shí)例

3.1 參數(shù)設(shè)定

為了研究方便，本文選取該汽車零部件自動(dòng)化立體倉(cāng)庫(kù)的一部分：3列9層6排作為研究對(duì)象。堆垛機(jī)的水平移動(dòng)速度v為2m/s，堆垛機(jī)的豎直移動(dòng)速度v為2m/s，垂直移動(dòng)速度v為0.5m/s。貨位單位長(zhǎng)度L為1.1m，巷道寬度為1.5m。貨物分類及其參數(shù)見(jiàn)表1。

表1 貨物分類及其參數(shù)

3.2 仿真結(jié)果

使用MATLAB對(duì)模型進(jìn)行求解，得到圖2和表2。圖2中虛線為遺傳算法的求解結(jié)果，實(shí)線為改進(jìn)遺傳算法的求解結(jié)果，可以明顯看出改進(jìn)遺傳算法的目標(biāo)函數(shù)值更優(yōu)且迭代次數(shù)更少。改進(jìn)遺傳算法在32次迭代時(shí)就已經(jīng)接近最優(yōu)解，此時(shí)的函數(shù)值為7 200左右，而遺傳算法在70次迭代后才接近最優(yōu)解，函數(shù)值在7 800左右。

表2 貨位分配結(jié)果

圖2 遺傳算法與改進(jìn)遺傳算法的各代平均值

優(yōu)化結(jié)果見(jiàn)表3將優(yōu)化前后的函數(shù)目標(biāo)值進(jìn)行對(duì)比，與隨機(jī)入庫(kù)相比，優(yōu)化后的函數(shù)值分別降低了34.35%和30.78%，加權(quán)后的總目標(biāo)函數(shù)值降低了31.66%。倉(cāng)庫(kù)的貨位分配主要集中在倉(cāng)庫(kù)的入口和貨架的底層，極大地提高了入庫(kù)效率和貨架穩(wěn)定性。

表3 優(yōu)化前后函數(shù)目標(biāo)值對(duì)比

3.3 Flexsim模型驗(yàn)證

具體實(shí)體種類及實(shí)現(xiàn)的功能見(jiàn)表4。

表4 模型實(shí)體種類及其功能

倉(cāng)庫(kù)模型中所需要的具體機(jī)械設(shè)備有：?jiǎn)卧浉袷截浖?0個(gè)；傳送帶18條；自動(dòng)堆垛機(jī)5個(gè)；機(jī)器人6個(gè)；貨格2 700個(gè)，倉(cāng)庫(kù)布局如圖3所示。

圖3 倉(cāng)庫(kù)仿真布局圖

將Flexsim仿真模型運(yùn)行8h，輸出運(yùn)行結(jié)果，得到實(shí)體的停留時(shí)間、阻塞時(shí)間、限制時(shí)間等數(shù)據(jù)，匯總見(jiàn)表5。分析表5數(shù)據(jù)可以看出，通過(guò)貨位分配，自動(dòng)化立體倉(cāng)庫(kù)設(shè)備利用率較高，不存在阻塞現(xiàn)象，系統(tǒng)可以有效持續(xù)運(yùn)行。

表5 匯總統(tǒng)計(jì)表

4 結(jié)語(yǔ)

本文提出一種改進(jìn)遺傳算法，在JIT背景下對(duì)汽車零部件自動(dòng)化立體倉(cāng)庫(kù)進(jìn)行貨位分配優(yōu)化。在提高自動(dòng)化立體倉(cāng)庫(kù)入庫(kù)效率的基礎(chǔ)上，兼顧貨架穩(wěn)定性構(gòu)建多目標(biāo)數(shù)學(xué)模型。仿真實(shí)例表明，優(yōu)化后的函數(shù)值顯著降低，倉(cāng)庫(kù)系統(tǒng)可以有效運(yùn)行，無(wú)阻塞現(xiàn)象，因此該優(yōu)化方案有較好的應(yīng)用價(jià)值。