鋁型材立體倉庫倒垛優(yōu)化的啟發(fā)式遺傳算法

胡奇飛

（中聯(lián)重科股份有限公司，湖南長沙410075）

鋁型材立體倉庫倒垛優(yōu)化的啟發(fā)式遺傳算法

胡奇飛

（中聯(lián)重科股份有限公司，湖南長沙410075）

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

鋁型材立體倉庫；最優(yōu)倒垛；啟發(fā)式規(guī)則；遺傳算法；自適應(yīng)

1 引言

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

2 問題的描述與數(shù)學(xué)模型

2．1 垛位結(jié)構(gòu)

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

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

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

2．2 最優(yōu)倒垛問題定義與數(shù)學(xué)模型

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

已知參數(shù)為：

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

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

決策變量為：數(shù)學(xué)模型為：

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

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

3 倒垛優(yōu)化問題的啟發(fā)式遺傳算法

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

3．1 啟發(fā)式遺傳算法結(jié)構(gòu)

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

圖2 啟發(fā)式遺傳算法總體結(jié)構(gòu)

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

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

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

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

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

3．2 基于啟發(fā)式規(guī)則的最優(yōu)垛位選擇

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

Step1，k＝1：對應(yīng)出庫任務(wù)中的第一個位置；

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

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

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

Step5，k＝k＋1：如果k＞m，則轉(zhuǎn)向Step6，否則轉(zhuǎn)向Step2；

Step6：計算總的倒垛次數(shù)。

3．3 最優(yōu)倒垛問題的遺傳編碼

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

3．4 最優(yōu)個體的保存

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

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

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

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

3．5 遺傳操作算子

（1）選擇運算

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

（2）交叉與變異算子

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

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

4 仿真實驗與分析

仿真數(shù)據(jù)的產(chǎn)生涉及以下五個因素：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

［1］李耀華，王 偉，徐樂江，等．熱軋生產(chǎn)軋制計劃模型與算法研究［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］席 陽．半在線入庫堆垛問題的動態(tài)求解算法［J］．計算機工程與科學(xué)，2011，33（5）：190－195．

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

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

［6］唐立新，楊自厚，胡國奮．板坯倒垛問題的有效啟發(fā)式算法［J］．系統(tǒng)工程學(xué)報，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－h(huán)ard 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－），男，碩士研究生學(xué)歷，現(xiàn)為中聯(lián)重科股份有限公司研究院技術(shù)人員，主要研究方向為PLC控制技術(shù)及其算法研究與開發(fā)。

2016－11－15