李彬璠，郭 麗，楊騰飛，石振鵬，汪鍇狄

（1.北京機械工業(yè)自動化研究所，北京 100120；2.北自所（北京）科技發(fā)展股份有限公司，北京 100120）

0 引言

隨著智能制造的加速推進，國內(nèi)外智能倉儲行業(yè)的發(fā)展日益迅速，大型物流倉儲庫區(qū)的出庫效率問題逐漸成為研究熱點。自動化立體倉庫（Automated Storage/Retrieval System，AS/RS）是生產(chǎn)型企業(yè)加工與存儲的交接樞紐，特別是在生產(chǎn)型廠內(nèi)物流中，零件出庫節(jié)拍要服從生產(chǎn)節(jié)拍。受限于倉庫空間，輸送線多采用交叉環(huán)線設(shè)計。多限制條件下的調(diào)度系統(tǒng)作為整個自動化立體庫系統(tǒng)中最為核心的部分之一，對于出庫效率的提升一直是研究的熱點與難點。

由于智能調(diào)度系統(tǒng)支配整個立體庫的運行，諸多學(xué)者對調(diào)度的智能化開展了深入探索研究。在國內(nèi)，王廳長[1]針對雙伸位的自動化立體庫建立貨架穩(wěn)定與提升存取效率的模型，并通過Matlab對比普通遺傳算法與病毒遺傳算法的優(yōu)劣。梁興等人[2]針對貨位分配問題進行升級創(chuàng)新，將Pareto最優(yōu)解的方法引入調(diào)度環(huán)節(jié)中，與之前的GA算法進行結(jié)合，最終通過仿真驗證了高效性。雷斌[3]通過運用遺傳算法、布谷鳥搜索算法、禁忌搜索等機器學(xué)習的算法,在貨位分配、作業(yè)調(diào)度等方面進行研究拓展。在國外，Lu ZHEN等人[4]使用設(shè)備互聯(lián)、集成的方式，對自動化立體倉庫進行升級改進，對調(diào)度分配地址問題進行了探索。Ahmed Mohammed[5]等人基于RFID的不確定性對自動倉儲系統(tǒng)的設(shè)計并進行優(yōu)化，不同于常見的是，他使用的是一種多準則模糊規(guī)劃方法。Gianluca Nastasi[6]主要在基于遺傳算法的多目標優(yōu)化算法上，將作業(yè)的效率大幅提升。AS/RS調(diào)度的改進優(yōu)化成為國內(nèi)外諸多學(xué)者研究熱點與難點，對智能倉儲行業(yè)的發(fā)展提供了動力。

1 生產(chǎn)型物流出庫效率問題簡介

對于汽車制造企業(yè)來說，供件效率非常關(guān)鍵。該企業(yè)引入了自動化立體倉庫，目的主要是為了節(jié)約空間、節(jié)省人力以及提升效率。立體庫用來存放一些汽車零部件，通過發(fā)起出庫訂單來滿足總裝車間的要貨需求，因此出庫效率直接影響了總裝車間的生產(chǎn)進度[7]?，F(xiàn)階段，對于效率要求高的自動化立體庫存在如下問題：部分立體庫前期布局規(guī)劃不合理、入庫時貨物分類不清晰、WCS系統(tǒng)調(diào)度算法較為落后，僅考慮是否可以出庫而并未考慮出庫效率問題等。

針對上述問題，我們制定了一系列方案來提升出庫效率，例如入出庫口的南北規(guī)劃、入庫分配控制、緊急件非緊急件的物料定義分類設(shè)計等，最核心的部分是堆垛機的空閑停留策略和遺傳算法的改進。這兩部分決定了廠區(qū)自動化立體庫的運行是否達到最高效率，減少不必要的資源浪費，從而滿足生產(chǎn)車間對于零件出庫的時效要求。

2 生產(chǎn)型物流出庫效率優(yōu)化設(shè)計

2.1 南北入出庫口方案規(guī)劃設(shè)計

在以往的項目中，自動化立體倉庫的入庫口、出庫口設(shè)計在同側(cè)或?qū)?cè)，這樣所有的貨物出庫都會經(jīng)過同一路線，增加了出庫等待時間。為更方便卸貨及取貨，提升立庫總體入出庫效率，在庫區(qū)的南北側(cè)均設(shè)計了入出庫站臺，對于出庫來說，可以根據(jù)距離巷道的遠近來選擇南區(qū)或北區(qū)的去向，避免了高峰出庫時段貨物堵線；對于入庫來說，提升了空間利用率，南北兩側(cè)均可以設(shè)計入庫緩存區(qū)來減少貨物積攢。南北規(guī)劃的設(shè)計作為項目的初期規(guī)劃環(huán)節(jié)，對于后期的調(diào)度策略以及環(huán)線控制有著關(guān)鍵作用，提高了整體的運行效率。

圖1 整體規(guī)劃布局圖

2.2 入庫分配控制及物料定義分類設(shè)計

由于本項目屬于環(huán)線軌道，同時又對堆垛機的運行效率要求較高，為避免環(huán)線堵塞，影響出庫效率，在入庫時，調(diào)度系統(tǒng)會自動分配合理的巷道；同時，針對入庫的物料，我們在定義時將其區(qū)分為緊急件和非緊急件，這樣可以有效區(qū)分物料的種類，提高立庫運行效率。我們在數(shù)據(jù)庫中對當前每個巷道已有的庫存量、所要入庫的物料在該巷道的數(shù)量、空貨位數(shù)量、該巷道所擁有的暫存量以及該物料的暫存量分別計數(shù)，通過數(shù)據(jù)庫的篩查，來尋求最優(yōu)入庫分配方案，最大限度避免堆垛機資源浪費與過剩。

2.3 堆垛機及環(huán)式輸送線調(diào)度方案設(shè)計

2.3.1 堆垛機停留策略分析與優(yōu)化

為了提升堆垛機的運行效率，我們可以縮短堆垛機在啟動時的時間消耗，對最后一條作業(yè)結(jié)束時堆垛機所停留的位置進行分析，共找出以下五種服務(wù)停留點的策略可供選擇，通過計算堆垛機啟動時所消耗的平均期望時間來尋求一種最優(yōu)策略。

策略1：當堆垛機完成所有下發(fā)作業(yè)后，停在入庫站臺；

策略2：當堆垛機完成所有下發(fā)作業(yè)后，停在出庫站臺；

策略3：當下發(fā)的最后一條作業(yè)是入庫作業(yè)時，堆垛機停留在完成入庫作業(yè)的位置；當下發(fā)的出庫作業(yè)是最后一條作業(yè)時，堆垛機停在出庫站臺；

策略4：當下發(fā)的最后一條作業(yè)是入庫作業(yè)時，堆垛機停在入庫站臺；當下發(fā)的出庫作業(yè)是最后一條作業(yè)時，堆垛機停在出庫站臺；

策略5：當最后一條作業(yè)是入庫作業(yè)時，則堆垛機停留在貨區(qū)中固定站臺D1，出庫作業(yè)是最后一條作業(yè)時，則堆垛機停在貨區(qū)中的固定站臺D2。

當堆垛機的第一條作業(yè)是入庫作業(yè)時，顯然堆垛機的最優(yōu)停留點是第0列入庫站臺；當堆垛機的第一條作業(yè)是出庫作業(yè)時，此時我們考慮最佳的停放位置自然是貨架中的某個位置。通常，在下發(fā)作業(yè)之前，無法得知起始作業(yè)的類型。對于本項目而言，我們?nèi)绻O(shè)定堆垛機按照作業(yè)下發(fā)的時間順序來執(zhí)行任務(wù)，從概率角度來看，入庫作業(yè)與出庫作業(yè)的可能性相同；但是從優(yōu)化角度出發(fā)，堆垛機調(diào)度系統(tǒng)將更多的去執(zhí)行多任務(wù)復(fù)合作業(yè)，那這樣起始作業(yè)是入庫作業(yè)的概率就會相對較大。因此，從長遠來看是合理的。如圖2所示，代表典型的任務(wù)系列執(zhí)行順序與過程，在此條件下有如下的結(jié)論：

圖2 堆垛機的任務(wù)隊列的執(zhí)行圖

我們優(yōu)先分析前4種停留策略，假設(shè)他們啟動時的平均期望時間為ES(i),(i=1,2,3,4)，則有以下結(jié)論：

其中，pr代表一個起始作業(yè)為入庫作業(yè)的概率；pc代表一個起始作業(yè)為出庫作業(yè)的概率；ETI/O代表堆垛機在貨區(qū)的某個位置與巷道的入出庫站臺之間的平均期望執(zhí)行時間；ETB代表堆垛機在貨區(qū)的兩個位置之間執(zhí)行作業(yè)的平均期望時間；T0代表堆垛機在巷道的入出庫站臺之間伸收叉的交替時間。

類似的，我們可以得到ES(4)≤ES(3),利用做差比較法得出：

為使得上式最小，我們需要找到D1*和D2*,根據(jù)最優(yōu)化得方向看，D1*=D2*，因此，在的情況下，

所以，在上述的分析與推導(dǎo)過程中我們可以得出，要使堆垛機減少空跑消耗的時間，可以進行調(diào)整堆垛機完成作業(yè)后的停留策略，如果從長遠考慮，通過方案比較，我們得出提高效率最優(yōu)的是第一種策略。

2.3.2 堆垛機入出庫作業(yè)調(diào)度算法優(yōu)化

1）模型的建立

針對于復(fù)合型作業(yè)調(diào)度，結(jié)合自動化立庫的結(jié)構(gòu)特點[8]，建立如下數(shù)學(xué)模型：

如果上位機共下發(fā)N條作業(yè)，其中入庫作業(yè)與出庫作業(yè)數(shù)目分別是n和m，即N=n+m。當收到每一條作業(yè)任務(wù)時，調(diào)度系統(tǒng)都會為其分配作業(yè)起始地址并且交叉完成入出庫作業(yè)。顯然，對于堆垛機來說，完成整套入庫與出庫作業(yè)耗費的總時間ti為：

tOA是執(zhí)行入庫作業(yè)所需時間，tOA=max{丨XA-0丨/vx,丨YA-0丨/vy}；tAB是堆垛機進行庫內(nèi)位置轉(zhuǎn)換所需時間tAB=max{丨XA-XB丨/vx,丨YA-YB丨/vy}；tBO是出庫作業(yè)所需時間tBO=max{丨XB-0丨/vx,丨YA-0丨/vy}。

當入庫作業(yè)小于出庫作業(yè)的數(shù)量時，我們可以認為堆垛機的作業(yè)有多次的復(fù)合作業(yè)循環(huán)過程，即單次循環(huán)的重疊，通常每個循環(huán)是由2～3次的單循環(huán)構(gòu)成，對于出入庫站臺來說，屬于所有循環(huán)的樞紐位置。我們通過分析可以得知，執(zhí)行完所用時間Tk是我們控制堆垛機最優(yōu)化的目標函數(shù)：

其中，k=max{m,n}代表循環(huán)總數(shù)。ti是在第i次堆垛機執(zhí)行作業(yè)是所需要的運行時間，這其中包含了入庫作業(yè)、出庫作業(yè)以及空載運行的時間。

針對以上的模型假設(shè)，我們可以將問題轉(zhuǎn)化為旅行商的類似問題。其本質(zhì)是尋找最短路徑問題，放在本實驗中，我們可以認為堆垛機的調(diào)度路徑即堆垛機的行駛路線是要求的結(jié)果，作業(yè)調(diào)度最優(yōu)解就是堆垛機的最優(yōu)路徑，進而來提高運行效率。

3 引入遺傳算法

對于堆垛機復(fù)合作業(yè)問題，我們轉(zhuǎn)化成了旅行商求解問題，由于隨著數(shù)據(jù)量增大，作業(yè)任務(wù)增多，常規(guī)方法較難尋求最優(yōu)解，對與遺傳算法本身來說，解決NP組合優(yōu)化問題，有很大的優(yōu)勢。我們設(shè)置入出庫作業(yè)共有N個，其中p個入庫任務(wù)，q個出庫任務(wù)。具體步驟如下：

1）進行編碼：

根據(jù)入出庫作業(yè)隊列，我們將每條作業(yè)所在貨位進行編碼，顯然，測試數(shù)據(jù)應(yīng)在同一巷道。例如，我們假設(shè)共有6個入出庫作業(yè)，作業(yè)地址分別為3-1-2，4-4-1，2-6-1，3-5-2，6-3-1，4-2-2，分別以1，2，3，4，5，6代表這6個貨位點，即這六個貨位點可以產(chǎn)生種組合路徑，染色體（6，3，2，1，4，5）代表堆垛機先運行到6號貨位，再運行至3號貨位，最終到5號貨位完成最終作業(yè)。

2）適應(yīng)度函數(shù)的建立

適應(yīng)度函數(shù)可以確定為，堆垛機從站臺起始位開始按照染色體的順序進行調(diào)度作業(yè)，所需要的總時間：

其中，I=(i1,i2,...,ip+q)表示任意一條循環(huán)回路。

3）產(chǎn)生初始種群

我們隨機產(chǎn)生兩個p*q的矩陣A與B,作為本次實驗的初始種群，矩陣q列代表染色體長度為q，即q-1個貨位地址；矩陣的p行代表種群規(guī)模為2p.矩陣每一行代表著堆垛機調(diào)度作業(yè)的執(zhí)行順序。

4）選擇

選擇操作顧名思義，即在種群進行交叉或變異操作之后，進行“優(yōu)勝劣汰”，生成的染色體按適應(yīng)度結(jié)果排序，最優(yōu)個體將取代適應(yīng)度最低的染色體，適應(yīng)度高的染色體會保留下來，連續(xù)的迭代會一直進行篩選最優(yōu)個體，提升了算法的收斂性，迭代操作終止時，會產(chǎn)生適應(yīng)度效果最好的染色體，該染色體即調(diào)度方案的最優(yōu)解。

5）交叉策略

在本實驗中，若采用傳統(tǒng)的交叉方式，將會產(chǎn)生無效錯誤的調(diào)度地址與路徑，為了避免這種情況，我們采用非常規(guī)的交叉方法，即單點交叉。即在染色體中隨機的進行基因交配，選擇某處位置，對于他的下一代染色體而言，該位置之后的基因段由另一條染色體的不重復(fù)的基因構(gòu)成，而該位置之前的基因段維持不變。例如：

選擇的交配基因在第三個位置，對于子代A來說，4 2 1保持不變，剩下的四位與父代B進行交叉，將重合的基因進行替換，子代B進行同樣的操作。

6）變異策略

傳統(tǒng)意義上的變異操作是將染色體中的某個基因進行無規(guī)則變換，但在本實驗條件下，如果進行隨機變異，染色體所對應(yīng)的基因編碼會變化成無效的貨位編號，導(dǎo)致該染色體為無效解。所以在本實驗中，計劃采用基因互換位置的變異方式，這樣可確保解的有效性。

7）參數(shù)選擇

參數(shù)主要有兩個，一個是交叉操作，一個是變異操作，在交叉時我們說過，交叉操作在迭代次數(shù)夠多的情況下，最終收斂的效果會相對較好，因為會逐步生成適應(yīng)度更優(yōu)的染色體?？梢栽O(shè)置為Pj=0.8；對于變異操作來說，考慮到為避免會破壞染色體，變異概率不宜取值過大，設(shè)置為Pb=0.05。

8）終止條件

遺傳算法的終止條件通常設(shè)置為在最大迭代次數(shù)內(nèi)，如果染色體適應(yīng)度基本保持平穩(wěn)，將會終止算法。迭代次數(shù)過大過小均會造成較大誤差，因此本實驗將maxgen賦值為500.

4 實例應(yīng)用

在建模與算法設(shè)計完成之后，我們在該汽車工廠自動化立體倉庫中進行驗證算法的可靠性與時效性。圖3為自動化立庫局部的監(jiān)控俯視圖，圖4為現(xiàn)場設(shè)備運行的實物照。

圖3 立體庫局部俯視示意圖

圖4 堆垛機與輸送線實物圖

我們從WMS系統(tǒng)上隨機下發(fā)了一批作業(yè)任務(wù)，在某巷道的作業(yè)隊列中接收了7條作業(yè)。接下來本文對于該部分的驗證實施方案做一個簡要說明。任務(wù)序號1-7，由于本項目存在單伸堆垛機與雙伸堆垛機，為避免偶然因素，我們?nèi)訂紊煳欢讯鈾C，減少因近遠排產(chǎn)生的誤差，計算時實際有效數(shù)據(jù)只有層與列。貨位地址(Xm,Ym)（m=1,2,…,7）分別為4-6，14-3，40-5，47-2，49-3，51-1，59-6。當m=2，3，6時，堆垛機作業(yè)狀態(tài)為出庫；當m=1，4，5，7時，堆垛機作業(yè)狀態(tài)為入庫。

7個貨位地址的堆垛機運行時間如上表1所示，倘若不進行算法優(yōu)化，按照原本的調(diào)度邏輯應(yīng)按順序進行作業(yè)，即（1，2，4，3，5，6，7）。運算可得所消耗時間為268s.根據(jù)我們前文所設(shè)計的算法，進行迭代后，篩選出最優(yōu)染色體，得到最優(yōu)調(diào)度路徑為（1，2，5，4，6，7，3），根據(jù)上表計算消耗時間為240s.顯而易見，本實驗所提出的調(diào)度方案效果顯著，對于廠區(qū)來說是高效的，節(jié)約了堆垛機的運行時間，保障了立體庫出庫的效率，其算法優(yōu)化效果通過Matlab呈現(xiàn)，如圖5所示。

表1 7個貨位地址的堆垛機運行總時間表

圖5 算法優(yōu)化效果圖

圖中種群均值我們可以看作平均適應(yīng)度，所謂解的變化是指最優(yōu)適應(yīng)度，從圖中可以看出，在迭代初期，種群均值、最優(yōu)解變化起伏不定，適應(yīng)度函數(shù)最優(yōu)值與原調(diào)度邏輯所得時間差距不大，隨迭代次數(shù)增加，種群均值趨向于收斂，適應(yīng)度函數(shù)最優(yōu)解達到收斂值240s，與之前的調(diào)度邏輯相比，效率提升明顯。

5 結(jié)語

基于遺傳算法的堆垛機調(diào)度策略可以從算法角度最大限度的提高堆垛機的運行效率，縮短出庫所用時間，提高資源利用率。對于生產(chǎn)型物流而言，解決出庫時效性問題，我們要從全局出發(fā)，從立庫的設(shè)計規(guī)劃起步，同時，環(huán)線的輸送系統(tǒng)要求我們在入庫時對物料定義、分配巷道等環(huán)節(jié)要加以調(diào)整來避免堵線，另外，我們建立了模型，設(shè)計了堆垛機空閑時的停留策略。本文通過對這幾個要點問題優(yōu)化分析，最終建立了一套相對效率較高的調(diào)度分配方案，并將其應(yīng)用在該項目中，通過實驗數(shù)據(jù)得出的算法運行結(jié)果符合預(yù)期設(shè)計，證明了研究成果的可行性。