基于遺傳算法的生產(chǎn)型物流出庫時(shí)效性研究

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

策略4：當(dāng)下發(fā)的最后一條作業(yè)是入庫作業(yè)時(shí)，堆垛機(jī)停在入庫站臺(tái)；當(dāng)下發(fā)的出庫作業(yè)是最后一條作業(yè)時(shí)，堆垛機(jī)停在出庫站臺(tái)；

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

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

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

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

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

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

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

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

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

1）模型的建立

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

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

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

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

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

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

3 引入遺傳算法

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

1）進(jìn)行編碼：

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

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

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

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

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

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

4）選擇

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

5）交叉策略

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

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

6）變異策略

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

7）參數(shù)選擇

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

8）終止條件

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

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

在建模與算法設(shè)計(jì)完成之后，我們?cè)谠撈嚬S自動(dòng)化立體倉庫中進(jìn)行驗(yàn)證算法的可靠性與時(shí)效性。圖3為自動(dòng)化立庫局部的監(jiān)控俯視圖，圖4為現(xiàn)場(chǎng)設(shè)備運(yùn)行的實(shí)物照。

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

圖4 堆垛機(jī)與輸送線實(shí)物圖

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

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

表1 7個(gè)貨位地址的堆垛機(jī)運(yùn)行總時(shí)間表

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

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

5 結(jié)語

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