基于遺傳算法的航天零件倉庫貨位優(yōu)化研究

李 陽，唐 磊，胡 俊

（東華大學(xué) 機(jī)械工程學(xué)院，上海 201620）

0 引言

現(xiàn)代物流將存儲、運(yùn)輸、裝箱搬運(yùn)等信息結(jié)合一體，滿足客戶多樣性的要求。所以，物流在企業(yè)的組成中占有很重要的位置。自動化立體倉庫（AS/RS）管理卻是物流供應(yīng)鏈最關(guān)鍵的一環(huán)，而在立體倉庫管理中，實(shí)現(xiàn)貨位優(yōu)化提高倉庫運(yùn)轉(zhuǎn)效率一直是一個難題，有效的貨位分配能提高貨物出入庫效率和庫位使用率，這是節(jié)省企業(yè)成本的有效途徑。因此，對自動化立體倉庫貨位分配優(yōu)化是一個亟待研究的課題，具有重要的現(xiàn)實(shí)研究價值。

當(dāng)前，國內(nèi)外學(xué)者基于立體倉庫貨位優(yōu)化的問題，已經(jīng)開展大量研究，積累了許多研究方法和實(shí)際應(yīng)用案例[1～6]。常見的貨位分配策略主要有：定位存儲策略、隨機(jī)存儲策略、就近存儲策略、分類存儲策略、共享存儲策略等。Rao等以庫存分布密度為出發(fā)點(diǎn)，提出了一種基于類別的存儲策略，引入優(yōu)化分區(qū)的數(shù)學(xué)模型，計算出非常接近實(shí)際的拾取行程。Paul Berglund提出了一種在解決給定存儲策略下，建立了單跨中通道優(yōu)化布局的解析模型，選擇在交叉通道最佳位置優(yōu)化選擇器移動距離問題的方法。Moghaddam M等在研究動態(tài)存儲分配問題時，基于產(chǎn)品的ABC分類和相互關(guān)聯(lián)性，提出了一種基于產(chǎn)品相似性的啟發(fā)式技術(shù)，極大的提高了平均揀貨時間。李珍萍在研究儲位優(yōu)化問題時，將產(chǎn)品按ABC分類法，提高了揀貨效率和庫存使用率。Kao等對某飲料公司的商品進(jìn)行ABC分類管理，建立大型零售商和小型零售店的經(jīng)濟(jì)訂貨量庫存控制模型，模型仿真證明提高了倉儲管理的效率。Yueting.C等討論了自動化倉庫中存儲區(qū)域的劃分和存儲分配原則，提出了倉庫存儲區(qū)域優(yōu)化的數(shù)學(xué)模型，將出口頻率高的貨物放在靠近貨架出口。

雖然貨位分配優(yōu)化在國內(nèi)外的研究已經(jīng)非常廣泛，但是從以上的綜述可以看出，針對不同的實(shí)際貨位優(yōu)化問題，分配策略的選用是有很大的差異的，而且對雙升式貨架的研究很少。本文研究的航天零件自動化立體倉庫是雙升式貨架，需要考慮貨物周轉(zhuǎn)情況下的翻庫情況。此外，存儲零件種類規(guī)模大，但是批次小，而庫存量有限制，一旦庫位分配不合理，就會造成出庫次序混亂，完成訂單的效率低下。針對這種問題，文中提出基于模擬退火遺傳算法的存儲策略進(jìn)行貨位分配優(yōu)化研究，為零件合理分配貨位，提高倉庫庫位的使用率和出庫效率。

1 問題描述

與其他立體倉庫不同，航天零件的倉儲系統(tǒng)具有以下特點(diǎn)：

1）存儲零件的特殊性。一般用于航天上的零件都比較精密，大多以小型為主，而且種類繁多。文中研究的航天零件大都是多品種、小批量的。選取該企業(yè)三個月的訂單數(shù)據(jù)分析，如圖1所示，橫坐標(biāo)表示貨物種類，縱坐標(biāo)表示貨物數(shù)量。倉庫中總共需要儲存的零件可達(dá)1900多種，種類冗雜，而且每類零件的數(shù)量有較大差異，這大大提高了倉庫的存儲難度。

圖1 立體倉庫存儲的零件種類及數(shù)量

2）零件出入庫的特殊性。由于入庫作業(yè)具有不確定性，平時主要以存儲零件為主，每3個月周轉(zhuǎn)一次，完成零件出庫作業(yè)。作為物流中轉(zhuǎn)部，需要對現(xiàn)場生產(chǎn)提供需求，滿足現(xiàn)場的生產(chǎn)節(jié)拍。所以，對零件出庫效率有很高的要求。

3）貨架布局的特殊性。要完全按不同種類存儲這些航天零件，所需的倉庫面積是非常大的。但是現(xiàn)在由于受到場地的限制，只有有限的空間存儲這些零件。所以，立體倉庫貨架的布局會對零件存儲數(shù)量會產(chǎn)生重要的影響。如圖2所示，兩排貨架為一組，采用雙深式貨架，可以增加貨物存放量，同時減少占地面積。

圖2 立體倉庫貨架示意圖

2 貨位優(yōu)化模型

2.1 模型假設(shè)

根據(jù)研究的航天零件立體倉庫貨位問題的描述，為方便模型的建立，簡化研究對象，文中對研究目標(biāo)提出如下假設(shè)條件：

1）雙深式貨架，令靠近I/O口一側(cè)作為內(nèi)側(cè)，遠(yuǎn)離I/O口一側(cè)作為外側(cè)。

2）堆垛機(jī)貨叉兩級伸縮，左右兩邊都能執(zhí)行出入庫操作，即堆垛機(jī)能夠接觸到立體庫的每個庫位。

3）貨物都是放在中轉(zhuǎn)箱中，所有貨位能夠放下貨箱，且每個庫位貨物種類只有一種。

4）堆垛機(jī)的水平和垂直方向上的運(yùn)動都是服從勻加速或勻減速運(yùn)動，且堆垛機(jī)能夠同時進(jìn)行水平和豎直方向上的運(yùn)動。

5）每個庫位貨格的規(guī)格，即每個貨位的尺寸都保持一致。

6）每一類貨物出庫的頻率能夠進(jìn)行恰當(dāng)?shù)念A(yù)測，得到合理的結(jié)果。

7）由于堆垛機(jī)貨叉出入庫的時間占總操作時間的比例很小，所以可以忽略不計。

8）立體倉庫內(nèi)的I/O口在同一側(cè)。

2.2 模型中各變量的定義

文中研究的航天零件倉庫模型的參數(shù)大致如下：

1）雙深式貨架，共X排Y層Z列，km,n,o（m=1，2，3，…，X；n=1，2，3，…，Y；o=1，2，3，…，Z）示該貨物處于第m排n層o列。設(shè)定立體倉庫出入庫的起始點(diǎn)位于k2，1，0緊靠出入庫平臺的庫位為第一層和第一列，且最左邊的貨架為第一排。

2）Mxyz表示x排y層z列庫位中貨物的重量；

3）Qxyz表示庫位（x，y，z）中貨物的數(shù)量；

4）H表示貨格高度，L表示貨格長度；

5）Vz表示堆垛機(jī)在水平方向上的平均速度；

6）vy表示堆垛機(jī)在豎直方向上的平均速度；

7）fxyz表示（x,y,z）貨位儲存貨物的平均出庫頻次；

8）txyz表示對應(yīng)生產(chǎn)周期內(nèi)（x,y,z）貨位零件出庫數(shù)量；

9）S表示一個周期內(nèi)所有出庫零件的總數(shù)量。

2.3 目標(biāo)函數(shù)及約束條件

根據(jù)航天零件存儲庫位的特殊性及堆垛機(jī)運(yùn)動相關(guān)參數(shù)，考慮立體倉庫中貨物出庫效率和貨架穩(wěn)定性之間的關(guān)聯(lián)，建立自動化立體倉庫的多目標(biāo)貨物優(yōu)化模型。

1）基于零件出庫效率的分析

由于文中研究的立體倉庫入庫作業(yè)具有不確定性，所以主要研究貨物出庫效率。而出庫效率主要以堆垛機(jī)周期運(yùn)行時間為依據(jù)，將所有零件出庫所需的最小時間作為出庫效率研究目標(biāo)，建立第一目標(biāo)函數(shù)如下：

式中，dy（ixyz，ix1y1z1）表示出庫位到周轉(zhuǎn)位豎直方向位移，dz（ixyz，ix1y1z1）表示出庫位到周轉(zhuǎn)位水平方向位移，第一個judeg表示判斷庫位是否有貨，若judeg=0，則庫位無貨，不需要出庫。第二個judge表示判斷庫位是否需要翻庫，若judge=1，則需要翻庫。

2）基于貨架穩(wěn)定性的分析

貨架穩(wěn)定性與貨架整體重心高低有關(guān)，現(xiàn)在普遍的研究方法是將較重的貨物盡可能的擺放在底層，較輕的貨物放在高層，做到“下重上輕”，這樣會減小貨架的整體重心，提高貨架的穩(wěn)定性，建立第二目標(biāo)函數(shù)如下：

式(3)中，將每個貨格中貨物總重與所在層數(shù)、貨格高度乘積之和，再除以每個貨格貨物總重之和。

由于雙深式貨架的特殊性，每一組貨架都是由兩排貨架組成的，而且貨架在橫向方向上的長度要遠(yuǎn)遠(yuǎn)大于縱向方向上的長度，所以為保證貨架抗傾覆的穩(wěn)定性，需要額外考慮每一組的兩排貨架x=2p-1和x=2p，p∈N且p∈[1，m/2]總重量基本保持一致。據(jù)此，建立第三目標(biāo)函數(shù)如下：

式(4)中，將同一組的外排貨架每個貨位總重跟里層貨架總重之差作為平衡水平穩(wěn)定性指標(biāo)

3）約束條件：結(jié)合文中研究的倉庫模型，總共有m排貨架，每排貨架又有n層o列，x、y、z分別表示立體倉庫中貨架的排、層、列。因此，貨位優(yōu)化模型問題的空間約束條件如下：1≤x≤m；1≤y≤n；1≤z≤o；x、y、z均為正整數(shù)。

2.4 多目標(biāo)函數(shù)歸一化

在研究多目標(biāo)函數(shù)時，要綜合考慮每個目標(biāo)函數(shù)各自之間的關(guān)聯(lián)及影響關(guān)系，從而達(dá)到各個目標(biāo)函數(shù)在給定的條件下，盡可能接近最優(yōu)解的目的，從而達(dá)到多目標(biāo)函數(shù)的最優(yōu)化。文中采用模擬退火遺傳算法，根據(jù)現(xiàn)場實(shí)際合理分配權(quán)重，將多目標(biāo)函數(shù)問題轉(zhuǎn)換為單一目標(biāo)函數(shù)。

多目標(biāo)函數(shù)中，F(xiàn)1（x，y，z）指最小出庫時間，單位是秒（s）；F2（x，y，z）指貨架的豎直重心盡可能低，F(xiàn)3（x，y，z）指貨位的水平重心坐標(biāo)盡量靠近中心，這兩個目標(biāo)函數(shù)無量綱。由于三個目標(biāo)函數(shù)的單位不一致，在進(jìn)行多目標(biāo)函數(shù)歸一化處理時，只需要對F1（x，y，z）歸一化，取最大和最小的兩個確定數(shù)值及參數(shù)?，處理后的歸一化目標(biāo)函數(shù)為：

將三個目標(biāo)函數(shù)賦予不同的權(quán)重 αi（i=1，2，3），將其轉(zhuǎn)換成單目標(biāo)函數(shù)如下：

3 基于模擬退火遺傳算法的存儲模型

遺傳算法作為一種智能優(yōu)化算法，應(yīng)用范圍廣，具有自然界生物選擇和遺傳的特點(diǎn)，在算法求解過程中，能夠很好的運(yùn)用自身交叉、變異來快速尋求最優(yōu)解，并且具有在全局范圍內(nèi)搜尋優(yōu)秀解的能力。然而，遺傳算法極易陷入早熟、收斂的缺陷，局部搜索能力不是很理想的問題，所以需要對它進(jìn)行改進(jìn)，跳出局部收斂，找到優(yōu)秀解。而模擬退火算法是在模擬固體物質(zhì)退火時，從開始的高溫慢慢下降到低溫過程中，會以一定概率跳變，能夠很好的在一定范圍的解空間中隨機(jī)尋找所需的最優(yōu)解。將模擬退火算法的跳變性與遺傳算法進(jìn)行融合，能很好的彌補(bǔ)遺傳算法早熟缺陷[7,8]。

3.1 染色體編碼

選用合理的染色體編碼方式對優(yōu)化問題有很大的幫助，不僅能簡化問題難度，而且還能提高遺傳算法的求解速度。一般的遺傳算法編碼技術(shù)主要有：二進(jìn)制編碼、實(shí)數(shù)編碼，但是由于二進(jìn)制編碼方式在解決貨位優(yōu)化問題時，其隨機(jī)性會使得遺傳算法局部搜索能力較差，在逼近最優(yōu)解時，變異后的子代跟父代的差異性很大，不連續(xù)，導(dǎo)致最優(yōu)解極其不穩(wěn)定。因此，文中主要采用實(shí)數(shù)編碼的方式來進(jìn)行染色體編碼，將貨物種類、每類貨物庫存實(shí)例及貨物坐標(biāo)雜糅成一條染色體[16]，表達(dá)形式如下：

1）染色體中基因所在的位置代表著庫位中貨物的三維坐標(biāo)Lijk（i—排，j—層，k—列），展開后的一維坐標(biāo)如下：

2）每一個庫位中貨物的實(shí)例采用實(shí)數(shù)m（m∈W）+小數(shù)n（n=.000，.001……，Nw）的形式，實(shí)數(shù)m代表庫位中貨物種類，小數(shù)部分代表該類型貨物在庫中的實(shí)例編號。

3）結(jié)合基因位置和貨物實(shí)例，p位置基因表達(dá)情況如下：

假設(shè)現(xiàn)有兩排貨架，每排貨架都是4層3列，庫中有5中不同類型的貨物。由于立體倉庫第1層與堆垛機(jī)平行，不存放貨物，故從第2層開始存放貨物，染色體基因編號從L1，2，1開始。K1=1.001指染色體中第一個基因：貨位L1，2，1存儲的是貨物類型1的第一個。圖1的貨位分配方式形成的染色體k=k1k2…k9，這些組成了遺傳算法的一個可行解。

表1 貨位與基因編碼示意

3.2 適應(yīng)度函數(shù)

遺傳算法中，適應(yīng)度函數(shù)可以衡量每代種群中各個體接近最優(yōu)解的優(yōu)秀程度，可以通過適應(yīng)度值近似確定每代種群最優(yōu)個體。文中將出庫時間和出庫穩(wěn)定性的三個目標(biāo)函數(shù)轉(zhuǎn)換成研究的適應(yīng)度函數(shù)。經(jīng)過變化后的適應(yīng)度函數(shù)如下所示：

3.3 選擇算子

文中采用k=2的錦標(biāo)賽選擇算子。錦標(biāo)賽選擇是一種比較流行的選擇策略，主要思想是：在整個種群中取若干個個體，讓他們互相競爭，最終得到最優(yōu)個體。選取錦標(biāo)賽算子，可以將競爭后的優(yōu)秀個體進(jìn)行選擇交叉、變異等操作，使其直接進(jìn)入下一代種群。

3.4 交叉算子

交叉操作可以為遺傳算法每代種群帶來新個體的補(bǔ)充，具有不可忽視的地位。適當(dāng)?shù)慕徊娣椒ǎ梢约涌爝z傳算法的運(yùn)算效率，提高目標(biāo)函數(shù)的優(yōu)化結(jié)果。張春濤[9]在研究TSP問題時，發(fā)現(xiàn)均勻兩點(diǎn)交叉遺傳算子相較于傳統(tǒng)的兩點(diǎn)交叉算子有較好的優(yōu)越性。所以，文中采用均勻兩點(diǎn)交叉算子。

3.5 變異算子

變異算子可以提高種群的多樣性，幫助遺傳算法脫離陷入局部收斂的現(xiàn)象。文中采用多次變換變異算子，并引入自適應(yīng)性函數(shù)調(diào)整變異概率。楊志龍[10]在研究倉儲貨位優(yōu)化時，在基于Srinival，M等人提出的一種自適應(yīng)遺傳算法（AGA）基礎(chǔ)上，改進(jìn)的自適應(yīng)函數(shù)能有效的得到全局最優(yōu)點(diǎn)，幫助遺傳算法跳出局部收斂，為每代種群提供多樣性個體。

其中，Pm1、Pm2：變異率大、小界值；fmax、favg：當(dāng)前種群最大、平均適應(yīng)度值，fε：變異個體適應(yīng)度值。

3.6 模擬退火算法（SA）操作

引入模擬退火算法是為了利用它的跳變性，在很大空間搜尋近似最優(yōu)解，從而幫助遺傳算法跳出局部收斂，得到最優(yōu)個體。文中擬定的模擬退火操作：先設(shè)定一個停止閾值溫度Tmin，在遺傳算法一系列操作后產(chǎn)生新的種群中，選擇一部分優(yōu)秀個體進(jìn)行SA操作，根據(jù)Metropolis的接受準(zhǔn)則進(jìn)行判斷是否接受新解，其接受準(zhǔn)則如下：

其中，fiti（T）表示經(jīng)過遺傳算法操作產(chǎn)生新個體的值，fitj（T）表示個體經(jīng)過SA操作后的值。在每一次迭代中，如果當(dāng)前溫度T＞Tmin，則進(jìn)行降溫操作，tk+1=β*tk，β∈[0.5，0.09]為降溫系數(shù)；否則，結(jié)束循環(huán)。

模擬退火優(yōu)化遺傳算法（SAGA）基本流程如圖3所示。

圖3 模擬退火優(yōu)化流程

4 仿真結(jié)果分析

4.1 基本參數(shù)設(shè)定

1）文中研究的航天零件立體倉庫相關(guān)參數(shù)配置及歷史訂單數(shù)據(jù)均來自某航天零件制造研究所立體倉庫的實(shí)際情況。相關(guān)參數(shù)如表2所示。

表2 立體倉庫基本參數(shù)

2）SA-GA算法控制參數(shù)及終止條件

本文中擬定種群初始大小為50，迭代次數(shù)為500代；交叉概率為pc=0.95，變異概率范圍為[0.008，0.01]；初始溫度T= 100000；閾值溫度Tmin=100，降溫系數(shù)β=0.95；當(dāng)前溫度低于Tmin時，算法運(yùn)行結(jié)束。同時，根據(jù)倉庫貨物的實(shí)際情況，對每個目標(biāo)函數(shù)進(jìn)行權(quán)重賦值，分別是：W1=0.7，W2=0.15，W3=0.15，將設(shè)定的參數(shù)應(yīng)用到算法中。

4.2 仿真結(jié)果

本文設(shè)計的算法由python語言編寫實(shí)現(xiàn)，利用四種分配策略：基于改進(jìn)遺傳算法的存儲（SA-GA）策略、就近存儲策略（COL）、隨機(jī)存儲策略（RS）和ABC分類存儲策略（ABC），對文中建立的模型進(jìn)行仿真模擬，對比這四種貨物分配策略的優(yōu)劣性。文中，COL策略是將出庫頻率高的貨物存儲在離出口近的貨位；RS分配策略是隨機(jī)給每個貨物分配貨位；ABC策略是將貨架按一定比例將貨架分成三類，按照貨物平均出庫頻率的高低將貨物放在分類的貨位中，貨架分配比例是1：2：7。

1）從圖4可以看到，傳統(tǒng)的遺傳算法容易陷入局部僵局，接近300代左右才收斂，并且解的質(zhì)量差，難以獲取迭代最優(yōu)解。然而，將模擬退火算法融入遺傳算法后，如圖5所示，遺傳算法快速達(dá)到收斂狀態(tài)，在100代左右就開始收斂，最終解接近全局最優(yōu)解，質(zhì)量好，算法效率極高。

圖4 傳統(tǒng)自適應(yīng)GA收斂曲線

圖5 SA-GA收斂曲線

2）在表3可以看到，SA-GA的結(jié)果優(yōu)于其他三種存儲策略，其中表示的出庫時間分別降低了11.7%，9.6%，55.7%；表示的貨架豎直重心分別降低了39.7%、68.2%、57.6%；表示的貨架水平重心分別降低了26.3%、63.1%、58.6%。

表3 四種分配策略目標(biāo)函數(shù)值對比

5 結(jié)語

本文主要從提高自動化立體倉庫貨物出庫效率和貨架穩(wěn)定性這兩個方向出發(fā)，以航天零件自動化立體倉庫為研究對象，構(gòu)建了三個數(shù)學(xué)模型，利用四種存儲策略進(jìn)行仿真分析，比較這四種分配策略的優(yōu)劣性，同時將遺傳算法跟模擬退火算法很好的融合，使遺傳算法跳出局部收斂。通過立體倉庫歷史訂單數(shù)據(jù)進(jìn)行仿真求解，得出基于模擬退火遺傳算法的存儲策略在出庫效率和貨架穩(wěn)定性上的性能要優(yōu)于其他三種貨物分配策略。同時，文中研究的立體倉庫貨架是很特殊的雙深式貨架，目前研究這方面的理論還比較少，所以，在這方面的研究還有可繼續(xù)深入的空間，如在建模過程中的假設(shè)條件跟實(shí)際存在一定的沖突性；建立的模型在實(shí)際的立體倉庫中不易實(shí)現(xiàn)等等。