鋁型材立體倉庫倒垛優化的啟發式遺傳算法

胡奇飛

（中聯重科股份有限公司，湖南長沙410075）

鋁型材立體倉庫倒垛優化的啟發式遺傳算法

胡奇飛

（中聯重科股份有限公司，湖南長沙410075）

對鋁型材立體倉庫的最優倒垛問題建立了0和1整數規劃模型。模型是一個二次規劃模型，其目標函數的系數與變量的取值相關聯，屬于NP難問題，獲得較大規模的最優解比較困難。為了求解此問題，結合啟發式規則構建了改進型啟發式遺傳算法。提出了適合于該立體倉庫倒垛優化問題的遺傳編碼，設計了相應的交叉與變異，使經過遺傳操作后得到的染色體仍然可行。改進了交叉操作，采用了自適應交叉與變異概率，增加了算法的局部搜索能力。通過隨機產生的問題實例實驗驗證了該算法的可行性和有效性。

鋁型材立體倉庫；最優倒垛；啟發式規則；遺傳算法；自適應

1 引言

鋁型材立體倉庫作業一般有入庫作業、出庫作業、貨位分配、貨位整理等［1－3］。在出庫作業時，操作者根據出庫訂單要求，把需要的型材信息輸入到計算機系統中。堆垛機在進行出庫作業之前，系統會同時釋放出多個出庫任務，所需要的型材的出庫順序可自由組合，同一種型材可能只存放在一個垛位，也可能存放在不同的垛位，型材出庫順序的不同以及所需型材不同垛位的選擇都將導致堆垛機需要進行倒垛的次數不同，對所需求的型材進行出庫順序的最優組合以及從可交換型材組中選擇倒垛次數最少的垛位以使堆垛機總的倒垛次數最少，這種研究鋁型材立體倉庫倒垛次數最少的問題稱為最優倒垛問題。倒垛次數越多，堆垛機的作業負荷越重，立體倉庫的效率越低，因此，最優倒垛問題直接關系到倉庫的運行效率和企業的生產效益，是企業產品流通中迫切需要解決的問題［4－6］。關于鋁型材立體倉庫的倒垛問題，國內外很少有文獻對其進行專門的研究。本文以某鋁業公司立體倉庫為背景，針對最優倒垛問題建立了數學模型，用改進的啟發式遺傳算法對其進行求解，并跟原有系統的“先到先服務”的倒垛機制進行比較。

2 問題的描述與數學模型

2．1 垛位結構

鋁型材立體倉庫的垛位是由料框堆積而成，一個垛位最多可以堆放6個料框，其垛位分布簡化模型圖如圖1所示。

圖1 立體倉庫垛位分布簡化模型圖

圖中，所需要的料框是待出庫的料框，在圖中用陰影部分表示，該料框的編號③已存在于出庫任務隊列中。該跺位的④、⑤、⑥是需要進行倒跺的料框，堆垛機必須將其移到其它垛位或者空垛位才能將出庫任務隊列中需要的料框③取走。當需要的料框取走之后，被堆垛機移走的料框不需要移回原來的垛位。跺高是指該垛位堆放的料框數，料框的計數從垛位的底部開始計起，也就是垛位底部為料框的第一層，依次往上。

2．2 最優倒垛問題定義與數學模型

在堆垛機的倒垛過程中，引入以下符號，以方便倒垛問題數學模型的定義。

已知參數為：

S＝｛1，2…，N｝為整個出庫任務中料框的集合，N為堆垛機執行隊列中料框的總數；

Ω＝｛1，2…，M｝為整個倉庫中鋁型材垛位的集合，M為一個料框所在的垛位編號。

決策變量為：數學模型為：

式中，Ci，j表示第i個料框在第j個垛位上時堆垛機所需倒跺的次數，它的值是動態變化的，不是一個恒定值，它的大小依賴于它的前i－1次料框出庫任務的垛位情況，亦即前i－1次所取的料框是否有跟它在同一個垛位的，若有在同一個垛位的料框存在，則它的倒跺次數依賴于同一個垛位的料框所在垛位的層數；如果不是同一個垛位，則它的倒跺次數依賴于它所在垛位之上是否有料框，若沒有，則倒垛次數為零，若有，則堆垛機最多倒垛5次，即所取料框為垛位第一層，而且該垛位第二至六層剛好都有料框的情況。

式（1）為目標函數，它使料框總的倒垛次數最少；式（2）為約束條件，它使同一個垛位上最多只能有6個料框；式（3）為約束條件，它保證出庫任務列表中所需要的型材在立體倉庫內至少在一個垛位中存在。

3 倒垛優化問題的啟發式遺傳算法

遺傳算法是一類基于自然進化和選擇機制自適應的搜索算法，它被成功應用到多種優化問題的求解。一般遺傳算法求解最優倒垛問題有兩個困難：（1）可行化的遺傳編碼構造；（2）最優性能難以保證。針對這種情況，本文構造了下面的啟發式遺傳算法。

3．1 啟發式遺傳算法結構

啟發式遺傳算法總體結構如圖2所示，與普通遺傳算法相比，其改進了交叉操作，增加了自適應交叉與變異，并應用啟發式規則評價個體適應度。關于出庫任務的順序排列問題采用遺傳算法進行確實，而對于出庫順序中的每個位置的最佳料框則采用啟發式規則進行選擇。

圖2 啟發式遺傳算法總體結構

種子交叉模式：種子模式交叉是通過選擇當前代最優的染色體個體與隨機產生的染色體進行配對交叉產生兩個新的染色體個體，這樣交叉產生的染色體都具有當前代最優染色體的部分基因。而傳統的交叉方式是通過隨機選擇兩個染色體個體進行配對交叉產生兩個新的染色體個體，這種交叉效果不是很理想。最優染色體個體與隨機產生的染色體個體采用位交叉方式進行交叉，交叉后的兩個新染色體仍然為原問題的可行解。

自適應交叉與變異概率：為了改善固定進化策略在迭代后期鈍化的問題，根據遺傳環境變化的自適應交叉、變異算子，在進化的初始階段采用高的交叉率和低的變異率，以充分發揮交叉算子的搜索效率，而在進化的后階段，逐漸降低交叉率，增加變異率，以提高了遺傳算法的局部搜索能力。而傳統遺傳算法中，采用固定不變的交叉率和變異率，隨著進化迭代次數的增加，好的個體在群體中所占比重迅速增加，不久會出現許多優秀個體重復現象，這時交叉操作的搜索作用迅速鈍化，而變異率一般取得很小，若再繼續迭代下去，對優化準則并沒有多大改善。

自適應交叉率和變異率的具體計算按下式進行：

其中Pcmax為最大交叉率，Pmmin為最小變異率，gen為進化代數，β是介于0和1之間的一個較小常數。

在上式中，交叉率pc隨著迭代次數的增加而減少，變異率pm隨著迭代次數的增加而增加。這樣在進化的初始階段，利用交叉算子組合父代中有價值的信息（模式），實現高效搜索，快速達到近優解附近。隨著進化代數的增加，交叉率減小，而變異加大，GA向隨機搜索方向轉化，使各個體迅速變化并覆蓋整個搜索區域，加快收斂速度。

3．2 基于啟發式規則的最優垛位選擇

啟發式最優垛位選擇的基本思想是出庫任務順序已經確定，針對出庫任務從第一個位置開始，根據設定的規則依次確定其最佳料框。每一個位置的最佳料框都是從該位置對應的可交換型材組中進行選擇。最佳料框是指在垛位中位于其上的料框數最小的可交換型材，若同時有多個料框滿足條件，則在其中任選一個垛位，其實現的具體過程如下：

Step1，k＝1：對應出庫任務中的第一個位置；

Step2：計算出庫任務中第k個位置的所有可交換型材組；

Step3：根據可交換型材組，得出所需型材在每個垛位中堆垛機需要進行倒垛的次數，選擇第k個位置倒垛次數最少的垛位；

Step4：取出所需型材后，更新計算機管理系統中的型材分布信息；

Step5，k＝k＋1：如果k＞m，則轉向Step6，否則轉向Step2；

Step6：計算總的倒垛次數。

3．3 最優倒垛問題的遺傳編碼

對于出庫任務列表中的所需料框，需堆垛機全部取出，可把每個料框都看作是列表中的唯一節點，因此可將任務列表的料框出庫排序看作一個TSP問題，采用Grefenstette編碼。對出庫任務列表中的料框進行無重復正整數編號，其編碼為R＝（r1，r2，r3，…，rn），n為列表中料框的個數，通過s［i］＝r［i］－m（其中m為r1到r［i－1］中小于r［i］的元素個數），得到的（s1，s2，s3，…，sn）就是所求的染色體編碼。由于該編碼與整數排列之間建立了一種一一對應的關系，因此通過該編碼方法得到的任意染色體的編碼都是有意義的，從而避免了無意義的染色體編碼，使得到的任何出庫順序都是有效的。

3．4 最優個體的保存

在遺傳算法進化過程中，經過交叉、變異后會不斷地產生新的個體。隨著種群的不斷進化，雖然在進化過程中會不斷地產生出越來越多的優良個體，但由于選擇、交叉、變異等遺傳操作的隨機性而導致適應度較好的個體沒被遺傳到下一代，或者遭到破壞，這樣很容易導致所設計的遺傳算法很快收斂到局部最優解，而搜索不到全局最優解，從而出現“早熟”現象。較好適應度的個體沒被選擇或者被破壞會降低整個種群的平均適應度且不利于遺傳算法在進化過程中的運行及收斂。為了解決此問題，也為了體現遺傳算法的優勝劣汰的原則，本文使用了保存最佳的個體直接遺傳到下一代的策略，即將當前種群中適應度最佳的個體進行保存，用保存下來的個體替代當前種群，經過選擇、交叉以及變異等遺傳算子操作后產生出新種群中適應度最低的個體。這種最優個體保存策略的具體操作過程如下：

（1）將當前代種群中的個體按適應度的大小進行排序，找出適應度最佳的個體并保存；

（2）將當前種群中的個體進行交叉、變異等遺傳操作使之產生新一代種群并找出來適應度最差的個體并將其刪除；

（3）將保存下來最佳的個體插入到新一代種群中，這樣使保存下來的最佳個體能直接遺傳到下一代，并使新一代種群的大小與當前種群的大小相同。

3．5 遺傳操作算子

（1）選擇運算

選擇運算采用基于適應度大小排序進行種群個體選擇和復制以及基于此種排序選擇最優個體并進行保存的策略。此種選擇運算的好處就是避免了因其它選擇算子在選擇過程中隨機性太大而使適應度最高的個體沒有被選中，增加了遺傳算法的全局搜索能力。

（2）交叉與變異算子

采用位交叉方法進行交叉，其過程為：根據隨機產生的交叉點，然后兩個隨機配對的染色體從交叉點后進行互換形成兩個新的染色體。兩個可行染色體通過位交叉操作后產生的兩個新的染色體仍為原問題的可行解。

采用基本位變異方法對染色體進行變異，即按變異概率找出所需要進行變異的基因座，將基因座的值變為1，如此操作能保證經過變異后的染色體仍然有效。

4 仿真實驗與分析

仿真數據的產生涉及以下五個因素：

（1）垛位個數：某鋁業公司立體倉庫垛位的最大容量為180個，對不多于180個垛位的幾種情況分別進行仿真；

（2）垛高層數：垛高最多為六層，在進行仿真時，考慮倉庫的實際情況，垛高由系統隨機選擇，設置為不大于六層；

（3）垛位分布：每個垛位型材的具體分布由系統隨機分布；

（4）所需型材的種類：鋁業公司生產的型材種類能細分很多種，本次仿真設置的型材種類最多為60種，并針對種類數量不同分別進行仿真分析，所需型材具體種類由系統隨機產生，且同一批作業任務中所需型材存在同種類的情況；

（5）所需料框個數：鋁業公司立體倉庫一天的出庫量很大，本次仿真設置的所需料框數最多為180個，大約為倉庫滿負載運行時五個小時的出貨量。

為了能更好地貼近實際情況，每種情況的解以每種情況仿真十次得到的平均結果為準，即。當對每種情況進行多次仿真時，其垛位分布以及所需型材的種類都是動態變化的，即每次仿真的垛位分布與所需型材種類都不相同。本次仿真遺傳算法的具體參數設置為：Pop＿Size＝50，。關于垛位隨機分布且所需型材種類隨機選擇情況的仿真結果如表1所示。

表1 45個垛位仿真情況對比

從表1～表4的仿真結果可得出以下結論：

（1）在最優性方面，對于四個表中給出的二十種情況，所提出的改進型啟發式遺傳算法都優于原系統的“先到先服務”的倒垛機制，最好的倒垛優化效率可達75%，最差的倒垛優化效率為5．96%；

（2）從表1～表4中的第二列可以看出，隨著倉庫中垛位分布個數的增加，改進型啟發式遺傳算法與原系統的“先到先服務”的倒垛機制相比，倒垛優化效率有明顯提升；

（3）從表1～表4中的第六行可以看出，在型材種類數相同的情況下，隨著所需出庫料框個數的增加，改進型啟發式遺傳算法與原系統的“先到先服務”的倒垛機制相比，倒垛優化效率有所下降；

（4）從表1～表4中的第六行可以看出，在所需出庫料框個數相同的情況下，當型材種類數從30種增加到60種時，改進的啟發式遺傳算法與原系統的“先到先服務”的倒垛機制相比，倒垛優化效率有明顯下降；

（5）在計算時間方面，遺傳算法比原系統消耗的時間多，特別是隨著垛位個數以及所需料框個數的增加，遺傳算法消耗的時間也增多。從實際運行情況來看，在同一個出庫任務列表中的料框個數一般為幾十框，且這些料框一般都分布在幾十個垛位，因此實際運行的情況大部分跟表1中第二列的情況差不多，雖然由啟發式遺傳算法產生的方案比原系統產生的方案所消耗的時間多，但堆垛機完成原系統多余的倒垛數所消耗的時間比遺傳算法的計算時間多許多，從而使啟發式遺傳算法產生的方案在整體運行過程中所消耗的時間比原系統還是縮短了。

表2 90個垛位仿真情況對比

表3 135個垛位仿真情況對比

表4 180個垛位仿真情況對比

5 結束語

本章對鋁型材自動化立體倉庫的倒垛問題進行了分析，建立了基于倒垛次數最少的堆垛機倒垛數學模型，并基于此模型提出了一種基于啟發式規則的最優垛位選擇與遺傳算法相結合的隨機搜索算法。在此算法基礎上，采用了最優個體交叉、保存的策略，設計了根據遺傳環境變化的自適應交叉、變異算子。這些策略對改善群體結構的多樣性、提高算法的搜索性能具有明顯效果。與某鋁業公司“先到先服務”的出庫倒垛機制相比，本文所設計的遺傳算法對堆垛機倒垛作業優化具有明顯效果，減少了堆垛機的倒垛次數，提高了堆垛機的作業效率。

［1］李耀華，王 偉，徐樂江，等．熱軋生產軋制計劃模型與算法研究［J］．控制與決策，2005，20（3）：275－279．

［2］Wang Q，Mclntosh R，Brain M．A new－generation automated warehousing capability［J］．International Journal of Computer Integrated Manufacturing，2010，23（6）：565－573．

［3］席 陽．半在線入庫堆垛問題的動態求解算法［J］．計算機工程與科學，2011，33（5）：190－195．

［4］王 敏，李鐵克．改進的單親遺傳算法求解倒垛問題［J］．工業工程與管理，2009，14（4）：67－72．

［5］李耀華，王 偉，胡國奮，等．熱軋板坯庫出庫計劃編制模型與算法研究［J］．計算機集成制造系統，2006，12 （3）：377－382．

［6］唐立新，楊自厚，胡國奮．板坯倒垛問題的有效啟發式算法［J］．系統工程學報，2011，16（2）：121－128．

Heuristic genetic algorithm for optimal turned－out slab pile in the aluminum profile warehouse

HU Qi－fei

（Zoomlion Heavy Industry Science＆Technology Co．，Ltd．，Changsha 410000，China）

The 0 and 1 integer programming model for the optimal turned－out slab pile（TOSP）problem of the aluminum profile warehouse is formulated．It is a quadratic programming model．The objective function coefficient is related to the value of the variable quantity．It is a NP－hard problem and is difficult to obtain the large－scale optimal solutions．In order to solve this problem and based on the heuristic rules，an improved genetic algorithm is constructed．The genetic encoding for the warehouse optimization problem is proposed．The corresponding crossover and mutation are designed to make the chromosomes passed the genetic operations to be still feasible．The crossover operation is improved by using the self－adaptive crossover and mutation probability，thus the local searching ability of the algorithm is increased．The experimental results show that the performance of the proposed algorithm is better than that of the original system．

aluminumprofilewarehouse；optimalturned－outslabpile；heuristicrule；geneticalgorithm；self－adaptive

TP29

A

1005—7277（2016）06—0048—06

胡奇飛（1977－），男，碩士研究生學歷，現為中聯重科股份有限公司研究院技術人員，主要研究方向為PLC控制技術及其算法研究與開發。

2016－11－15