基于遺傳算法的生產型物流出庫時效性研究

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

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

0 引言

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

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

1 生產型物流出庫效率問題簡介

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

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

2 生產型物流出庫效率優化設計

2.1 南北入出庫口方案規劃設計

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

圖1 整體規劃布局圖

2.2 入庫分配控制及物料定義分類設計

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

2.3 堆垛機及環式輸送線調度方案設計

2.3.1 堆垛機停留策略分析與優化

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

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

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

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

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

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

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

圖2 堆垛機的任務隊列的執行圖

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

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

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

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

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

2.3.2 堆垛機入出庫作業調度算法優化

1）模型的建立

針對于復合型作業調度，結合自動化立庫的結構特點[8]，建立如下數學模型：

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

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

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

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

針對以上的模型假設，我們可以將問題轉化為旅行商的類似問題。其本質是尋找最短路徑問題，放在本實驗中，我們可以認為堆垛機的調度路徑即堆垛機的行駛路線是要求的結果，作業調度最優解就是堆垛機的最優路徑，進而來提高運行效率。

3 引入遺傳算法

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

1）進行編碼：

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

2）適應度函數的建立

適應度函數可以確定為，堆垛機從站臺起始位開始按照染色體的順序進行調度作業，所需要的總時間：

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

3）產生初始種群

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

4）選擇

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

5）交叉策略

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

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

6）變異策略

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

7）參數選擇

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

8）終止條件

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

4 實例應用

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

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

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

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

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

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

圖5 算法優化效果圖

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

5 結語

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