姜 山，季業(yè)飛

JIANG Shan1, JI Ye-fei2

（1. 交通運(yùn)輸部公路科學(xué)研究院 公路交通發(fā)展研究中心，北京 100088；2. 中國(guó)中元國(guó)際工程公司 工程事業(yè)二部，北京 100089）

GASA混合優(yōu)化算法在自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)作業(yè)調(diào)度問(wèn)題中的應(yīng)用

Application of GASA hybrid optimization algorithm in the stacker’s dispatch problem in as/rs

姜 山1，季業(yè)飛2

JIANG Shan1, JI Ye-fei2

（1. 交通運(yùn)輸部公路科學(xué)研究院 公路交通發(fā)展研究中心，北京 100088；2. 中國(guó)中元國(guó)際工程公司 工程事業(yè)二部，北京 100089）

堆垛機(jī)出入庫(kù)調(diào)度優(yōu)化問(wèn)題是提高自動(dòng)化立體倉(cāng)庫(kù)工作效率的關(guān)鍵技術(shù)之一。本文通過(guò)對(duì)出入庫(kù)調(diào)度問(wèn)題中影響堆垛機(jī)作業(yè)時(shí)間因素的分析，把堆垛機(jī)調(diào)度的優(yōu)化路線問(wèn)題轉(zhuǎn)化為TSP問(wèn)題，然后采用遺傳—模擬退火混合優(yōu)化算法來(lái)解決。數(shù)值試驗(yàn)表明混合優(yōu)化算法吸收了單一算法的各自優(yōu)點(diǎn)，克服了本身的缺點(diǎn)，顯示出較強(qiáng)的全局優(yōu)化能力，為立體倉(cāng)庫(kù)任務(wù)調(diào)度問(wèn)題提供了新的求解思路。

遺傳算法；模擬退火算法；堆垛機(jī)；自動(dòng)化立體倉(cāng)庫(kù)

0 引言

自動(dòng)化立體倉(cāng)庫(kù)是物流系統(tǒng)的重要組成部分，又稱自動(dòng)存儲(chǔ)自動(dòng)檢索系統(tǒng)（Automatedstorage/Retrieval system，As/Rs），是一種新型的倉(cāng)儲(chǔ)技術(shù)。它是以高層貨架為主體，以成套搬運(yùn)設(shè)備為基礎(chǔ)，以計(jì)算機(jī)控制技術(shù)為手段的高效率物流、大容量存儲(chǔ)的機(jī)電一體化高科技集成系統(tǒng)。它的出現(xiàn)大大拓展了倉(cāng)庫(kù)功能，使之從“靜態(tài)倉(cāng)庫(kù)”變成了“動(dòng)態(tài)倉(cāng)庫(kù)”，由單純的保管型向綜合的流通型方向發(fā)展，通過(guò)有效銜接生產(chǎn)與庫(kù)存，加快了物資周轉(zhuǎn)，大大降低了生產(chǎn)成本。

近30年來(lái)自動(dòng)化立體倉(cāng)庫(kù)的硬件設(shè)備的技術(shù)、自動(dòng)控制以及通訊技術(shù)己十分完善，工作效率有了大幅提高，但現(xiàn)代機(jī)械制造對(duì)倉(cāng)庫(kù)的工作效率的要求也在不斷提高。如何在不增加設(shè)備投資的情況下，通過(guò)優(yōu)化倉(cāng)庫(kù)的管理和調(diào)度，減少作業(yè)時(shí)間，就成為提高自動(dòng)化立體倉(cāng)庫(kù)工作效率的關(guān)鍵研究技術(shù)，其中堆垛機(jī)出入庫(kù)調(diào)度優(yōu)化問(wèn)題是一個(gè)重要的研究課題。本文通過(guò)對(duì)立體倉(cāng)庫(kù)出入庫(kù)調(diào)度問(wèn)題中影響堆垛機(jī)作業(yè)時(shí)間因素的分析，把堆垛機(jī)調(diào)度的優(yōu)化路線問(wèn)題轉(zhuǎn)化為常見(jiàn)的TSP問(wèn)題，然后采用遺傳—模擬退火混合優(yōu)化算法（GASA）來(lái)求解，取得了較好的效果。

1 堆垛機(jī)作業(yè)調(diào)度優(yōu)化問(wèn)題

自動(dòng)化立體倉(cāng)庫(kù)貨物的存取有兩種基本方式：一種是單一作業(yè)方式，另一種是復(fù)合作業(yè)方式。在單一作業(yè)方式下，堆垛機(jī)作業(yè)時(shí)間是一個(gè)定值，與作業(yè)任務(wù)的執(zhí)行順序無(wú)關(guān)。在復(fù)合作業(yè)時(shí)，堆垛機(jī)接到一批出入庫(kù)指令，即堆垛機(jī)從原點(diǎn)出發(fā)執(zhí)行第一條指令，運(yùn)行到指定貨格取出托盤并將托盤運(yùn)送到原點(diǎn)，由操作人員按單據(jù)具體內(nèi)容取出或放人物料，接著堆垛機(jī)再將托盤放回原庫(kù)位處，從而完成一個(gè)庫(kù)位作業(yè)。之后，堆垛機(jī)并不回到原點(diǎn)而是直接執(zhí)行下一個(gè)指令，即尋找下一個(gè)庫(kù)位號(hào)，如此反復(fù)直到完成所有的指令為止。堆垛機(jī)復(fù)合作業(yè)方式如圖1所示：

圖1 堆垛機(jī)復(fù)合作業(yè)示意圖

此種方式下，圖1所示三個(gè)作業(yè)任務(wù)時(shí)的作業(yè)時(shí)間為：

不難推導(dǎo)出堆垛機(jī)執(zhí)行完n條作業(yè)任務(wù)時(shí)，總的作業(yè)時(shí)間是：

其中Tn為堆垛機(jī)完成所有的作業(yè)任務(wù)所花費(fèi)的總時(shí)間，T0,j為從原點(diǎn)P0（出入庫(kù)臺(tái)處）到Pi（指定庫(kù)位處）所用的時(shí)間，Ti,0為堆垛機(jī)從點(diǎn)Pi（指定庫(kù)位處）到原點(diǎn)P0處所用的時(shí)間， Ti-1,i為從點(diǎn)Pi-1（前一庫(kù)位）到Pi（當(dāng)前庫(kù)位）所用時(shí)間。最后一項(xiàng) 為堆垛機(jī)完成所有出入庫(kù)任務(wù)后從最后一個(gè)庫(kù)位Pn處回到原點(diǎn)P0（出入庫(kù)臺(tái)處）待命所用的時(shí)間。

不難發(fā)現(xiàn)，當(dāng)一批出入庫(kù)任務(wù)指定后，不管任務(wù)執(zhí)行的先后順序如何，第一部分的值總是確定的，它對(duì)堆垛機(jī)的運(yùn)行時(shí)間是沒(méi)有影響的。而第二部分為一個(gè)從原點(diǎn)出發(fā)途經(jīng)各指定庫(kù)位的回路，當(dāng)堆垛機(jī)采用不同的行走順序，路徑長(zhǎng)度是不同的，執(zhí)行的時(shí)間也不相同。對(duì)于這部分堆垛機(jī)所走的路徑就是一個(gè)從原點(diǎn)出發(fā)途經(jīng)各指定庫(kù)位再回到原點(diǎn)的回路，這是一個(gè)典型的旅行商(TSP)問(wèn)題。

2 GASA混合優(yōu)化算法求解堆垛機(jī)作業(yè)調(diào)度優(yōu)化問(wèn)題

旅行商（TSP）問(wèn)題是典型的非多項(xiàng)式時(shí)間可解難題(NP-hard Problem)。目前遺傳算法(Genetic Algorithm，GA)和模擬退火算法( Simulated Annealing Algorithm， SA)等智能優(yōu)化算法被廣泛用于求解TSP問(wèn)題。但是對(duì)于NP難問(wèn)題，單一機(jī)制的優(yōu)化算法很難實(shí)現(xiàn)全局優(yōu)化，且效率也不高。遺傳算法有較強(qiáng)的全局搜索能力，但算法的一些參數(shù)如果選取不當(dāng)，易陷入局部最優(yōu)解難以自拔。模擬退火算法有較強(qiáng)的局部搜索能力，但其參數(shù)一樣很難確定，且返回一個(gè)高質(zhì)近似解的時(shí)間花費(fèi)較多，當(dāng)問(wèn)題規(guī)模增大時(shí)，難于承受的運(yùn)行時(shí)間將使算法喪失可行性。多種優(yōu)化機(jī)制的相互結(jié)合，是提高全局優(yōu)化能力的有效途徑之一。本文提出利用遺傳—模擬退火混合優(yōu)化算法求解堆垛機(jī)作業(yè)調(diào)度優(yōu)化問(wèn)題。

遺傳—模擬退火混合優(yōu)化算法可以歸納如下：GA利用SA得到的解作為初始種群，通過(guò)復(fù)制、交叉、變異等遺傳操作使種群得以進(jìn)化；SA對(duì)GA得到的進(jìn)化種群進(jìn)行進(jìn)一步優(yōu)化，溫度較高時(shí)表現(xiàn)出較強(qiáng)的概率突變性，體現(xiàn)為對(duì)種群的“粗搜索”，溫度較低時(shí)演化為局部搜索，體現(xiàn)為對(duì)種群的“細(xì)搜索”?；旌蟽?yōu)化算法求解堆垛機(jī)作業(yè)調(diào)度問(wèn)題步驟如下：

1）對(duì)作業(yè)序列決策變量隨機(jī)編碼產(chǎn)生初始種群X(1)，確定初溫和合理的適應(yīng)度函數(shù)。

2）計(jì)算種群中每一個(gè)體xi(k)，k=1,2,……N的適應(yīng)度。如果連續(xù)幾代個(gè)體平均適應(yīng)度的差異小于某一個(gè)極小的閾值，則選當(dāng)前最佳的個(gè)體為最優(yōu)染色體，進(jìn)行解碼得到最優(yōu)解。否則轉(zhuǎn)3）。

3）根據(jù)適應(yīng)度分布復(fù)制種群X(k)。

4）根據(jù)交叉概率Pc，執(zhí)行交叉操作。

5）根據(jù)變異概率Pm，執(zhí)行變異操作，從而得到新種群X(k+1)。

6）對(duì)X(k+1)中每一個(gè)體進(jìn)行Metropolis抽樣。

7）由SA狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新個(gè)體。

8）以概率接受新個(gè)體。

9）若抽樣穩(wěn)定，退溫，轉(zhuǎn)2）。否則，轉(zhuǎn)7）。

關(guān)于上述算法的說(shuō)明：

1）在1）中，堆垛機(jī)執(zhí)行復(fù)合作業(yè)要實(shí)現(xiàn)時(shí)間越少越好，即實(shí)際優(yōu)化目標(biāo)函數(shù)為因此確定混合優(yōu)化算法的適應(yīng)度函數(shù)為為一數(shù)值較大的實(shí)數(shù)。

2）在7）中，SA狀態(tài)產(chǎn)生函數(shù)可設(shè)計(jì)為互換操作(SWAP)，即隨機(jī)交換染色體中兩不同基因的位置，也可設(shè)計(jì)為逆序操作(INV)，即將染色體中兩不同隨機(jī)位置間的基因串逆序。

3 數(shù)值模擬

假設(shè)某自動(dòng)化立體倉(cāng)庫(kù)巷道堆垛機(jī)從上位管理機(jī)接受單據(jù)，任務(wù)序數(shù)為1～7，貨位地址（XK，Yk）（k=l，2，…，7），其中1、4、5、7為入庫(kù)任務(wù)，2、3、6為出庫(kù)任務(wù)。堆垛機(jī)從出入庫(kù)臺(tái)O點(diǎn)(0，0)出發(fā)進(jìn)行復(fù)合作業(yè)，最后要返回到出入庫(kù)臺(tái)0點(diǎn)。各個(gè)貨位之間的運(yùn)行時(shí)間如表1 所示。

表1 各個(gè)貨位之間的運(yùn)行時(shí)間 單位：秒

分別采取遺傳算法、模擬退火算法和GASA混合優(yōu)化算法求解，三種優(yōu)化算法都得到相同的復(fù)合作業(yè)順序結(jié)果，7個(gè)貨位點(diǎn)之間進(jìn)行復(fù)合作業(yè)的順序?yàn)?1，2，5，4，6，7，3)，即堆垛機(jī)按照(0→1→2→0→5→0→4→6→0→7→3→0)完成復(fù)合作業(yè)，對(duì)應(yīng)的堆垛機(jī)運(yùn)行時(shí)間為264.5秒。但從表2中可以看出SA優(yōu)化時(shí)間性能較差，GA略有改善，GASA混合優(yōu)化算法在時(shí)間性能上優(yōu)于它們。

表2 混合算法和相關(guān)算法性能統(tǒng)計(jì)比較

4 結(jié)束語(yǔ)

本文運(yùn)用遺傳—模擬退火混合優(yōu)化算法求解自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)的作業(yè)調(diào)度優(yōu)化問(wèn)題。數(shù)值模擬實(shí)驗(yàn)表明，混合優(yōu)化算法吸收了單一算法的各自優(yōu)點(diǎn)，克服了它們本身的缺點(diǎn)，大大提高了搜索效率。遺傳算法與模擬退火算法的結(jié)合顯示出卓越的優(yōu)勢(shì)，遺傳算法跟其它優(yōu)化算法的結(jié)合在求解自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)調(diào)度問(wèn)題方面也可能發(fā)揮更大的威力，對(duì)此問(wèn)題我們將另文討論。

[1] 周明,孫樹棟.遺傳算法原理及應(yīng)用(M).北京:國(guó)防工業(yè)出版社,1999.

[2] 康立山,謝云,尤矢勇,等.非數(shù)值并行算法(第一冊(cè)):模擬退火算法[M].北京:科學(xué)出版社, 1997.

[3] 王凌.智能優(yōu)化算法及其應(yīng)用(M).北京:清華大學(xué)出版社,2001.

[4] 劉偉銘,姜山.基于GASA混合優(yōu)化策略的雙層規(guī)劃模型求解算法研究[J].土木工程學(xué)報(bào),2003,36(7):27-32.

[5] 朱耀明.自動(dòng)化立體倉(cāng)庫(kù)優(yōu)化調(diào)度研究[D].濟(jì)南:山東大學(xué),2006.

[6] 劉惠.自動(dòng)化立體倉(cāng)庫(kù)效率優(yōu)化研究[D].沈陽(yáng):遼寧工程技術(shù)大學(xué),2007.

TH166

B

1009-0134(2010)10(上)-0063-03

10.3969/j.issn.1009-0134.2010.10(上).19

2010-04-06

姜山（1977 -），男，山東諸城人，經(jīng)濟(jì)師，碩士，研究方向?yàn)榻煌ㄟ\(yùn)輸工程與交通運(yùn)輸經(jīng)濟(jì)。